Вулиця

Є нескінченно довга вулиця, яка йде з заходу на схід. Її можна уявити, як координатну пряму.

На цій вулиці буде проведено $n$ ремонтів. $i$-ий ремонт буде проведений на координаті $x_i$ з моменту ($s_i-0.5$) по момент ($t_i-0.5$).

Всього є $q$ людей, кожна з яких знаходиться на координаті $0$. $i$-та людина починає рухатися в момент часу $d_i$ у сторону збільшення координат зі швидкістю $1$. Якщо людина не може пройти через те, що відбувається ремонт у тій же координаті, то вона зупиняється і більше не буде рухатися.

Для кожної людини знайдіть відстань, яку вона пройде, або повідомте, що вона ніколи не зупиниться.

Гарантується, що для кожної пари чисел $i$ та $j$ ($i\ne j$), відрізки $[s_i,t_i)$ та $[s_j,t_j)$ не перетинаються.

Giriş verilənləri

Перший рядок містить два цілі числа $n$ та $q$ ($1\le n,q\le 2\cdot 10^5$).

Кожен з наступних $n$ рядків містить по три цілі числа $s_i$, $t_i$, $x_i$ ($0\le s_i<t_i\le 10^9$, $1\le x_i\le 10^9$).

Кожен з наступних $q$ рядків містить по одному цілому числі $d_i$ ($0\le d_i\le 10^9$).

Гарантується, що $0\le d_1<d_2<\dots ,<d_q\le 10^9$.

Гарантується, що для кожної пари чисел $i$ та $j$ ($i\ne j$), відрізки $[s_i,t_i)$ та $[s_j,t_j)$ не перетинаються.

Çıxış verilənləri

В $i$-му рядку виведіть відстань, яку пройде $i$-та людина, або $-1$, якщо вона не зупиниться.

Nümunələr