Please solve the below problem! Lazim has recently decided to open a pizza restaurant. His restaurant’s speciality is that they can deliver a large number of pizzas on demand. For this, customers need to tell their order amounts beforehand. After performing many deliveries, Lazim wants to know how many pizzas he has sent to each customer. And it is your job to figure that out.

Lazim has given you all of his customer records. Initially, all customers have set the count of pizza they want to be 0. Then the events were recorded sequentially. There are two types of records:

111 lll rrr kkk: meaning that for each l≤i≤rl \leq i \leq rl≤i≤r, the iii th customer increases their current order amount by kkk meaning that, if he previously had order amount set to xxx then his new order amount is x+kx+kx+k

222 lll rrr kkk : meaning that for each l≤i≤rl \leq i \leq rl≤i≤r , the iiith customer ordered kkk times with his/her order amount. So if at that time his/her order was xxx, then they ordered kkk times and got k⋅xk \cdot xk⋅x pizzas delivered.

You have seen all the records, now for each customer 1,⋯ ,n1, \cdots, n1,⋯,n you have to determine how many pizzas Lazim delivered to them in total.
Input

First line of the input will contain an integer TTT, the number of testcases.

For each testcase, first two two integers nnn and qqq are given in a line, representing the number of customers and number of records. Then qqq records are given in the next qqq line. The iiith record is given as 444 integers ttt lll rrr kkk, where ttt is 111 or 222 as described above.
constraints

1≤T≤2⋅1031 \leq T \leq 2 \cdot 10^31≤T≤2⋅103

1≤n, q≤1051 \leq n, q \leq 10^51≤n, q≤105

1≤t≤21 \leq t \leq 21≤t≤2

1≤l≤r≤n1 \leq l \leq r \leq n1≤l≤r≤n

1≤k≤1041 \leq k \leq 10^41≤k≤104

Sum of nnn over all testcase ≤106\leq 10^6≤106

Sum of qqq over all testcase ≤106\leq 10^6≤106

Subtask 1 (5 points) : For all records l=rl = rl=r

Subtask 2 (20 points) : For type 1 records l=rl = rl=r, type 2 records can have l≠rl \neq rl=r

Subtask 3 (75 points) : All records can have l≠rl \neq rl=r
Output

For each test case, output in a line nnn integers. The iiith integer should be the total amount ordered by customer iii. Note that the answer will fit into 64 bit signed integer.
Sample
Input Output

2
5 5
1 2 5 10
1 1 4 5
2 1 3 5
2 1 5 2
2 5 5 1
6 10
1 1 6 5
1 4 5 100
2 1 4 5
1 3 6 1
2 2 5 20
2 1 3 10
1 1 6 50
2 3 4 12
1 2 6 15
2 1 4 5

35 105 105 30 30
350 525 1232 5372 2120 0

In the first test, initially all customers have their order amount set to 0.

After first record, customer 2 to 5 increase their order amount by 10. Current order amounts: 0 10 10 10 10

After second record, customer 1 to 4 increase their order amount by 5. Current order amounts: 5 15 15 15 10

After third record, customer 1 to 3 order 5 times. So customer 1 receives 25 pizzas and customer 2-3 receive 75 pizzas each. Current order amounts: 5 15 15 15 10

After fourth record, customer 1 to 5 order 2 times. So customer 1 receives 10 pizzas, customer 2-4 receive 30 pizzas each and customer 5 receives 20 pizza. Current order amounts: 5 15 15 15 10

After fifth record, customer 5 orders 1 time. So customer 5 receives 10 pizzas. Current order amounts: 5 15 15 15 10

If you count the deliveries you will see that the customers received 35, 105, 105, 30, 30 pizzas.

Note that the sample is not considered part of subtask 1 and subtask 2. So for subtask 1 and subtask 2, your code doesn't have to work on the sample