P4828 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$ 取模。

对于$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$