第一行包含两个正整数 n,qn,qn,q，表示序列里数的个数和操作的个数。
接下来一行，包含 nnn 个非负整数 a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an。
输出共一行，包含 nnn 个整数，表示每个数的答案
5 5 1 5 2 3 4
3152671 3796875 3692207 3623487 3515626
对于所有的测试数据，保证序列中数的大小不超过 10910^9109，即 ai≤109，并且每个数是 000 到 10910^9109 之间的随机整数。n≤400, q≤400n \leq 400, \ q \leq 400n≤400, q≤400。