Четыре полуфинала, двенадцать участников… Двадцать шестое место, конечно, не так уж и плохо, хотя хотелось и на финал. А теперь — карьера закончена, проект Team.GOV закрыт. Впереди дорога на поезде в родной Екатеринбург, окончание университета и магистратура во Франции…

Такие мысли крутились в голове Вадима Канторова, когда голос декана вернул его к реальности:
— Вадим, ты с кем в блоке поедешь?

В каждом блоке плацкартного вагона четыре купейных и два боковых места. В делегации УрГУ ровно 6n человек, поэтому декан купил билеты на места в соседних n блоках одного вагона. Каждый член делегации сказал, какое место ему больше нравится — купейное или боковое. Помимо этого, каждый человек хочет ехать в одном блоке со всеми своими друзьями. Нужно решить, кто в каком блоке поедет, чтобы никого при этом не обидеть.

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

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