题目描述

小 Y 非常喜欢 $42$ 这个数，于是他也喜欢以 $42$ 为初始数，然后往后面依次拼接 $4,2$ 的数，如 $42,424,4242,\cdots$。小 Y 给了你一个大小为 $n$ 的整数序列 $a$，小 Y 有 $m$ 次操作，操作有四种：

• 1 l r x 将 $l\sim r$ 中的数加上 $x$。

• 2 l r x 将 $l\sim r$ 中的数乘上 $x$。

• 3 l r x 将 $l\sim r$ 中的数修改为 $x$。

• 4 l r 询问 $l\sim r$ 中有多少个小 Y 喜欢的数。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,a_3\cdots a_n$。

接下来 $m$ 行，每行 $3$ 或 $4$ 个整数描述一次操作。

输出格式

每行一个操作 $4$ 的答案。

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

提示

样例解释

第 $1$ 次操作为询问区间 $1\sim8$ 中有多少个小 Y 喜欢的数，共 $1$ 个，为 $a_2$。

第 $2$ 次操作为将区间 $1\sim8$ 中的数加上 $377$，数列 $a$ 变为 $418,419,420,421,422,423,424,424$。

第 $3$ 次操作为询问区间 $1\sim8$ 中有多少个小 Y 喜欢的数，共 $2$ 个，为 $a_7,a_8$。

第 $4$ 次操作为将区间 $1\sim1$ 中的数乘上 $100$，数列 $a$ 变为 $41800,419,420,421,422,423,424,424$。

第 $5$ 次操作为将区间 $1\sim8$ 中的数加上 $624$，数列 $a$ 变为 $42424,1043,1044,1045,1046,1047,1048,1048$。

第 $6$ 次操作为询问区间 $1\sim7$ 中有多少个小 Y 喜欢的数，共 $1$ 个，为 $a_1$。

第 $7$ 次操作为将区间 $1\sim8$ 中的数修改为 $424242$，数列 $a$ 变为 $424242,424242,424242,424242,424242,424242,424242,424242$。

第 $8$ 次操作为询问区间 $1\sim5$ 中有多少个小 Y 喜欢的数，共 $5$ 个，为 $a_1,a_2,a_3,a_4,a_5$。

数据范围

对于 $100\%$ 的数据，$1\le n,m,a_i,x\le5\times10^5$，$1\le l,r\le n$。

保证每次操作后 $1\le a_i\le5\times10^5$。