VK Cup 2021 - Квалификация (Engine) |
---|
Finished |
Немногие знают, что сотрудники ВКонтакте могут менять цвет подсветки в куполе знаменитого Дома Зингера, где расположена штаб-квартира ВКонтакте. Для этого нужно всего лишь отправить сообщение с цветом в специальный чат «Зингер | color», а бот его распознает и сменит подсветку. При этом на время городских мероприятий смена цвета блокируется.
Формально, бот обрабатывает три типа сообщений:
Вам дана история сообщений, полученных ботом, в хронологическом порядке. Считайте, что перед получением первого сообщения купол подсвечивается голубым (blue), а изменение цвета не заблокировано.
В качестве эксперимента было решено поддержать в боте эффективную обработку редактирования сообщений. Вам дана последовательность пар вида $$$(i, msg)$$$, означающих, что $$$i$$$-е в хронологическом порядке сообщение было отредактировано и теперь имеет вид $$$msg$$$. Обратите внимание, что редактироваться может любое сообщение, и при редактировании сообщения бот должен обработать всю историю сообщений заново (в частности, перед обработкой первого сообщения цвет купола голубой, а изменение цвета не заблокировано).
Определите, какой цвет будет у купола Дома Зингера до первой операции редактирования, а также после каждой операции редактирования.
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — число сообщений, полученных ботом.
В следующих $$$n$$$ строках заданы сообщения, полученные ботом, в хронологическом порядке, по одному сообщению в строке. Каждое сообщение — строка из следующего набора: lock, unlock, red, orange, yellow, green, blue, indigo, violet. Сообщения пронумерованы от $$$1$$$ до $$$n$$$.
В следующей строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — число операций редактирования сообщений.
В следующих $$$t$$$ строках заданы операции редактирования в хронологическом порядке, по одной в строке. Каждая операция — пара из номера сообщения $$$i$$$ ($$$1 \le i \le n$$$) и его нового содержимого $$$msg$$$, также принадлежащего набору lock, unlock, red, orange, yellow, green, blue, indigo, violet.
Выведите $$$t+1$$$ строку: цвет купола до первой операции редактирования, а также после каждой операции редактирования в хронологическом порядке.
7 red violet unlock red orange lock indigo 6 5 green 6 lock 6 yellow 4 lock 1 lock 5 unlock
orange green green indigo violet blue indigo
1 red 8 1 lock 1 unlock 1 blue 1 unlock 1 unlock 1 lock 1 yellow 1 lock
red blue blue blue blue blue blue yellow blue
Name |
---|