# And Another Data Structure Problem

Time Limit: 7 Seconds

Memory Limit: 262144 KB

## Description

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.

## 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


None

None