Nagisa loves Tomoya
题目描述
可爱的古河渚得到了一个序列。她定义一次操作为 将所有的 $a_i$ 变为 $a_i+a_{(i\ mod \ n+1)}$
然后她会向你进行 $Q$ 次询问,每次问你 $x,y$ ,意义为在第 $x$ 次操作后位置 $y $ 的元素是多少。
这个问题太简单了,我们的 Nagisa 轻易地就解决了这个问题。请问您能解决这个问题吗?
输入输出格式
输入格式
一个整数 $n$,表示序列的长度。
接下来一行 $n$ 个整数,表示这个序列。
接下来一行一个整数 $Q$,表示询问次数
接下来 $Q$ 行,每行两个整数 $x,y$,意义如题所示。
输出格式
共 $Q$ 行,每行一个整数表示询问的答案,请注意对 $998244353$ 取模。
输入输出样例
输入样例 #1
5
1 2 3 4 5
2
1 2
2 2
输出样例 #1
5
12
说明
对于$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$