Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
У правителя Темерии Фольтеста много врагов, многие из которых не по силам даже ведьмаку. Поэтому король на всякий случай защитил свою столицу длинной прямой стеной с часовыми. Каждый часовой занимает свой пост на стене и зорко следит за окрестностями.
Время от времени через стену пытаются перебраться лазутчики-скоя'таэли, каждый из которых обладает определенной заметностью `v_j`. Если лазутчик приближается к стене в некоторой точке `b_j`, то все часовые, находящиеся от точки `b_j` на расстоянии не более `v_j` (расстояния измеряются вдоль стены), сразу же замечают опасность и бегут к нарушителю по стене с одинаковой единичной скоростью (за `1` единицу времени часовой пробегает `1` единицу длины стены). Если какой-то из часовых настигает скоя'таэля, перебирающегося через стену, то сразу же задерживает его, и все часовые останавливаются в тех местах, где находились в этот момент. Также часовые останавливаются в том случае, если лазутчик успевает перебраться через стену и скрыться в городе. Скоя'таэли пытаются пробраться в город по одному: можно считать, что следующий появляется у стены только после того, как предыдущий проник в город (либо был задержан).
Зная начальное расположение часовых и план действий скоя'таэлей, определите, кто из стражников сможет отличиться при поимке нарушителей и кто из лазутчиков сможет проникнуть в город.
В первой строке входных данных содержатся `2` положительных целых числа: количество часовых `N` (`1 <= N <= 10^5`) и количество скоя'таэлей (`1 <= M <= 10^5`).
Во второй строке содержится `N` целых чисел `a_i` (`0 <= a_i <= 10^{18}`) — начальное положение каждого из часовых на стене (стена считается бесконечно длинной прямой, все расстояния измеряются вдоль неё). Стражники нумеруются от 1 до `N` в порядке их перечисления во входных данных.
Затем следует `M` строк, описывающих лазутчиков в порядке их появления. Каждая строка содержит `3` целых числа: `b_j` — точку на стене, в которой лазутчик пытается пробраться в город (`0 <= b_j <= 10^{18}`), `t_j` — время, которое на это требуется (`1 <= t_j <= 10^{18}`), и `v_j` — заметность лазутчика (`0 <= v_j <= 10^{18}`). Если в момент появления лазутчика часовой находится прямо в точке `b_j`, то ловит его мгновенно. Если часовой настигает лазутчика в точности через `t_j` после его появления, то еще успевает его задержать (в последний момент).
Выведите `M` строк, по одной для каждого из лазутчиков. Каждая строка должна содержать `2` целых числа:
* время, которое лазутчик проведет у стены до того, как будет пойман либо скроется в городе;
* номер стражника (`1 <= i <= N`), который задержит лазутчика, либо `-1`, если он успеет скрыться. Если несколько часовых настигнут скоя'таэля одновременно, выведите минимальный из их номеров.
```sample Пример ввода
4 6
8 3 11 8
3 100 0
4 100 0
4 1 1
1 2 100
12 10 6
5 100 100
```
```sample Пример вывода
0 2
100 -1
1 2
2 -1
3 3
3 2
```
Пояснение к примеру:
* первый лазутчик появляется в точности там, где находится часовой `2`, и мгновенно попадает ему в руки (не спасает даже нулевая заметность);
* второй лазутчик имеет нулевую заметность и перебирается через стену непойманным;
* третьего лазутчика замечает только часовой `2` и ловит его в последний момент;
* четвертого лазутчика замечают все, но никто не успевает догнать; теперь часовые находятся в точках `6`, `2`, `9` и `6` соответственно;
* пятого лазутчика замечают часовые `1`, `3` и `4`, часовой `3` успевает первым; теперь часовые находятся в точках `9`, `2`, `12` и `9` соответственно;
* последнего лазутчика замечают все, часовой `2` успевает первым; часовые `1` и `3` бегут навстречу, но им нужно на `1` больше времени.
Начало
Рабочее место участника
Дерево отрезков, декартово дерево, √-декомпозиция