# Count the Deliveries

National High School Prog...
Limits 2s, 512 MB

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:

1. $1$ $l$ $r$ $k$: meaning that for each $l \leq i \leq r$, the $i$ th customer increases their current order amount by $k$ meaning that, if he previously had order amount set to $x$ then his new order amount is $x+k$

2. $2$ $l$ $r$ $k$ : meaning that for each $l \leq i \leq r$ , the $i$th customer ordered $k$ times with his/her order amount. So if at that time his/her order was $x$, then they ordered $k$ times and got $k \cdot x$ pizzas delivered.

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

## Input

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

For each testcase, first two two integers $n$ and $q$ are given in a line, representing the number of customers and number of records. Then $q$ records are given in the next $q$ line. The $i$th record is given as $4$ integers $t$ $l$ $r$ $k$, where $t$ is $1$ or $2$ as described above.

#### constraints

• $1 \leq T \leq 2 \cdot 10^3$

• $1 \leq n, q \leq 10^5$

• $1 \leq t \leq 2$

• $1 \leq l \leq r \leq n$

• $1 \leq k \leq 10^4$

• Sum of $n$ over all testcase $\leq 10^6$

• Sum of $q$ over all testcase $\leq 10^6$

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

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

Subtask 3 (75 points) : All records can have $l \neq r$

## Output

For each test case, output in a line $n$ integers. The $i$th integer should be the total amount ordered by customer $i$. Note that the answer will fit into 64 bit signed integer.

## Sample

InputOutput
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.

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

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

3. 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

4. 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

5. 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 changing the order amount does not mean delivery, deliveries are performed only during type 2 record. Similarly delivery does not mean change of order amount.

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.