Chicken Chap

Time Limit: 1 sec

 

The Problem

 

Hey Guys

Whats Up!!

Let’s Grab Some

Chicken Chap!!

 

Hello Guys. I am Azax. I am now in a restaurant named “Khaite Thak”. I would like to offer you some chicken chap for free. Will you please agree to have it?

 

Well, not in free actually. You have to do a little work for me. My friends are also waiting for having chicken chap. Let me clear a bit. I have some friends sitting on a restaurant on a straight line. They are indexed by 1, 2, 3, ….. N. My friends are bit weird. While they order chaps they will order for a range of persons. That is the order will be like “Please bring X chaps for persons indexed by L  to R i.e. for persons L, L+1, L+2, ….. , R-1, R”.  That means if they order 5 chicken chaps for persons indexed by  4 to 9, the waiter will bring 5 chicken chap from each of my friend from 4th to 9th where X=5, l=4,r=9 .

The waiter of “Khaite Thak” restaurant is now in a fix. He will serve chicken chap after taking all of the orders. So he has to calculate how many chaps each of my friends ordered. He gave me the details of orders and asked me to calculate the number of chaps each of my friends ate. Note that there can be several orders. I am a bit busy in chatting with them. That’s why I would like you to help waiter. I promise I will feed you unlimited chaps if you do me this favor.

The Input

Input starts with an integer T that denotes the number of test cases.

Each case starts with two integers N and Q denotes number of friends I have and number of orders the waiter enlisted.

The next Q lines contains three integers L, R, X denotes the starting index of person, the ending index of person, and the amount of chaps the waiter should serve.

 

Constraints

1 <= T <=15

1 <= N, Q <= 10^5

1 <= L, R <= N

1 <= X <= 10^9

 

The Output

For each test case you need to print the case number in format “Case Y: ” where Y is the case number followed by N space separated integers which are the amount of chaps ordered by my friends in a single line. See the samples for further clarification.

 

Sample Input

1

3 2

1 3 5

2 3 2

 

Sample Output

Case 1: 5 7 7

 

[Note:  In this case there are 3(N) friends and they will give 2(Q) orders. In the first order, L= 1, R = 3, X = 5. That means 5 chicken chaps is ordered for 1 to 3 indexed friend.  So the number of required chicken chap for each friend = (5, 5, 5). In the second order, L= 2, R= 3, X= 2. So the number of required chicken chap of 2nd friend and 3rd friend will increased  by 2. Now the number of required chicken chap for each friend (5, 5+2, 5+2) = (5, 7, 7).]

 

 

 

Inter University Programming Contest(I) - 2018 [BGC Trust University Bangladesh]

Problem Setter: Avik Sarkar