Description

可爱的古河渚得到了一个序列。她定义一次操作为 将所有的 $a_i$ 变为 $a_i+a_{(i\ mod \ n+1)}$ 然后她会向你进行 $Q$ 次询问，每次问你 $x,y$ ,意义为在第 $x$ 次操作后位置 $y$ 的元素是多少。

这个问题太简单了，我们的 Nagisa 轻易地就解决了这个问题。请问您能解决这个问题吗？

Input Format

一个整数 $n$，表示序列的长度。

接下来一行 $n$ 个整数，表示这个序列。

接下来一行一个整数 $Q$，表示询问次数

接下来 $Q$ 行，每行两个整数 $x,y$，意义如题所示。

Output Format

共 $Q$ 行，每行一个整数表示询问的答案，请注意对 $998244353$ 取模。

5
1 2 3 4 5
2
1 2
2 2

5
12

Hint

对于$30 \%$的数据，满足： $1 \leq n \leq 100$

$1 \leq x \leq 100$

$1 \leq Q \leq 100$

对于 $50\%$ 的数据：

$1\leq n \leq 100000$

$1 \leq x \leq 500$

$1 \leq Q \leq 100$

对于 $100 \%$ 的数据，满足

$1 \leq n \leq 10^6$

$1 \leq a_i \leq 10^9$

$1 \leq x \leq 2000$

$1 \leq Q \leq 10^4$