|
B |
Judgment
Day Input: Standard Input Output: Standard Output |
Nowadays,
Talent Shows have become really popular. There are a number of TV and News
media in your country, and each and every one of them has it's own “Who is the
Biggest Talent” show. These shows require a set of judges, who evaluate the
performance of all the participants. All the participants are called to
participate in a particular order to perform in front of the judges. Then the
judges simultaneously evaluates them. Although, they are asked to grade them by
a score between 0 and 100, some of the judges feel that, there are
participants, who deserves more, so, they can actually give them any score they
think right. The final score of a participant is the sum of all the scores
given by the judges.
Any people, not involved with any of these activities, may think that this is a really easy job both for the judges and the participants. Because, all the participants has to do is to do something they really like. On the other hand, judges have the easier job, they just have to relax and enjoy the performance pulled by the competitors. Since, everyone do this thing in their leisure time, they think that being a judge is possibly the best possible work anyone can find.
But actually, it is as exhausting as any other work. The first few hours may be enjoyable, but soon it becomes tedious and boring. Now, as there are so many talent shows, and every one of them use the same persons as their judge, Since, one has to judge at different shows, not all of them can watch all the performances. They decided to appear each of the show for only one session. It means, that, a judge may appear in one show, at some specified time, and stay a certain period there, and leave. After he leaves, he will never return to the show.
Goju is working in one of the Talent shows and he is very optimistic about his show. At the end of the day, one of the crews, who was inside with the judges, informed him that, all the judges were really tired, so, they just gave the same score to all the participants. Your inside man don't know how much each participants scored. But he was able to guess that, and he assures you that, the participant didn't score less than what he guessed. He has also given you a crucial information, how much generous the judges are. He has also given a generosity score to each of the judges, which is an integer between 1 and 1000000. The lower the generosity score, the higher he is supposed to grade. But you should remember that, the generosity score is just an assumption. It is possible that, a judge with lower generosity score, may grade lower than someone, whose generosity score is higher.
Now, Goju wants to know how much point each judge given to the participants. But, since he is very busy, he don't have time to solve this on his own. He asked you to solve it.
Input
First line of the input contains T(≤200), the number of test cases. Each test case starts with two integers J C(1≤J,C,100), the number of judges and the number of competitors. Next line contains C integers si(i = 1, 2, …, C) where si (1 ≤ si ≤ 1000000) is the score of the i-th participant, the crew guessed. All the participants are numbered from 1 to C. This is followed by J lines, where j-th of this contain three integers, pj, qj and gj, (1 ≤ gj ≤1000000, 1≤pj≤ qj≤ C)which means that, j-th judge only grades participants numbered between pj and qj (inclusive), and his generosity is gj.
There is a blank line before each test case.
Output
For each test case, output the case number, followed by J integers mj, how much points, each judge has given. All the scores are nonnegative integers and must fit inside a 32 bit signed integer. Since, there can be many solutions, he wants you to minimize ∑ mj * gj. If there are still more than one solution answer any one of them. You can assume that there will always be at least one solution.
Sample Input Output for Sample
Input
|
2 5 4 5 12 10 6 2 4 1 1 4 1 3 4 1 1 1 1 1 2 1 5 4 5 12 10 6 2 4 2 1 4 1 3 4 1 1 1 1 1 2 1 |
Case 1: 7 3 0 0 2 Case 2: 0 10 0 0 2 |
Problem setter: Manzurur Rahman Khan, Special Thanks:
Sabbir Yusuf Sanny