Background

“Things can be inferred from each other, and each has its place. So although branches split, they share the same trunk. This only reveals one end of it. Also, when analyzing principles through words and explaining structures with diagrams, it may be concise yet complete, clear yet not verbose. Readers will understand more than half just by thinking.” — Liu Hui.

Problem Description

Xiao Song has a sequence $A=\{a_1,a_2\dots,a_n\}$, where $\forall i\in [1,n],a_i\in[0,9]$.

For $1\le l\le r\le n$, he defines $f(l,r)$ as the number of consecutive trailing $5$’s at the end of $\overline{a_la_{(l+1)}\dots a_r}$.

For example, for the sequence $a=\{1,1,4,5,1,4\}$, $f(2,4)=1,f(1,3)=0$.

Xiao Song will keep performing operations on this sequence. Specifically, he will do the following operations:

• $(1,x,y)$: Change the $x$-th number to $y$ ($x\in[1,n],y\in[0,9]$).

• $2$: Reverse the sequence $a$. For example, $\{1,1,4,5\}$ becomes $\{5,4,1,1\}$ after reversing.

• $3$: Query the sequence.

• $(4,l,r)$: Query the sequence.

For each operation $3$, output:

$$\Big(\sum\limits_{l=1}^ {n}\sum\limits_{r=l}^{n} f(l,r)\Big) \bmod 10^9+7$$

For each operation $4$, output:

$$\Big(\sum\limits_{i=l}^{r}a_i\Big) \bmod 10^9+7$$

Input Format

The first line contains two positive integers $n,q$, representing the length of the sequence and the number of queries.

The second line contains $n$ integers $a_1, a_2,\dots a_n$, representing the sequence $A$.

The next $q$ lines each contain one or three positive integers, representing an operation.

Output Format

For each operation $3$ and operation $4$, output the answer.

3 4
1 5 5
1 3 3
3
1 1 5
4 1 3

2
13

6 5
1 1 4 5 1 4
3
2
3
1 1 5
4 1 4

4
3
15

Hint

Explanation for Sample $1$:

Operation	Sequence after the operation	Answer
$(1,3,3)$	$\{1,5,3\}$	$/$
$3$	$/$	$2$
$(1,1,5)$	$\{5,5,3\}$	$/$
$(4,1,3)$	$/$	$13$

Explanation for Sample $2$:

Operation	Sequence after the operation	Answer
$3$	$/$	$4$
$2$	$\{4,1,5,4,1,1\}$	$/$
$3$	$/$	$3$
$(1,1,5)$	$\{5,1,5,4,1,1\}$	$/$
$(4,1,4)$	$/$	$15$

Constraints

Test Point ID	$n\le$	$q\le$	Special Property
$1$	$100$		$/$
$2,3$	$10^3$		$\mathbf{A}$
$4$			$\mathbf{B}$
$5\sim10$	$2\times 10^5$		$/$
$11\sim13$			$\mathbf{A}$
$14,15$			$/$
$16\sim18$	$5\times 10^5$		$\mathbf{B}$
$19\sim25$			$/$

Special property $\mathbf{A}$: There is no operation $2$.

Special property $\mathbf{B}$: There is no operation $3$.

For $100\%$ of the testdata: $1\le n\le 5\times 10^5$, $1\le q\le 5\times 10^5$.

$\forall i\in [1,n]$, $a_i\in[0,9]$.

Translated by ChatGPT 5