Departure

The final match of the prestigious national football championship has just ended. It is midnight, and football fans from across the country have gathered at the national stadium, the largest sports venue in Mouseland, and are leaving to head home by bus.

Mouseland is modelled as a very long straight east-west road, and its inhabitants live in houses along it. The national stadium is the most important building in Mouseland, so it sits at kilometre zero. Every location is given as a single number relative to the stadium. Locations east of the stadium are positive, and locations west are negative. For example, 10 is ten kilometres east of the stadium, and -4 is four kilometres west. The stadium is at location 0.

There are N public bus routes along this road. Each route runs one bus each day. The i-th bus travels from S_i to E_i at a constant speed and direction, leaving at midnight and reaching its destination at midnight the next day. Every midnight, an identical bus leaves each route's start location for the same destination. The speed of a bus depends on the distance it has to cover. Routes are one-directional, so there may be no bus running the opposite way.

People can board a bus, alight from it, and transfer between buses at the same location instantly, at any point along a route, even while the bus is moving.

M people left the national stadium at midnight. The j-th person lives at P_j. For each person, find the minimum time needed to get home by bus.

The first line contains N and M, the number of bus routes and the number of people. Each of the next N lines contains S_i and E_i, the start and destination locations of the i-th bus route. The last line contains M integers, where the j-th integer is the location of the j-th person's home.

Print exactly M lines. On line j, print two integers A_j and B_j such that $A_j / B_j$ is in lowest terms (gcd(A_j, B_j) = 1) and equals the minimum number of days the j-th person needs to get home by bus. Report the exact value, including any fractional part. For example, if the earliest arrival is noon on the fourth day, then 3.5 days have passed, so the answer is $7/2$, printed as '7 2'. It is guaranteed that every person can eventually get home by bus.

• $1 \le N \le 10^6$
• $1 \le M \le 10^6$
• $-10^6 \le S_i, E_i \le 10^6$ for all $1 \le i \le N$
• $-10^6 \le P_j \le 10^6$ for all $1 \le j \le M$
• $S_i \ne E_i$ for all $1 \le i \le N$
• $P_j \ne 0$ for all $1 \le j \le M$

For any integer $x$, $\text{sign}(x)$ is 1 if $x$ is positive, 0 if $x$ is zero, and -1 if $x$ is negative.