20523번 - Обитаемые горы 서브태스크다국어

문제

По мотивам фантастической повести

А. и Б. Стругацких Обитаемый остров

Правительство страны Неизвестных Отцов планирует построить в гористом районе на границе с Хонтией башню противобаллистической защиты.

Участок горной цепи в этом районе представлен ломаной, состоящей из $n$ звеньев, последовательно соединяющих $n + 1$ вершину, расположенную в порядке возрастания $x$-координаты. Вершины пронумерованы числами от 0ドル$ до $n,ドル а звенья --- от 1ドル$ до $n,ドル при этом $i$-е звено соединяет вершины с номерами $i - 1$ и $i$.

Вершина номер 0ドル$ находится в точке $(0, 0)$. Звено номер $i$ задано длиной проекции на горизонтальную ось $d_i$ и угловым коэффициентом $k_i$. Таким образом, если вершина номер $i - 1$ имеет координаты $(x_{i-1}, y_{i-1}),ドル то координаты $i$-й вершины можно вычислить как $(x_{i-1} + d_i, y_{i-1} + k_i \cdot d_i)$. Последняя вершина имеет нулевую $y$-координату, то есть $y_n = 0$.

Точка $A$ $(x_A, y_A)$ находится в прямой видимости из точки $B$ $(x_B, y_B),ドル если ни одна точка отрезка $AB$ не находится строго под ломаной.

Башня представляет собой вертикальный отрезок ненулевой длины, нижняя точка которого расположена на ломаной. Гражданин страны Неизвестных Отцов чувствует себя в безопасности, если верхняя точка башни находится в его прямой видимости.

Пусть верхняя точка башни находится в точке с координатами $(x, y)$. Рассмотрим двух разведчиков, выбегающих из нижней точки башни соответственно на запад (в направлении уменьшения $x$-координаты) и на восток (в направлении увеличения $x$-координаты). Каждый разведчик бежит по поверхности горной цепи до тех пор, пока дальнейшее перемещение не выводит верхнюю точку башни из его прямой видимости или до границы горной цепи.

Правительство подготовило $m$ вариантов расположения башни, каждый из которых характеризуется двумя целыми числами $(u_j, v_j)$ --- координатами верхней точки башни. Требуется написать программу, которая для каждого из вариантов определяет $x$-координаты точки, до которых добежит каждый из разведчиков.

입력

Первая строка входных данных содержит два числа $n$ и $m$ (1ドル \leq n, m \leq 400,000円$) --- количество звеньев ломаной и количество вариантов расположения башни.

Ограничения на величины последующих входных данных зависят от значения константы $C,ドル которая может быть равна 10ドル^4$ или 10ドル^9$ в зависимости от подзадачи (см. таблицу системы оценивания).

Каждая из последующих $n$ строк содержит по два целых числа $d_i,ドル $k_i$ (1ドル \le d_i \le C$; $-C \le k_i \le C$) --- проекцию на горизонтальную ось и угловой коэффициент $i$-го звена ломаной (0ドル = x_0 < x_1 < \cdots < x_i < \cdots < x_n \leq C$; $y_0 = y_n = 0$; $-C \le y_i \le C$).

Каждая из последующих $m$ строк содержит по два целых числа $u_j,ドル $v_j$ (0ドル \leq u_j \leq C,ドル $-C \leq v_j \leq C$) --- координаты верхней точки башни в $j$-м варианте расположения.

출력

Выходные данные должны содержать $m$ строк, в каждой из которых находятся по два целых числа $l_j$ и $r_j$ --- $x$-координаты точек, до которых добегут разведчики, направляющиеся на запад и на восток соответственно в $j$-м варианте расположения башни. Гарантируется, что числа $l_j$ и $r_j$ являются целыми.

제한

서브태스크

힌트

Рис. 1: Первый пример

Обратите внимание, что все точки отрезка между $(6, 2)$ и $(7, 1)$ находятся в прямой видимости из верхней точки башни согласно определению в условии.

Рис. 2: Второй пример

В данном тесте из условия основания башен из всех вариантов находятся в одной точке.

Рис. 3: Третий пример

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

Рис. 4: Четвертый пример

В четвёртом тесте из условия показывается, что в стране Неизвестных Отцов горная цепь может целиком находиться ниже уровня её крайних точек.