Repeated Alien Sum Arrays

Given an array A of length n, we define its alien sum array B = F(A) as another array of length n such that:

Similarly, the second alien sum array is defined as F(F(A)), the third as F(F(F(A))) and so on.

You are given q queries. For each query, you are given an integer k and an index x. You need to output the value of the x-th element of the k-th alien sum array of A, taken modulo $$998244353$$.

Note: For k = 0, the alien sum array is just the original array A.

inputFormat

The first line contains two integers n and q, denoting the number of elements in the array and the number of queries respectively.

The second line contains n integers, representing the array A.

Then q lines follow, each containing two integers k and x, where k indicates the number of times the alien sum operation is applied and x (1-indexed) is the position you need to output.

outputFormat

For each query, output the value of the x-th element of the k-th alien sum array of A modulo $$998244353$$.

sample

3 3
1 2 3
0 1
1 2
2 3

1
4
9