Problem Description

There are two weight sequences \(a\) and \(b\), each of length \(n\), constants \(p\) and \(k\), and two functions:

\[ g(x) = \sum_{i=1}^x p^i \times a_i \]

\[ f(x) = \sum_{i=1}^x g(i)^k \times b_i \]

There are \(m\) operations, which can be one of the following three types:

1. \(1 \ x \ y\), which means to modify \(a_x\) to \(y\).
2. \(2 \ x \ y\), which means to modify \(b_x\) to \(y\).
3. \(3 \ x\), which means to query the value of \(f(x)\) modulo \(10^9 + 7\).

Input Format

The first line contains four integers \(n\), \(m\), \(p\), and \(k\).

The second line contains \(n\) integers representing the sequence \(a\).

The third line contains \(n\) integers representing the sequence \(b\).

The next \(m\) lines each describe an operation.

Output Format

For each \(3 \ x\) operation, output the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

610
1034
390
674
1018
246

Input Sample #2

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

Output Sample #2

35415628
483475596
154061492

Input Sample #3

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

Output Sample #3

214010503
321766325
894782746
274293582

Notes/Hints

[Sample Explanation]

This is the result after the fourth operation in Sample #1:

[Data Range]

• For \(100\%\) of the data:

  \(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\).

• Detailed Data Range:

  Test Case #	\(n, m \le\)	\(k\)	Special Properties
  1	300	\(\le 3\)	None
  2	300	\(\le 3\)	None
  3	\(3 \times 10^3\)	\(\le 3\)	None
  4	\(3 \times 10^3\)	\(\le 3\)	None
  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\)	None
  16	\(7 \times 10^4\)	\(= 2\)	None
  17	\(7 \times 10^4\)	\(= 3\)	None
  18	\(2 \times 10^5\)	\(= 1\)	None
  19	\(2 \times 10^5\)	\(= 2\)	None
  20	\(2 \times 10^5\)	\(= 3\)	None

  A: At any time, all \(b_i = 1\).

  B: There are no type 2 operations.

[Hint]

Sample #2 satisfies property A, and Sample #3 satisfies property B.

见题面 Input 部分

见题面 Output 部分