函数求值

有两个长度均为 $n$ 的权值序列 $a,b$，常数 $p,k$，以及两个函数： $$g(x) = \sum_{i=1}^x p^i \times a_i$$ $$f(x) = \sum_{i=1}^x g(i) ^ k \times b_i$$ 有 $m$ 个操作，操作有以下三种： * $1\ x\ y$，表示将 $a_x$ 修改为 $y$。 * $2\ x\ y$，表示将 $b_x$ 修改为 $y$。 * $3\ x$，表示查询 $f(x)$ 对 $10 ^ 9 + 7$ 取模的值。

第一行四个整数，$n,m,p,k$。 第二行 $n$ 个整数，表示序列 $a$。 第三行 $n$ 个整数，表示序列 $b$。 接下来 $m$ 行，每行描述一个操作。

对于每个 $3\ x$ 操作，输出答案。

10 10 1 1
0 1 8 8 5 6 6 8 0 1 
9 2 8 8 6 2 5 0 1 8 
3 9
1 2 3
3 10
3 5
2 10 0
3 10
1 5 9
2 9 7
3 9
3 4

610
1034
390
674
1018
246

10 10 873892251 2
393158301 365328187 234823508 38818450 963771276 826653462 358628534 626503513 239326879 647251399 
1 1 1 1 1 1 1 1 1 1 
1 6 861625956
1 2 300158647
1 2 84103073
3 8
1 1 942644245
1 9 883742604
1 2 974963615
3 5
1 8 710319943
3 1

35415628
483475596
154061492

10 10 480345252 3
494173949 364489100 93066339 249297520 207335443 117096873 864460454 113006173 214332928 582507765 
5658914 222040024 221653308 296560771 594076100 151232714 410372721 23331041 374481229 184401699 
3 6
3 8
1 1 931776921
1 6 44943479
1 6 946828878
1 4 9046748
3 3
1 7 692410213
1 10 483672045
3 10

214010503
321766325
894782746
274293582

**【样例解释】** 这是样例一操作四后的结果： | $/$ | $1$ | $2$ | $3$ | $4$ | $5$ | | :-: | :-: | :-: | :-: | :-: | :-: | | $a_i$ | $0$ | $3$ | $8$ | $8$ | $5$ | | $b_i$ | $9$ | $2$ | $8$ | $8$ | $6$ | | $g(i)$ | $0$ | $3$ | $11$ | $19$ | $24$ | | $f(i)$ | $0$ | $6$ | $94$ | $246$ | $390$ | ---------------------- **【数据范围】** - 对于 $100\%%$ 的数据： $1 \le n,m \le 2 \times 10 ^ 5$。 $0 \le a_i,b_i,p \le 10 ^ 9 + 6$。 $1 \le x \le n$，$0 \le y \le 10 ^ 9 + 6$。 $1 \le k \le 3$。 - **详细的数据范围：** 测试点编号 | $n,m \le$ | $k$ | 特殊性质 :-: | :-: | :-: | :-: $1$ | $300$ | $\le 3$ | 无 $2$ | $300$ | $\le 3$ | 无 $3$ | $3 \times 10 ^ 3$ | $\le 3$ | 无 $4$ | $3 \times 10 ^ 3$ | $\le 3$ | 无 $5$ | $7 \times 10 ^ 4$ | $= 1$ | A $6$ | $7 \times 10 ^ 4$ | $= 1$ | A $7$ | $7 \times 10 ^ 4$ | $= 1$ | A $8$ | $7 \times 10 ^ 4$ | $= 2$ | A $9$ | $7 \times 10 ^ 4$ | $= 3$ | A $10$ | $7 \times 10 ^ 4$ | $= 1$ | B $11$ | $7 \times 10 ^ 4$ | $= 1$ | B $12$ | $7 \times 10 ^ 4$ | $= 2$ | B $13$ | $7 \times 10 ^ 4$ | $= 3$ | B $14$ | $7 \times 10 ^ 4$ | $= 3$ | B $15$ | $7 \times 10 ^ 4$ | $= 1$ | 无 $16$ | $7 \times 10 ^ 4$ | $= 2$ | 无 $17$ | $7 \times 10 ^ 4$ | $= 3$ | 无 $18$ | $2 \times 10 ^ 5$ | $= 1$ | 无 $19$ | $2 \times 10 ^ 5$ | $= 2$ | 无 $20$ | $2 \times 10 ^ 5$ | $= 3$ | 无 A：任意时刻所有 $b_i = 1$。 B：无操作二。 --------------------- **【提示】** 样例二满足A类性质，样例三满足B类性质。