You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

数组累加

题目描述

小明有一个由 $n$ 个数构成的数组 $a$ 和另一个数组 $b$，他会进行很多次操作，每次操作会按顺序执行以下两步：

1、对所有 $1\le i\le n$，令 $b_i=a_{(i\ mod \ n +1)}$

2、对所有 $1\le i\le n$，令 $a_i=a_i+b_i$

小明会向你进行 $Q$ 次询问，每次问第 $x$ 次操作后的 $a_y$ 是多少。由于答案可能很大，请将输出对 $998244353$ 取模。

输入格式

第一行一个整数 $n$，表示数组的长度。

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

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

接下来 $Q$ 行，每行两个整数 $x,y$，表示问第 $x$ 次操作后的 $a_y$ 是多少。

输出格式

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

样例 #1

样例输入 #1

3
1 2 3
2
1 2
2 2

样例输出 #1

5
9

提示

数据范围

对于$30 \%$的数据，$1 \leq n,x,Q \leq 100$

对于 $50\%$ 的数据，$1\leq n \leq 10^5$，$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$