Как вы думаете, чем больше всего любят заниматься студенты? Учиться? Ну это, разумеется, на первом месте. А вот второе место в списке их приоритетов, несомненно, занимает вкусный обед. Правда, руководство университета совершенно не понимает студентов, поэтому большая перемена длится всего 40 минут. А ведь нужно успеть отстоять очередь, выбрать любимые блюда и скушать их. Чтобы уменьшить время нахождения в очереди, студенты идут на различные хитрости, и многое здесь решают связи...

У студента Лёши только что закончилась пара, и он спешит в университетскую столовую. К сожалению, других студентов отпустили раньше, и в кассы уже выстроились многометровые очереди. Ждать или не ждать? Кто-то бы начал гадать, но только не Лёша! Молниеносным движением руки он выхватывает ноутбук из рюкзака и начинает писать программу, которая для каждого студента сможет сказать, когда тот покинет очередь. Может быть, вы тоже попробуете?

В столовой УрФУ одновременно работают две кассы, к каждой из которых выстраивается своя очередь. Встав в одну из очередей, студент уже не может перейти в другую. На кассах сидят опытные кассирши, поэтому время обслуживания одного студента составляет одну секунду. В некоторые моменты времени в столовую заходит очередная группа студентов. Следует считать, что все они заходят одновременно, но тем не менее по очереди: сначала первый студент из группы, потом второй и так далее. Зашедший в столовую студент может встать или в конец любой из очередей, или если кто-то из его знакомых стоит в очереди, то непосредственно за ним. При этом он пытается занять наиболее оптимальное место, то есть такое, что количество человек в очереди перед ним будет минимальным. Если позиция в правой очереди и позиция в левой очереди одинаково оптимальны, студент всегда выбирает правую очередь. Если в один и тот же момент времени студент, обслуженный кассиром, покидает очередь, а в столовую заходит новая группа студентов, следует считать, что первое событие происходит раньше.

В первой строке даны целые числа n и m — количество студентов и количество групп студентов соответственно (5 ≤ n ≤ 1000; 1 ≤ m ≤ n). Студенты пронумерованы целыми числами от 1 до n.

В следующих n строках находится информация о студентах. В (i + 1)-й строке дан список номеров тех студентов, после которых i-й студент может встать в очередь. Гарантируется, что для каждого студента список содержит не более 100 чисел и не содержит собственного номера студента. Список завершается числом 0. Если студент i может встать в очередь после студента j, это не означает, что и студент j может встать в очередь после студента i.

Далее следует информация о группах студентов, пришедших в столовую. Описание каждой группы состоит из двух строк. В первой из них записаны целые числа t_i и k_i — время, когда данная группа зашла в столовую, и количество студентов в этой группе (1 ≤ t_i ≤ 10⁹; 1 ≤ k_i ≤ n). Во второй строке описания группы записаны k_i целых чисел — номера студентов в этой группе, перечисленные в порядке их входа в столовую. Описания групп упорядочены по возрастанию t_i. Гарантируется, что каждый студент посещает столовую ровно один раз.

Выведите n строк. i-я строка должна содержать время, когда i-й студент покинет очередь, и очередь, в которой он стоял («left» для левой очереди и «right» для правой).