Задача №1861. Мышата
У мышонка сегодня день рождения! По этому поводу он решил собрать друзей. Друзья приходят к мышонку и садятся вокруг круглого стола.
Вначале за столом сидит один мышонок, празднующий день рождения. Все его друзья приходят по одному и садятся слева или справа от кого-то из уже сидящих за столом.
Определите, в каком порядке будут сидеть друзья мышонка, когда все придут.
В первой строке записано имя мышонка, празднующего день рождения, и одно число \(n\) — количество его друзей (\(1 \le n \le 100\,000\)). В каждой из следующих \(n\) строк записаны имя \(a\) очередного приходящего гостя, имя \(b\) того, рядом с кем он садится, и буква «r», если \(a\) садится справа от \(b\), или буква «l», если слева.
Все имена будут различными строками из латинских букв длиной от 1 до 10 символов. Строчные и заглавные буквы следует считать различными. Гарантируется, что тот, рядом с кем садится очередной гость, уже сидит за столом.
Выведите \(n+1\) строку, по одному имени в каждой строке. Выводите сидящих за столом в порядке движения вправо, начиная с мышонка.
Jerry 4 Tuffy Jerry l Tom Jerry r Spike Tom l Quacker Jerry r
Jerry Quacker Spike Tom Tuffy