Xuexue is a pretty monkey living in the Emei mountain. She is extremely thirsty during time 2 and time 9 everyday, so she must drink 2 units water during this period. She may drink water more than once, as long as the total amount of water she drinks is exactly 2 - she never drinks more than she needs. Xuexue drinks 1 unit water in one time unit, so she may drinks from time 2 to time 4, or from 3to5,...,orfrom7to9,orevendrinkstwice: firstfrom2to3,thenfrom8to9. Butshecan’tdrink from 1 to 3 since she’s not thirsty at time 1, and she can’t drink from 8 to 10, since she must finish at time 9. There are many monkeys like Xuexue: we use a triple (v, a, b) to describe a monkey who is thirsty during time a and b, and must drink exactly v units of water during that period. Every monkey drinks at the same speed (i.e. one unit water per unit time). Unfortunately, people keep on doing something bad on the environment in Emei Mountain. Even- tually, there are only one unpolluted places for monkeys to drink. Further more, the place is so small that at most m monkeys can drink water together. Monkeys like to help each other, so they want to find a way to satisfy all the monkeys’ need. Could you help them? Input The input consists of several test cases. Each case contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 5), followed by n lines of three integer numbers (v,a,b), where 0 ≤ v,a,b ≤ 50,000, a < b, 0 < v ≤ b−a. The last test case is followed by a single zero, which should not be processed. There are at most 50 test cases. Output For each test case, print the case number and whether there is a solution. If there is a solution, the following n lines describe the solution: one monkey on a separate line. The first number k means the monkey drinks water for k times. The following k pairs (ai,bi) means the monkey drinks from ai to bi (ai < bi). The pairs should be sorted in ascending order, and ai should not be equal to ai+1 for 1 ≤ i ≤ k − 1 (otherwise these two drinking periods could be combined). If more than one solution exists, any one is acceptable. Note that there should be exactly one space between k and pairs (ai,bi), but no space within each pair. Sample Input 31 229 235 358 21 459 4 8 12 52 213 235 257 217
2/2 426 0 Sample Output Case 1: Yes 2 (2,3) (8,9) 1 (3,5) 1 (5,8) Case 2: No Case 3: Yes 1 (1,3) 1 (3,5) 1 (5,7) 2 (1,2) (6,7) 1 (2,6)