P3747 [Six Provinces Joint Exam 2017] Greeting Upon Meeting

> Informatik verbindet dich und mich. > Information connects you and me. Mr. B wants to maintain an array of length $n$, whose indices are the positive integers from $1$ to $n$. There are $m$ operations, of two types: - `0 l r` means: for each number $a_i$ among the $l$-th to the $r$-th numbers ($a_l,a_{l+1} ...a_r$), replace $a_i$ with $c^{a_i}$, i.e., assign $a_i = c^{a_i}$, where $c$ is a given constant in the input. - `1 l r` asks for the sum of the $l$-th to the $r$-th numbers, i.e., output $\sum_{i=l}^{r} a_i$. Because the result can be very large, you only need to output the result $\bmod \space p$.

The first line contains four integers $n, m, p, c$, whose meanings are given in the problem statement. The next line contains $n$ integers, the initial values of the array $a$. The next $m$ lines each contain three integers; the first integer indicates the type of operation. - If it is `0`, this is an update operation with parameters $l, r$. - If it is `1`, this is a query operation with parameters $l, r$.

For each query operation, output one line with a single integer: the answer $\bmod \space p$.

Constraints - For $0\%$ of the test points, identical to the sample. - For another $10\%$ of the test points, there are no updates. - For another $20\%$ of the test points, each update modifies only one position (i.e., $l = r$), and each position is updated at most once. - For another $10\%$ of the test points, $p = 2$. - For another $10\%$ of the test points, $p = 3$. - For another $10\%$ of the test points, $p = 4$. - For another $20\%$ of the test points, $1\le n, m \le 100$. - For $100\%$ of the test points, $1\le n, m \le 5\times 10^4$, $1 \le p \le 10^8$, $0< c < p$, $0 \le a_i < p$. Translated by ChatGPT 5