20785번 - Julius Caesar and Kazusa 다국어

Have you ever heard of the Caesar cipher? It is one of the simplest and best-known encryption techniques. Named after Julius Caesar, he used this cipher to communicate with his generals. 

Caesar cipher is a type of substitution cipher in which each letter in the plaintext is shifted a certain number of places down the alphabet. The alphabet is considered wrapped around. For example, with a shift of $1$ in the Latin alphabet, A would be replaced by B, B would become C, Z would be A, and so on.

Kazusa now has an array $a$ of integers $a_1,a_2,\dots,a_n$ of length $n$, with each $a_i$ in the range $[0,65\,536)$, and she wants to encrypt it using Caesar cipher several times. She selects an interval $[l,r](1\leq l\leq r\leq n)$ each time, and makes an encryption using Caesar cipher with shift of $1$ to the numbers in the interval. Formally, for all $l\leq i\leq r$, this transforms $a_i$ into $(a_i+1) \bmod 65\,536$. 

However, while Kazusa is encrypting the array, her sister, Setsuna, raises some questions about the array. Each query asks on the current copy of the array, where zero or more encryptions using Caesar cipher has been done. Each query is given by three integers $x, y, L$, which asks whether the two strings $a_x,a_{x+1} \dots a_{x+L-1}$ and $a_y,a_{y+1} \dots a_{y+L-1}$ are same.

While Kazusa is busying doing the encryption, she has no time to answer these queries. Could you please help her?

The first line contains two integers $n,q$ $(1 \leq n, q \leq 500\,000)$, denoting the size of the array and the number of operations, respectively. The second line contains $n$ integers $a_1,a_2,\dots,a_n$ $(0 \leq a_i < 65\,536)$, denoting the initial array. The next $q$ lines describe the operations, each operation is in one of the two following types:

• Operation of type 1 contains three integers $1, l, r$ $(1 \leq l \leq r \leq n)$, meaning that Kazusa made an encryption using Caesar cipher with shift $1$ to the numbers in the interval $[l,r]$;
• Operation of type 2 contains four integers $2, x, y, L$ $(1 \leq x, y \leq n,\max \{x,y\}+L-1 \leq n)$, meaning that Setsuna asked a query whether the two strings are the same.

For each operation of type 2, if the two strings are same, please print yes in one line; otherwise print no.

The first test case is explained below.