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

Ural SU contest. Petrozavodsk training camp. Summer 2010

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Лидер армии магов

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
После того как правительство королевства Магов собрало новую армию, на повестку дня встал вопрос о выборе её единоличного лидера. Два мудрейших Наставника — глава королевства Загамиус и лич Сандро — решили провести собеседование с достойными кандидатами. Они разошлись по разным кабинетам и стали независимо друг от друга вызывать к себе нужного мага или же отпускать того, с кем они уже пообщались. При этом как Сандро, так и Загамиус могли вызывать к себе одного и того же мага несколько раз, а в их кабинетах могли находиться несколько магов одновременно.
Оба Наставника заранее определили порядок, в котором они будут вызывать и отпускать магов. Если в некоторый момент времени оба Наставника могут совершить очередное действие, то один из них совершает его, а другой ждёт. В некоторых случаях только один Наставник может совершить очередное действие. Например, если Сандро вызовет к себе мага a, а он в это время будет находиться в кабинете Загамиуса, то Сандро придётся ждать до тех пор, пока маг a не освободится.
К сожалению, может возникнуть ситуация, в которой оба Наставника будут ждать друг друга. В этом случае они не смогут выбрать лидера своей армии и проиграют ещё не начавшуюся войну. Вы должны определить, возможно ли такое глупое поражение.

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

В первой строке записано целое число t (1 ≤ t ≤ 10) — количество тестов. Каждый тест начинается строкой, в которой через пробел записаны целые числа n, m и k (1 ≤ n, m, k ≤ 1 000) — количество записей в плане собеседования Сандро, количество записей в плане собеседования Загамиуса и количество магов в новой армии. Маги занумерованы целыми числами от 1 до k. Далее в n строках содержится план Сандро: в каждой строке через пробел записаны знак «+» или «-» и целое число i (1 ≤ ik). Знак «+» означает, что Сандро собирается пригласить i-го мага, а знак «-» — отпустить его. Далее в m строках содержится план Загамиуса в таком же формате. В обоих планах каждый маг покидает кабинет, только если он там находится. Гарантируется, что ни один Наставник не вызывает мага, если он уже находится в его кабинете. Также известно, что в случае выполнения всех запланированных действий в кабинетах Наставников не останется ни одного мага.

Результат

Для каждого теста в отдельной строке выведите «:-)», если оба Наставника обязательно выполнят свой план и выберут лидера армии. В противном случае выведите «:-(».

Пример

исходные данныерезультат
2
4 4 2
+ 1
+ 2
- 2
- 1
+ 1
+ 2
- 2
- 1
4 4 2
+ 1
+ 2
- 1
- 2
+ 2
+ 1
- 2
- 1
:-)
:-(
Автор задачи: Евгений Курпилянский
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2010
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1844. Лидер армии магов