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 Bi is equal to . And for each query, the answer is Br-Bl-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 Ai = 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 Ai to Ai + 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 Ai 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.