Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3998
Yet Another Data Structure Problem

Time Limit: 5 Seconds      Memory Limit: 65536 KB

Given $N$ integers $A_1, A_2, \dots, A_N$. There are 3 types of operations:

• 1 l r v: Multiply $A_l, A_{l+1}, \dots, A_r$ by $v$;
• 2 l r k: Change each element in $A_l, A_{l+1}, \dots, A_r$ to $A_l^k, A_{l+1}^k, \dots, A_r^k$;
• 3 l r: Query the multiplication of $A_l, A_{l+1}, \dots, A_r$ modulo 1,000,000,007.

Input

There are multiple test cases. The first line of the input is an integer $T$ ($1 \le T \le 200$), indicating the number of test cases. For each test case:

The first line contains two integers $N$ ($1 \le N \le 10^5$) and $Q$ ($1 \le Q \le 10^5$), indicating the number of the given integers and the number of operations.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^3$), indicating the given integers.

The first integer on each of the following $Q$ lines will be $op$ ($1 \le op \le 3$), indicating the type of operation.

• If $op$ equals 1, then three integers $l, r, v$ ($1 \le l \le r \le N$, $1 \le v \le 10^3$) follow, indicating the first type of operation.
• If $op$ equals 2, then three integers $l, r, k$ ($1 \le l \le r \le N$, $1 \le k \le 10^9$) follow, indicating the second type of operation.
• If $op$ equals 3, then two integers $l, r$ ($1 \le l \le r \le N$) follow, indicating an query.

It's guaranteed that neither the sum of $N$ nor the sum of $Q$ over all test cases will exceed $10^6$.

Output

For each query, output one line containing one integer, indicating the answer.

Sample Input

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

Sample Output

4
32
16

Author: LIU, Zhenwei
Source: ZOJ Monthly, January 2018
Submit    Status