Letters

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ dormitories numbered from $1$ to $n$. Dormitory $i$ contains $a_i$ rooms, locally numbered from $1$ to $a_i$.

If all rooms are concatenated into one sequence, their global numbers range from $1$ to

All rooms of dormitory $1$ come first, then all rooms of dormitory $2$, and so on.

There are $m$ letters. Letter $j$ contains only a global room number $b_j$, where $1\le b_j\le S$. For every letter, determine the dormitory number and the local room number inside that dormitory.

Input

• The first line contains integers $n,m$.
• The second line contains $a_1,a_2,\ldots,a_n$.
• The third line contains $b_1,b_2,\ldots,b_m$ in increasing order.

Output

Print $m$ lines. Line $j$ contains two integers $f_j,k_j$: the dormitory number and local room number corresponding to $b_j$.

Subtasks

• Subtask 1 — 20%: $1\le n,m\le100$, $1\le a_i\le10^3$.
• Subtask 2 — 30%: $1\le n,m\le5000$, $1\le a_i\le10^6$.
• Subtask 3 — 50%: $1\le n,m\le2\cdot10^5$, $1\le a_i\le10^{10}$; every $b_j$ satisfies $1\le b_j\le\sum_{i=1}^{n}a_i$.

Example

Input

3 6
10 15 12
1 9 12 23 26 37

Output

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

Explanation

The prefix totals are $10,25,37$. For example, $b_3=12$ belongs to dormitory $2$ because $10<12\le25$. There are $10$ rooms before that dormitory, so its local room number is $12-10=2$.