Lucky Array

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A positive integer is lucky if its decimal representation contains only digits 4 and 7. Given a positive array, process:

• add l r d: add $d$ to every element in $[l,r]$.
• count l r: count how many elements in $[l,r]$ are currently lucky.

The operations guarantee that array values do not exceed $10^4$.

Input

The first line contains $n,m$. The second line contains the initial array. Each following line is add l r d or count l r.

Output

For every count operation, print the number of lucky values on its own line.

Subtasks

• Subtask 1 (20%): n,m≤30; all other conditions are unchanged.

• Subtask 2 (30%): n,m≤3000; all other conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n,m\le10^5$

• $1\le a_i\le10^4$

• $1\le d\le10^4$

• after every addition, every array value remains at most $10^4$

Examples

Input

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

Output

1
0
1
1

Explanation

Initially only 4 is lucky. After adding 2 to all elements the array is [4,5,6]; after adding 3 to positions 2..3 it is [4,8,9], so the final count is still 1.