Вулиця#10757
Є нескінченно довга вулиця, яка йде з заходу на схід. Її можна уявити, як координатну пряму.
На цій вулиці буде проведено ремонтів. -ий ремонт буде проведений на координаті x_i з моменту (s_i - 0.5) по момент (t_i - 0.5).
Всього є людей, кожна з яких знаходиться на координаті . -та людина починає рухатися в момент часу d_i у сторону збільшення координат зі швидкістю . Якщо людина не може пройти через те, що відбувається ремонт у тій же координаті, то вона зупиняється і більше не буде рухатися.
Для кожної людини знайдіть відстань, яку вона пройде, або повідомте, що вона ніколи не зупиниться.
Гарантується, що для кожної пари чисел та (i \neq j), відрізки [s_i, t_i) та [s_j, t_j) не перетинаються.
Перший рядок містить два цілі числа та (1 \leq n, q \leq 2 \cdot 10^5).
Кожен з наступних рядків містить по три цілі числа s_i, t_i, x_i (0 \leq s_i < t_i \leq 10^9, 1 \leq x_i \leq 10^9).
Кожен з наступних рядків містить по одному цілому числі d_i (0 \leq d_i \leq 10^9).
Гарантується, що 0 \leq d_1 < d_2 < \dots < d_q \leq 10^9.
Гарантується, що для кожної пари чисел та (i \neq j), відрізки [s_i, t_i) та [s_j, t_j) не перетинаються.
В -му рядку виведіть відстань, яку пройде -та людина, або , якщо вона не зупиниться.
Example 1