#LQ1586. 异位和

异位和

问题描述

给定一个数组 AA,我们称 AA 的异位和数组为另一个等长的数组 B=F(A)B=F(A),满足

Bi=jiAjB_i=∑_{j≠i}A_j

类似地,其二次异位和数组为 F(F(A))F(F(A)) ,三次异位和数组为 F(F(F(A)))F(F(F(A))),以此类推。

给定若干次询问,每次问 AAkik_i 次异位和数组的第 xix_i 个元素的值是多少。输出答案对 998244353998244353 取模后的结果。

输入格式

输入的第一行包含一个整数 nn

第二行包含 nn 个整数 A1,A2,,AnA_1,A_2,⋯ ,A_n,相邻整数之间使用一个空格分隔。

第三行包含一个整数 QQ 表示询问次数。

接下来 QQ 行,每行包含两个整数 ki,xik_i,x_i​ 表示一组询问,用一个空格分隔。

输出格式

输出 QQ 行,每行包含一个整数,依次表示每个询问的答案。

5
1 2 3 4 5
4
1 1
2 5
7 3
999 4
14
50
49152
781284616

评测用例规模与约定

对于 60%60\% 的评测用例,1n,Q,ki50001≤n,Q,k_i≤5000

对于所有评测用例,1n,Q1051≤n,Q≤10^51Ai,ki1091≤A_i,k_i≤10^91xin1≤x_i≤n