English · Original
Chinese · Translation
Formal · Original
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.
[samples]
## 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
在贝兰德国立大学中有 $n$ 栋宿舍楼，编号为从 $1$ 到 $n$ 的整数。每栋宿舍楼包含若干房间，第 $i$ 栋宿舍楼有 $a_i$ 个房间，房间编号从 $1$ 到 $a_i$。
邮递员负责投递信件。有时信封上没有写明具体的宿舍楼和房间号，而只写了一个在所有 $n$ 栋宿舍楼所有房间中的房间编号。在这种情况下，假设所有房间被统一编号为从 $1$ 到 $a_1 + a_2 + dots.h + a_n$，其中第一栋宿舍楼的房间排在最前面，第二栋宿舍楼的房间紧随其后，依此类推。
例如，当 $n = 2$，$a_1 = 3$ 且 $a_2 = 5$ 时，信封上可能写有从 $1$ 到 $8$ 的任意整数。如果写的是数字 $7$，则表示信件应递送到第二栋宿舍楼的第 $4$ 个房间。
对于 $m$ 封信，每封信的信封上都给出了一个在所有 $n$ 栋宿舍楼中的房间编号，请确定每封信应递送到的具体宿舍楼编号及其在该宿舍楼内的房间编号。
第一行包含两个整数 $n$ 和 $m$ $(1 lt.eq n, m lt.eq 2 dot.op 10^5)$ —— 宿舍楼数量和信件数量。
第二行包含一个序列 $a_1, a_2, dots.h, a_n$ $(1 lt.eq a_i lt.eq 10^(10))$，其中 $a_i$ 表示第 $i$ 栋宿舍楼的房间数。第三行包含一个序列 $b_1, b_2, dots.h, b_m$ $(1 lt.eq b_j lt.eq a_1 + a_2 + dots.h + a_n)$，其中 $b_j$ 表示第 $j$ 封信对应的房间编号（在所有宿舍楼的房间中）。所有 $b_j$ 均按*递增*顺序给出。
请输出 $m$ 行。对于每封信，输出两个整数 $f$ 和 $k$ —— 宿舍楼编号 $f$ $(1 lt.eq f lt.eq n)$ 和该宿舍楼内的房间编号 $k$ $(1 lt.eq k lt.eq a_f)$，用于投递该信件。
## Input
第一行包含两个整数 $n$ 和 $m$ $(1 lt.eq n, m lt.eq 2 dot.op 10^5)$ —— 宿舍楼数量和信件数量。第二行包含一个序列 $a_1, a_2, dots.h, a_n$ $(1 lt.eq a_i lt.eq 10^(10))$，其中 $a_i$ 表示第 $i$ 栋宿舍楼的房间数。第三行包含一个序列 $b_1, b_2, dots.h, b_m$ $(1 lt.eq b_j lt.eq a_1 + a_2 + dots.h + a_n)$，其中 $b_j$ 表示第 $j$ 封信对应的房间编号（在所有宿舍楼的房间中）。所有 $b_j$ 均按*递增*顺序给出。
## Output
请输出 $m$ 行。对于每封信，输出两个整数 $f$ 和 $k$ —— 宿舍楼编号 $f$ $(1 lt.eq f lt.eq n)$ 和该宿舍楼内的房间编号 $k$ $(1 lt.eq k lt.eq a_f)$，用于投递该信件。
[samples]
## Note
在第一个例子中，信件应按以下顺序投递：
第一封信投递到第一栋宿舍楼的第 $1$ 个房间，
第二封信投递到第一栋宿舍楼的第 $9$ 个房间，
第三封信投递到第二栋宿舍楼的第 $2$ 个房间，
第四封信投递到第二栋宿舍楼的第 $13$ 个房间，
第五封信投递到第三栋宿舍楼的第 $1$ 个房间，
第六封信投递到第三栋宿舍楼的第 $12$ 个房间。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of dormitories and letters, respectively.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers where $ a_i $ is the number of rooms in dormitory $ i $.
Let $ S = \sum_{i=1}^n a_i $ be the total number of rooms across all dormitories.
Let $ B = (b_1, b_2, \dots, b_m) $ be a strictly increasing sequence of positive integers with $ b_j \in [1, S] $, representing the global room numbers for each letter.
Define the prefix sum array $ P = (p_0, p_1, \dots, p_n) $ where:
$$ p_0 = 0, \quad p_i = \sum_{k=1}^i a_k \quad \text{for } i \in \{1, \dots, n\} $$
**Constraints**
1. $ 1 \le n, m \le 2 \cdot 10^5 $
2. $ 1 \le a_i \le 10^{10} $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \le b_1 < b_2 < \dots < b_m \le S $
**Objective**
For each $ j \in \{1, \dots, m\} $, find the unique pair $ (f_j, k_j) $ such that:
- $ f_j \in \{1, \dots, n\} $ is the dormitory number,
- $ k_j \in \{1, \dots, a_{f_j}\} $ is the room number within dormitory $ f_j $,
satisfying:
$$ p_{f_j - 1} < b_j \le p_{f_j} \quad \text{and} \quad k_j = b_j - p_{f_j - 1} $$
Output the sequence $ \{(f_j, k_j)\}_{j=1}^m $.
API Response (JSON)
{
"problem": {
"name": "C. Letters",
"description": {
"content": "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$\\-",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF978C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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$\\-...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在贝兰德国立大学中有 $n$ 栋宿舍楼，编号为从 $1$ 到 $n$ 的整数。每栋宿舍楼包含若干房间，第 $i$ 栋宿舍楼有 $a_i$ 个房间，房间编号从 $1$ 到 $a_i$。\n\n邮递员负责投递信件。有时信封上没有写明具体的宿舍楼和房间号，而只写了一个在所有 $n$ 栋宿舍楼所有房间中的房间编号。在这种情况下，假设所有房间被统一编号为从 $1$ 到 $a_1 + a_2 + dots.h +...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of dormitories and letters, respectively. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers where $ a_i $ is the...",
"is_translate": false,
"language": "Formal"
}
]
}