Problem Description

Xiao Y likes the number $42$ very much, so he also likes numbers that start with $42$ and then keep appending $4,2$ alternately, such as $42,424,4242,\cdots$. Xiao Y gives you an integer sequence $a$ of length $n$. There are $m$ operations, and there are four types of operations:

• 1 l r x Add $x$ to the numbers in positions $l\sim r$.

• 2 l r x Multiply the numbers in positions $l\sim r$ by $x$.

• 3 l r x Set the numbers in positions $l\sim r$ to $x$.

• 4 l r Query how many numbers in positions $l\sim r$ are liked by Xiao Y.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers $a_1,a_2,a_3\cdots a_n$.

The next $m$ lines each contain $3$ or $4$ integers describing one operation.

Output Format

Output one line for each operation of type $4$, containing its answer.

8 8
41 42 43 44 45 46 47 47
4 1 8
1 1 8 377
4 1 8
2 1 1 100
1 1 8 624
4 1 7
3 1 8 424242
4 1 5

1
2
1
5

Hint

Sample Explanation

In the $1$st operation, query how many numbers in the interval $1\sim8$ are liked by Xiao Y. There is $1$ such number, which is $a_2$.

In the $2$nd operation, add $377$ to the numbers in the interval $1\sim8$, and the sequence $a$ becomes $418,419,420,421,422,423,424,424$.

In the $3$rd operation, query how many numbers in the interval $1\sim8$ are liked by Xiao Y. There are $2$ such numbers, which are $a_7,a_8$.

In the $4$th operation, multiply the numbers in the interval $1\sim1$ by $100$, and the sequence $a$ becomes $41800,419,420,421,422,423,424,424$.

In the $5$th operation, add $624$ to the numbers in the interval $1\sim8$, and the sequence $a$ becomes $42424,1043,1044,1045,1046,1047,1048,1048$.

In the $6$th operation, query how many numbers in the interval $1\sim7$ are liked by Xiao Y. There is $1$ such number, which is $a_1$.

In the $7$th operation, set the numbers in the interval $1\sim8$ to $424242$, and the sequence $a$ becomes $424242,424242,424242,424242,424242,424242,424242,424242$.

In the $8$th operation, query how many numbers in the interval $1\sim5$ are liked by Xiao Y. There are $5$ such numbers, which are $a_1,a_2,a_3,a_4,a_5$.

Constraints

For $100\%$ of the testdata, $1\le n,m,a_i,x\le5\times10^5$, $1\le l,r\le n$.

It is guaranteed that after each operation, $1\le a_i\le5\times10^5$.

Translated by ChatGPT 5