← 返回题目列表

Codeforces · 121/E

E. 幸运阵

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

Petya 喜欢幸运数字。大家都知道,幸运数字是正整数,其十进制表示只包含幸运数字4和7。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

Petya 有一个由 n 个数字组成的数组。他想要执行两种类型的 m 个操作:

- add l r d — 将一个整数 d 添加到所有索引属于 l 到 r 区间的元素,包括 (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ 104);
- count l r — 查找并在屏幕上打印索引属于 l 到 r 区间(含 1 ≤ l ≤ r ≤ n)的元素中有多少个幸运数字。每个幸运数字应按照其在间隔中出现的次数进行计数。

Petya 有一个所有操作的列表。这些操作使得在所有加法之后,数组中的数字不会超过 104。帮助 Petya 编写一个执行这些操作的程序。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105) — 数组中数字的数量以及相应的运算次数。第二行包含 n 个正整数,其中没有一个超过 104 — 这些是数组编号。接下来的 m 行包含操作,每行一个。它们与声明中给出的描述相对应。

保证所有操作完成后数组中的每个数字不会超过104。

输出

对于第二种类型的每个操作,在单行上打印单个数字 - 相应区间内的幸运数字的数量。

示例

输入 #1

3 6
2 3 4
count 1 3
count 1 2
add 1 3 2
count 1 3
add 2 3 3
count 1 3

输出 #1

1
0
1
1

输入 #2

4 5
4 4 4 4
count 1 4
add 1 4 3
count 1 4
add 2 3 40
count 1 4

输出 #2

4
4
4

注意

在第一次添加后的第一个示例中,数组将按以下方式查找:

4 5 6

第二次添加后:

4 8 9

第一次添加后的第二个样本:

7 7 7 7

第二次添加后:

7 47 47 7