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

1859. Последний сезон Team.GOV

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Четыре полуфинала, двенадцать участников… Двадцать шестое место, конечно, не так уж и плохо, хотя хотелось и на финал. А теперь — карьера закончена, проект Team.GOV закрыт. Впереди дорога на поезде в родной Екатеринбург, окончание университета и магистратура во Франции…
Такие мысли крутились в голове Вадима Канторова, когда голос декана вернул его к реальности:
— Вадим, ты с кем в блоке поедешь?
В каждом блоке плацкартного вагона четыре купейных и два боковых места. В делегации УрГУ ровно 6n человек, поэтому декан купил билеты на места в соседних n блоках одного вагона. Каждый член делегации сказал, какое место ему больше нравится — купейное или боковое. Помимо этого, каждый человек хочет ехать в одном блоке со всеми своими друзьями. Нужно решить, кто в каком блоке поедет, чтобы никого при этом не обидеть.

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

В первой строке записано целое число n (1 ≤ n ≤ 1000). Во второй строке дана последовательность битов длины 6n. i-й бит в этой последовательности равен единице, если i-й человек хочет ехать на купейном месте, и нулю — если на боковом месте. В следующей строке записано целое число m — количество пар друзей (0 ≤ m ≤ 15n). Далее в m строках перечислены все эти пары — целые числа aj и bj (1 ≤ aj < bj ≤ 6n). Все перечисленные пары различны.

Результат

Выведите n строк. В каждой из них выведите через пробел в произвольном порядке номера членов делегации, которые должны ехать в одном блоке вагона. Если существует несколько решений, можно вывести любое из них. Гарантируется, что хотя бы одно решение существует.

Пример

исходные данныерезультат
2
001111001111
2
1 2
7 8
1 2 3 4 5 6
7 8 9 10 11 12
Автор задачи: Михаил Рубинчик (идея — Дмитрий Кузнецов)
Источник задачи: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011