Как вы думаете, чем больше всего любят заниматься студенты? Учиться? Ну
это, разумеется, на первом месте. А вот второе место в списке их
приоритетов, несомненно, занимает вкусный обед. Правда, руководство
университета совершенно не понимает студентов, поэтому большая перемена
длится всего 40 минут. А ведь нужно успеть отстоять очередь, выбрать
любимые блюда и скушать их. Чтобы уменьшить время нахождения в очереди,
студенты идут на различные хитрости, и многое здесь решают связи...
У студента Лёши только что закончилась пара, и он спешит в университетскую
столовую. К сожалению, других студентов отпустили раньше, и в кассы уже
выстроились многометровые очереди. Ждать или не ждать? Кто-то бы начал
гадать, но только не Лёша! Молниеносным движением руки он выхватывает
ноутбук из рюкзака и начинает писать программу, которая для каждого
студента сможет сказать, когда тот покинет очередь. Может быть, вы тоже
попробуете?
В столовой УрФУ одновременно работают две кассы, к каждой из которых
выстраивается своя очередь. Встав в одну из очередей, студент уже не может
перейти в другую. На кассах сидят опытные кассирши, поэтому время
обслуживания одного студента составляет одну секунду. В некоторые моменты
времени в столовую заходит очередная группа студентов. Следует считать, что
все они заходят одновременно, но тем не менее по очереди: сначала первый
студент из группы, потом второй и так далее.
Зашедший в столовую студент может встать или в конец любой из очередей,
или если кто-то из его знакомых стоит в очереди, то непосредственно за ним.
При этом он пытается занять наиболее оптимальное место, то есть такое, что
количество человек в очереди перед ним будет минимальным. Если позиция в
правой очереди и позиция в левой очереди одинаково оптимальны, студент
всегда выбирает правую очередь.
Если в один и тот же момент времени студент, обслуженный кассиром,
покидает очередь, а в столовую заходит новая группа студентов, следует
считать, что первое событие происходит раньше.
Исходные данные
В первой строке даны целые числа n и m — количество студентов и
количество групп студентов соответственно (5 ≤ n ≤ 1000; 1 ≤ m ≤ n).
Студенты пронумерованы целыми числами от 1 до n.
В следующих n строках находится информация о студентах. В (i + 1)-й
строке дан список номеров тех студентов, после которых i-й студент
может встать в очередь. Гарантируется, что для каждого студента список
содержит не более 100 чисел и не содержит собственного номера студента.
Список завершается числом 0. Если студент i может встать в очередь после
студента j, это не означает, что и студент j может встать в очередь
после студента i.
Далее следует информация о группах студентов, пришедших в столовую.
Описание каждой группы состоит из двух строк. В первой из них записаны
целые числа ti и ki — время, когда данная группа зашла в столовую,
и количество студентов в этой группе (1 ≤ ti ≤ 109; 1 ≤ ki ≤ n).
Во второй строке описания группы записаны 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