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