Description

There is a sequence $a_{1\sim n}$ and several operations.

• $\mathrm{1\ l \ r \ }$: Find the sum from $a_l$ to $a_r$.
• $\mathrm{2\ l \ r \ val \ }$: Assign $\mathrm{val}$ to $a_l$ through $a_r$.
• $\mathrm{3\ l \ r \ val\ }$: Add $\mathrm{val}$ to $a_l$ through $a_r$.
• $\mathrm{4\ l_1 \ r_1 \ l_2 \ r_2 }$: Copy $a_{l_1}$ through $a_{r_1}$ to the range $a_{l_2}$ through $a_{r_2}$.
• $\mathrm{5\ l_1 \ r_1 \ l_2 \ r_2 }$: Swap $a_{l_1}$ through $a_{r_1}$ with $a_{l_2}$ through $a_{r_2}$.
• $\mathrm{6\ l \ r \ }$: Reverse $a_l$ through $a_r$.

Input Format

The first line contains two numbers $n$ and $m$, the length of the sequence and the number of operations.

The second line contains $n$ numbers, which are $a_{1\sim n}$.

The next $m$ lines each describe an operation type and several corresponding integers.

Output Format

Print several lines. For each operation of type $1$, output the answer.

Since the answer may be too large, take it modulo $10^9+7$.

On the last line, output the sequence $a_{1\sim n}$. It should also be taken modulo.

10 10
7 1 3 2 2 4 0 1 2 2 
4 10 10 3 3
3 4 10 5
6 6 7
6 9 10
1 10 10
5 9 10 6 7
2 8 10 0
5 4 4 5 5
5 2 4 8 10
3 3 9 0

7
7 0 0 0 7 7 7 1 2 7

Hint

Please pay attention to constant-factor optimizations.

For operations $4$ and $5$, it is guaranteed that $r_1-l_1=r_2-l_2$ and the intervals do not overlap.

The testdata is guaranteed to be random.

For $30\%$ of the testdata, $\ n,m\le 10^3\$.

For $50\%$ of the testdata, $\ n,m\le 5\times 10^4\$.

For $70\%$ of the testdata, $\ n,m\le 1.5\times 10^5\$.

For $100\%$ of the testdata, $\ n,m\le 3\times 10^5\$，$\ 0\le a_i,\mathrm{val}< 10^9+7$。

Translated by ChatGPT 5