P12389 COmPoUNdS

For some reason, Little S is especially fond of range add and range modulo. He created some problems like this, but basically could not solve any of them. One day, Little S accidentally drank a bit of iced black tea and suddenly got inspired, instantly solving all the problems. Taking advantage of the effect, he randomly picked one problem and generated the testdata. However, after the effect wore off, he no longer knew how to solve it. So please help him write a standard solution. If you succeed, he will give you a bottle of iced black tea.

Given positive integers $n, k, q$ and a sequence $a$ of length $n$, there are $q$ operations or queries: - `1 l r c`: For every $i \in [l, r]$, set $a_i \gets (a_i + c) \bmod k$. - `2 l1 r1 l2 r2`: Determine whether two subsegments of $a$ with the same length, $a_{l_1 \cdots r_1}$ and $a_{l_2 \cdots r_2}$, are equal.

The first line contains three positive integers $n, k, q$. The second line contains $n$ positive integers representing the initial values of the sequence $a$. The next $q$ lines each describe an operation or query. The format is given in the description.

Output several lines, one for each operation of type 2. If they are equal, output `Yes`; otherwise output `No`.

**This problem uses bundled tests and subtask dependencies.** | Subtask ID | Score | Special Restriction | Dependent Subtasks | Time Limit | | :---: | :---: | :---: | :---: | :---: | | $1$ | $10$ | $n, q \le 10^3$ | | $\text{1.5 s}$ | | $2$ | $20$ | $k = 2$ | | $\text{2.5 s}$ | | $3$ | $20$ | $n \le 10^5$ | $1$ | $\text{1.5 s}$ | | $4$ | $50$ | No special restriction | $1, 2, 3$ | $\text{2.5 s}$ | For all testdata, $1 \le n, q \le 10^6$, $2 \le k \le 10^6$, $0 \le a_i, c < k$. For operations of type 2, $r_1 - l_1 = r_2 - l_2$. Translated by ChatGPT 5