2016 ACM ICPC Asia Nha Trang Regional Contest Replay

Start

2017-10-15 12:00 UTC

2016 ACM ICPC Asia Nha Trang Regional Contest Replay

End

2017-10-15 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -427 days 12:35:21

Time elapsed

5:00:00

Time remaining

0:00:00

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 conatins, ${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}, i = 1, 2,..., 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 serveral datasets. The first liine of the input conatins the number of datasets whifch is a positive number and is not greater than $100$. 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}^{th}$ line in the following $n$ line contains three positive integers ${p}_{i}, {r}_{i}, {d}_{i}, ({p}_{i}, {r}_{i}, {d}_{i} \leq 30000$ for $i = 1, 2,..., n$)

Output

For each dataset, write in one line YES if 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}^{th}$ block contains an integer ${\zeta }_{i}$ - the number of periods the ${i}^{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}^{th}$ file is constantly printed from moment $x$ to moment $y$ by the ${z}^{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 10MB output for every single input file.

Clarificaion 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 moment $2$ to $4$, by the second printer from moment $5$ to $7$.

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

Sample Input 1 Sample Output 1
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