
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 ith 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. InputThe 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 x_{i}, q_{i} (0 ≤ q_{i} ≤ 100, x_{i} is a nonnegtive signed 32bit integer), which mean the window is at (x_{i}, 0) and the number of students waiting in front of the window is q_{i}. The next m lines each contains two integers x_{i}, t_{i} (both within 32bit signed integers, and are nonnegative), which mean the window at (x_{i}, 0) is opened at the beginning of t_{i}th second. All x_{i} in a case will be different. OutputFor 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. Sample Input3 1 4 5 6 5 7 0 5 1 Sample Output4 4 5 4 5 6 6 5 6 5 HintAt 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 