Kefa and Watch

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain a digit string. Type 1 assigns one digit to a whole range. Type 2 checks whether substring $[l,r]$ has period $d$.

Input

The first line contains $n,m,k$: string length, number of changes, and number of checks. The second line is the digit string. Exactly $m+k$ operation lines follow: 1 l r c assigns digit $c$ to a range; 2 l r d checks whether substring $[l,r]$ has period $d$.

Output

For each check print YES if the substring has period $d$, otherwise print NO.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n\le10^5$

• $1\le m+k\le10^5$

• $0\le c\le9$

• $1\le d\le r-l+1$

Examples

Input

3 1 2
112
2 2 3 1
1 1 3 8
2 1 2 1

Output

NO
YES

Explanation

Substring 12 does not have period 1, so the first answer is NO. After assigning the whole string to 888, substring 88 has period 1, so the second answer is YES.