D. Туристы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Двойная туристическая тропа, расположенная в одном из парков города Крайняя Туле, работает по следующему принципу:

  • Вводится декартова система координат.
  • В некоторые моменты времени из точек ( - 1, 0) и (1, 0) одновременно выходят два туриста. Первый — из точки ( - 1, 0), второй — из точки (1, 0).
  • Оба туриста в паре движутся с одинаковой скоростью 1 (единица длины в секунду), первый — вдоль прямой x =  - 1, второй — вдоль прямой x = 1, оба — в положительном направлении оси Oy.
  • В некоторые моменты времени появляются перегородки. Перегородка (li, ri) — это отрезок между точками (0, li) и (0, ri). Каждая перегородка появляется мгновенно.

Правительство Крайней Туле хочет узнать для каждой пары туристов, выходящих одновременно, сколько времени (в секундах) они не будут видеть друг друга. Два туриста не видят друг друга, если отрезок, соединяющий их положения на плоскости, пересекает хотя бы одну перегородку. Два отрезка пересекаются, если они имеют хотя бы одну общую точку. Считается, что концы отрезков принадлежат отрезкам.

Помогите правительству, посчитайте требуемые времена. Обратите внимание, что перегородки могут пересекаться (любым способом), накладываться или совпадать.

Входные данные

В первой строке записаны через пробел два целых числа n и m (1 ≤ n, m ≤ 105) — количество пар туристов и количество возводимых перегородок. В следующих m строках располагается по три целых числа li, ri и ti, разделенные пробелом (0 ≤ li < ri ≤ 109, 0 ≤ ti ≤ 109) — границы перегородки и время ее появления. В последней строке записаны через пробел в строго возрастающем порядке n различных целых чисел q1, q2, ..., qn (0 ≤ qi ≤ 109) — времена выхода пар туристов.

Все времена заданы в секундах.

Выходные данные

Для каждой пары выведите в отдельной строке единственное целое число — время в секундах, в течение которого туристы из соответствующей пары не будут видеть друг друга. Выводите эти числа в том же порядке, в каком пары заданы во входных данных.

Примеры
Входные данные
2 2
1 4 3
3 6 5
0 1
Выходные данные
2
4
Входные данные
3 3
0 3 4
0 1 2
2 4 0
1 3 4
Выходные данные
2
4
4