Background

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.

Problem Description

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.

Input Format

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 Format

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

6 3 6
0 1 2 0 1 2
2 1 2 1 2
2 1 2 4 5
2 1 2 5 6
1 1 2 1
2 1 2 4 5
2 1 2 5 6

Yes
Yes
No
No
Yes

Hint

This problem uses bundled tests and subtask dependencies.

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