시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB111100.000%

문제

Given are $n$ walls, the $i$-th wall has height $h_i$ and strength $s_i$. You need to arrange them in a line from left to right.

For the next $q$ days, the wind will blow every night. Due to the inaccuracy of the weather forecast, you cannot be sure of the strength of the wind blowing each night.

On the morning of the $k$-th day, the security center will build an infinitely strong wall of height $h'_k$ on the far left side of the ground. You can then arrange the $n$ walls you have in any order to the right of this wall. Note that the wall built by the security center each day is only available for that day. The original one will be removed before a new wall is built the next day.

In the evening, the wind with strength $v$ will blow from the far left. For each $i$, the $i$-th wall from the left will receive the impact of $\Delta_i = v \cdot \max(0, h_i - \max_{0 \le j < i} h_j)$. Here, wall $0$ is the wall that the security center built: its height on the $k$-th day is $h'_k$, and its strength is infinite. If $\Delta_i > s_i$ for some $i$, then the $i$-th wall will collapse and you will suffer a heavy economic loss.

You want to know, for each day, the maximum strength of the wind you can sustain without suffering economic losses if you arrange your $n$ walls optimally.

It can be shown that the answer is either infinite or can be expressed in the form $r = a/b$, where $a$ and $b$ are coprime positive integers. You only need to output the values of $a$ and $b$.

입력

The first line of the input consists two integers $n$ and $q$ ($1 \le n,q \le 5 \cdot 10^5$).

Each of the next $n$ lines contains two integers $h_i$ and $s_i$ ($1 \le h_i \le 4 \cdot 10^6$, $1 \le s_i \le 10^9$), indicating the height and strength of the $i$-th wall.

Each of the next $q$ lines contains an integer $h'_k$ ($1 \le h'_k \le 4 \cdot 10^6$), indicating the height of the infinitely strong wall that the security center built on the $k$-th day.

출력

Output $q$ lines, each in the format of an irreducible fraction "$a$/$b$", with no spaces and a slash in between, indicating that the answer has the value $r=a/b$. If the walls can withstand wind of any strength, print the infinite answer as "1/0".

예제 입력 1

4 5
3 5
4 3
2 5
6 3
5
2
3
7
2

예제 출력 1

3/1
3/2
3/2
1/0
3/2

예제 입력 2

5 6
10 6
3 7
6 15
7 6
8 15
5
3
9
7
7
9

예제 출력 2

3/1
3/1
6/1
3/1
3/1
6/1