P6215 Function Evaluation

There are two weighted sequences $a, b$ of length $n$, constants $p, k$, and two functions: $$g(x) = \sum_{i=1}^x p^i \times a_i$$ $$f(x) = \sum_{i=1}^x g(i) ^ k \times b_i$$ 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)$.

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.

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

**Sample Explanation** This is the result after the 4th operation in Sample 1: | $/$ | $1$ | $2$ | $3$ | $4$ | $5$ | | :-: | :-: | :-: | :-: | :-: | :-: | | $a_i$ | $0$ | $3$ | $8$ | $8$ | $5$ | | $b_i$ | $9$ | $2$ | $8$ | $8$ | $6$ | | $g(i)$ | $0$ | $3$ | $11$ | $19$ | $24$ | | $f(i)$ | $0$ | $6$ | $94$ | $246$ | $390$ | ---------------------- **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$ | $300$ | $\le 3$ | None $3$ | $3 \times 10 ^ 3$ | $\le 3$ | None $4$ | $3 \times 10 ^ 3$ | $\le 3$ | None $5$ | $7 \times 10 ^ 4$ | $= 1$ | A $6$ | $7 \times 10 ^ 4$ | $= 1$ | A $7$ | $7 \times 10 ^ 4$ | $= 1$ | A $8$ | $7 \times 10 ^ 4$ | $= 2$ | A $9$ | $7 \times 10 ^ 4$ | $= 3$ | A $10$ | $7 \times 10 ^ 4$ | $= 1$ | B $11$ | $7 \times 10 ^ 4$ | $= 1$ | B $12$ | $7 \times 10 ^ 4$ | $= 2$ | B $13$ | $7 \times 10 ^ 4$ | $= 3$ | B $14$ | $7 \times 10 ^ 4$ | $= 3$ | B $15$ | $7 \times 10 ^ 4$ | $= 1$ | None $16$ | $7 \times 10 ^ 4$ | $= 2$ | None $17$ | $7 \times 10 ^ 4$ | $= 3$ | None $18$ | $2 \times 10 ^ 5$ | $= 1$ | None $19$ | $2 \times 10 ^ 5$ | $= 2$ | None $20$ | $2 \times 10 ^ 5$ | $= 3$ | None 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