有一天,鹦鹉科法从餐馆回家的路上走在街上,突然看到路边有东西闪闪发光。当他走近时,他明白那是一块手表。他决定把它拿到当铺赚点钱。
当铺表示,每块手表都包含一个由0到9的一串数字表示的序列号,这个数字通过的质量检查越多,手表的价值就越高。该检查由三个正整数 l、r 和 d 定义。手表通过检查从 l 到 r 的序列号的子串是否具有周期 d。有时,当铺商会分心,Kefa 将序列号的某些子字符串全部数字更改为 c,以增加手表的利润。
卖家本来有很多事情要做,在Kefa胡搅蛮缠的情况下,他给了你一个任务:写一个程序来确定手表的价值。
让我们提醒您,数字 x 被称为字符串 s 的周期 (1 ≤ x ≤ |s|),如果 si = si + x 对于从 1 到 |s| 的所有 i - x。
输入
输入的第一行包含三个正整数 n、m 和 k (1 ≤ n ≤ 105, 1 ≤ m + k ≤ 105) — 序列号长度、科发更改次数和质量检查次数。
第二行包含由 n 位数字组成的序列号。
接下来是 m + k 行,包含检查或更改。
变化表示为 1 l r c (1 ≤ l ≤ r ≤ n, 0 ≤ c ≤ 9)。这意味着Kefa将第l位到第r位的所有数字都改为了c。
检查给出为 2 l r d (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ r - l + 1)。
输出
对于单行的每项检查,如果手表通过,则打印“YES”,否则打印“NO”。
示例
输入 #1
3 1 2 112 2 2 3 1 1 1 3 8 2 1 2 1
输出 #1
NO YES
输入 #2
6 2 3 334934 2 2 5 2 1 4 4 3 2 1 6 3 1 2 3 8 2 3 6 1
输出 #2
NO YES NO
注意
在第一个样本测试中将进行两项检查。在第一个子串“12”中检查其是否具有周期1,因此答案是“否”。在第二个子串“88”中检查是否有周期1,并且有这个周期,所以答案是“是”。
在第二个语句测试中将进行三项检查。第一个检查处理子字符串“3493”,它没有句点 2。在第二个检查之前,该字符串看起来为“334334”,因此答案为“YES”。最后,第三次检查处理子字符串“8334”,该子字符串没有句点 1。