题目背景

小 G 在打 Phigros 收 GOODTEK 的过程中，发现平板没电了，抄起 良锤 开始砸平板……十分气愤，出了这道简单题。

题目描述

对于一个 $N$ 个物量的谱面，第 $i$ 个 Note 获得 Perfect 的概率为 $P_i$ 。

接下来，小 G 会开始打歌，但是由于手感的变化以及环境的影响， $P_i$ 也会相应的做出改变。

然而，小 G 又因为使用了良锤，导致砸掉了一些 Note ，也就是说只剩下了一部分要打的 Note 。

可是作为一把良锤，它只砸掉了一部分，并且留下了第 $s, (s + k), (s + 2k), \cdots , (s + xk)$ 个 Note ，其中 $s + (x + 1)k > N$ 。

收歌的定义为获得全部 Perfect 的好成绩（当然要除去被砸掉的部分）。

接下来，小 G 会打 $Q$ 次该谱面，每次打前，小 G 想知道收歌的概率是多少。

输入格式

第一行，一个整数 $N$ 。

第二行，共 $N$ 个整数，表示 $P_i \mod 998244353$ 。

第三行，一个整数 $Q$ 。

接下来 $Q$ 行，每行五个整数 $l, r, p, s, k$ ，表示 $[l, r]$ 区间内的 Note 的 Perfect 概率乘上 $p$ ，并且对于 $s, k$ 进行一次询问。

输出格式

共 $Q$ 行，每行一个整数，表示概率在 $\mod 998244353$ 意义下的答案。

6
1 1 748683265 598946612 1 748683265
10
2 5 166374059 3 6
1 4 598946612 1 2
2 4 1 1 1
3 6 166374059 3 6
2 3 0 2 3
2 6 499122177 1 5
1 5 499122177 6 6
4 5 332748118 5 5
5 6 332748118 1 1
2 2 332748118 3 5

291154603
328034186
268324123
641926577
0
927535378
644699478
404381393
0
0

10
813863002 699374024 318583239 711171373 242232285 325187500 540381033 923606592 661729992 752037743
10
1 10 383012730 6 10
4 5 13323606 1 3
1 5 623610194 2 8
1 4 903839842 7 9
9 10 494020793 6 8
4 10 331681763 5 5
2 6 746546353 2 9
6 9 64101767 3 3
8 10 786866701 1 2
4 10 342269377 2 2

220087588
32408947
670619558
962595218
220087588
399043671
119042016
446732356
147550140
185472576

附加样例

goodtek3.in
goodtek3.out
goodtek4.in
goodtek4.out
goodtek5.in
goodtek5.out
goodtek6.in
goodtek6.out
goodtek7.in
goodtek7.out
goodtek8.in
goodtek8.out
goodtek9.in
goodtek9.out
goodtek10.in
goodtek10.out
goodtek11.in
goodtek11.out

说明/提示

【样例说明】

【数据范围】

每个测试点分数等分。

对于所有数据，

$1\leq N, Q\leq 10^5, 0\leq P_i, p < 998244353$

$1\leq l\leq r\leq N, 1\leq s\leq k\leq N$

请注意特殊的数据范围。