English · Original
Chinese · Translation
Formal · Original
Ivar the Boneless is a great leader. He is trying to capture Kattegat from Lagertha. The war has begun and wave after wave Ivar's warriors are falling in battle.
Ivar has $n$ warriors, he places them on a straight line in front of the main gate, in a way that the $i$\-th warrior stands right after $(i-1)$\-th warrior. The first warrior leads the attack.
Each attacker can take up to $a_i$ arrows before he falls to the ground, where $a_i$ is the $i$\-th warrior's strength.
Lagertha orders her warriors to shoot $k_i$ arrows during the $i$\-th minute, the arrows one by one hit the first still standing warrior. After all Ivar's warriors fall and all the currently flying arrows fly by, Thor smashes his hammer and all Ivar's warriors get their previous strengths back and stand up to fight again. In other words, if all warriors die in minute $t$, they will all be standing to fight at the end of minute $t$.
The battle will last for $q$ minutes, after each minute you should tell Ivar what is the number of his standing warriors.
## Input
The first line contains two integers $n$ and $q$ ($1 \le n, q \leq 200\,000$) — the number of warriors and the number of minutes in the battle.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) that represent the warriors' strengths.
The third line contains $q$ integers $k_1, k_2, \ldots, k_q$ ($1 \leq k_i \leq 10^{14}$), the $i$\-th of them represents Lagertha's order at the $i$\-th minute: $k_i$ arrows will attack the warriors.
## Output
Output $q$ lines, the $i$\-th of them is the number of standing warriors after the $i$\-th minute.
[samples]
## Note
In the first example:
* after the 1-st minute, the 1-st and 2-nd warriors die.
* after the 2-nd minute all warriors die (and all arrows left over are wasted), then they will be revived thus answer is 5 — all warriors are alive.
* after the 3-rd minute, the 1-st warrior dies.
* after the 4-th minute, the 2-nd warrior takes a hit and his strength decreases by 1.
* after the 5-th minute, the 2-nd warrior dies.
Ivar the Boneless 是一位伟大的领袖。他正试图从 Lagertha 手中夺取 Kattegat。战争已经打响，Ivar 的战士们一波接一波地倒在战场上。
Ivar 有 $n$ 个战士，他将他们排成一条直线，位于主门前方，第 $i$ 个战士站在第 $(i -1)$ 个战士的正后方。第一个战士负责冲锋。
每个攻击者最多能承受 $a_i$ 支箭矢后才会倒下，其中 $a_i$ 是第 $i$ 个战士的强度。
Lagertha 命令她的战士们在第 $i$ 分钟射出 $k_i$ 支箭矢，箭矢依次击中当前仍站立的最前面的战士。当所有 Ivar 的战士都倒下且所有正在飞行的箭矢都已落地后，Thor 会砸下他的锤子，使所有 Ivar 的战士恢复他们之前的强度并重新站起来继续战斗。换句话说，如果所有战士在第 $t$ 分钟死亡，他们将在第 $t$ 分钟结束时全部复活。
战斗将持续 $q$ 分钟，在每分钟结束后，你需要告诉 Ivar 他有多少战士仍处于站立状态。
第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n, q lt.eq 200 thin 000$）——战士的数量和战斗的分钟数。
第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^9$），表示战士们的强度。
第三行包含 $q$ 个整数 $k_1, k_2, dots.h, k_q$（$1 lt.eq k_i lt.eq 10^(14)$），第 $i$ 个数表示第 $i$ 分钟 Lagertha 的命令：$k_i$ 支箭矢将攻击战士们。
请输出 $q$ 行，第 $i$ 行为第 $i$ 分钟后仍站立的战士数量。
在第一个示例中：
## Input
第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n, q lt.eq 200 thin 000$）——战士的数量和战斗的分钟数。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^9$），表示战士们的强度。第三行包含 $q$ 个整数 $k_1, k_2, dots.h, k_q$（$1 lt.eq k_i lt.eq 10^(14)$），第 $i$ 个数表示第 $i$ 分钟 Lagertha 的命令：$k_i$ 支箭矢将攻击战士们。
## Output
请输出 $q$ 行，第 $i$ 行为第 $i$ 分钟后仍站立的战士数量。
[samples]
## Note
在第一个示例中：
在第 1 分钟后，第 1 和第 2 个战士死亡。
在第 2 分钟后，所有战士死亡（剩余的箭矢被浪费），然后他们被复活，因此答案是 5——所有战士都活着。
在第 3 分钟后，第 1 个战士死亡。
在第 4 分钟后，第 2 个战士受到一次攻击，其强度减少 1。
在第 5 分钟后，第 2 个战士死亡。
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the number of warriors and the number of minutes, respectively.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the strength vector of the warriors, where $ a_i $ is the maximum number of arrows warrior $ i $ can withstand.
Let $ K = (k_1, k_2, \dots, k_q) \in \mathbb{Z}^q $ be the arrow attack vector, where $ k_i $ is the number of arrows shot in minute $ i $.
Let $ H_t \in \mathbb{Z}^n $ denote the health vector of the warriors at the end of minute $ t $, with initial state $ H_0 = A $.
Let $ s_t \in \mathbb{Z} $ denote the number of standing warriors after minute $ t $.
**Constraints**
1. $ 1 \le n, q \le 200{,}000 $
2. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \le k_i \le 10^{14} $ for all $ i \in \{1, \dots, q\} $
**Dynamics**
For each minute $ i \in \{1, \dots, q\} $:
- $ k_i $ arrows are fired sequentially, each hitting the first standing warrior (smallest index with positive health).
- For each arrow, subtract 1 from the health of the first warrior with $ H_{i-1}[j] > 0 $.
- After all $ k_i $ arrows are applied, update $ H_i $ as the resulting health vector.
- If all warriors have $ H_i[j] = 0 $, then **at the end of minute $ i $**, all warriors are restored to their original strengths:
$$
H_i = A
$$
**Objective**
For each minute $ i \in \{1, \dots, q\} $, output:
$$
s_i = \left| \left\{ j \in \{1, \dots, n\} \mid H_i[j] > 0 \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "C. Valhalla Siege",
"description": {
"content": "Ivar the Boneless is a great leader. He is trying to capture Kattegat from Lagertha. The war has begun and wave after wave Ivar's warriors are falling in battle. Ivar has $n$ warriors, he places them",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF975C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Ivar the Boneless is a great leader. He is trying to capture Kattegat from Lagertha. The war has begun and wave after wave Ivar's warriors are falling in battle.\n\nIvar has $n$ warriors, he places them...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Ivar the Boneless 是一位伟大的领袖。他正试图从 Lagertha 手中夺取 Kattegat。战争已经打响，Ivar 的战士们一波接一波地倒在战场上。\n\nIvar 有 $n$ 个战士，他将他们排成一条直线，位于主门前方，第 $i$ 个战士站在第 $(i -1)$ 个战士的正后方。第一个战士负责冲锋。\n\n每个攻击者最多能承受 $a_i$ 支箭矢后才会倒下，其中 $a_i$ 是第 $...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of warriors and the number of minutes, respectively. \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the strength vector of t...",
"is_translate": false,
"language": "Formal"
}
]
}