Problem H
Printer Scheduling

There are $n$ files to be printed using $m$ identical printers. The files are numbered from $1$ to $n$. The printers are numbered from $1$ to $m$. Assuming each page takes one unit of time to print, for each file $i$, we have the following information:

• The number of pages it contains, ${p}_{i}$ (i.e. the time it takes to print file $i$);

• Ready time ${r}_{i}$ (the printing of the $i$ cannot be started before time ${r}_{i}$);

• Finish time ${d}_{i}$ (the printing for file $i$ has to be completed no later than time ${d}_{i}$).

We can assume that ${d}_{i} - {r}_{i} \geq {p}_{i}, 1 \le i \le n$. The printing process of a file can be interrupted between pages. In other words, while printing file $f$, the printer can interrupt this job and move to print a different file. The printing process of file $f$ can be resumed on any available printer afterwards. We can assume that:

• The time it takes to move the printing of a file from one printer to another printer is negligible.

• The starting time for printing the files is $0$.

A schedule of printing $n$ files using $m$ printers has to satisfy the following requirements:

• The printing of each file $j$ cannot be started before the ready time ${r}_{j}$;

• The printing of each file $j$ has to be completed no later than the finish time ${d}_{j}$;

• At any one time, the printing of file $j$ can be processed by at most one printer and the total amount of printing time of file $j$, i.e. its number of pages, is ${p}_{j}$;

• At any one time, each printer can only process at most one page of one file.

Your task is to find if there exists a schedule to print $n$ files using $m$ printers satisfying the requirements.

Input

The input consists of several datasets. The first line of the input contains the number of datasets which is a positive number and is not greater than $25$. The following lines describe the datasets.

Each dataset is described by the following lines:

• The first line contains two integers $n, m$ $(1 \leq n, m \leq 200)$;

• The ${i}^\textrm {th}$ line in the following $n$ line contains three positive integers ${p}_{i}$, ${r}_{i}$, and ${d}_{i}$, where ${p}_{i}, {r}_{i}, {d}_{i} \leq 30\, 000$ for $1 \le i \le n$.

Output

For each dataset, output YES if a valid schedule exists, NO otherwise. In case the solution does exist, describe an arbitrary valid schedule as below:

• The description contains $n$ blocks of lines, each provides instruction for printing a file.

• The first line of the ${i}^\textrm {th}$ block contains an integer ${\zeta }_{i}$ - the number of periods the ${i}^\textrm {th}$ file gets printed.

• Each of the rest ${\zeta }_{i}$ lines of this block contains three integers $x, y, z$ $({d}_{i} \leq x < y \leq {r}_{i}, 1 \leq z \leq m)$, meaning that the ${i}^\textrm {th}$ file is constantly printed from time $x$ to time $y$ by the ${z}^\textrm {th}$ printer.

Write an extra blank line after every test case.

Notes

• No two periods corresponding to one file can overlap.

• No two periods assigned to one printer (even from two different files) can be overlap.

• Your program must not provide any larger than $10$MB output for every single input file.

Clarification for Sample Output

Valid solutions exist for the former dataset, but do not for the latter one. As stated in the sample output:

• The first file is printed by the first printer from time $2$ to $4$, by the second printer from time $5$ to $7$.

• The fourth file is firstly printed by the first printer in one second, immediately switched to the second one for another second. From time $7$ to $8$, it gets printed by the first printer and then from $8$ to $10$ by the second printer.

2
4 2
4 2 7
3 3 8
3 4 7
5 1 10
4 1
4 2 7
3 3 8
3 4 7
5 1 10

YES
2
2 4 1
5 7 2
2
7 8 1
3 5 2
1
4 7 1
4
1 2 1
8 10 1
2 3 2
7 8 2

NO