Little L has two sequences $f$ and $g$ of length $n+1$, with indices starting from $0$.

Little L also has an integer $d$. It is guaranteed that $0\le d\le n$.

You need to perform the following three operations:

1. Given $i,x$, change $f_i$ to $x$.
2. Given $j,y$, change $g_j$ to $y$.
3. Given $k\in\{-1,1\}$, add $k$ to $d$. It is guaranteed that after the modification, $0\le d\le n$ still holds. Then output the value of $(\sum_{i=0}^df_ig_{d-i})\bmod p$.

Here $P=10^9+7$, which is a prime.

It is guaranteed that $1\le n,Q\le 2\times 10^5$, and at any time, $\forall 0\le i\le n,\;0\le f_i,g_i< P$.

Input

The first line contains three non-negative integers $n,Q,d$.

The second line contains $n+1$ numbers: $f_0,f_1,\cdots,f_n$.

The third line contains $n+1$ numbers: $g_0,g_1,\cdots,g_n$.

The next $Q$ lines each first read an integer $op\in\{1,2,3\}$.

If $op=1$, then two numbers $i,x$ follow.

If $op=2$, then two numbers $j,y$ follow.

If $op=3$, then one number $k$ follows.

Output

For each operation with $op=3$, output one line containing one number, representing the corresponding answer.

Examples

Sample Input 1

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

Sample Output 1

67
108
155
151
128