Description

There are two weighted sequences $a, b$ of length $n$, constants $p, k$, and two functions:

There are $m$ operations, of the following three types:

• $1\ x\ y$: modify $a_x$ to $y$.

• $2\ x\ y$: modify $b_x$ to $y$.

• $3\ x$: query the value of $f(x) \bmod (10 ^ 9 + 7)$.

Input Format

The first line contains four integers $n, m, p, 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 one operation.

Output Format

For each operation of the form $3\ x$, output the answer.

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

Hint

Sample Explanation

This is the result after the 4th operation in Sample 1:

Constraints

• For $100\%$ of the testdata:

  $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 constraints:

  Test point ID	$n, m \le$	$k$	Special property
  $1$	$300$	$\le 3$	None
  $2$
  $3$	$3 \times 10 ^ 3$
  $4$
  $5$	$7 \times 10 ^ 4$	$= 1$	A
  $6$
  $7$
  $8$		$= 2$
  $9$		$= 3$
  $10$		$= 1$	B
  $11$
  $12$		$= 2$
  $13$		$= 3$
  $14$
  $15$		$= 1$	None
  $16$		$= 2$
  $17$		$= 3$
  $18$	$2 \times 10 ^ 5$	$= 1$
  $19$		$= 2$
  $20$		$= 3$

  A: At any time, all $b_i = 1$.

  B: There is no operation of type 2.

Hint

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

Translated by ChatGPT 5