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:
: meaning that for each , the th customer increases their current order amount by meaning that, if he previously had order amount set to then his new order amount is
: meaning that for each , the th customer ordered times with his/her order amount. So if at that time his/her order was , then they ordered times and got pizzas delivered.
You have seen all the records, now for each customer you have to determine how many pizzas Lazim delivered to them in total.
First line of the input will contain an integer , the number of testcases.
For each testcase, first two two integers and are given in a line, representing the number of customers and number of records. Then records are given in the next line. The th record is given as integers , where is or as described above.
Sum of over all testcase
Sum of over all testcase
Subtask 1 (5 points) : For all records
Subtask 2 (20 points) : For type 1 records , type 2 records can have
Subtask 3 (75 points) : All records can have
For each test case, output in a line integers. The th integer should be the total amount ordered by customer . Note that the answer will fit into 64 bit signed integer.
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 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.