#include using namespace std; using lint = long long; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template void ndarray(vector &vec, int len) { vec.resize(len); } template void ndarray(vector &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); } template void ndfill(V &x, const T &val) { x = val; } template void ndfill(vector &vec, const T &val) { for (auto &v : vec) ndfill(v, val); } template bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; } template bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } template pair operator+(const pair &l, const pair &r) { return make_pair(l.first + r.first, l.second + r.second); } template pair operator-(const pair &l, const pair &r) { return make_pair(l.first - r.first, l.second - r.second); } template vector srtunq(vector vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template istream &operator>>(istream &is, vector &vec) { for (auto &v : vec) is >> v; return is; } template ostream &operator<<(ostream &os, const vector &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; // Binary lifting / `Doubling` // Complexity: O(NlogN) precalculation / O(logN) per query // struct BinaryLifting { int N, INVALID, lgD; std::vector> mat; BinaryLifting() : N(0), lgD(0) {} BinaryLifting(const std::vector &vec_nxt, int INVALID = -1, int lgd = 0) : N(vec_nxt.size()), INVALID(INVALID), lgD(lgd) { while ((1LL << lgD) < N) lgD++; mat.assign(lgD, std::vector(N, INVALID)); mat[0] = vec_nxt; for (int i = 0; i < N; i++) if (mat[0][i] < 0 or mat[0][i] >= N) mat[0][i] = INVALID; for (int d = 0; d < lgD - 1; d++) { for (int i = 0; i < N; i++) if (mat[d][i] != INVALID) mat[d + 1][i] = mat[d][mat[d][i]]; } } int kth_next(int now, long long k) { if (k >= (1LL << lgD)) exit(8); for (int d = 0; k and now != INVALID; d++, k >>= 1) if (k & 1) now = mat[d][now]; return now; } // Distance from l to [r, \infty) // Requirement: mat[0][i] > i for all i (monotone increasing) int distance(int l, int r) { if (l >= r) return 0; int ret = 0; for (int d = lgD - 1; d >= 0; d--) { if (mat[d][l] < r and mat[d][l] != INVALID) ret += 1 << d, l = mat[d][l]; } if (mat[0][l] == INVALID or mat[0][l] >= r) return ret + 1; else return -1; // Unable to reach } }; int main() { int N; cin >> N; vector A(N); cin >> A; int D = 40; vector> nxt(D, vector(N)); vector> d(D, vector(N)); REP(i, nxt[0].size()) { nxt[0][i] = (i + A[i % N]) % N; d[0][i] = A[i % N]; } FOR(j, 1, D) { REP(i, N) nxt[j][i] = nxt[j - 1][nxt[j - 1][i]]; REP(i, N) d[j][i] = d[j - 1][i] + d[j - 1][nxt[j - 1][i]]; } int Q; cin >> Q; while (Q--) { lint k; cin >> k; int now = 0; lint ret = 0; REP(j, D) { if ((k >> j) & 1) { ret += d[j][now]; now = nxt[j][now]; } } cout << ret << '\n'; } }