Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4009
And Another Data Structure Problem

Time Limit: 7 Seconds      Memory Limit: 262144 KB

Given \(n\) integers \(a_1, a_2, \dots, a_n\). There are 2 types of operations:

  • 1 l r: Change \(a_l, a_{l+1}, \dots, a_r\) to \(a_l^3, a_{l+1}^3, \dots, a_r^3\);
  • 2 l r: Query the value of \(\displaystyle\sum_{i=l}^r a_i\) modulo 99971.

For each query, please output the answer.

Input

There are multiple test cases. The first line of the input is an integer \(T\) (about 5), 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\) (\(0 \le a_i \le 10^9\)), indicating the given integers.

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

  • If \(op\) equals 1, then two integers \(l, r\) (\(1 \le l \le r \le n\)) follow, indicating the first type of operation;
  • If \(op\) equals 2, then two integers \(l, r\) (\(1 \le l \le r \le n\)) follow, indicating a query.

Output

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

Sample Input

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

Sample Output

15
36

Author: CHEN, Jingbang
Source: ZOJ Monthly, March 2018
Submit    Status