광부

광산 동굴의 바닥을 좌표평면 위의 꺾은선으로 생각한다. 이 꺾은선은 $n + 1$개의 꼭짓점 $(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$과 이웃한 꼭짓점을 잇는 $n$개의 선분으로 이루어진다. 바닥은 원점에서 시작해 왼쪽에서 오른쪽으로 뻗어 나가고 $x$축 위에서 끝난다. 즉 $0 = x_0 < x_1 < \ldots < x_n$이고 $y_0 = y_n = 0$이다.

꼭짓점 $(x_{i-1}, y_{i-1})$과 꼭짓점 $(x_i, y_i)$를 잇는 선분은 두 정수 $d_i$와 $k_i$로 주어진다. $d_i$는 선분을 $x$축에 정사영한 길이이고, $k_i$는 선분이 놓인 직선의 기울기이다. 따라서 $(x_i, y_i) = (x_{i-1} + d_i, y_{i-1} + k_i d_i)$이다.

예제 데이터를 나타낸 그림

광부는 동굴 바닥보다 위에 있는 임의의 점 $A$에 램프를 걸 수 있다. 선분 $AB$가 동굴 바닥을 가로지르지 않으면 램프가 바닥 위의 점 $B$를 비춘다고 한다. 선분 $AB$가 바닥에 한 점에서 닿거나 선분을 따라 닿는 것은 허용된다. 램프는 $A$ 바로 아래에 있는 바닥 위의 점 $A'$을 당연히 비춘다.

점 $A$에 있는 램프의 주 구간은 광부가 $A'$에서 출발해 바닥을 따라 걸어서 도달할 수 있는 바닥의 영역이다. 이때 광부는 걷는 내내 점 $A$의 램프에 비춰져 있어야 한다.

램프를 걸 수 있는 위치 $q$개가 주어진다. 각 위치에 대해 그 위치에 건 램프의 주 구간의 왼쪽 끝과 오른쪽 끝을 구하시오.

첫째 줄에 동굴 바닥을 이루는 선분의 수 $n$과 램프를 걸 수 있는 위치의 수 $q$가 주어진다. ($1 \le n, q \le 100\,000$)

다음 $n$개의 줄 중 $i$번째 줄에는 $i$번째 선분의 정사영 길이 $d_i$와 기울기 $k_i$가 주어진다. ($1 \le d_i \le 10^9$, $-10^9 \le k_i \le 10^9$) 바닥의 꼭짓점은 $0 = x_0 < x_1 < \ldots < x_n \le 10^9$, $y_0 = y_n = 0$, $-10^9 \le y_i \le 10^9$를 만족한다.

다음 $q$개의 줄 중 $i$번째 줄에는 $i$번째 위치의 좌표 $x'_i$, $y'_i$가 주어진다. ($0 \le x'_i \le x_n$, $-10^9 \le y'_i \le 10^9$) 모든 위치는 동굴 바닥보다 엄격하게 위에 있다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 위치에 건 램프의 주 구간에서 왼쪽 끝의 $x$좌표와 오른쪽 끝의 $x$좌표를 공백으로 구분해 순서대로 출력한다. 구하는 좌표는 항상 정수이다.