The Hotel Room Riddle

Problem code: HS08RIDL

You have, no doubt, many times come across riddles in which you are given some information about a set of people, houses, and other objects, and you are to figure out something more about them, e.g. the place where each person lives. The Zebra Puzzle is one of the best known examples of this sort of mind bender.

In this problem the riddle is much simpler. So simple, in fact, that your computer should be able to solve it... with a little help on your part.

Input

The input consists of a sequence of lines. The first line contains the following text:

n people are staying at a hotel which has k floors.

where n and k are some positive integers, 2 <= k <= n. Each of the next n lines introduces exactly one hotel guest, as follows.

The line introducing the first guest only provides information about this person's name:

One of the guests is called [Name 1].

The names of the people staying at the hotel are sequences of exactly four characters of the Latin alphabet written in lower case starting with a capital letter (e.g. John, Jack, or Mary). However, many foreigners are staying at the hotel, so some of the names may sound rather strange to you. The names of all the people staying at the hotel are different.

Then, for the i-th person, with 2 <= i <= n, we learn exactly one piece of information about the floor (storey) on which this person is staying. This is given in the form of exactly one of the following lines:

[Name i]'s room is on the same floor as [Name j]'s.
[Name i]'s room is not on the same floor as [Name j]'s.
[Name i]'s room is lower than [Name j]'s.
[Name i]'s room is higher than [Name j]'s.

where [Name j] refers to the name of some previously introduced person (j < i).

Output

Decide whether there exists a solution to the riddle which satisfies the provided constraints. If so, for each of the guests staying at the hotel, output a line containing the name of the guest, followed by a space and the number of the floor on which this person's room is located. Floors are numbered from 1 to k. The order of lines at output is irrelevant. If there does not exist a solution to the riddle, output the text "No solution.".

Example 1

Input:
5 people are staying at a hotel which has 3 floors.
One of the guests is called John.
Mary's room is lower than John's.
Bill's room is not on the same floor as Mary's.
Kate's room is higher than John's.
Paul's room is on the same floor as Bill's.

Output:
Mary 1
John 2
Bill 2
Kate 3
Paul 2

This is not the only correct solution to the riddle. The other solution, in which Bill and Paul are staying on the third floor, will also be judged correct.

Example 2

Input:
4 people are staying at a hotel which has 2 floors.
One of the guests is called John.
Mary's room is lower than John's.
Bill's room is not on the same floor as Mary's.
Kate's room is higher than Bill's.

Output:
No solution.

Points

You can score 10 points for this problem. The program will be tested against 10 datasets, for solving each of which you will be awarded 1 point.

---

Added by:	Adrian Kosowski
Date:	2008-10-25
Time limit:	1s-5s
Source limit:	50000B
Languages:	SED C99 strict C++ 4.0.0-8 C++ 4.3.2 TCL SCALA NEM PHP SCM guile LISP sbcl LISP clisp ERL TECS TEXT DOC PDF PS PERL 6 JS
Resource:	High School Programming League 2008/2009