Prefix Sum is a useful trick in data structure problems.

For example, given an array A of length n and m queries. Each query gives an interval [l,r] and you need to calculate . How to solve this problem in O(n+m)? We can calculate the prefix sum array B in which B_i is equal to . And for each query, the answer is B_r-B_l-1.

Since Rikka is interested in this powerful trick, she sets a simple task about Prefix Sum for you:

Given two integers n,m, Rikka constructs an array A of length n which is initialized by A_i = 0. And then she makes m operations on it.

There are three types of operations:
1. 1 L R w, for each index i ∈ [L,R], change A_i to A_i + w.
2. 2, change A to its prefix sum array. i.e., let A' be a back-up of A, for each i ∈ [1,n], change A_i to .
3. 3 L R, query for the interval sum .

The first line contains a single number t(1≤ t ≤ 3), the number of the testcases.

For each testcase, the first line contains two integers n,m(1 ≤ n,m ≤ 105). 

And then m lines follow, each line describes an operation(1 ≤ L ≤ R≤ n, 0 ≤ w ≤ 109). 

The input guarantees that for each testcase, there are at most 500 operations of type 3.

For each query, output a single line with a single integer, the answer modulo 998244353.

1
100000 7
1 1 3 1
2
3 2333 6666
2
3 2333 6666
2
3 2333 6666

13002
58489497
12043005