Server Time: Fri Sep 25, 2020 12:38 am
Welcome ( logout
J - Aladdin and the Grand Feast
  PDF (English) Ranklist
Time Limit: 1 second(s) Memory Limit: 32 MB

As Aladdin invited all people in the town to share his happiness and joy, all people came to meet him. And he arranged a Grand Feast for them. There were many delicious food items, fruits, drinks, sweets and a lot more.

As like a regular function, each person had a particular arrival time (ai) and departure time (di). It means, he can start eating in time ai, and cannot eat after time di - 1. And of course not all of them wanted to have the same amount of food. So, a person wanted to eat exactly fi unit of food and of course within his arrival and departure time. Note that a person can have one unit of food in one time unit.

But there were only t tables, and each table had c chairs. So, in a single time unit, at most t * c people can eat together. But in the next time unit, a new group of people can replace them (takes negligible amount of time). So, Aladdin made a schedule (when to eat and where to sit) for the persons such that all became happy.

Now your task is to do the same. You are given all the necessary information, your task is to find a schedule for the persons such that everyone becomes happy. A person is happy if he gets exactly fi unit of food in his time interval. Assume that the feast will last long until all the persons are gone.


Input starts with an integer T (≤ 30), denoting the number of test cases.

Each case starts with a blank line. Next line contains four integers: n t c e (1 ≤ n ≤ 50, 1 ≤ t, c ≤ 5, 2 ≤ e ≤ 104), where n denotes the number of invited people and e denotes the end time of the feast. Each of the next n lines contains three integers: ai di fi (1 ≤ ai < di ≤ e, 1 ≤ fi ≤ di - ai).


For each case, print the case number and 'Yes' if it's possible to make everyone happy. Print 'No' otherwise.

If the result is yes, then print additional e-1 lines. The ith line should contain the persons sitting in the tables in ith time in the following format:

1)      First 26 persons should be identified by the lower case English letters; the next ones should be identified by capital letters (in same order). So, person 6 is 'f', and person 28 is 'B'.

2)      Each table should be denoted by c characters, where a '.' denotes the chair in that table is empty; otherwise it should contain the person who is eating here. Print all the tables in a single line. Two tables should be separated by a '|' character. See the samples for more details.

There can be multiple solutions, any valid one will do.

Sample Input

Output for Sample Input



1 1 2 3

1 3 2


7 2 3 5

1 4 3

1 5 4

1 5 4

1 2 1

2 4 2

2 5 2

3 5 1


4 1 3 3

1 3 2

1 3 1

1 3 2

1 3 2

Case 1: Yes



Case 2: Yes





Case 3: No


1)      Dataset is huge, use faster I/O methods.

2)      This is a special judge problem; wrong output format may cause 'Wrong Answer'.

Problem Setter: Jane Alam Jan
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan