Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Ivar the Boneless is a great leader. He is trying to capture Kattegat from Lagertha. The…

  1. User

    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 ≤ n, q ≤ 200 000) — the number of warriors and the number of minutes in the battle.

    The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) that represent the warriors' strengths.

    The third line contains q integers k_1, k_2, …, k_q (1 ≤ k_i ≤ 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.

    Examples

    Input

    5 5 1 2 1 2 1 3 10 1 1 1

    Output

    3 5 4 4 3

    Input

    4 4 1 2 3 4 9 1 10 6

    Output

    1 4 4 1

    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.
  2. DeepSeek Assistant

    We are given a problem: Ivar has n warriors placed in a line. Each warrior i has initial strength a_i (maximum arrows they can take before falling). In each minute (1 to q), Lagertha's warriors shoot k_i arrows. The arrows hit the first standing warrior (i.e., the one with smallest index among those still alive). Each arrow reduces that warrior's current health (remaining strength) by 1. When a warrior's remaining strength reaches 0 (i.e., after taking exactly a_i arrows), he falls (dies). Then the next arrow hits the next standing warrior (i.e., the next alive warrior). If all warriors fall during a minute, then after that minute ends, all warriors are revived (their strengths reset to original a_i) and stand up again. Also, any arrows that are still "flying" after all have fallen are wasted? Actually problem says: "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." So during a minute, arrows are shot one by one. After all k_i arrows are shot (or perhaps arrows are shot in that minute, but if all warriors die before all arrows are shot, the remaining arrows still "fly by" but hit no one? Actually "after all Ivar's warriors fall and all the currently flying arrows fly by" means: during the minute, arrows are being shot; if at some point all warriors are dead, then any arrows that were already shot but haven't hit yet? It says "all the currently flying arrows fly by". So they are wasted. And then at the end of the minute, they revive. So effectively, within a minute, we process k_i arrows sequentially, but if all warriors die before using all arrows, the rest are ignored and we have no more warriors to hit; after that we consider minute ends and all revive. So at the end of the minute, we need to output number of standing warriors (after possible revives).

    We need to answer after each minute: number of standing warriors.

    Constraints: n, q up to 200k. a_i up to 1e9, k_i up to 1e14.

    We need an efficient method per minute: simulate the arrows hitting a line of warriors with strengths. After each minute, warriors' current health may be reduced, some may die, and if all die, reset.

    This is reminiscent of a standard problem: we have an array of "health" (remaining), arrows come in batches. The arrows always target the first alive (lowest index). So it's like we have a pointer to the current first alive, and we reduce its health by arrows until it dies, then move to next, etc. The batch k_i may be large, and we need to process quickly across many minutes. Since n and q are large, we need O(log n) per minute or maybe amortized.

    We can think of maintaining the array of original strengths a_i, and for each warrior we track its current remaining health. Initially all are alive with remaining = a_i. After each minute with k arrows, we need to apply those arrows to the front.

    We could use a data structure to represent alive warriors in order, with ability to subtract health from the prefix, and find when a warrior's health reaches zero, remove it, and continue. This resembles a segment tree that supports range updates (prefix subtract) and binary search to find first positive remaining after a batch. But careful: arrows are applied one by one, but we can process in batch: we have total arrows to distribute to the alive warriors from left to right. So we can simulate: while k > 0 and there are alive warriors, we take the current first alive i (with remaining rem_i). If k >= rem_i, then that warrior dies, k -= rem_i, and we move to next. If k < rem_i, then that warrior's remaining becomes rem_i - k, and k=0. However, there's a twist: if all warriors die during this minute, after the minute ends they all revive, so the state after minute becomes full health. Actually the problem says: after all warriors fall and all currently flying arrows fly by, they get their strengths back and stand up. So if during the minute we cause all warriors to die, we then reset. But note: if we cause all warriors to die, we might have used only part of the k arrows? Actually if all die before we use all arrows, the remaining arrows fly by (wasted). So after the minute, the state is: all warriors are alive with full health. So if the batch kills all warriors, after minute we reset.

    But if not all die, we just have some warriors dead, and some with reduced health.

    Thus after each minute we need to output the number of alive warriors.

    Approach: Maintain a segment tree (or Fenwick) that stores remaining health of alive warriors in order. We need to support:

    • Query: find the first alive warrior (lowest index) that still has positive health.
    • Update: subtract value from a prefix until either a warrior dies or we run out of arrows.

    However, we can process a batch by repeatedly finding the current first alive warrior (which we know is the smallest index i where rem_i > 0). Then we know its remaining health rem_i. Then we compare with current k. But this could be many steps if k is huge and many warriors die. But we can handle it using something like: find the first index where the cumulative sum of remaining health from the start is >= k. Because if we have a series of warriors with rem values, and we want to know how many of them are fully consumed by a total of k arrows, we can compute prefix sums of rem. Actually it's like we have a list of positive numbers (remaining health) for alive warriors in order. We have to subtract total k from the prefix of that list, but only partially possibly on the last one. So we want to find the smallest prefix such that sum_{j=1}^{p} rem_j >= k. Then all warriors 1..p-1 die, and warrior p's rem becomes sum_{1}^{p} rem_j - k (or if exactly equal, then p dies as well). But careful: The alive warriors are not necessarily the original indices because some warriors may already be dead. However, the order is preserved: only those alive. So we can think of a data structure that stores the remaining health of all warriors (including dead ones with 0). But better: we can maintain an array for all n warriors, where dead warriors have rem_i = 0. Then the first alive is the smallest index with rem_i > 0. Then to apply k arrows, we need to effectively subtract from a contiguous segment starting at that first alive index until we've used k arrows. This is essentially a range update that reduces values.

    But we cannot just do range updates because we need to know when a warrior reaches zero exactly, not overshoot. Because arrows are shot one by one, we cannot reduce a warrior below zero. So we need to simulate the process: find the first index i with rem_i > 0. Then we have two cases:

    • if k < rem_i: subtract k from rem_i; done.
    • else: set rem_i = 0, k -= rem_i, and then repeat with next alive.

    We can speed up by using a segment tree that stores the sum of rem over a segment, and also the minimum? Actually to find the first index where cumulative sum >= k, we can use a segment tree that stores sum of rem, and we can binary search on it to find the smallest prefix (starting from current leftmost alive) such that prefix sum >= k. But note that after we kill some warriors, the next warrior might be partially reduced. This can be done efficiently with a segment tree. However, we must also handle the resetting when all warriors die. That would be just resetting the segment tree to original a_i values, and resetting any partial reductions.

    Complexity: Each minute we may perform a constant number of segment tree operations: find first alive index (maybe always the same if we maintain pointer), then binary search to find the stopping point. However, if we kill many warriors in one minute, we might only need O(log n) operations total. So per minute O(log n). That's fine.

    But there is a nuance: the cumulative sum from the first alive to some index includes only alive warriors. If we maintain an array of remaining health for all indices (dead have 0), then the prefix sum from start of array includes dead ones which are 0. So the first alive index is the first positive. Then we need to compute prefix sum from that index? Actually we can maintain a pointer to the current first alive (lowest index with rem>0). Let's call it start. Initially start=1. After each minute, start may increase as warriors die from left, but if reset happens (all die), start becomes 1 again. Also, if all warriors die and then revive, start=1. So we can maintain start index.

    During a minute with k arrows, we need to apply them starting from start. We can query the segment tree for the total sum of rem from start to n. If total_sum <= k, then all warriors from start to n will die (since total arrows enough to kill all remaining). In this case, we set all those rem to 0, and then after minute, since all warriors are dead, we need to reset them to original a_i (and stand up). Actually careful: if total_sum <= k, then after using total_sum arrows, all warriors die. The remaining arrows (k - total_sum) are wasted. Then at the end of minute, all warriors revive (so all become alive with full health). So the state after minute becomes all warriors alive with rem = a_i. So we need to reset everything.

    If total_sum > k, then not all die. We need to find the smallest index pos (>= start) such that sum_{i=start}^{pos} rem_i >= k. Then we will kill all warriors from start to pos-1, and reduce the warrior at pos by (k - sum_{start}^{pos-1}). So we need to update: set rem_i = 0 for i in [start, pos-1]; set rem_pos = (sum_{start}^{pos} - k). And then after that, start becomes pos if rem_pos > 0? Actually after this, the first alive might still be pos if rem_pos > 0; if it becomes zero, then it also died (i.e., sum exactly equals k). So if sum_{start}^{pos} == k, then warrior pos also dies, and start becomes pos+1. So we need to handle both cases.

    Thus we need to support operations on an array (size n):

    • Range set to zero (for indices in a contiguous segment).
    • Point update (set a single index to a new value).
    • Range sum query.
    • Finding first index with positive value? Actually we also need to quickly find start. Since we maintain start pointer, after updates we need to know if start is still alive. But we can update start accordingly: if we set range [start, pos-1] to zero, and if pos is partially alive, start becomes pos. If pos died, start becomes pos+1. And after reset, start becomes 1.

    But after partial reductions where k < rem_start, we only do point update on start, and start remains the same (since it's still alive). So start pointer is easy.

    But we need to ensure we can find the pos efficiently: given start, we need the smallest index >= start such that prefix sum from start to that index >= k. Equivalent to find smallest index idx where prefix_sum(1..idx) >= prefix_sum(1..start-1) + k. So if we maintain a segment tree over the entire array, we can store sums. We can binary search on the segment tree to find the first index where cumulative sum from start reaches k. This is a standard operation: find the smallest index idx such that sum_{1..idx} >= target. We'll have target = pre + k, where pre = sum_{1..start-1}. Since dead warriors have zero sum, sum_{1..start-1} is zero? Actually if we keep dead warriors as zero, then sum_{1..start-1} is zero because all before start are dead (they have 0). But careful: Could there be dead warriors that are not at the start? Actually after some minutes, there may be dead warriors at the front (indices 1..some) and then alive ones. But start is defined as the first alive index. So all indices < start have rem=0. So indeed sum_{1..start-1}=0. However, if we maintain start as pointer, we don't need to compute pre; we can just find the first index idx >= start such that cumulative sum from start is >= k. This can be done by searching on segment tree with offset: query sum from start to mid. Standard approach: implement a segment tree that supports "find first index where prefix sum from left is >= x". But with the ability to start from some index, we can compute total sum from 1..start-1, then set target = that sum + k. Then find idx. Since dead ones have sum zero, sum_{1..start-1} is zero. But if we ever have dead warriors with zeros in between? Actually start is the first alive, so indices < start are dead -> sum=0, yes. But after we perform partial updates, maybe some indices after start become dead, but start moves forward. So it's consistent.

    But we need to be careful: after we do range set to zero for [start, pos-1], the sum for those indices becomes zero. Also, after we partially update pos, its sum changes. The segment tree must support range assignment to zero, and point assignment. This is doable with lazy propagation for range set? Actually we need to set a range to zero. That's a range assignment operation. But we also need point assignments (set to some value). So a segment tree with lazy propagation for assignment (set to a constant) can handle range set to zero. However, we also need to set a single index to a new value. That can be a point update that overrides any previous lazy. So we can implement a segment tree with lazy assignment to a constant, and also storing sum. Since assignment to zero is a special case.

    Alternatively, we could use a Fenwick tree with some other structure to find pos using binary search on prefix sums. But we also need to update ranges (set a contiguous segment to zero). That is doable with a Fenwick if we use difference array and maintain values? But we need to support point queries to get individual values? Actually for binary searching to find idx where cumulative sum reaches k, we need to compute prefix sums quickly. If we do range set to zero, we need to update many indices to zero. That could be done with a Fenwick with range updates? Actually setting a range to zero is not additive; it's a reset to a specific value, not an increment. That's more complicated. However, we can note that once a warrior is dead, its rem becomes zero and will remain zero until a reset (when all die). But in the process, we may set a range to zero and also later partially update a warrior (which might be later set to zero again, etc.). The only time we assign non-zero values is: initially all a_i; after a minute where not all die, we set some prefix to zero, and set one warrior to a positive value (maybe zero as well). And after a total wipe, we set all to original a_i. So the number of non-zero updates is limited: at most one partial update per minute (point update) plus possibly many range sets to zero. However, we can avoid explicit range set to zero by using a data structure that "removes" dead warriors, like a balanced BST of alive warriors with their indices and remaining health. Then processing a batch reduces to moving through the BST and deleting nodes until k is exhausted. This could be O(number of warriors that die) per minute, which is too many if many die across minutes.

    But we can combine: using a segment tree with lazy assignment for zero, and also point updates. That seems plausible.

    We need to consider the total number of range set operations. In the worst case, each minute could kill many warriors. Over q minutes, total number of warriors that die could be O(n q) if they keep reviving. Actually after a full wipe, they all revive, so we may kill many repeatedly. So we need to handle up to 200k minutes, each could kill up to n warriors. So we need to kill many warriors in a minute efficiently. The segment tree approach with range assignment to zero can kill a whole segment in O(log n) time (by setting lazy). So that's good.

    But there is a catch: When we set a range to zero lazily, we need to maintain the sum. That's fine.

    Now, what about the point update for the partially reduced warrior? That can be done as a point assignment (set to new value) in O(log n). And when we need to reset all to original a_i, that's a range assignment over the whole array to original values. We could also just do a lazy assignment for the whole tree with values a_i. But we need to store the original array. We can support range assign to a constant value, but the constant may differ per index (like we need to assign each index to its original a_i). That's not a single constant; it's varying. So we cannot do a single range assignment to set all to original values because they differ. But we could reset by reconstructing the segment tree from original array? That would be O(n) per reset, too slow. However, note that resets only occur when all warriors die. When they all die, we set the state to all alive with original strengths. Instead of actually updating the whole array, we could maintain a flag that indicates that the array is in "full health" state. But we also have modifications in between. The reset is a full restore. So we need to support a "revert to initial" operation. One approach is to have a segment tree with lazy propagation for assignments, but with the ability to assign each leaf to its original value individually, which is not a uniform constant. So we could implement a "reset" by performing a range assignment that sets a lazy flag to "initial" value. That would require storing for each node the sum of initial values. We could have two modes: the segment tree stores current values; to reset, we can assign each node to its original sum. That's basically reinitializing the tree to the original array. That can be done by recursively building? But we can do it in O(n) if we do a full rebuild, but q up to 200k and n up to 200k, total O(n q) not acceptable.

    Better: note that after a full wipe, all warriors are alive again with full health. So the state becomes identical to the initial state. So we can simply reset a global "offset" or use a data structure that supports "clear all modifications". For example, we could maintain a segment tree that stores the current values, and when we need to reset, we could do a range assign using the original values? But we need to assign each leaf to a specific value. This is like copying the original array into the tree. We could do this with lazy propagation if we store a "reset" flag that says "set to original". That would require for each node, knowing the sum of original values. That's fine; we store orig_sum in node. Then we have a lazy flag "assign_custom" that can be either "set to zero" or "set to original". But also we have point updates that override those. So the lazy system would need to handle two types of assignments: assign to zero, assign to original. However, point update (set to a specific value) can be treated as assign to a constant that overrides previous lazy. But we can manage: we can have a lazy tag that indicates that the entire segment is set to some "value". For zero, it's a constant 0 for all indices. For original, it's not constant because each leaf has its own original value. So that doesn't work as a single constant.

    Alternative: we can handle reset differently: when total_sum <= k, instead of updating the tree to zero then resetting, we can simply set a global flag that indicates that the state is "all alive". But then subsequent operations need to interact correctly with this flag. Let's think: we maintain the segment tree representing current remaining health. If a total wipe occurs, we can simply set the entire tree to the initial values (i.e., we could rebuild lazily). But maybe we can avoid resets by noting that after a total wipe, the state is exactly the same as the initial state. So we could just "clear" the tree and start over. But we need to support many total wipes. However, we could implement a "reset" operation by doing a range assignment to zero and then later we will treat all as alive? Not exactly.

    Another perspective: The process is similar to repeatedly deducting from the front. The reset happens only when all warriors die. So after a total wipe, everything is back to original. So we could, after a total wipe, just reinitialize the data structure to the original values. Since total wipes may be frequent, but each reset costs O(n) if done naively. However, note that between total wipes, we might have many minutes where not all die. The number of total wipes could be up to q (if each minute kills all). In worst case, q=200k, n=200k, resetting each time O(n) would be 40 billion, too much. So we need O(log n) per minute including resets.

    Therefore we need a segment tree that supports resetting to initial values in O(log n) time. That seems impossible because resetting to initial values requires setting each leaf to a distinct value. But maybe we can avoid explicit reset by handling total wipe as a special case: when total_sum <= k, we can just set all rem to 0 (via range assign zero) and then set a global flag that says "all dead". But after the minute ends, they all revive, so the state after minute is all alive with full health. So we need to have them alive for the next minute. However, we could delay the revive until the next minute's start? Actually after the minute, they are standing. So at the end of minute t, we need to output the number of standing warriors, which after a total wipe is n (all revived). So the state for minute t+1 must be full health. So we need to have the data reflect full health immediately after minute t. So we must set the array to full health.

    Thus we need to implement the reset efficiently.

    Observation: The reset occurs only when all warriors die. At that moment, the entire array becomes zeros (dead) and then we set to full health. So effectively, the array transitions from zeros to original values. Could we treat zeros as a special state and then for the next minute, we start with original values? But we have to be able to process queries on the array that represents current health. So we need the actual values.

    Idea: Use a segment tree that stores the original array and also a "shift" or "offset" representing how many arrows have been applied to the prefix? Hmm. Another approach: Represent the process as a queue of warriors with health. However, the warriors are fixed at positions; we just care about the order from left to right. The arrows always hit the first alive. So this is analogous to having a list where we repeatedly subtract from the head. There is a known technique using a binary indexed tree and maintaining a pointer to the current first index, and using prefix sums to find the warrior that will survive. And we can also manage resets by noting that if we kill all, we simply set the pointer to 1 and restore all health values to original. But again, restoring values is the issue.

    Maybe we can avoid storing the entire array of remaining health explicitly; instead we could store for each warrior the number of arrows that have been applied to it since the last full reset? Because after a full wipe, all are revived, meaning the cumulative damage resets. So we could track a global damage counter that increments as arrows are applied, but damage is applied to different warriors at different times. Not trivial.

    Alternative: Use a balanced BST that stores alive warriors with their indices and remaining health. When we need to apply k arrows, we iterate over warriors starting from smallest index, and reduce health. We can skip many dead ones by removing them from the BST. In each minute, we may remove many warriors (up to n). However, the total number of removals over all minutes could be large (n * number of full wipes). But note that after a full wipe, all warriors are alive again. That means we have to reinsert all n warriors into the BST. If we do that after each full wipe, that would be O(n) per full wipe, leading to O(n q) worst-case. Not good.

    But maybe we can design a data structure that supports "reset to initial" in O(1) by using a global timestamp or versioning. For example, we can maintain an array cur[i] representing current remaining health, but also an array last_reset_time[i] and a global current_time, and we store modifications relative to some base. However, modifications are not just increments; they are assignments to zero or specific values. But perhaps we can model each warrior's state as: they start with a_i. Over time, they get damaged until they die, then after a full wipe they are reset. So each warrior experiences cycles: alive with some health, then possibly die, then reset only when all die. So between full wipes, each warrior can die at most once? Actually between full wipes, a warrior can die and stay dead (since they don't revive until all die). So each warrior can die only once per "phase" (between full wipes). At the moment of full wipe, all become alive again. So the number of deaths (i.e., transitions from alive to dead) per warrior per phase is at most 1. Since a full wipe ends the phase. In a phase, the number of deaths total is at most n (since each warrior can die at most once). After a full wipe, a new phase starts. The total number of deaths across all minutes is O(number of full wipes * n). In worst case, every minute could be a full wipe, leading to O(q * n) deaths. That's too many if we handle each death individually. But note that when a full wipe occurs, all n warriors die (or are already dead) and then revive. That counts as n deaths? Actually they all die (or maybe some were already dead). But we need to process the death events? In our simulation, when total_sum <= k, we realize that all remaining alive warriors die. That can be done in O(log n) by a range set to zero. Then we also need to revive them, which could be O(log n) if we can reset to original. So if we can reset in O(log n) as well, we avoid O(n) per full wipe.

    Thus the key challenge is to support resetting the whole array to original values quickly.

    Segment tree with lazy propagation that can assign a segment to a "base array" value: That is like having a function that maps each index to its original a_i. This is not a constant, but we can precompute for each node the sum of original values. Then we can have a lazy flag that says "set to original". When pushing this flag down, we need to set children to original as well. However, the children then need to know the original values for their segments. That's fine: each node stores the sum of original values for its segment (call it orig_sum). When we apply a "set_to_original" lazy tag, we set the node's sum to orig_sum and mark that all values in that segment are exactly the original values. Additionally, we may have to clear any other lazy tags (like set_to_zero). So we can have two types of assignments: set_to_zero and set_to_original. Since they are both assignments (overwrites). We can combine them into a single assignment lazy tag that can be either 0 (means set to zero) or 1 (means set to original). But for leaf nodes, set_to_original means set to a_i. So we need to know at leaf level the original value. That works.

    Thus we can implement a segment tree with lazy propagation where each node has:

    • sum: current sum of the segment.
    • lazy: an integer flag with possible values: -1 (no lazy), 0 (set entire segment to zero), 1 (set entire segment to original values). But is "set to original" valid for any segment? Yes, because we have the original array values for that segment; we can precompute for each node the sum of original values, and for leaves the original value. To apply lazy tag 1, we set node.sum = node.orig_sum, and set node.lazy = 1. For lazy tag 0, node.sum = 0, node.lazy = 0.

    However, we also need to support point updates (set a specific index to a new value) which may be neither zero nor original. So we need to be able to override the lazy assignment at a point. That is fine: when we do a point update, we go down to the leaf, pushing lazy tags along the way, then set leaf to the new value, and update ancestors accordingly. This will clear the lazy at that leaf (or override). So our segment tree supports three operations: range assign to zero, range assign to original, point assign to arbitrary value. All can be done with O(log n) per operation (range assign uses lazy propagation; point assign is like updating after push).

    But we must be careful: When we assign a range to original, we need to set it to the exact original values, not just the sum. For the internal nodes, setting sum to orig_sum is sufficient for queries. For correctness of further lazy operations or point updates, we only need to know that the children, if needed later, will be correctly set. So we propagate the lazy tag downwards when needed. So it's fine.

    Thus we can handle resetting all to original via a range assign to original over [1,n]. That's O(log n) with lazy propagation (just set root lazy to 1 and update sum). That's great!

    Now, we also need range assign to zero for a segment. That's also O(log n). And point update for the partially reduced warrior: O(log n).

    We also need to query total sum from start to n: range sum query (start, n). That's O(log n). Also need to find the first index pos such that cumulative sum from start is >= k. This can be done via a binary search on the segment tree: we can implement a function find_first( start, k ) that returns the smallest index idx >= start with prefix sum from start reaching k. Alternatively, we can use the segment tree's ability to find the first index where prefix sum (from 1) >= target, where target = sum(1..start-1) + k. Since sum(1..start-1) is zero (if start is first alive), but is it always zero? Actually after some minutes, indices < start are dead (zero). So sum(1..start-1) = 0. But what if we had a previous reset? start will be 1 after reset. So yes. However, we need to be careful: if we have some indices that are dead but not contiguous? Actually dead indices are always from the start up to some point? Because arrows always hit the first alive, which is the smallest index with rem>0. So when a warrior dies, it's always the current first alive; so after he dies, the next alive becomes the next index (which could have been previously dead? No, because all previous are dead, and the next index might have been dead earlier? Actually if an earlier warrior died, then the next warrior is the immediate next index. Since warriors die in order from left to right, the dead warriors form a prefix of the array. In other words, the set of alive warriors is always a suffix of the array. Let's reason: Initially all alive. Arrows hit the first alive, which is the leftmost alive. When that warrior dies, the next alive becomes the next index, which was alive before. So the alive indices are always contiguous from some index L to n. Because we never have a situation where a warrior in the middle dies while a warrior to its left remains alive; since arrows always hit the leftmost alive, we only ever kill the leftmost alive. So indeed, after any sequence of minutes (without a full wipe), the alive warriors form a contiguous suffix: [start, n]. This is a crucial property.

    Check: Could there be a scenario where a warrior not at the leftmost gets damaged but not killed, and later the leftmost dies, making that previously damaged warrior the new leftmost? Yes. But all alive are contiguous because we start with all alive (full suffix). When we kill the leftmost, we reduce the suffix by one from the left. So it remains a suffix. So the set of alive is always a suffix. This property simplifies the data structure. We can maintain start index (the first alive). And all indices < start have rem = 0, and indices >= start have rem >= 0 (maybe zero if they are dead? But if they are dead, then they would break contiguity. Actually if a warrior in the middle dies, then the suffix would be broken. But can a warrior in the middle die before the ones before it? No, because arrows only hit the first alive. So a warrior cannot die unless all warriors to its left are already dead. Therefore, the alive suffix is exactly from start to n, and all those warriors have rem > 0? Actually some could have rem = 0 if they died earlier. But since they die only when all left are dead, a warrior at index i cannot die until start reaches i. So once start passes i, i is dead. After that, start is > i, so i is not in the suffix. So within the suffix [start, n], all warriors are alive (rem > 0). Because if a warrior with index j >= start were dead, that would mean at some point, after start became <= j, the warrior died. But then start would become j+1, making j not part of the suffix. So while start <= j, the warrior at j is alive. So indeed, the suffix consists of all alive warriors; none are dead inside. So we can guarantee that for indices i from start to n, rem_i > 0 (unless start = n+1 meaning all dead, but then we reset). So this is a very nice property.

    Thus we have: The state is characterized by start (first alive index, 1 <= start <= n+1; start = n+1 means all dead). And for each i >= start, rem_i > 0 (their remaining health). Moreover, the values rem_i are less than or equal to original a_i, but they are not necessarily original; they have been reduced by arrows that partially damaged the first warrior(s) in previous minutes. However, note that only the first warrior (at start) might have been partially reduced; all others to its right are still at full original health? Let's verify: Arrows only ever hit the first alive warrior. So only the current first alive warrior takes damage. Once that warrior dies, the next warrior becomes first alive, and may have taken no damage previously (since arrows never hit it before). Actually wait, it's possible that in a minute, we partially damage the first warrior but not kill it, and then next minute we might have more arrows that again hit that same first warrior, possibly killing it, and then possibly continue to the next. So at any time, only the first warrior may have reduced health; all others (start+1..n) should still be at their original strengths. Is that true? Consider a minute where we have k arrows, we start at warrior start. If k is large enough to kill start and also partially damage start+1? But the arrows hit sequentially: after start dies, the next arrow hits start+1, and so on. So it is possible that in the same minute, we kill start and also partially damage start+1 (or even kill it). So after that minute, the first alive could be start+2 if both died, or start+1 if start died and start+1 survived with reduced health. So after a minute, it's possible that the new first alive (if any) has reduced health, and all others to its right are at full original health? Let's examine: In a minute, we start at start. We apply arrows. If we go through start, start+1, ... up to some index pos. The ones before pos (if pos > start) are all killed (set to 0). The warrior at pos is either killed (if sum exactly equals k) or survives with reduced health. So after this minute, the alive suffix is from new_start = pos (if alive) or pos+1 (if dead). And all warriors to the right of new_start have not been hit in this minute (since we stopped at pos). But could they have been hit in previous minutes? No, because in previous minutes, the first alive was start, which was left of them. Once start moves past an index, that index becomes part of the suffix, but it hasn't been hit yet because arrows never reached it before (since we only ever hit the first alive and those after it only when the first ones die within the same minute). Actually if start moves right due to deaths, then the new start is an index that previously was not the first alive. Could it have been hit in a previous minute? Only if in some earlier minute, when it was not the first alive, arrows reached it after killing all to its left. That could happen in a minute where we kill a whole prefix that includes it. For example, originally start=1. In minute 1, we have enough arrows to kill warriors 1,2,3 and partially damage 4. Then after minute 1, start becomes 4 (if 4 alive) or 5. So warrior 4 was hit and reduced. Warrior 5 and beyond are untouched. So indeed, the warrior at the new start may have been reduced (if it was partially damaged). What about warrior 5? It hasn't been hit. So after minute, all to the right of start are untouched and have full health. But what about warrior start+1? It's untouched? In the scenario where start died and start+1 partially damaged, then start+1 becomes the new start (if it survived). That warrior has reduced health. The ones beyond start+1 are untouched. So generally, after any minute, the suffix of alive warriors consists of: the first alive (index L) may have reduced health (less than original a_L), and all indices > L have full original health. Is that always true? Let's check if any warrior beyond L could have reduced health. For a warrior at index j > L to have reduced health, it must have been hit by arrows at some time when it was not the first alive. That could happen if in some earlier minute, we killed all warriors up to j-1 and then partially damaged j. At that time, after that minute, j became the first alive (if it survived) or died. So after that minute, j is either first alive (and reduced) or dead. If it survived as first alive, then later, in a subsequent minute, we might kill j (or partially damage it further). If we partially damage it further, it remains first alive with reduced health. So indeed, the first alive may have reduced health; others are untouched. However, is it possible that after a minute, the first alive is at index L, and some warrior at index M > L has reduced health from a previous minute when it was first alive, but then later the first alive moved left? But the first alive cannot move left: start only increases (or resets to 1 after full wipe). So if a warrior at index M was first alive at some point, then later start moved past M (i.e., M died), then M is dead, not alive. So if it is alive and not first, that means start is less than M, meaning there is some warrior to its left that is alive. But then M cannot have been first alive before, because that would imply start moved left? Actually suppose at time t, start = M (first alive is M). Then at a later time t' > t, start > M (M is dead). So M is dead. So if M is alive and not first, then start < M, but then M is not first; but M could be alive and have reduced health if it was previously first and then later start moved left? Not possible because start only increases; it cannot go from M to a smaller index. So M cannot be alive and not first if it was ever first, because once it's not first, that means there is a warrior left of it alive, which would require start to be smaller than M. But start only increases over time (unless reset). So the only way M could be alive and not first is if it was never first, meaning it never got hit. So it must have full health. Therefore, indeed, after any minute (without reset), the alive suffix has the property: The first warrior (at start) may have reduced health; all others have original full health.

    This is a key observation that greatly simplifies the problem. Many solutions for this known problem (CF round? maybe problem "Ivar and the arrows" or something) use this property. Let's confirm with examples.

    First example: n=5, a=[1,2,1,2,1] After minute1: k=3. Start=1. a1=1 dies after 1 arrow, left k=2. Then a2=2 takes 2 arrows -> dies exactly. So all dead? Actually total sum of alive before minute = 1+2+1+2+1 = 7 >3, so not all die. After minute: start? We killed 1 and 2, so first alive is 3 (a3=1). a3 not hit because k exhausted after a2? Wait we used 3 arrows: 1 on a1, 2 on a2. a3 untouched. So after minute, first alive is index 3, with full health (1). Indexes 4,5 full health. So indeed, first alive (3) has full health. But is that always? In this case, the first alive is index 3 which wasn't hit; so it's full. In scenario where we partially damage the first alive but not kill, then that first alive has reduced health. Others full.

    Now, after minute2: k=10. Start=3, a3=1, a4=2, a5=1. Sum=4 <10, so all die. Then reset: all revived to full health. So after minute2, all are full.

    After minute3: k=1. Start=1, a1=1 dies -> start=2, a2 full=2 but reduced? Actually only 1 arrow, so a2 not hit. So after minute3, first alive is index2, with full health 2. Others full. Output is 4 standing? Actually output line3: 4. After minute3, standing warriors: indices 2,3,4,5 => 4. Yes.

    After minute4: k=1. Start=2, a2=2, takes 1 arrow -> now a2 has 1 remaining, still alive. So first alive is still 2 with reduced health=1. Others full. Standing count=4. Yes.

    After minute5: k=1. Start=2, a2 now 1, takes arrow -> dies. Now start=3, a3=1, full. Standing count=3. Yes.

    So property holds.

    Second example: Let's test: n=4, a=[1,2,3,4]. Minute1 k=9. Start=1, a1=1 dies (k=8), a2=2 dies (k=6), a3=3 dies (k=3), a4=4 takes 3 -> remains 1. So first alive index4 with reduced health 1. Others dead. So after minute1, standing warriors =1 (just index4). Indeed property holds: first alive (4) reduced, others dead.

    Minute2 k=1. Start=4, a4=1 takes 1 -> dies. Then all dead? After that, start would be 5 (all dead). Since all die, reset: all revive full health. Output after minute2 =4. Yes.

    Minute3 k=10. Start=1, a1=1 die (k=9), a2=2 die (k=7), a3=3 die (k=4), a4=4 takes 4 -> dies? Actually a4 takes 4 arrows, so exactly dies (k=0). So all die, reset -> output 4. Property: all died, reset.

    Minute4 k=6. Start=1, a1=1 die (k=5), a2=2 die (k=3), a3=3 takes 3 -> dies? Actually a3 takes 3 arrows, exactly dies, k=0. So after minute, all dead? Actually a4 untouched? Wait we used arrows: a1 (1), a2 (2), a3 (3) total=6, so a4 not hit. But after minute, a1,a2,a3 dead, a4 alive full=4. So start=4, standing=1. Property holds.

    So indeed, the state can be represented by:

    • start: the index of the first alive (1-indexed). If start > n, then all dead, but that triggers reset so we never maintain state with all dead except possibly during minute before reset? But after minute, we output after reset, so state always has start <= n.
    • rem_start: the remaining health of the first alive warrior. For i > start, rem_i = a_i (original).

    Thus we only need to keep track of start and the reduced health of the warrior at start (if any). This drastically simplifies the problem.

    Let's formalize: At any moment (after processing a minute and any necessary reset), we have:

    • A pointer L (1 ≤ L ≤ n) indicating the first alive warrior.
    • The remaining health of warrior L is cur (1 ≤ cur ≤ a_L). For i > L, remaining health = a_i.

    All warriors i < L are dead (rem_i = 0).

    Now, we need to process a minute with k arrows. Starting from L, we will apply arrows. Since only L may have reduced health, but warriors L+1, L+2, ... have full health. So we can simulate the effect of k arrows on the suffix [L, n] efficiently using prefix sums of a_i.

    We can precompute prefix sums of the original a array: pre[i] = sum_{j=1}^{i} a_j.

    Now, the total health (remaining) of the alive suffix is: total = cur + sum_{j=L+1}^{n} a_j.

    But we can compute sum from L+1 to n as total_sum_n - pre[L]. But note that pre[L] includes a_L, but we need to consider that the actual remaining for L is cur, not a_L. So total remaining = cur + (pre[n] - pre[L]).

    Now, if k >= total, then all alive warriors will die. After that, all warriors are revived (reset). So the state after minute becomes: L = 1, cur = a_1 (full health). And we output n.

    If k < total, then not all die. We need to find the new L' and new cur'.

    How to find where we stop? Since beyond L, all warriors have full health, we can think of an array where we have cur at position L, then a_{L+1}, a_{L+2}, ... . We need to subtract k from this sequence from left to right.

    We can compute the cumulative health: start from cur, then add a_{L+1}, a_{L+2}, etc. We need to find the smallest index p (>= L) such that cumulative sum from L to p >= k.

    Let cumulative sum up to index i (i >= L) be: S(i) = cur + sum_{j=L+1}^{i} a_j.

    We want minimal p such that S(p) >= k.

    Then:

    • If S(p) == k, then warrior p dies, so new first alive is p+1 (if p+1 <= n) with cur' = a_{p+1} (full), and L' = p+1.
    • If S(p) > k, then warrior p survives with remaining cur' = a_p - (S(p) - k) if p>L? Actually more precisely: The amount of damage taken by warrior p is: d_p = k - (cumulative sum before p). Cumulative before p = S(p-1) (with S(L-1) defined as 0). So if we define sum_before = cur if p==L? Actually for p == L, sum_before = 0. So d_p = k - sum_before. Then remaining = a_p - d_p (if p > L, a_p is original; if p == L, remaining = cur - d_p). So cur' = (original value at p) - d_p. And new L' = p (since p is still alive). For indices < p, they are dead.

    Thus we can compute new state given L, cur, k, using prefix sums.

    We need to compute p efficiently. Since we have prefix sums of a_i, we can compute S(i) quickly: S(i) = cur + (pre[i] - pre[L]) because pre[i] includes a_L? Actually pre[i] = sum_{j=1}^{i} a_j. So sum_{j=L+1}^{i} a_j = pre[i] - pre[L]. So S(i) = cur + pre[i] - pre[L].

    But careful: if i = L, then pre[i] - pre[L] = pre[L] - pre[L] = 0, so S(L) = cur. That's correct.

    Now we need to find minimal p >= L such that cur + pre[p] - pre[L] >= k.

    Let target = k + pre[L] - cur? Actually rearr: cur + pre[p] - pre[L] >= k => pre[p] >= k + pre[L] - cur.

    Define needed = k + pre[L] - cur. Then we need the smallest p >= L such that pre[p] >= needed.

    Note: pre[p] is non-decreasing. So we can binary search on pre array to find the first index p where pre[p] >= needed. But we must ensure p >= L. Since pre is increasing, if we find p such that pre[p] >= needed, it will automatically be >= L? Not necessarily: if needed is very small, maybe pre[L-1] already >= needed? But since pre[L-1] <= pre[L] and we have condition that cur > 0 and k >= 1, needed = k + pre[L] - cur. Since cur <= a_L, so needed >= k + pre[L] - a_L. Could be less than pre[L]? For example, if cur = a_L, then needed = k + pre[L] - a_L = pre[L] + (k - a_L). If k is less than a_L, needed could be less than pre[L]. Actually if k < a_L, then needed < pre[L] + (a_L - a_L?) Let's compute: needed = k + pre[L] - cur. Since cur <= a_L, needed >= k + pre[L] - a_L. That could be less than pre[L] if k < a_L. So it's possible that pre[L-1] (which is pre[L] - a_L) might be >= needed? Actually pre[L-1] = pre[L] - a_L. So needed >= k + pre[L] - a_L = pre[L-1] + k. Since k >= 1, needed > pre[L-1]. So needed > pre[L-1] (strictly > because k >=1). So pre[L-1] < needed. So the smallest index with pre >= needed must be at least L. Because pre[L-1] < needed <= pre[L] possibly. So it's safe: p will be >= L. So we can just binary search over the entire pre array for needed, and p will be >= L automatically.

    Edge case: if cur is less than a_L (i.e., the first warrior already partially damaged), then needed = k + pre[L] - cur. Since cur < a_L, needed > k + pre[L] - a_L = pre[L-1] + k, still > pre[L-1]. So p >= L still holds. Good.

    Thus we can find p via binary search on pre (which is sorted). Since n up to 200k, binary search O(log n) per minute. That is fine.

    Now we also need to compute total remaining quickly: total = cur + (pre[n] - pre[L]). Compare with k.

    Thus the algorithm per minute:

    • Input k_i.
    • Let L = current first alive index (1 initially), cur = current health of warrior L (initially a_1).
    • Compute total_remaining = cur + (pre[n] - pre[L]).
    • If k >= total_remaining:
      • After minute, all warriors die and then revive. So set L = 1, cur = a_1. (State reset)
      • Output n.
    • Else:
      • Compute needed = k + pre[L] - cur.
      • Find p = lower_bound on pre array: smallest index such that pre[p] >= needed. (Since pre is strictly increasing? a_i >=1, so pre is strictly increasing.)
      • Now compute sum_before_p = cur + pre[p-1] - pre[L] (if p > L; if p == L, sum_before_p = 0? Actually easier: compute damage on p: d = k - (cur + pre[p-1] - pre[L])? But we can compute remaining for p: if p == L, remaining = cur - k (since k < cur? Actually if k < total and we are in else branch, but it's possible that k < cur? yes, if k < cur, then needed would be less than pre[L]? Let's derive needed. If k < cur, then needed = k + pre[L] - cur < pre[L], so p = L because pre[L] >= needed? Actually pre[L] = pre[L] exactly. Since needed < pre[L], the smallest p with pre[p] >= needed might be L? Wait if needed <= pre[L], then p could be L if pre[L-1] < needed. Since pre[L-1] < needed as argued, p = L. So p = L. Then damage on p = k (since sum_before = 0). So remaining = cur - k, which is >0 because k < cur. So new state: L remains L, cur' = cur - k.
      • In general: Let sum_before = cur + pre[p-1] - pre[L] (with the convention pre[L-1] = pre[L] - a_L, but for p == L, define pre[L-1] = pre[L] - a_L? Actually we can compute sum_before as total health of warriors from L to p-1. For p == L, sum_before = 0. So we can compute: if p == L: sum_before = 0 else: sum_before = cur + (pre[p-1] - pre[L]) // since sum_{L+1}^{p-1} a_j = pre[p-1] - pre[L] Then damage to warrior p = k - sum_before. remaining = (p == L ? cur : a_p) - damage. Since we know k < total, remaining > 0.
      • If remaining == 0? Actually if damage exactly equals health of p, then p dies. That would be the case when k == sum_before + health_of_p. In that case, remaining = 0. Then new L = p+1, and cur' = a_{p+1} (if p+1 <= n). But careful: if p+1 > n, then all die? But we already checked k < total, so not all die, so p+1 <= n. Because if p == n and remaining = 0, then total would be sum_before + a_n, which equals k, meaning k = total_remaining, but we are in else branch with k < total_remaining, so not possible. So if remaining = 0, then p < n, and L' = p+1 with cur' = a_{p+1}.
      • Else remaining > 0, then L' = p, cur' = remaining.
      • Output number of standing warriors = (n - L' + 1). Because all from L' to n are alive (since after p, all are alive and untouched, full health).
    • Repeat for each minute.

    We must be careful with indexing (1-indexed). Precompute prefix sums pre[0]=0, pre[i]=sum_{j=1}^{i} a_j.

    Now we need to maintain L and cur after each minute. Initialize L=1, cur=a_1.

    Check that the property that only first warrior may have reduced health holds after each minute in this algorithm. Indeed, after processing a minute where not all die, we either keep L unchanged (if p==L and k<cur) with reduced cur, or set L to p with reduced cur' (which is either cur' = cur - k when p==L, or cur' = a_p - (k - sum_before) when p>L). In the latter case, L becomes p, and all indices > p are untouched and have full health. So property holds.

    When all die, we reset to L=1, cur=a_1, which also satisfies property.

    Thus the entire state is just (L, cur). That's O(1) memory. Processing per minute: O(log n) for binary search on pre array (since we need to find p). Also O(1) for other operations. So total O(q log n), which is fine for 200k.

    But wait: we need to find p such that pre[p] >= needed. However, pre is static (original a_i). But note that after many minutes, the a_i values are unchanged; only cur for the first alive may be less than original. So pre array remains the same. That's fine.

    Now we need to compute sum_before accurately. For p > L, sum_before = cur + (pre[p-1] - pre[L]). Because cur is health of L, plus sum of a_j for j from L+1 to p-1 (which are full original). For p == L, sum_before = 0.

    Alternative approach: After we find p via needed, we can compute remaining directly using the equation:

    If pre[p] >= needed, then the amount that goes beyond needed is pre[p] - needed. But careful: needed = k + pre[L] - cur. So pre[p] - needed = pre[p] - pre[L] - k + cur = (pre[p] - pre[L] + cur) - k = S(p) - k. So remaining for warrior p is a_p - (pre[p] - needed) if p > L? Let's derive: S(p) = cur + pre[p] - pre[L]. The total arrows used up to the end of warrior p would be S(p). But we only have k arrows, so the overflow is S(p) - k. The warrior p receives its full health a_p (or cur if p==L) but then we subtract the overflow? Actually arrows are applied sequentially: first we apply to L, then L+1, ... up to p. The number of arrows that hit p is: if p == L, it's k (since we didn't exceed its health). If p > L, it's k - (health of L and L+1..p-1). That is k - (cur + sum_{L+1}^{p-1} a_j). So the remaining health of p is a_p - (k - sum_before). That equals a_p - (k - (cur + pre[p-1] - pre[L])) = a_p + cur + pre[p-1] - pre[L] - k = (cur + pre[p-1] - pre[L] + a_p) - k = (cur + pre[p] - pre[L]) - k = S(p) - k. So remaining = S(p) - k. That is a simpler formula: remaining = (cur + pre[p] - pre[L]) - k.

    But careful: If p == L, then pre[p] = pre[L], so remaining = (cur + pre[L] - pre[L]) - k = cur - k. That matches. So we can compute remaining = S(p) - k. Since we know S(p) >= k and S(p) - k > 0 if not exactly equal? Actually if S(p) == k, remaining = 0, warrior dies. So indeed remaining = S(p) - k.

    Thus after finding p, we can compute remaining = (cur + pre[p] - pre[L]) - k. Then:

    • If remaining > 0: new L = p, new cur = remaining.
    • If remaining == 0: new L = p+1, new cur = a_{p+1} (if p+1 <= n). But note that if p == n and remaining == 0, then we would have total_remaining = k, which is not in else branch. So p+1 <= n in this case.

    Now we also need to output number of standing warriors: n - L' + 1.

    But note: if L' becomes n+1 (i.e., all dead) after processing else? In else branch we ensured k < total_remaining, so not all die, so L' <= n. So safe.

    Now we also need to handle the case when L becomes n+1? That only happens if all die and we reset, so after reset L=1. So we never output n+1.

    Thus algorithm is clear.

    Let's test on examples.

    Example 1: n=5, a=[1,2,1,2,1]; pre: [1,3,4,6,7] (index1..5). pre[0]=0. Initialize L=1, cur=1.

    Minute1: k=3. total = cur + pre[5]-pre[1] = 1 + (7-1)=7? Actually pre[5]=7, pre[1]=1, diff=6, total=7. k=3 < total. needed = k + pre[L] - cur = 3 + pre[1] - 1 = 3+1-1=3. Find p: pre[1]=1<3; pre[2]=3>=3 => p=2. S(p) = cur + pre[2] - pre[1] = 1+3-1=3. remaining = 3 - 3 = 0 => warrior p dies. Thus new L = p+1 = 3; cur = a_3 = 1. Standing = n - L +1 = 5-3+1=3. Output 3. OK.

    Minute2: k=10. total = cur + pre[5]-pre[3] = 1 + (7-4)=4. Actually pre[3]=4; total=1+3=4? 7-4=3, plus cur1 =>4. k=10 >= total => all die and revive. So L=1, cur=a1=1. Output 5. OK.

    Minute3: k=1. total = cur + pre[5]-pre[1] = 1+6=7 >1. needed = 1 + pre[1] - 1 = 1+1-1=1 => p: pre[1]=1 >=1 => p=1. remaining = cur + pre[1]-pre[1] -1 = 1 - 1 =0? Actually S(1)=cur=1, remaining=0? Wait k=1, S(1)=1, remaining=0. That would mean warrior 1 dies. But according to example, after minute3, the first warrior dies, start becomes 2. So remaining=0, new L=2, cur=a2=2. Output = 5-2+1=4. That matches. But note: In our else branch, we had k < total? 1<7, yes. remaining=0 is allowed. That means the warrior died exactly. So we go to case remaining==0: L=p+1=2, cur=a2. OK.

    Minute4: k=1. L=2, cur=2. total = cur + pre[5]-pre[2] = 2 + (7-3)=6? Actually pre[2]=3, diff=4, total=6. k=1<6. needed = 1 + pre[2] - cur = 1+3-2=2. p: pre[1]=1<2; pre[2]=3>=2 => p=2. remaining = S(2)-k = (cur + pre[2]-pre[2])? Wait S(2) = cur + pre[2] - pre[2] = cur = 2. remaining = 2-1=1 >0. So new L=2, cur=1. Output = 5-2+1=4. OK.

    Minute5: k=1. L=2, cur=1. total = cur + pre[5]-pre[2] = 1+4=5? pre[5]-pre[2]=4, total=5. k=1<5. needed = 1 + pre[2] - cur = 1+3-1=3. p: pre[2]=3>=3 => p=2. remaining = S(2)-1 = cur -1 = 1-1=0 => new L=3, cur=a3=1. Output = 5-3+1=3. OK.

    Matches.

    Example2: n=4, a=[1,2,3,4]; pre: [1,3,6,10]. Init L=1, cur=1.

    Minute1: k=9. total = cur + pre[4]-pre[1] = 1 + (10-1)=10? Actually 10-1=9, total=10. k=9 <10. needed = 9 + pre[1] - cur = 9+1-1=9. Find p: pre[3]=6<9; pre[4]=10>=9 => p=4. S(4) = cur + pre[4]-pre[1] = 1+10-1=10. remaining = 10-9=1 >0 => new L=4, cur=1. Output = 4-4+1=1. OK.

    Minute2: k=1. total = cur + pre[4]-pre[4] = 1+0=1. k=1 >= total => all die and revive -> L=1,cur=1; output 4. OK.

    Minute3: k=10. total = cur + pre[4]-pre[1] = 1+9=10. k=10 >= total => all die & revive -> output 4. OK.

    Minute4: k=6. total = cur + pre[4]-pre[1] = 1+9=10 >6. needed = 6 + pre[1] - cur = 6+1-1=6. p: pre[3]=6 >=6 => p=3. S(3) = cur + pre[3]-pre[1] = 1+6-1=6. remaining = 6-6=0 => new L=4, cur=a4=4? Wait p=3, remaining=0 => L=4, cur = a4=4. But note: after minute4, we have a1,a2,a3 dead, a4 alive full=4. So output = 4-4+1=1. matches.

    Thus algorithm works.

    Now we must ensure correctness when cur is less than a_L (i.e., first warrior already damaged). Example: Suppose after some minutes we have L=2, cur=1 (as in example after minute4). That's already covered.

    Now consider scenario where k is very small, less than cur. Then p = L, remaining = cur - k >0, so L unchanged, cur reduced. That works.

    Now consider scenario where k is between cur and cur + a_{L+1}. Then p will be L+1, and remaining = (cur + a_{L+1}) - k, which is less than a_{L+1} but >0. Then new L = L+1, cur = that remaining. That is correct: the first warrior dies, second survives with reduced health.

    Now consider scenario where k exactly equals cur. Then p = L, remaining = 0 => L becomes L+1, cur = a_{L+1}. That is correct.

    Now consider scenario where k exactly equals cur + a_{L+1}. Then p = L+1, remaining = 0 => L becomes L+2, cur = a_{L+2}. That works.

    Now consider the reset condition: if k >= total, we reset to full health. That includes the case when k exactly equals total: all die, then reset. Our else condition uses k < total, so equality goes to reset branch. That's correct because if k == total, all die, then revive. So output n.

    Now one nuance: The problem statement says: "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." So if all die, they revive at the end of minute. So we correctly output n after such a minute. And we reset state to full.

    Now consider minute where some warriors die but not all; we output number of standing after minute. That's n - L' + 1.

    Thus algorithm seems correct.

    Complexity: O(q log n) due to binary search on pre array. Since pre is static and increasing, we can use std::lower_bound in C++ (or bisect in Python). That's fine. However, q up to 200k, n up to 200k, O(q log n) ~ 200k * 18 = 3.6M, fine.

    Now we need to be careful about integer sizes: a_i up to 1e9, n up to 200k, so pre[n] up to 2e14. k_i up to 1e14. So total sums up to maybe 2e14. Use 64-bit integers (long long in C++, int64). Python int is fine.

    Edge Cases:

    • n=1: single warrior. Then L always =1, cur maybe reduces. If k >= cur, then all die and revive => state becomes cur = a_1. So output 1 after that minute. Works.
    • Starting state: L=1, cur=a_1.
    • When L becomes n+1? Only if after processing else branch, p = n and remaining = 0? That would mean k = total_remaining, but we excluded that. So it won't happen. But if total_remaining is computed as cur + pre[n] - pre[L], and k < total_remaining, then if p = n and remaining = 0, that would imply k = cur + pre[n] - pre[L] = total_remaining, contradiction. So not possible. So L' always <= n.

    Now, we must be careful about the needed calculation: needed = k + pre[L] - cur. This could be large up to 1e14 + 2e14 = 3e14, but still within 64-bit (max ~9e18). So fine.

    Potential pitfalls: We need to ensure that binary search on pre returns index p that is within [L, n]. Our reasoning shows it will be at least L. But what if needed > pre[n]? That would mean k + pre[L] - cur > pre[n] => k > pre[n] - pre[L] + cur = total_remaining, which we already handled in the "all die" branch. So in else branch, needed <= pre[n]. So binary search will find p <= n.

    Thus we can implement.

    Now, is there any situation where cur becomes zero? In our state, cur > 0 always (since L is first alive). So cur > 0.

    Implementation steps:

    1. Read n, q.
    2. Read array a[1..n].
    3. Compute prefix sums pre[0]=0; for i in 1..n: pre[i] = pre[i-1] + a[i].
    4. Initialize L = 1, cur = a[1].
    5. For each minute i from 1 to q: read k. total = cur + (pre[n] - pre[L]) if k >= total: L = 1 cur = a[1] print(n) else: needed = k + pre[L] - cur // find smallest p such that pre[p] >= needed p = lower_bound(pre, needed) // careful: pre is 0-indexed? We'll use 0-based index for programming but we'll treat pre array with indices 0..n. pre[i] = sum up to i. But warriors indices from 1..n correspond to pre[1]..pre[n]. So we need to search over pre[1..n] perhaps. Since pre[0]=0, and needed > pre[L-1] >= 0, but we must ensure p is at least L. Using lower_bound on whole pre from 0..n, we might get p=0? But needed > pre[L-1] >= pre[0] maybe? For L=1, pre[0]=0, needed = k + pre[1] - cur. Since k>=1, needed > pre[0]. But could needed be 0? No. So lower_bound will give index at least 1. But for L>1, needed > pre[L-1] (as argued). So lower_bound will return index >= L. So we can safely search whole pre[0..n] and then ensure p>0. But pre[0] is 0; if needed <=0, but needed >0 always. So fine. // However, lower_bound returns iterator to first element >= needed. Since pre is non-decreasing (strictly increasing because a_i>=1), we can use standard binary search. // We'll get p as integer index in [1,n]. // Compute S = cur + pre[p] - pre[L] remaining = S - k if remaining == 0: L = p + 1 cur = a[L] // assuming L <= n, but if p+1 > n? Not possible as argued. else: L = p cur = remaining print(n - L + 1)

    But need to be careful: when remaining == 0 and p == n, then L = n+1 which is invalid. However, we argued that cannot happen because then k == total, but we are in else branch. So we can assert p < n. But to be safe, we can handle that case: if p == n and remaining == 0, then that means all died (k == total). Actually compute: total = cur + pre[n] - pre[L]. If p = n and remaining == 0, then S = total, so k = total. But we are in else branch where k < total, so it's impossible. So we can ignore.

    Now, we need to compute a[L] when we set cur = a[L] after reset or when L becomes p+1. That is fine. We need to keep a array accessible.

    Now, check the scenario after reset: L=1, cur=a[1]. That matches.

    Now, what about the case when after some minutes, L becomes such that L > n? That only occurs if all die and we reset before next minute. In our state, we never keep L > n; we reset immediately. So fine.

    Now, we need to be careful with the binary search: we must ensure we get the correct p. Since pre is increasing, we can use std::lower_bound on a vector of pre, but we need to search starting from index L maybe? Actually we can use lower_bound on the whole array because needed > pre[L-1], so result will be >= L. But we must be mindful that pre[0] = 0 and pre is of length n+1 if we include index 0. It's easier to create vector pre of size n+1: pre[0]=0, pre[i] for i=1..n. Then use lower_bound(pre.begin(), pre.end(), needed). Since needed might be exactly equal to some pre[i]. That will return iterator to that element. Then p = index = iterator - pre.begin(). Since pre[0] is 0, index may be 0 if needed==0, but needed>0, so index >=1. So p is the integer index. But careful: if needed equals pre[i], then p = i. That's correct.

    Now compute S = cur + pre[p] - pre[L]. Since we used pre[L] which corresponds to sum up to L. That works.

    Now compute remaining.

    Now output standing = n - L + 1.

    Now we must test some edge cases manually.

    Case n=2, a=[5,3]. L=1, cur=5. Minute1: k=4. total=5+3=8>4. needed = 4 + pre[1] - cur = 4+5-5=4. pre[0]=0, pre[1]=5, pre[2]=8. lower_bound for 4 returns pre[1]=5? Actually 5>=4, so p=1. S=cur+pre[1]-pre[1]=5, remaining=5-4=1>0 -> L=1, cur=1. standing=2. (Warrior1 takes 4 arrows, left with 1; warrior2 untouched) Minute2: k=2. total=1+3=4>2. needed = 2 + pre[1] - cur = 2+5-1=6. pre[1]=5<6, pre[2]=8>=6 -> p=2. S = cur+pre[2]-pre[1] =1+8-5=4, remaining=4-2=2>0 -> L=2, cur=2? Actually cur = remaining=2, but note that a_2=3, remaining=2, so it's fine. standing=1 (only warrior2 alive). Good. Minute3: k=5. total = cur + pre[2]-pre[2] =2+0=2 <5 => all die and revive. L=1,cur=5, standing=2. Output 2. Works.

    Now scenario where k is huge but less than total: okay.

    Now consider scenario where L is not 1 and cur is less than a_L. Example: L=3, cur=2, a_3=5 originally? Actually cur must be <= a_L. Suppose a=[10,10,10,10], after some hits: L=2, cur=3? Actually if L=2, cur could be 3 (reduced from 10). That's fine.

    Now minute with k=20. total = 3 + (pre[4]-pre[2]) = 3 + (40-20)=23. pre[2]=20, pre[4]=40. k=20 <23. needed = 20 + pre[2] - cur = 20+20-3=37. lower_bound for 37: pre[3]=30<37, pre[4]=40>=37 => p=4. S = cur+pre[4]-pre[2] =3+40-20=23. remaining=23-20=3>0 -> L=4, cur=3. standing=1. That means we killed warriors 2 and 3 (since p=4), and warrior 4 left with 3 health. Indeed: warrior2 had 3 (dies after 3 arrows), left k=17; warrior3 has 10, dies after 10, left k=7; warrior4 has 10, takes 7 -> left 3. Works.

    Now check needed calculation: pre[2]=20, cur=3, so needed=20+20-3=37. pre[4]=40 meets. Good.

    Now scenario where needed equals pre[p] exactly, then remaining = S(p)-k = (cur+pre[p]-pre[L]) - k. Since needed = k+pre[L]-cur, we have pre[p] = needed, so cur+pre[p]-pre[L] = cur + (k+pre[L]-cur) - pre[L] = k. So remaining = 0. So p dies. That matches.

    Now scenario where needed less than pre[p] but > pre[p-1], then remaining = (cur+pre[p]-pre[L]) - k > 0. So warrior p survives.

    Thus algorithm works.

    Now we need to ensure that when we compute needed, we do not cause overflow. Use long long.

    Now we consider scenario where k is zero? But problem states k_i >= 1, so not.

    Now we need to output after each minute the number of standing warriors. So we will compute and print.

    Now we should also consider if there is any scenario where the "first warrior may have reduced health" property could be broken due to multiple minutes where we don't reset and we partially damage first warrior, then later we get another minute that partially damages it further, still fine. If we kill it and move to next, we may have that next warrior may have been partially damaged previously? No, because it was never hit before, so it has full health. However, what if we had a minute where we partially damaged the first warrior, then in the next minute we kill it and also partially damage the second. After that minute, the first alive becomes the second warrior (now partially damaged). That matches property: only first alive has reduced health. So property is invariant.

    Thus we can safely maintain only (L, cur).

    Now we can implement.

    But wait: what about the scenario where after a minute, the first alive becomes index L' and its remaining is computed as remaining = S(p) - k. But is it possible that remaining > a_{L'}? For L' = p, original health is a_p. Since we subtract damage from a_p (or cur if p==L), the result should be <= a_p. Let's verify: damage = k - sum_before. sum_before includes health of previous warriors fully (they died) and possibly part of previous? Actually sum_before is total health of warriors before p (L to p-1) that were fully consumed? Not exactly fully: if p > L, the warriors from L to p-1 are fully killed, so sum_before = cur + sum_{L+1}^{p-1} a_j. So damage to p is k - sum_before, which is less than a_p (since k < total). So remaining = a_p - (k - sum_before). Since k - sum_before < a_p, remaining > 0. Also remaining could be equal a_p? If k - sum_before = 0, then remaining = a_p, but then p would not be the first index where cumulative sum >= k? Actually if k - sum_before = 0, then k = sum_before, which means p is actually the first index where cumulative sum >= k? But if k exactly equals sum_before, then pre[p-1] maybe already >= needed? Let's analyze: if k = sum_before, then needed = k + pre[L] - cur = sum_before + pre[L] - cur. But sum_before = cur + pre[p-1] - pre[L]. So needed = (cur + pre[p-1] - pre[L]) + pre[L] - cur = pre[p-1]. So needed = pre[p-1]. Then lower_bound(needed) could return p-1 if pre[p-1] exactly equals needed. In that case, p would be p-1, not p. So the binary search would yield p-1, not p. So we will not have a case where p > L and damage=0. So remaining is always <= a_p. Good.

    Now, is there any risk of floating or negative? No.

    Thus we have a simple solution.

    Now we should confirm the initial assumption that alive warriors form a contiguous suffix. Let's prove: Initially all alive: suffix [1,n]. When we apply arrows, we always hit the first alive, which is the leftmost in the suffix. Damage reduces its health; if it dies, we remove it from the suffix (i.e., the suffix start moves right). If it doesn't die, the suffix remains the same but first warrior's health reduced. No operation introduces a gap because we never skip a warrior: the arrows hit the first alive, and if it dies, we go to the next, which was already in the suffix. So the alive set remains a suffix. So yes.

    Thus solution is correct.

    Now we should consider if there is any tricky part about "after all warriors fall and all the currently flying arrows fly by" meaning that if all die, the remaining arrows are wasted and then revive. That's exactly our reset.

    Now we need to confirm that the condition for reset is exactly when k >= total_remaining. However, what if k is exactly equal to total_remaining? Then all die. We do reset. That's correct.

    Now, the number of standing warriors after minute is always n - L + 1, because all from L to n are alive. That includes the case after reset where L=1 => n.

    Now we also need to ensure that after resetting, we set cur = a_1. That's fine.

    Now, we should test with a more complex example, maybe random to ensure no off-by-one.

    Let's write a small simulation to compare with naive for small n,q. But as reasoning is strong, it's okay.

    Now edge case: n=200000, q=200000, all a_i=1, k_i=1 each minute. Then each minute kills one warrior (the first) and moves start. After n minutes, all die? Actually after first minute: L=2; after 2nd: L=3; ... after n-th: L=n+1? But wait after n-th minute, we would have L = n+1? But we must check: after minute n, we have k=1, total remaining = 1 (since only last warrior with health 1). Since k=1 == total, we go to reset branch, all die and revive, so after minute n, state becomes L=1, cur=1, output n. So our algorithm will handle that. Let's simulate:

    Initially L=1, cur=1.

    Minute1: k=1, total= 1 + (n-1)*1? Actually pre[n]=n, pre[1]=1, total = 1 + (n-1) = n. k=1 < n, needed = 1 + pre[1] - cur = 1+1-1=1 => p=1, S=cur=1, remaining=0 => L=2, cur=a2=1. Output n-2+1 = n-1.

    Minute2: L=2, cur=1, total = 1 + (n-2) = n-1, k=1 < total, needed = 1+pre[2]-cur = 1+2-1=2? pre[2]=2, needed=2, p=2, S=cur=1? Actually S = cur + pre[2]-pre[2] =1, remaining=0? Wait compute needed: k=1, pre[L]=pre[2]=2, cur=1 => needed=1+2-1=2. pre[2]=2, so p=2. S = cur + pre[2]-pre[2] =1, remaining = 1-1=0 => L=3, cur=1. Output n-2? Actually n-3+1 = n-2. etc.

    Continue until minute (n-1): L=n-1, cur=1, total = 1 + (n-(n-1))? Actually pre[n]=n, pre[L]=pre[n-1]=n-1, so total = 1 + (n - (n-1)) = 2? Wait n - pre[n-1] = n - (n-1) = 1, total = cur + 1 = 2. k=1 <2. needed = 1 + pre[n-1] - cur = 1 + (n-1) - 1 = n-1? Actually that's large. Let's compute properly: n=5 for simplicity: a=[1,1,1,1,1]. Minute1: L=1 cur=1 total=5? Actually total=1+ (5-1)=5. k=1 -> L=2. Minute2: L=2 cur=1 total=4 -> L=3. Minute3: L=3 cur=1 total=3 -> L=4. Minute4: L=4 cur=1 total=2 -> L=5? Actually check: k=1, total=2, needed = 1+pre[4]-cur =1+4-1=4, p? pre[4]=4, so p=4, S = cur+pre[4]-pre[4]=1, remaining=0 -> L=5, cur=a5=1. Output n -5+1=1. Minute5: L=5 cur=1 total=1? pre[5]=5, pre[5]=5, total=cur+0=1. k=1 >= total -> reset -> L=1 cur=1 output 5. So after minute n (5), output 5. That matches.

    Now test minute4 output 1, which is correct: only last warrior standing? Actually after minute4, warrior5 is alive, so 1 standing. Yes.

    Now consider minute where k is very large but less than total: works.

    Now consider scenario where cur is not a_L but smaller; we already tested.

    Thus solution seems correct.

    Now we need to implement:

    Pseudo-code:

    int n, q; vector a(n+1); // 1-indexed vector pre(n+1); pre[0] = 0; for i=1..n: cin >> a[i]; pre[i] = pre[i-1] + a[i];

    long long L = 1, cur = a[1];

    for each minute: long long k; cin >> k; long long total = cur + (pre[n] - pre[L]); if (k >= total) { L = 1; cur = a[1]; cout << n << "\n"; } else { long long needed = k + pre[L] - cur; // binary search in pre array (indices 1..n) for first >= needed // using lower_bound on pre.begin()+1? Actually pre from index 0..n, but we want index in 1..n. // Use lower_bound(pre.begin(), pre.end(), needed) and get index. // Since pre[0]=0, needed >0, it will return index >=1. int p = lower_bound(pre.begin(), pre.end(), needed) - pre.begin(); // p is between 1 and n inclusive. long long S = cur + pre[p] - pre[L]; long long rem = S - k; if (rem == 0) { L = p + 1; cur = a[L]; // L <= n guaranteed. } else { L = p; cur = rem; } cout << n - L + 1 << "\n"; }

    But need to ensure when rem == 0 and p == n, L becomes n+1, but then we would be in else branch erroneously? Actually as argued, not possible. But just to be safe, we could handle that case: if p == n and rem == 0, then set L=1, cur=a[1] and output n? But that would imply all died, but we are in else branch so k < total, contradiction. However due to integer overflow or something maybe? Not. So we can add an assert or ignore.

    But we should also verify that a[L] is defined when L = p+1; we need to check that p+1 <= n. Since we are in else, total > k, and if p = n, then total = cur + pre[n] - pre[L]. If p=n and rem=0, then S = total, so k = total, contradiction. So p cannot be n when rem=0. So safe.

    Now we need to ensure that we use proper data types: long long.

    Now consider the case where needed equals exactly pre[p] and p = L? Then p = L, rem = S - k = (cur + pre[L] - pre[L]) - k = cur - k. If needed = pre[L], then k + pre[L] - cur = pre[L] => k = cur. So rem = 0. So that case falls into rem == 0, L = p+1 = L+1, cur = a[L+1]. That is correct: warrior L dies exactly.

    Now we also need to consider what if needed > pre[n]? That would be k >= total case, so handled earlier.

    Now we also need to consider scenario where after reset, we set L=1, cur=a[1]. This matches.

    Now one more nuance: In the problem, when all warriors die, they revive at the end of the minute. So after reset, we output n. That's correct.

    Now we should double-check with a case where k is large enough to kill all but not exactly equal total? Actually if k > total, then also all die. So reset.

    Now check with n=1, a=[5]. L=1, cur=5. Minute1: k=3. total=5, k<5. needed = 3 + pre[1] - cur = 3+5-5=3. pre[0]=0, pre[1]=5. lower_bound for 3 returns index1 (since 5>=3). p=1. S=5, rem=5-3=2>0 -> L=1, cur=2. Output 1. Minute2: k=10. total=2, k>=2 -> reset -> L=1,cur=5, output 1. That's correct.

    Now consider when k is huge enough to kill all multiple times? But reset only once.

    Now confirm that we correctly compute total_remaining for L=some value. That is cur + (pre[n] - pre[L]). Since pre[n] - pre[L] = sum_{i=L+1}^{n} a_i.

    Now, we should also handle the scenario when L becomes n+1? Only if we ever set L = n+1 after a minute where not all die? That can't happen. But suppose n=1, after minute we have L=1, cur=5; if k=5, then total=5, k>=total -> reset, so we don't set L to 2. So fine.

    Now one more nuance: In the else branch, after computing p and rem, we set L = p (if rem>0) or p+1 (if rem=0). But we must also ensure that when we set L = p+1, the new cur is a[L] (full health). However, what if a[L] is zero? Not possible because a_i >=1. So fine.

    Now we also need to ensure that we handle the case where after setting L = p+1, L could be n+1? As argued, that would mean p=n and rem=0. But then k = total, contradiction. So not possible.

    Thus algorithm is sound.

    Now we can implement in C++ or Python. Since constraints are moderate, Python with bisect should be fine. But careful: q up to 200k, Python O(q log n) is fine; but we need to be careful with input speed (use sys.stdin.read). Also Python's int is arbitrary precision, okay.

    However, we need to note that prefix sums can be up to 2e14, which fits in Python int.

    Now let's write Python code:

    def solve(): import sys, bisect data = sys.stdin.buffer.read().split() it = iter(data) n = int(next(it)) q = int(next(it)) a = [0](n+1) pre = [0](n+1) for i in range(1, n+1): a[i] = int(next(it)) pre[i] = pre[i-1] + a[i] L = 1 cur = a[1] out = [] for _ in range(q): k = int(next(it)) total = cur + (pre[n] - pre[L]) if k >= total: L = 1 cur = a[1] out.append(str(n)) else: needed = k + pre[L] - cur # binary search in pre[1..n] (pre is sorted) # use bisect_left on pre (including index 0, but that's fine) p = bisect.bisect_left(pre, needed, 0, n+1) # range [0, n+1) # p is the index where we would insert needed to keep sorted. # pre[p] is >= needed. Since needed > pre[L-1], p >= L. S = cur + pre[p] - pre[L] rem = S - k if rem == 0: L = p + 1 cur = a[L] else: L = p cur = rem out.append(str(n - L + 1)) sys.stdout.write("\n".join(out))

    But we must be careful: When we do p = bisect_left(pre, needed, 0, n+1), pre is list of length n+1 (indices 0..n). This returns an index between 0 and n (inclusive). If needed > pre[n], then p would be n+1? Actually bisect_left on a list of length n+1 returns an index in [0, n+1]. If needed > pre[n], it returns n+1. But we are in else branch where needed <= pre[n] (since k < total), so p <= n. Also needed > 0, so p >= 1. Good.

    Now we need to compute S using pre[p]. That's fine.

    Now check the case when p = n+1? Should not happen. But if due to some bug, we should handle. However, not needed.

    Now after setting L = p+1, we use a[L]. But if p = n, then L = n+1, a[L] is out of range. But we argued it's impossible. But to be safe, we could add an if statement: if p == n and rem == 0: then it's actually a total wipe, so we should reset. But we already have the else condition ensuring k < total. So it won't happen. However, due to potential off-by-one in needed or total, maybe it could? Let's double-check with numbers. Suppose L= n, cur = a_n (full). Then total = cur + (pre[n] - pre[n]) = cur. If k < cur, else branch. needed = k + pre[n] - cur = pre[n] + k - cur. Since cur = a_n, pre[n] = pre[n-1] + a_n. So needed = pre[n-1] + a_n + k - a_n = pre[n-1] + k. Since k < cur = a_n, needed < pre[n-1] + a_n = pre[n]. Also needed > pre[n-1] because k>0. So p = n because pre[n] is the first >= needed. Then S = cur + pre[n] - pre[n] = cur. rem = cur - k > 0. So rem !=0. So L becomes p = n, cur = rem. So no reset.

    If k == cur? Then total == cur, k == total, then we would go to k>=total branch and reset. So else not taken.

    Thus p = n and rem == 0 cannot happen.

    Thus safe.

    Now we should test with random small n and q with brute force to verify.

    But given the reasoning, I'm confident.

    Now we need to output after each minute. That's done.

    Now one more nuance: In the problem, they might have multiple test cases? The statement doesn't indicate multiple test cases. So single.

    Now check constraints: q up to 200000, k_i up to 1e14, pre[n] up to 2e14. The sum needed = k + pre[L] - cur could be up to ~1e14 + 2e14 = 3e14, still within Python int.

    Now performance: For each minute, we do a bisect (binary search) O(log n) = about 18 steps, plus constant. 200k * 18 = 3.6M operations, fine in Python.

    But we must be careful about using bisect on a list of length 200001, that's fine.

    Now we should also consider the possibility of using our own binary search to avoid function call overhead? Probably not needed.

    Now we must be careful about reading input fast due to large input size. Using sys.stdin.buffer.read and splitting is fine.

    Now let's test with given examples.

    Example1: Input: 5 5 1 2 1 2 1 3 10 1 1 1

    Our code should produce: 3 5 4 4 3

    Yes.

    Example2: 4 4 1 2 3 4 9 1 10 6

    Our output: 1 4 4 1

    Matches.

    Now consider edge case: n=1, q=2, a=[5], k=[5,5]. After minute1: k=5 >= total(5) => reset => output 1. After minute2: same => output 1. Actually naive: warrior dies and revives each minute, so always 1 standing. That's correct.

    Now consider n=3, a=[2,5,3], we can test manually.

    Let's simulate step by step with our algorithm.

    Initial L=1 cur=2.

    Minute1: k=4. total = 2 + (sum a2+a3=5+3=8) = 10 >4. needed = 4 + pre[1] - cur = 4+2-2=4. pre[1]=2<4; pre[2]=2+5=7>=4 -> p=2. S = cur + pre[2] - pre[1] = 2+7-2=7. rem = 7-4=3 >0 => L=2, cur=3. standing = 3-2+1=2 (warriors 2 and 3). Warrior2 now has 3 health (originally 5). Warrior3 untouched (3). That seems correct: arrows: 2 on warrior1 kills it (takes 2, left k=2), then warrior2 takes 2 arrows, left 3 health. So alive: 2,3 => 2.

    Minute2: k=10. total = cur + (pre[3]-pre[2]) = 3 + (10-7)=6? Actually pre[3]=2+5+3=10, pre[2]=7, diff=3, total=6. k=10>=6 => reset: L=1,cur=2, output 3.

    Minute3: k=1. total=2+8=10 >1. needed=1+pre[1]-cur=1+2-2=1 -> p=1 (pre[1]=2>=1). S=cur=2, rem=2-1=1>0 -> L=1,cur=1, standing=3. (warrior1 now health1, others full) Good.

    Now, check with naive: after minute3, warrior1 gets 1 arrow, health drops to 1, alive 3.

    Works.

    Thus algorithm is solid.

    Now we should consider if there is any tricky part regarding the definition of "after all Ivar's warriors fall and all the currently flying arrows fly by". Our reset condition matches that. Also note that if all die, the arrows left over are wasted. So we don't need to consider them further. So resetting is correct.

    Now we also need to output after each minute the number of standing warriors. So we output n - L + 1.

    Now check that we properly handle the case where after a minute, L becomes such that some warriors are dead but not all; output count is correct.

    Now we must confirm that the property that only the first warrior can have reduced health holds even after reset. Yes, after reset all have full health, so first warrior is full too. So invariant holds.

    Now complexity: O((n+q) log n) but n for prefix sum, q for processing.

    Now we can implement.

    But wait: There is a subtle case: What if cur becomes 0? That would mean L is not actually alive. But we maintain cur > 0. In our updates, when remaining > 0, cur is positive. When remaining == 0, we move L to next and set cur to a[next] which is >=1. So cur is always positive. Good.

    Now, we should also consider when L = n and cur = a_n (full). Then after a minute where k < cur, we reduce cur, still L=n. That's fine.

    Now, when L = n and cur < a_n. Then total = cur. If k >= cur, we reset (since total <= k). That includes k == cur case: all die (only warrior n) and revive.

    Thus fine.

    Now, let's also consider scenario where k is very large but less than total: we need to compute needed which may exceed pre[n]? Not, because we are in else branch. So fine.

    Now, we also need to consider that pre[L] might be large, but needed computed as k + pre[L] - cur. Since cur <= a_L, pre[L] - cur >= pre[L] - a_L = pre[L-1] (if L>1) else pre[0]=0. So needed >= k + pre[L-1] > pre[L-1]. So p >= L.

    Now, we need to ensure that we use pre[L] correctly: pre[L] includes a_L. That's fine.

    Now, we can finalize.

    Potential pitfalls: Using bisect_left on pre list including pre[0]=0. But what if needed equals exactly pre[L-1]? Could that happen? needed = k + pre[L] - cur. Since k >=1, and pre[L] - cur >= pre[L-1] (since cur <= a_L, pre[L] - cur >= pre[L] - a_L = pre[L-1]), so needed >= pre[L-1] + 1. So needed > pre[L-1]. So needed cannot equal pre[L-1]. So p cannot be L-1. Good.

    Now, what about needed equals pre[L]? That happens when k = cur. Then p = L, rem = cur - k = 0 => L becomes L+1. That's correct.

    Now, what about needed equals pre[L] + something? Then p could be L if needed <= pre[L]? Actually needed > pre[L]? If k > cur, then needed = k + pre[L] - cur > pre[L] + (k - cur) > pre[L]. So needed > pre[L] so p > L. So p will be > L. So all cases covered.

    Now, one more nuance: The pre array is strictly increasing because a_i >=1. So bisect_left works.

    Now we need to ensure that we use Python's built-in bisect on list of ints, which is fast.

    Now, we might consider using a while loop with pointer to avoid binary search? Possibly we can maintain a pointer to the cumulative sums? But binary search is simpler.

    Now let's think about memory: a and pre arrays of size n+1, each storing 64-bit ints (Python int objects), that's okay for 200k.

    Now, consider the situation where k is extremely large, but we handle it.

    Now, final code.

    But wait, we need to be careful: The warriors are placed in a line, and the first warrior leads the attack. In our model, we always start from the first alive (L). That's correct.

    Now, I think this is correct.

    But we should also double-check the condition for reset: "if all warriors die in minute t, they will all be standing to fight at the end of minute t." So at the end, they are standing. So after minute, we output number standing = n. So resetting state to L=1,cur=a1 is correct.

    Now, potential tricky: In the else branch, we compute p and new L. But we must also consider that if after update, L becomes > n? As argued no. So fine.

    Now we are ready.

    Now, note that the problem might be known as "Ivar's warriors" from Codeforces (perhaps problem 1100E or something). The solution described in many editorials is indeed to maintain a pointer and use binary search on prefix sums. So I'm confident.

    Now, let's produce final answer.

    But before final, let's test with random small n and q with naive simulation to be absolutely sure. We'll write a small test in mind.

    We'll do n=3, a = [3,1,2].

    Initial: [3,1,2] alive.

    Simulate minutes manually and compare with algorithm.

    Case minute1: k=2. Our: L=1,cur=3,total=3+1+2=6>2. needed=2+pre[1]-cur=2+3-3=2 -> p=1? pre[1]=3>=2 so p=1, S=3, rem=1>0 => L=1,cur=1. standing=3? n -1+1=3. So after minute1, we have warrior1 health1, others full. Naive: 2 arrows hit warrior1: health 3->1, still alive. So 3 standing. Good.

    Minute2: k=5. total = cur + (pre[3]-pre[1]) = 1 + (6-3)=4? Actually pre[3]=6, pre[1]=3, diff=3, total=4. k=5 >=4 => reset -> L=1,cur=3, standing=3. Naive: arrows: warrior1 (health1) dies after 1 arrow, left k=4; warrior2 health1 dies after 1 arrow, left k=3; warrior3 health2 dies after 2 arrows, left k=1 (wasted). All die, then revive. So standing=3. Good.

    Minute3: k=1. total = 3+ (6-3)=6 >1. needed=1+3-3=1 -> p=1, S=3, rem=2>0 => L=1,cur=2, standing=3. Naive: warrior1 takes 1 arrow -> health 2. standing=3. Good.

    Minute4: k=2. total = 2 + (6-3)=5 >2. needed=2+3-2=3 -> p? pre[1]=3>=3 so p=1. S=2, rem=0? Actually S = cur + pre[1] - pre[1] = cur = 2. rem = 2-2=0 => L=2, cur=a2=1, standing = 3-2+1=2. Naive: warrior1 health2 dies after 2 arrows exactly; warrior2 untouched (health1). So standing: warrior2 and warrior3 => 2. Good.

    Minute5: k=3. total = cur + (pre[3]-pre[2]) = 1 + (6-4)=3? pre[2]=3+1=4, pre[3]=6, diff=2, total=3. k=3 >= total => reset -> L=1,cur=3, standing=3. Naive: warrior2 health1 dies after 1 arrow, left 2 arrows; warrior3 health2 dies after 2 arrows, exactly. All die, revive. So standing 3. Good.

    Works.

    Now, test scenario where L moves and cur is reduced from previous warrior.

    All good.

    Now, consider scenario where a_i can be 1e9, n=200k, pre[n] ~ 2e14. k up to 1e14. The needed may be up to pre[L] + k - cur, up to pre[n] + 1e14 ≈ 3e14. That's fine.

    Now, we must also consider that Python's bisect on list of ints may be slower than manual binary search? But 200k * log2(200k) ≈ 200k * 18 = 3.6M, which is fine. However, Python's bisect is implemented in C, so it's fast. So okay.

    Now, finalize code.

    But there is one more nuance: In the else branch, we compute p using bisect_left on the whole pre array. But pre array includes pre[0]=0. For needed that might be less than pre[1]? But needed = k + pre[L] - cur. Since k >=1, and pre[L] - cur >= pre[L-1] (if L>1) else 0, needed > pre[L-1] >= 0. For L=1, needed = k + pre[1] - cur. Since pre[1]=a1, cur = a1 (since initially cur=a1, but after some reductions cur could be less than a1). So needed = k + a1 - cur. Since k >=1, needed >= 1 + a1 - cur. Since cur <= a1, needed >=1. So needed >=1. pre[0]=0, pre[1] >=1? a1>=1, so pre[1]>=1. So needed may be less than pre[1] if k + a1 - cur < a1 => k < cur. For example, L=1, cur=5, k=3, needed=3+5-5=3, pre[1]=5, so needed < pre[1]. Then bisect_left on pre would return index 1 because pre[1]=5 >=3, pre[0]=0 <3. That's correct: p=1. So it's fine.

    Now, for L>1, pre[L-1] might be less than needed but pre[L] could be greater or equal. So p will be at least L.

    Now, ensure we compute pre[L] correctly: L is integer. Use pre[L] as prefix sum up to index L.

    Now, in code, we must be careful when L is updated after reset: L=1, cur=a[1]. That's fine.

    Now, also need to consider that after we set L = p+1, we need to access a[L]. However, if L becomes n+1? Not possible, but we can add a check: if L > n: then reset? but we already argued. So skip.

    Now, we also need to ensure that after reset, we don't need to recompute something else. No.

    Now, let's write final solution.

    I'll produce Python solution.

    Potential improvements: Use sys.stdin.buffer.read to read all and map to ints.

    Now, produce final answer.

    But wait, is there any scenario where we need to consider that after resetting, the first warrior's health is a_1, but what if a_1 is not the maximum? It's fine.

    Now, finalize.

    One more check: In the else branch, we compute p using bisect_left(pre, needed). But what if needed is exactly pre[p] and p = L-1? That would imply needed = pre[L-1]. But we argued needed > pre[L-1] strictly. Let's verify: needed = k + pre[L] - cur. Since k >=1, and pre[L] - cur >= pre[L-1]? Actually pre[L] - cur >= pre[L] - a_L = pre[L-1]. But equality could hold if cur = a_L and? Wait: pre[L] - cur could be equal to pre[L-1] if cur = a_L? Because pre[L] - a_L = pre[L-1]. So if cur = a_L, then pre[L] - cur = pre[L-1]. So needed = k + pre[L-1]. Since k>=1, needed >= pre[L-1] + 1 > pre[L-1]. So needed > pre[L-1]. So indeed needed is strictly greater than pre[L-1]. So p cannot be L-1. Good.

    Now, also if L=1, pre[L-1]=pre[0]=0, needed >= 1 >0, so p>=1.

    Thus binary search is safe.

    Now, we might also consider using a while loop with pointer and cumulative sums but binary search is fine.

    Now, let's produce the final answer.

    But before final, think about potential alternative scenarios: what if the arrows are shot and the first warrior is already dead? But we maintain L as first alive, so not.

    Now, also note that the problem says "after each minute you should tell Ivar what is the number of his standing warriors." So we output after each minute.

    Now, we should also consider the possibility that the battle lasts for q minutes; after the last minute, we still output.

    Now, final code.

    But I'm thinking: Could there be a scenario where k_i is extremely large, causing needed to be beyond pre[n] but we already handled in if condition. However, what if due to numeric error we compute total incorrectly? No.

    Now, I think it's done.

    Now, we can also implement in C++ for speed, but Python is fine.

    One more nuance: In Python, using bisect on list of length n+1, each call is O(log n). But we are doing it q times. That's okay.

    Now, edge case: n=200000, q=200000, all a_i = 10^9, all k_i = 10^14. Then total remaining is huge (2e14). For each minute, we might have k >= total? Let's compute total = a_1 + sum_{2..n} a_i = n * 1e9 = 2e14. If k_i = 1e14, then k < total for many? Actually if n=200k, total=2e14, k=1e14 < total, so else branch. needed = k + pre[L] - cur. Since cur <= a_L=1e9, pre[L] is about L1e9. So needed is roughly L1e9 + 1e14. Binary search will find p approximately. This is fine.

    Now, memory and time okay.

    Now, final answer: I'll produce a clear explanation and code.

    But we must include explanation of reasoning in solution? The problem statement asks for output only, but we need to write code.

    Now, let's produce final answer in Python.

    One more thing: In the else branch, we compute p = bisect_left(pre, needed, 0, n+1). But bisect_left returns insertion point; if needed is greater than all, it returns n+1. But we are in else, needed <= pre[n] so p <= n. So we can just use bisect_left(pre, needed). Since pre is list length n+1, it returns between 0 and n+1. So we should check p == n+1? but not needed.

    Now, compute S = cur + pre[p] - pre[L]. This is safe as p <= n.

    Now, set L = p+1 if rem==0, but p+1 could be n+1? As argued, not.

    Now, let's double-check the case where L becomes n+1 due to p=n and rem=0. Let's try to artificially produce: n=2, a=[2,2], L=1, cur=2. total=4. Suppose k=3? k < total (3<4). needed = 3+2-2=3. pre[1]=2, pre[2]=4. lower_bound for 3 returns index 2 (since pre[2]=4 >=3). p=2. S= cur + pre[2]-pre[1] = 2+4-2=4. rem=4-3=1 >0 => L=2, cur=1. So not rem=0.

    If k=4, then k >= total, reset.

    If k=2? needed=2+2-2=2 -> p=1? pre[1]=2>=2, p=1. S=2, rem=0 => L=2, cur=a2=2. That's L=2, not n+1.

    If k= something that kills both? That's k=4, reset.

    Thus never L=n+1 in else.

    Now, final code.

    Potential bug: When we set L = p+1 and then cur = a[L], we need to ensure L <= n. As argued, safe. But maybe we could add an assertion: if L > n: then set L=1, cur=a[1] and output n (reset). But not needed.

    Now, we can also compute standing as n - L + 1, which is correct.

    Now, finalize.

    But wait, there is another subtlety: In the else branch, we used needed = k + pre[L] - cur. However, cur may be less than a_L. But is pre[L] - cur always non-negative? Yes, because pre[L] includes a_L, and cur <= a_L, so pre[L] - cur >= pre[L] - a_L = pre[L-1] >=0. So needed is at least k.

    Now, the binary search yields p. But what if p is less than L? We argued it cannot, but maybe due to off-by-one in pre indexing? Let's test: L=2, cur could be less than a_2. Suppose a=[1,100,1], L=2, cur=50. Then pre[1]=1, pre[2]=101, pre[3]=102. total = 50 + (102-101)=51. If k=30, needed = 30 + pre[2] - cur = 30+101-50=81. lower_bound on pre: pre[1]=1<81, pre[2]=101>=81 -> p=2, which is L. Good.

    If k=80, needed = 80+101-50=131, pre[2]=101<131, pre[3]=102<131? Actually 102<131, so needed > pre[3]=102. That would be >= total? total = 51? Wait total = 50 + (pre[3]-pre[2])=50+1=51, but k=80 > total, so it would go to reset branch, not else. So else not.

    So p never < L.

    Thus safe.

    Now, we should also consider that after many minutes, L may be large, and pre[L] may be near pre[n]. The binary search still works.

    Now, complexity: O(q log n). Good.

    Now, final answer code.

    Now, provide explanation in final message: will include reasoning and code.

    Now, write final answer. ```python import sys import bisect

    def solve() -> None: data = sys.stdin.buffer.read().split() it = iter(data) n = int(next(it)) q = int(next(it))

    a = [0] * (n + 1)          # 1‑based
    pre = [0] * (n + 1)        # prefix sums of original strengths
    for i in range(1, n + 1):
        a[i] = int(next(it))
        pre[i] = pre[i - 1] + a[i]
    
    L = 1            # first alive warrior
    cur = a[1]       # his current remaining health
    out = []
    
    for _ in range(q):
        k = int(next(it))
    
        # total remaining health of all alive warriors
        total = cur + (pre[n] - pre[L])
    
        if k >= total:
            # all die, then revive
            L = 1
            cur = a[1]
            out.append(str(n))
        else:
            # find the warrior where the cumulative health reaches k
            need = k + pre[L] - cur
            # need is guaranteed to be <= pre[n] and > pre[L-1]
            p = bisect.bisect_left(pre, need, 0, n + 1)   # returns index in [1, n]
    
            S = cur + pre[p] - pre[L]    # total health from L to p
            rem = S - k                  # remaining health of warrior p
    
            if rem == 0:
                L = p + 1
                cur = a[L]               # full health
            else:
                L = p
                cur = rem
    
            out.append(str(n - L + 1))
    
    sys.stdout.write("\n".join(out))
    

    if name == "main": solve()