Welcome to ZOJ
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.

For each query, please output the answer.

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