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.
A new window is only opened at the beginning of a second and no two windows will be opened at the same time.
Students will go to another queue only at the second the corresponding window is opened.
Students who go to the new queue will be lined up in the order of the distance between his/her original position and the new window. The nearer one goes ahead. But if some students have the same distance, one of them will help others get meals so that they can be considered as one student in the queue.
It takes one second for a student to get meal even if he/she should get for others.
It takes one second for a student to go to the queue of the new window, despite how far he/she is from the window.
The strategy students choose whether to go to the new queue is that if going to the new queue will not make him/her get meal later, he/she will choose to go, otherwise he/she will stay in the original queue. Also, every student knows that other students take the same strategy so that they can figure out whether to go.
With the status at the beginning of the 0th second given, you should tell me at which window does every student get meals.
Input
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.
Output
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.
Sample Input
3 1
4 5
6 5
7 0
5 1
Sample Output
4 4 5 4 5 6 6 5 6 5
