← 返回题目列表

Codeforces · 978/C

C. 信件

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

Berland州立大学共有$$$n$$$个宿舍,编号为从$$$1$$$到$$$n$$$的整数。每个宿舍由房间组成,第$$$i$$$个宿舍有$$$a_i$$$个房间。第$$$i$$$宿舍的房间编号从$$$1$$$到$$$a_i$$$。

邮递员送信。有时信封上没有具体的宿舍和房间号。信封上只写了所有$$$n$$$宿舍的所有房间中的房间号。在这种情况下,假设所有房间的编号从$$$1$$$到$$$a_1 + a_2 + \dots + a_n$$$,并且第一宿舍的房间在前面,第二宿舍的房间在后面,依此类推。

例如,如果 $$$n=2$$$、$$$a_1=3$$$ 和 $$$a_2=5$$$,信封上可以写有从 $$$1$$$ 到 $$$8$$$ 的任何整数。如果信封上写着数字$$$7$$$,则表示这封信要投递到第二宿舍房间号$$$4$$$。

对于所有 $$$n$$$ 宿舍中按房间号排列的每个 $$$m$$$ 字母,确定该字母应投递到的特定宿舍以及宿舍中的房间号。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(1 \le n, m \le 2 \cdot 10^{5})$$$ — 宿舍数和字母数。

第二行包含序列 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{10})$$$,其中 $$$a_i$$$ 等于第 $$$i$$$ 宿舍的房间数。第三行包含序列 $$$b_1, b_2, \dots, b_m$$$ $$$(1 \le b_j \le a_1 + a_2 + \dots + a_n)$$$,其中 $$$b_j$$$ 等于第 $$$j$$$ 个字母的房间号(在所有宿舍的所有房间中)。所有 $$$b_j$$$ 均按升序给出。

输出

打印 $$$m$$$ 行。对于每封信,打印两个整数 $$$f$$$ 和 $$$k$$$ — 宿舍号 $$$f$$$ $$$(1 \le f \le n)$$$ 和该宿舍的房间号 $$$k$$$ 来投递信件。

示例

输入 #1

3 6
10 15 12
1 9 12 23 26 37

输出 #1

1 1
1 9
2 2
2 13
3 1
3 12

输入 #2

2 3
5 10000000000
5 6 9999999999

输出 #2

1 5
2 1
2 9999999994

注意

在第一个示例中,信件应按以下顺序发送:

- 第一宿舍$$$1$$$房间的第一个字母
- 第一宿舍$$$9$$$房间的第二个字母
- 第二宿舍$$$2$$$房间的第三个字母
- 第二宿舍$$$13$$$房间的第四封信
- 第三宿舍$$$1$$$房间的第五封信
- 第三宿舍$$$12$$$房间的第六封信