← 返回题目列表

Codeforces · 580/E

E. 科发与手表

中文机器翻译题面 查看原题

有一天,鹦鹉科法从餐馆回家的路上走在街上,突然看到路边有东西闪闪发光。当他走近时,他明白那是一块手表。他决定把它拿到当铺赚点钱。

当铺表示,每块手表都包含一个由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。