P4828 Nagisa loves Tomoya

Cute Furukawa Nagisa gets a sequence. She defines one operation as changing all $a_i$ to $a_i + a_{(i\ mod\ n + 1)}$. Then she will ask you $Q$ queries. Each query gives $x, y$, meaning: after the $x$-th operation, what is the value of the element at position $y$. This problem is too easy, and our Nagisa solved it effortlessly. Can you solve it too?

An integer $n$, representing the length of the sequence. The next line contains $n$ integers, representing this sequence. The next line contains an integer $Q$, representing the number of queries. The next $Q$ lines each contain two integers $x, y$, with the meaning as described in the statement.

Output $Q$ lines. Each line contains one integer, the answer to the query. Please output the result modulo $998244353$.

For $30\%$ of the testdata, it holds that: $1 \leq n \leq 100$ $1 \leq x \leq 100$ $1 \leq Q \leq 100$ For $50\%$ of the testdata: $1 \leq n \leq 100000$ $1 \leq x \leq 500$ $1 \leq Q \leq 100$ For $100\%$ of the testdata, it holds that: $1 \leq n \leq 10^6$ $1 \leq a_i \leq 10^9$ $1 \leq x \leq 2000$ $1 \leq Q \leq 10^4$ Translated by ChatGPT 5