ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2009. Очереди в столовой

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Как вы думаете, чем больше всего любят заниматься студенты? Учиться? Ну это, разумеется, на первом месте. А вот второе место в списке их приоритетов, несомненно, занимает вкусный обед. Правда, руководство университета совершенно не понимает студентов, поэтому большая перемена длится всего 40 минут. А ведь нужно успеть отстоять очередь, выбрать любимые блюда и скушать их. Чтобы уменьшить время нахождения в очереди, студенты идут на различные хитрости, и многое здесь решают связи...
У студента Лёши только что закончилась пара, и он спешит в университетскую столовую. К сожалению, других студентов отпустили раньше, и в кассы уже выстроились многометровые очереди. Ждать или не ждать? Кто-то бы начал гадать, но только не Лёша! Молниеносным движением руки он выхватывает ноутбук из рюкзака и начинает писать программу, которая для каждого студента сможет сказать, когда тот покинет очередь. Может быть, вы тоже попробуете?
В столовой УрФУ одновременно работают две кассы, к каждой из которых выстраивается своя очередь. Встав в одну из очередей, студент уже не может перейти в другую. На кассах сидят опытные кассирши, поэтому время обслуживания одного студента составляет одну секунду. В некоторые моменты времени в столовую заходит очередная группа студентов. Следует считать, что все они заходят одновременно, но тем не менее по очереди: сначала первый студент из группы, потом второй и так далее. Зашедший в столовую студент может встать или в конец любой из очередей, или если кто-то из его знакомых стоит в очереди, то непосредственно за ним. При этом он пытается занять наиболее оптимальное место, то есть такое, что количество человек в очереди перед ним будет минимальным. Если позиция в правой очереди и позиция в левой очереди одинаково оптимальны, студент всегда выбирает правую очередь. Если в один и тот же момент времени студент, обслуженный кассиром, покидает очередь, а в столовую заходит новая группа студентов, следует считать, что первое событие происходит раньше.

Исходные данные

В первой строке даны целые числа n и m — количество студентов и количество групп студентов соответственно (5 ≤ n ≤ 1000; 1 ≤ mn). Студенты пронумерованы целыми числами от 1 до n.
В следующих n строках находится информация о студентах. В (i + 1)-й строке дан список номеров тех студентов, после которых i-й студент может встать в очередь. Гарантируется, что для каждого студента список содержит не более 100 чисел и не содержит собственного номера студента. Список завершается числом 0. Если студент i может встать в очередь после студента j, это не означает, что и студент j может встать в очередь после студента i.
Далее следует информация о группах студентов, пришедших в столовую. Описание каждой группы состоит из двух строк. В первой из них записаны целые числа ti и ki — время, когда данная группа зашла в столовую, и количество студентов в этой группе (1 ≤ ti ≤ 109; 1 ≤ kin). Во второй строке описания группы записаны ki целых чисел — номера студентов в этой группе, перечисленные в порядке их входа в столовую. Описания групп упорядочены по возрастанию ti. Гарантируется, что каждый студент посещает столовую ровно один раз.

Результат

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

Пример

исходные данныерезультат
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
Автор задачи: Алексей Кунгурцев
Источник задачи: Уральская региональная командная олимпиада по программированию 2013