Darwin has been observing finches flying around the Galapagos Islands, and it is now mating season. For mating, the finches exhibit an interesting behavior: $$$n$$$ male finches will fly straight up and come back straight down as a flight display. The $$$i$$$th finsh starts at a horizontal location $$$l_i$$$ ($$$l_i$$$ can be negative) and reaches a height of $$$h_i$$$. Female finches will then fly to where the male landed and fan their tails to signal acceptance.
The wind will naturally affect where the male finch lands. There are $$$m$$$ jetstreams currently above the Galapagos. The $$$j$$$th jetstream is located at altitude $$$a_j$$$ and blows any finches at this height by $$$w_j$$$ units to the right ($$$w_j$$$ can be negative, blowing finches to the left). Male finches that go past a jetstream will be blown over both going up and coming down, while those peaking at the jetstream altitude will only be blown over once.
Natural female finches are adapted to adjusting for wind when locating the males, but Darwin rescued a baby finch that he will be releasing soon, and he needs to train this finch. Please provide the landing locations of each of the male finches that Darwin can communicate to his baby finch (don't worry about how, he's a trained scientist).
The first line contains $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of male finches, and $$$m$$$ $$$(0 \leq m \leq 10^5)$$$, the number of jetstreams.
Each of the next $$$n$$$ lines contain two integers $$$l_i$$$ and $$$h_i$$$ ($$$0 \leq |l_i|, h_i \leq 10^9$$$) – the starting location and max altitude of the $$$i$$$th finch.
Each of the next $$$m$$$ lines contain two integers $$$a_j$$$ and $$$w_j$$$ ($$$0 \leq a_j, |w_j| \leq 10^9$$$) — the altitude and strength of the $$$j$$$th jetstream.
Output one line containing the landing positions of each of the $$$n$$$ male finches in order.
3 15 22 4-2 64 2
5 4 2
| Name |
|---|


