Problem Description

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?

Input Format

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 Format

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

5
1 2 3 4 5
2
1 2
2 2

5
12

Hint

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