Letters

4000ms

262144K

Description:

There are $$$n$$$ dormitories in Berland State University, they are numbered with integers from $$$1$$$ to $$$n$$$. Each dormitory consists of rooms, there are $$$a_i$$$ rooms in $$$i$$$-th dormitory. The rooms in $$$i$$$-th dormitory are numbered from $$$1$$$ to $$$a_i$$$.

A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all $$$n$$$ dormitories is written on an envelope. In this case, assume that all the rooms are numbered from $$$1$$$ to $$$a_1 + a_2 + \dots + a_n$$$ and the rooms of the first dormitory go first, the rooms of the second dormitory go after them and so on.

For example, in case $$$n=2$$$, $$$a_1=3$$$ and $$$a_2=5$$$ an envelope can have any integer from $$$1$$$ to $$$8$$$ written on it. If the number $$$7$$$ is written on an envelope, it means that the letter should be delivered to the room number $$$4$$$ of the second dormitory.

For each of $$$m$$$ letters by the room number among all $$$n$$$ dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 2 \cdot 10^{5})$$$ — the number of dormitories and the number of letters.

The second line contains a sequence $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{10})$$$, where $$$a_i$$$ equals to the number of rooms in the $$$i$$$-th dormitory. The third line contains a sequence $$$b_1, b_2, \dots, b_m$$$ $$$(1 \le b_j \le a_1 + a_2 + \dots + a_n)$$$, where $$$b_j$$$ equals to the room number (among all rooms of all dormitories) for the $$$j$$$-th letter. All $$$b_j$$$ are given in increasing order.

Output:

Print $$$m$$$ lines. For each letter print two integers $$$f$$$ and $$$k$$$ — the dormitory number $$$f$$$ $$$(1 \le f \le n)$$$ and the room number $$$k$$$ in this dormitory $$$(1 \le k \le a_f)$$$ to deliver the letter.

Sample Input:

3 6
10 15 12
1 9 12 23 26 37

Sample Output:

Sample Input:

2 3
5 10000000000
5 6 9999999999

Sample Output:

1 5
2 1
2 9999999994

Note:

In the first example letters should be delivered in the following order:

the first letter in room $$$1$$$ of the first dormitory
the second letter in room $$$9$$$ of the first dormitory
the third letter in room $$$2$$$ of the second dormitory
the fourth letter in room $$$13$$$ of the second dormitory
the fifth letter in room $$$1$$$ of the third dormitory
the sixth letter in room $$$12$$$ of the third dormitory

Informação

Provedor Codeforces

Código CF978C