시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 0 0 0 0.000%

문제

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 ith bus travels from location Si to Ei 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 jth person lives at location Pj. 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 ith of these N lines contains integers Si and Ei, which represent the start location and destination location of bus route ith respectively.

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

출력

Your program must print to standard output.

The output should contain exactly M lines. The jth line should contain two integers, Aj and Bj, such that Aj / Bj is a fraction in its simplest form (i.e. gcd(Aj, Bj) = 1) representing the minimum number of days the jth 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 ≤ 106
  • 1 ≤ M ≤ 106
  • −106 ≤ Si, Ei ≤ 106 for all 1 ≤ i ≤ N
  • −106 ≤ Pj ≤ 106 for all 1 ≤ j ≤ M
  • Si ≠ Ei for all 1 ≤ i ≤ N
  • Pj ≠ 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.

서브태스크

번호 배점 제한
1 10

N ≤ 104, M ≤ 103, sign(Si) ≠ sign(Ei) for all 1 ≤ i ≤ N

2 14

N ≤ 102, M ≤ 103

3 12

N ≤ 103, M ≤ 105, Aj / Bj ≤ 103 for all 1 ≤ j ≤ M, for any x, min{Si, Ei} ≤ x ≤ max{Si, Ei} for at most 102 choices of i

4 8

M ≤ 103, for any x, min{Si, Ei} ≤ x ≤ max{Si, Ei} for at most 104 choices of i

5 15

M ≤ 104, Aj / Bj ≤ 102 for all 1 ≤ j ≤ M

6 13

sign(Si) ≠ sign(Ei) for all 1 ≤ i ≤ N

7 28

예제 입력 1

5 8
0 5
3 11
1 -8
4 10
1 -3
1 2 5 6 8 -3 -7 11

예제 출력 1

1 5
2 5
1 1
4 3
13 8
4 9
8 9
2 1

The above diagram (not to scale) shows the location of the stadium on the road, as well as all the bus routes (represented by blue arrows, and numbered for convenience).

To get to location 1, person 1 can take bus 1 from the stadium directly to location 1, and this takes 1 5 of a day. There is no way to reach location 1 faster than this, so the output for person 1 is 1 5.

To get to location 8, person 5 can take bus 1 from the stadium to location 3, and this takes 3 / 5 of a day. They stay overnight at location 3, and take bus 2 from location 3 to location 8 the next day, thus reaching at 5 / 8 of the second day. Since we need to measure the time taken from the start of the first day, the total number of days is 1 + 5 / 8 = 13 / 8. There is no way to reach location 8 faster than this, so the output for person 5 is 13 8. Note that person 5 could instead stay overnight anywhere between location 3 and location 5, including at non-integer locations.

To get to location −7, person 7 can take bus 3 from the stadium directly to location −7, and reaches at 8 / 9 of the first day. Note that even though they spent some time waiting at the stadium for the bus, that waiting time should be counted too. There is no way to reach location −7 faster than this, so the output for person 7 is 8 9.

예제 입력 2

3 2
-1 4
-2 5
0 -5
4 -4

예제 출력 2

6 7
4 5

The above diagram (not to scale) shows the location of the stadium on the road, as well as all the bus routes (represented by blue arrows, and numbered for convenience).

To get to location 4, person 1 can take bus 1 to location 1.5, and instantaneously transfer to bus 2 to reach their destination at 6 / 7 of a day. There is no way to reach location 4 faster than this, so the output for person 1 is 6 7.

To get to location −4, person 2 can take bus 3 directly to location −4, and this takes 4 / 5 of a day. There is no way to reach location −4 faster than this, so the output for person 2 is 4 5.

예제 입력 3

5 3
0 2
2 4
4 6
6 8
8 10
9 10 10

예제 출력 3

9 2
5 1
5 1

The above diagram (not to scale) shows the location of the stadium on the road, as well as all the bus routes (represented by blue arrows, and numbered for convenience).

All people need to take the five buses in sequence to get to their destinations.

채점 및 기타 정보

  • 예제는 채점하지 않는다.