← 返回题目列表

Codeforces · 609/F

F. 青蛙和蚊子

中文机器翻译题面 查看原题

有 n 只青蛙坐在坐标轴 Ox 上。对于每只青蛙来说,有两个值 xi 和 ti 是已知的——第 i 只青蛙舌头的位置和初始长度(保证所有位置 xi 都不同)。 m只蚊子一只一只地落在坐标轴上。对于每只蚊子,有两个已知值 pj — 第 j 个蚊子着陆位置的坐标和 bj — 第 j 个蚊子的大小。青蛙和蚊子用坐标轴上的点表示。

如果蚊子与青蛙处于同一位置或在右侧,并且它们之间的距离不大于青蛙舌头的长度,则青蛙可以吃蚊子。

如果在某个时刻几只青蛙可以吃掉一只蚊子,那么最左边的青蛙就会吃掉它(xi 最小)。青蛙吃掉蚊子后,舌头的长度会随着所吃蚊子大小的增加而增加。之后青蛙可能会吃掉其他一些蚊子(在这种情况下青蛙应该吃掉它们)。

对于每只青蛙,打印两个值——吃掉的蚊子数量以及所有蚊子着陆后和青蛙吃掉所有可能的蚊子后舌头的长度。

只有青蛙吃掉之前降落的所有可能的蚊子后,每只蚊子才会降落到坐标轴。蚊子按照其降落到坐标轴的顺序给出。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 2·105) — 青蛙和蚊子的数量。

接下来的 n 行每行包含两个整数 xi, ti (0 ≤ xi, ti ≤ 109) — 第 i 只青蛙舌头的位置和初始长度。保证所有的 xi 都是不同的。

接下来的 m 行包含两个整数,每行 pj, bj (0 ≤ pj, bj ≤ 109) — 第 j 只蚊子的位置和大小。

输出

打印 n 行。第 i 行应包含两个整数值 ci、li——第 i 只青蛙吃掉的蚊子数量和第 i 只青蛙的舌头长度。

示例

输入 #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