题目描述

有两个长度均为 $n$ 的权值序列 $a,b$，常数 $p,k$，以及两个函数：

有 $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

提示

【样例解释】

这是样例一操作四后的结果：

【数据范围】

• 对于 $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$
  $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$	无
  $16$		$= 2$
  $17$		$= 3$
  $18$	$2 \times 10 ^ 5$	$= 1$
  $19$		$= 2$
  $20$		$= 3$

  A：任意时刻所有 $b_i = 1$。

  B：无操作二。

【提示】

样例二满足A类性质，样例三满足B类性质。