Migrated from Lutece 2478 Little Horse's Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Little Horse loves making problems. This day, Little Horse meets Little Rabbit. He immediately makes a problem for Little Rabbit.

Given a string $s$ of length $n$. There are two kinds of operations.

1. $1 \ l_1 \ r_1 \ l_2 \ r_2$: query whether the substring $s_{l_1}s_{l_1+1}\ldots s_{r_1}$ and $s_{l_2}s_{l_2+1}\ldots s_{r_2}$ are the same.
2. $2 \ l \ r \ k$: right circular shift the substring $s_{l}s_{l+1}\dots s_{r}$ by $k$ positions.

If you right circular shift $s_1s_2\cdots s_m$ by $1$ position, you will get $s_ms_1s_2\cdots s_{m-1}$. To right circular shift by $k$ positions means to repeat such operation $k$ times.

Now, Little Horse has $m$ operations. He wants Little Rabbit to tell him the result. Little Rabbit is not clever enough to answer this problem. Can you help him?

Input

The first line contains two integers $n$ and $m$ ($1 \le n,m \le 2\times10^5$) — the length of $s$ and the number of operations.

The second line contains a string $s$, which consists of only lowercase letters.

In the next $m$ lines, each line contains an operation. The format is in the description ($1 \le l_1 \le r_1 \le n, 1 \le l_2 \le r_2 \le n, 1 \le l \le r \le n,1 \le k \le 2\times10^5$).

Output

For each operation $1$, output Yes or No in a line.

Samples

6 4
aabbab
2 1 6 1
1 1 2 5 6
2 1 6 2
1 1 2 5 6

Yes
No

Constraints

$1 \le n,m \le 2\times10^5$ $1 \le l_1 \le r_1 \le n, 1 \le l_2 \le r_2 \le n, 1 \le l \le r \le n,1 \le k \le 2\times10^5$

Note

aabbab

1. $2 \ 1 \ 6 \ 1$: right circular shift the substring $s_{1}s_{2}\dots s_{6}$ by $1$ positions. baabba
2. $1 \ 1 \ 2 \ 5 \ 6$: query whether the substring $s_1s_2$ and $s_5s_6$ are the same. Yes
3. $2 \ 1 \ 6 \ 1$: right circular shift the substring $s_{1}s_{2}\dots s_{6}$ by $1$ positions. babaab
4. $1 \ 1 \ 2 \ 5 \ 6$: query whether the substring $s_1s_2$ and $s_5s_6$ are the same. No

Resources

Macaron_lin