벽과 바람

$n$개의 벽이 있다. $i$번째 벽의 높이는 $h_i$이고 강도는 $s_i$이다. 이 벽들을 왼쪽에서 오른쪽으로 일렬로 세운다.

앞으로 $q$일 동안 매일 밤 바람이 분다. 일기예보가 부정확하여 매일 밤 부는 바람의 세기는 미리 알 수 없다.

$k$번째 날 아침, 보안센터가 가장 왼쪽에 무한히 강한 벽을 높이 $h'_k$로 세운다. 그다음 가지고 있는 $n$개의 벽을 원하는 순서로 이 벽 오른쪽에 배치할 수 있다. 그날 세운 벽은 그날에만 존재한다. 다음 날 새 벽을 세우기 전에 이 벽은 철거된다.

저녁이 되면 가장 왼쪽에서 세기 $v$의 바람이 분다. 왼쪽에서 $i$번째 벽은 다음 충격을 받는다.

$\Delta_i = v \cdot \max(0, h_i - \max_{0 \le j < i} h_j)$

여기서 벽 $0$은 보안센터가 세운 벽이며, $k$번째 날의 높이는 $h'_k$, 강도는 무한대이다. 어떤 $i$에 대해 $\Delta_i > s_i$이면 $i$번째 벽이 무너지고 큰 경제적 손실이 발생한다.

각 날에 대해, 벽을 최적으로 배치했을 때 무너지지 않고 버틸 수 있는 바람 세기의 최댓값을 구하라.

첫 줄에 정수 $n$과 $q$가 주어진다 ($1 \le n,q \le 5 \cdot 10^5$).

다음 $n$개의 줄에는 각각 정수 $h_i$와 $s_i$가 주어진다 ($1 \le h_i \le 4 \cdot 10^6$, $1 \le s_i \le 10^9$).

다음 $q$개의 줄에는 각각 정수 $h'_k$가 주어진다 ($1 \le h'_k \le 4 \cdot 10^6$).

$q$개의 줄을 출력한다. 각 줄에는 기약분수 $a/b$를 공백 없이 출력한다. 어떤 세기의 바람도 버틸 수 있으면 1/0을 출력한다.