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.

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

Hint

None

Source

None

提交代码