Favorite Number Operations

Little Y loves the number \(42\). In fact, his favorite numbers form an interesting sequence: the first is \(42\), and each subsequent number is formed by appending digits alternately \(4\) and \(2\) to the previous one. For example, the sequence is \(42, 424, 4242, 42424, \ldots\).

You are given an integer sequence \(a\) of size \(n\) and \(m\) operations. There are four kinds of operations:

• 1 l r x: For each index \(i\) in \([l,r]\), set \(a_i = a_i + x\).
• 2 l r x: For each index \(i\) in \([l,r]\), set \(a_i = a_i \times x\).
• 3 l r x: For each index \(i\) in \([l,r]\), assign \(a_i = x\).
• 4 l r: Query the number of elements in \(a[l\ldots r]\) that are one of Little Y's favorite numbers.

A number is considered a favorite number if its decimal representation exactly matches one of the numbers in the sequence \(42,424,4242,42424,\ldots\). Note that all indices are 1-indexed.

inputFormat

The first line contains two integers \(n\) and \(m\).
The second line contains \(n\) space-separated integers, representing the initial sequence \(a\).
The next \(m\) lines each describe an operation in one of the following formats:

• 1 l r x
• 2 l r x
• 3 l r x
• 4 l r

outputFormat

For each operation of type 4 (query), output the answer on a separate line.

sample

5 5
42 10 4242 100 424
4 1 5
1 2 4 2
4 1 5
3 3 3 42
4 1 5

3
2
3