ZOJ Problem Set - 3572
Life in university passes very fast. However, the memory about the dining hall always lasts long.
Regard the dining hall as a 2D plane. Assume that in the dining hall, there is a window at every point (x, 0) for all integer x where students can get meals. In front of every window, there is a queue waiting for getting meals. The i-th person in the queue in front of window (x, 0) is at point (x, i). Every time, the student in (x, 1) gets the meal and leave the queue, then all the students in the queue go one unit toward the window.
Also, sometimes, a new window may be opened, and some student would go to the new window in order to get the meal earlier. Assume the new window opened is in (x, 0), and the following conditions hold.
With the status at the beginning of the 0th second given, you should tell me at which window does every student get meals.
The input contains multiple test cases. For each case, the first line contains two integers n, m (0 ≤ n ≤ 100, 0 ≤ m ≤ 100) indicating the number of windows opened at the beginning of the 0th second and the number of windows to be opened. The next n lines each contains two integers xi, qi (0 ≤ qi ≤ 100, xi is a non-negtive signed 32-bit integer), which mean the window is at (xi, 0) and the number of students waiting in front of the window is qi. The next m lines each contains two integers xi, ti (both within 32-bit signed integers, and are non-negative), which mean the window at (xi, 0) is opened at the beginning of tith second. All xi in a case will be different.
For each case, print one line containing the x coordinates where each student gets meal. The student with smaller x coordinate at 0th second should be printed first. If the x coordinates are the same, the one being closer to the window should be printed first.
3 1 4 5 6 5 7 0 5 1
4 4 5 4 5 6 6 5 6 5
At the 0th second, the students at (4, 1) and (6, 1) get their meals.
At the 1st second, the new window at (5, 0) is opened. The students at (4, 3), (6, 3), (4, 5), (6, 5) go to the new queue(it takes one second). And the students at (4, 2) and (6, 2) at the beginning of 0th second get their meals.
Author: ZHUANG, Junyuan
Contest: ZOJ Monthly, February 2012