Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Count the Deliveries

By upobir · 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. 11 ll rr kk: meaning that for each lirl \leq i \leq r, the ii th customer increases their current order amount by kk meaning that, if he previously had order amount set to xx then his new order amount is x+kx+k

  2. 22 ll rr kk : meaning that for each lirl \leq i \leq r , the iith customer ordered kk times with his/her order amount. So if at that time his/her order was xx, then they ordered kk times and got kxk \cdot x pizzas delivered.

You have seen all the records, now for each customer 1,,n1, \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 TT, the number of testcases.

For each testcase, first two two integers nn and qq are given in a line, representing the number of customers and number of records. Then qq records are given in the next qq line. The iith record is given as 44 integers tt ll rr kk, where tt is 11 or 22 as described above.

constraints

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

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

  • 1t21 \leq t \leq 2

  • 1lrn1 \leq l \leq r \leq n

  • 1k1041 \leq k \leq 10^4

  • Sum of nn over all testcase 106\leq 10^6

  • Sum of qq over all testcase 106\leq 10^6

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

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

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

Output

For each test case, output in a line nn integers. The iith integer should be the total amount ordered by customer ii. 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.

    Discussion

    Statistics


    38% Solution Ratio

    longlongintEarliest, 1M ago

    gryffindoFastest, 0.4s

    NirjhorLightest, 17 MB

    sakib.17442Shortest, 1458B

    Submit

    Login to submit

    Editorial

    Subtask 1: For first task, we can just simulate the records (since only one customer’s order changes...