In your opinion, what is a student’s favorite activity? Studying? OK, that
is the number one priority. And the number two priority is tasty lunch, of
course. Unfortunately, the university authorities don’t understand
students at all and the lunch break lasts for forty minutes only.
The forty minutes should include standing in a line, choosing favorite
dishes and eating them. The students come up with lots of tricks to spend
less time in a line and knowing the right people becomes very important...
Alexey’s lecture has just finished and he is rushing to the university
canteen. The problem is, other students finished earlier and there are
huge lines in front of canteen counters. To wait or not to wait?
Some people might feel lost but Alexey arms himself with his good old
laptop and starts writing a program that would say for each student the
time when he would leave the line. Can you give it a try?
Ural FU canteen has two counters that work simultaneously, so there
is a line in front of each counter. If a student joins a line, he can’t
move to the other one. The cashiers are very professional, so it takes
them one second to serve one customer. At some moments of time a new group
of students enters the canteen. We can assume that all students in the
group enter at the same time but in turn: the first student from the
group, then the second one and so on. When each student enters the canteen
he can stand either at the end of a line or, if he knows some student that
is already in the line, right behind him. Moreover, each student tries to
get the most optimal place, that is, such place that the number of people
in front of him is minimum. If the position in the right line and the
position in the left line are identically optimal, a student always
chooses the right line. If at the same moment a student served by a
cashier leaves a line and new group of students enters the canteen, you
should consider that the first action occurs earlier.
Input
The first line contains integers n and m that are the number of
students and the number of groups of students (5 ≤ n ≤ 1000;
1 ≤ m ≤ n). The students are enumerated with integers from 1 to n.
Next n lines contain the information about the students. The (i + 1)'th
line of input data contains list of numbers of students which will let i’th
student stand behind them in a line. It is guaranteed that for each
student this list has at most 100 numbers and doesn’t contain this
student’s own number. The list ends with number 0. If the i’th student
will let the j’th student stand behind him in a line, this is not means
that the j’th student will let the i’th student too.
Then an information about groups of students entering the canteen follows.
The description of each group consists of two lines. The first line
contains integers ti and ki that are the time when the group enters
the canteen and the number of students in the group
(1 ≤ ti ≤ 109; 1 ≤ ki ≤ n). The second line of the
description contains ki integers: the numbers of students in the group
listed in the order they enter the canteen. All groups are listed by
increasing ti. It is guaranteed that each student visits the canteen
exactly once.
Output
Output n lines. The i’th one should contain the time when the i’th
student leaves the line and the line he stands in (“left” for the left
line and “right” for the right one).
Sample
input | output |
---|
5 1
0
0
0
0
1 0
1 5
1 2 3 4 5
| 2 right
2 left
4 right
3 left
3 right
|
Problem Author: Alexey Kungurtsev
Problem Source: Ural Regional School Programming Contest 2013