Kefa và chiếc đồng hồ (Kefa and Watch)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho chuỗi chữ số độ dài $n$. Thao tác loại 1 gán mọi chữ số trong đoạn thành $c$. Thao tác loại 2 kiểm tra chuỗi con $[l,r]$ có chu kỳ $d$ hay không.

Input

Dòng đầu chứa $n,m,k$: độ dài chuỗi, số thao tác thay đổi và số thao tác kiểm tra. Dòng thứ hai là chuỗi gồm $n$ chữ số. Sau đó có đúng $m+k$ thao tác:

• 1 l r c: gán mọi chữ số ở các vị trí $l..r$ thành $c$.
• 2 l r d: kiểm tra chuỗi con $[l,r]$ có chu kỳ $d$ hay không.

Output

Mỗi thao tác loại 2 in YES nếu chuỗi con có chu kỳ $d$, ngược lại in NO.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n\le10^5$

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

• $0\le c\le9$

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

Ví dụ

Input

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

Output

NO
YES

Giải thích

Chuỗi con 12 không có chu kỳ 1 nên in NO. Sau khi gán cả chuỗi thành 888, chuỗi con 88 có chu kỳ 1 nên in YES.