题目描述

给定正整数 $p,b$，构造一张 $p$ 行无限列的数字表格，第 $i$ 行第 $j$列的数字为 $\frac{i}{p}$在$b$进制下的小数点后的第 $j$位。现在取出该表格的第 $k$列，设为 $a_1,...,a_p$，再给定 $b$个整数 $w_0,...,w_{b-1}$ 。接下来有 $q$ 次操作：

1 l r ：询问序列 $w_{a_l},..,w_{a_r}$的最大非空子段和；

2 x y ：把 $a_x$修改为$y$ 。

输入格式

第一行：四个整数 $p,b,k,q$。

第二行：$b$ 个整数，表示 $w_0,...,w_{b-1}$。

接下来 $q$行：每行表示一个操作

输出格式

对于每个询问，输出一行一个整数表示答案。

样例

13 10 3 8
1 10 -6 7 -9 -8 -5 8 3 4
1 2 5
2 7 3
2 7 6
1 1 7
2 6 1
1 1 13
2 2 5
1 2 10

16
17
17
10

17 13 10 10
1 10 -6 7 -9 -8 -5 8 3 4 -17 -16 12
2 17 7
2 10 11
1 4 13
2 14 12
1 1 17
2 16 0
1 5 13
1 6 7
2 14 10
1 10 12

12
34
12
8
-6

大样例

数据范围

$2\le p\le 10^9,2\le b\le 2\times 10^4,1\le k\le 10^9,1\le q\le 2\times 10^5$