Problem Statement

$10^{100}$ potatoes are coming from a conveyor belt one by one. The weights of the potatoes are described by a sequence $W=(W_0,…,W_{(N−1)})$ of length $N$: the weight of the $i-th$ potato coming is $W_{(i−1)\bmod N}$ where $(i−1)\bmod N$ denotes the remainder when $i−1$ is divided by $N$.

Takahashi will prepare an empty box and then pack the potatoes in order, as follows.
Pack the incoming potato into the box. If the total weight of the potatoes in the box is now X or greater, seal that box and prepare a new empty box.

You are given $Q$ queries. In the $i$-th query $(1≤i≤Q)$, given a positive integer $K_i$, find the number of potatoes in the $K_i$-th box to be sealed. It can be proved that, under the Constraints of the problem, there will be at least $K_i$ sealed boxes.

Constraints

$1≤N,Q≤2×10^5$
$1≤X≤10^9$
$1≤Wi≤10^9(0≤i≤N−1)$
$1≤K_i≤10^{12} (1≤i≤Q)$
All values in input are integers.

$滑动窗口+循环节，暴力求循环节会超时$
$用装入箱子的第一个土豆表示每种装法，当从同一个土豆开始装时，箱子里的数量总是一样$
$优化1:当x>sum=w_0+w_1+…+w_{n-1}时，可以将每种装法先加上x/sum*n$
$并将x\%=sum，再求循环节$
$优化2:可以用滑动窗口求出每种装法可以装多少个土豆，求循环节时就不用从第一个土豆开始枚举$
$到最后一个求出一节，而是一节一节地求$

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;

const int N = 2e5 + 10, INF = 1e8;
const int mod = 998244353;

int n, q, x;
int w[N * 2];
ll sum;
int cnt[N];

int main()
{
    scanf("%d%d%d", &n, &q, &x);
    for (int i = 0; i < n; i ++ ) 
    {
        scanf("%d", &w[i]);
        w[i + n] = w[i];
        sum += w[i];
    }

    for (int i = 0; i < n; i ++ ) cnt[i] = (x / sum) * n;
    x %= sum;
    for (int i = 0, j = 0, s = 0; i < n; i ++ )
    {
        if (j < i)
        {
            j = i;
            s = 0;
        }
        while (s < x)
        {
            s += w[j];
            j ++ ;
        }
        cnt[i] += j - i;
        s -= w[i];
    }

    vector<int> order(n, -1), path;
    int loop = -1;
    for (int u = 0, k = 0; ; k ++ )
    {
        if (order[u] != -1)
        {
            loop = k - order[u];
            break;
        }
        order[u] = k;
        path.push_back(u);
        u = (u + cnt[u]) % n;
    }

    int non_loop = path.size() - loop;
    while (q -- )
    {
        ll k;
        scanf("%lld", &k);
        k -- ;
        if (k < non_loop) printf("%d\n", cnt[path[k]]);
        else 
        {
            k = (k - non_loop) % loop;
            printf("%d\n", cnt[path[non_loop + k]]);
        }
    }

    return 0;
}