22257번 - Departure 서브태스크다국어

The final match of the prestigious national football championship has finally ended. It is now midnight, and football fans from all over the country were gathered in the national stadium, the largest sports venue in the whole of Mouseland, and are now leaving the venue to head back home by bus.

Mouseland may be modelled as a very long straight road in the east-west direction, and its inhabitants live in houses along this road. As the national stadium is the most important building in Mouseland, it is located at kilometre zero of this road, and all locations are specified relative to the stadium as a single number. Specifically, locations to the east of the stadium use positive numbers, and locations to the west of the stadium use negative numbers. For example “10” refers to the location ten kilometres east of the national stadium, while “-4” refers to the location four kilometres west of the national stadium. The stadium is at location “0”.

There are N public bus routes along this road. Each bus route runs a single bus each day. The i^th bus travels from location S_i to E_i at a constant speed and direction, starting at midnight and reaching its destination at midnight the next day. Buses leave at midnight every day, so for every bus route, there is an identical bus that leaves its start location every day, travelling to the same destination. People can board buses, alight from them, and transfer between buses (at the same location) instantly and at any point along the bus route — they can hop on and off while the bus is moving, anywhere along the road. Note that the speed of a bus depends on the distance it needs to travel, and that bus routes are unidirectional (i.e. there might not be another bus that travels in the opposite direction of a given bus).

There are M people that left the national stadium at midnight. The j^th person lives at location P_j. For each of the M people, what is the minimum amount of time they need to get home by bus?

Your program must read from standard input.

The first line contains two integers, N and M, which represent the number of buses and number of people respectively.

The next N lines each contain two integers. The i^th of these N lines contains integers S_i and E_i, which represent the start location and destination location of bus route i^th respectively.

The final line contains M integers. The j^th integer represents the location of the j^th person’s home.

Your program must print to standard output.

The output should contain exactly M lines. The j^th line should contain two integers, A_j and B_j, such that A_j / B_j is a fraction in its simplest form (i.e. gcd(A_j, B_j) = 1) representing the minimum number of days the j^th person needs to get home by bus. It is guaranteed that every person is able to eventually get home by bus.

Note that you need to report the exact number of days required, including the fractional part if any. For example, if a person can get home at the earliest at noon on the fourth day (so it took exactly 3.5 days to get home), then the required fraction is 7 / 2 , so you should output “7 2”.

• 1 ≤ N ≤ 10⁶
• 1 ≤ M ≤ 10⁶
• −10⁶ ≤ S_i, E_i ≤ 10⁶ for all 1 ≤ i ≤ N
• −10⁶ ≤ Pj ≤ 10⁶ for all 1 ≤ j ≤ M
• S_i ≠ E_i for all 1 ≤ i ≤ N
• P_j ≠ 0 for all 1 ≤ j ≤ M

For any integer x, sign(x) is 1 if x is positive, 0 if x is zero, and −1 if x is negative.