Weighted Sequence Operations

You are given two weight sequences a and b, each of length n, along with two constants p and k. Define the functions:

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

$$f(x)=\sum_{i=1}^{x} \Bigl(g(i)\Bigr)^k\times b_i$$

There are m operations of the following three types:

• 1 x y: Update a[x] to y.
• 2 x y: Update b[x] to y.
• 3 x: Query the value of f(x) modulo \(10^9+7\).

The input begins with four integers: n m p k. The next two lines contain n integers each, representing the initial values of a and b respectively. Then follow m lines each describing an operation.

inputFormat

The first line contains four integers n m p k.

The second line contains n integers: a1 a2 ... an.

The third line contains n integers: b1 b2 ... bn.

Each of the following m lines contains an operation in one of the following forms:

• 1 x y — update a[x] to y.
• 2 x y — update b[x] to y.
• 3 x — output f(x) mod (10^9+7).

outputFormat

For each operation of the third type, output a single line containing the value of f(x) mod (10^9+7).

sample

5 5 2 2
1 2 3 4 5
5 4 3 2 1
3 3
1 2 5
3 3
2 3 10
3 3

3888
8304
23116