Statement

晨意微寒秋渐深 侧伴无事俏佳人

梦里不觉秋已深 余情岂是为他人

校园祭后和纱果真需要补考期末，然而和纱怎么做得出来？尤其是数学，对她来说如同 天书一般，数学老师自然知道这一点，于是象征性的给了道题，做出这个她就算及格了，允 许他人帮助。可和纱一看傻眼了，连题都看不懂，只好拿回家让春希帮忙，然而春希虽为学 霸，确也难做出来，也只能通过人脉找到你来解决。

给你一个长度为 $n$ 的序列 $a_i$，以及三个整数 $A,B,f(1)$。

定义 $f(0) = 0,f(i) = Af(i - 1) + Bf(i - 2)(i > 1)$。

记 $g(S) = \sum_{T\subseteq S}f(\sum_{x\in T} x)^k$，存在 $q$ 次操作，每次可以为其中一种：

$1\ i\ x$ 表示将 $a_i$ 设为 $x$。

$2\ l\ r$ 表示询问 $\sum_{i=l}^r\sum_{j=i}^rg(\{a_i,a_{i+1},\cdots,a_j \})$，对 $998244353$ 取模的结果。

Input Format

第一行输入六个整数 $A,B,f(1),k,n,q$，意义见题目描述。

第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

接下来的 $q$ 行，每行两个整数，表示一次操作。

Output Format

对于第二种询问，每行输出一个整数，表示结果。

Sample 1 Input

1 1 1 2 5 3
1 2 3 4 5
2 1 2
1 2 3
2 1 2

Sample 1 Output

8
19

Sample 2 Input

114 514 1919 10 8 10
427492 452090 412626 412129 413263 460507 419562 449515
2 1 3
2 2 4
1 4 409543
1 3 481980
1 8 462784
2 2 8
1 3 418489
2 6 7
1 8 417561
2 1 4

Sample 2 Output

155666360
294520134
768468575
462632291
195617086

Sample 3&4

大样例

Constraints & Hints

对于 $100\%$ 的数据，$0\le A,B,f_1,a_i,x<998244353,1\le n,q\le 3\times 10^5,1\le k\le 10$。

$\text{subtask1 (5pts)}:f_1 = 0$。

$\text{subtask2 (10pts)}$：$1\le n,q\le 20,0\le a_i,x\le 5\times 10^5$。

$\text{subtask3 (10pts)}$：$k = 2,1\le n,q\le 100$。

$\text{subtask4 (15pts)}$：$k = 2,1\le n,q\le 10^3$。

$\text{subtask5 (20pts)}$：$k = 2,1\le n,q\le 10^5$。

$\text{subtask6 (20pts)}$：$k = 2,1\le n,q\le 3\times 10^5$。

$\text{subtask7 (20pts)}$：无特殊限制。