Thư từ (Letters)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ ký túc xá, được đánh số từ $1$ đến $n$. Ký túc xá thứ $i$ có $a_i$ phòng; các phòng bên trong ký túc xá đó được đánh số từ $1$ đến $a_i$.

Nếu ghép toàn bộ các phòng thành một dãy liên tiếp, ta đánh số chúng từ $1$ đến

Toàn bộ phòng của ký túc xá $1$ đứng trước, sau đó là toàn bộ phòng của ký túc xá $2$, rồi ký túc xá $3$, và cứ như vậy.

Có $m$ lá thư. Trên lá thư thứ $j$ chỉ ghi một số phòng toàn cục $b_j$, với

Với mỗi lá thư, hãy xác định:

• ký túc xá chứa phòng toàn cục $b_j$;
• số phòng tương ứng bên trong ký túc xá đó.

Ví dụ, nếu $a_1=3$ và $a_2=5$ thì các phòng toàn cục $1,2,3$ thuộc ký túc xá $1$, còn $4,5,6,7,8$ thuộc ký túc xá $2$. Vì vậy phòng toàn cục $7$ chính là phòng $4$ của ký túc xá $2$.

Input

• Dòng đầu chứa hai số nguyên $n,m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.
• Dòng thứ ba chứa $m$ số nguyên $b_1,b_2,\ldots,b_m$ theo thứ tự tăng dần.

Output

In $m$ dòng. Dòng thứ $j$ chứa hai số nguyên $f_j,k_j$, trong đó $f_j$ là số thứ tự ký túc xá và $k_j$ là số phòng bên trong ký túc xá ứng với phòng toàn cục $b_j$.

Subtask

• 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}$; mọi $b_j$ thỏa $1\le b_j\le\sum_{i=1}^{n}a_i$.

Ví dụ

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

Giải thích

Tổng số phòng tính đến hết từng ký túc xá lần lượt là $10,25,37$. Chẳng hạn, $b_3=12$ nằm trong ký túc xá $2$ vì $10<12\le25$. Trước ký túc xá này có $10$ phòng nên số phòng cục bộ là $12-10=2$.