题面描述

小 L 有两个长度为 $n+1$ 的序列 $f,g$，下标均从 $0$ 开始。

小 L 还有一个整数 $d$，保证 $0\le d\le n$。

你需要进行以下三种操作：

1. 给定 $i,x$，将 $f_i$ 更改为 $x$。
2. 给定 $j,y$，将 $g_j$ 更改为 $y$。
3. 给定 $k\in\{-1,1\}$，将 $d$ 加上 $k$，保证修改后依然满足 $0\le d\le n$，随后输出 $(\sum_{i=0}^df_ig_{d-i})\bmod p$ 的值。

其中 $P=10^9+7$，是一个质数。

保证 $1\le n,Q\le 2\times 10^5$，且任意时刻 $\forall 0\le i\le n,\;0\le f_i,g_i< P$。

输入格式

第一行三个非负整数 $n,Q,d$。

第二行 $n+1$ 个数，分别为 $f_0,f_1,\cdots,f_n$。

第三行 $n+1$ 个数，分别是 $g_0,g_1,\cdots,g_n$。

接下来 $Q$ 行，每行先读入一个 $op\in\{1,2,3\}$。

若 $op=1$，那么接下来两个数 $i,x$。

若 $op=2$，那么接下来两个数 $j,y$。

若 $op=3$，那么接下来一个数 $k$。

输出格式

对于每次 $op=3$ 的操作，输出一行一个数，表示对应的答案。

输入输出样例

样例输入

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

样例输出

67
108
155
151
128