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.

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 t_i and k_i that are the time when the group enters the canteen and the number of students in the group (1 ≤ t_i ≤ 10⁹; 1 ≤ k_i ≤ n). The second line of the description contains k_i integers: the numbers of students in the group listed in the order they enter the canteen. All groups are listed by increasing t_i. It is guaranteed that each student visits the canteen exactly once.

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).