Frogs and mosquitoes

题意翻译

有 $n$ 只青蛙，第 $i$ 只青蛙位置为 $x_i$，舌头长度为 $t_i$，能吃到 $[x_i,x_i+t_i]$ 范围内的蚊子。青蛙的位置互不相同。 有 $m$ 只蚊子依次出现，位置为 $p_j$，价值为 $b_j$，它会被能吃掉它的最左边的青蛙吃掉，吃完它后那只青蛙的舌头长度会增长 $b_j$。蚊子的位置可能相同。 只有已经出现的蚊子都被吃了或者无法被吃掉时，新的蚊子会出现。 问每只青蛙吃掉了多少只蚊子及最终的舌头长度。 $1 \le n,m \le 2 \times 10^5$，$0 \le x_i,t_i,p_i,b_i \le 10^9$

题目描述

There are $ n $ frogs sitting on the coordinate axis $ Ox $ . For each frog two values $ x_{i},t_{i} $ are known — the position and the initial length of the tongue of the $ i $ -th frog (it is guaranteed that all positions $ x_{i} $ are different). $ m $ mosquitoes one by one are landing to the coordinate axis. For each mosquito two values are known $ p_{j} $ — the coordinate of the position where the $ j $ -th mosquito lands and $ b_{j} $ — the size of the $ j $ -th mosquito. Frogs and mosquitoes are represented as points on the coordinate axis. The frog can eat mosquito if mosquito is in the same position with the frog or to the right, and the distance between them is not greater than the length of the tongue of the frog. If at some moment several frogs can eat a mosquito the leftmost frog will eat it (with minimal $ x_{i} $ ). After eating a mosquito the length of the tongue of a frog increases with the value of the size of eaten mosquito. It's possible that after it the frog will be able to eat some other mosquitoes (the frog should eat them in this case). For each frog print two values — the number of eaten mosquitoes and the length of the tongue after landing all mosquitoes and after eating all possible mosquitoes by frogs. Each mosquito is landing to the coordinate axis only after frogs eat all possible mosquitoes landed before. Mosquitoes are given in order of their landing to the coordinate axis.

输入输出格式

输入格式

First line contains two integers $ n,m $ ( $ 1<=n,m<=2·10^{5} $ ) — the number of frogs and mosquitoes. Each of the next $ n $ lines contains two integers $ x_{i},t_{i} $ ( $ 0<=x_{i},t_{i}<=10^{9} $ ) — the position and the initial length of the tongue of the $ i $ -th frog. It is guaranteed that all $ x_{i} $ are different. Next $ m $ lines contain two integers each $ p_{j},b_{j} $ ( $ 0<=p_{j},b_{j}<=10^{9} $ ) — the position and the size of the $ j $ -th mosquito.

输出格式

Print $ n $ lines. The $ i $ -th line should contain two integer values $ c_{i},l_{i} $ — the number of mosquitoes eaten by the $ i $ -th frog and the length of the tongue of the $ i $ -th frog.

输入输出样例

输入样例 #1

4 6
10 2
15 0
6 1
0 1
110 10
1 1
6 0
15 10
14 100
12 2

输出样例 #1

3 114
1 10
1 1
1 2

输入样例 #2

1 2
10 2
20 2
12 1

输出样例 #2

1 3