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 re- quire 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 eval- uates 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 activ- ities, may think that this is a really easy job both for the judges and the participants. Because, all the par- ticipants 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
2/2 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 answer any one of them. You can assume that there will always be at least one solution. Sample Input 2 54 5 12 10 6 241 141 341 111 121 54 5 12 10 6 242 141 341 111 121 Sample Output Case 1: 7 3 0 0 2 Case 2: 0 10 0 0 2 ∑ mj ∗ gj . If there are still more than one solution