Welcome to ZOJ
 Problem Sets 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