B. Полуфиналы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В турнире по бегу только что прошли два полуфинала. В каждом полуфинале участвовало n человек. В финал проходят n человек, определяемых следующим образом: из каждого полуфинала выбираются k человек (0 ≤ 2k ≤ n), показавших наилучший результат в своем полуфинале, а все остальные места в финале достаются тем, кто не попал в первые k в своем полуфинале, но попал в число n - 2k лучших среди остальных.

Организаторы турнира пока не определили число k, поэтому участники хотят знать, у кого еще остались шансы попасть в финал, а кому уже можно отправляться домой.

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 105) — количество участников в каждом полуфинале.

В следующих n строках записано по два целых числа ai и bi (1 ≤ ai, bi ≤ 109) — результаты i-ого участника (количество миллисекунд, за которое он пробежал дистанцию полуфинала) первого и второго полуфиналов соответственно. Все результаты различны. Последовательности a1, a2, ..., an и b1, b2, ..., bn упорядочены по возрастанию — в том порядке, в каком участники финишировали в соответствующем полуфинале.

Выходные данные

Выведите две строки, состоящие n символов, каждый из которых — «0» или «1». Первая строка должна соответствовать участникам первого полуфинала, а вторая — участникам второго полуфинала. i-ый символ в j-ой строке должен быть равен «1», если i-ый участник j-ого полуфинала имеет шансы пройти в финал, и «0» — иначе.

Примеры
Входные данные
4
9840 9920
9860 9980
9930 10020
10040 10090
Выходные данные
1110
1100
Входные данные
4
9900 9850
9940 9930
10000 10020
10060 10110
Выходные данные
1100
1100
Примечание

Рассмотрим первый пример. В каждом полуфинале участвовало 4 человека. Результаты первого полуфинала — 9840, 9860, 9930, 10040. Результаты второго полуфинала — 9920, 9980, 10020, 10090.

  • В случае k = 0 финалисты определяются исключительно по времени, поэтому дальше пройдут спортсмены с результатами 9840, 9860, 9920 и 9930.
  • В случае k = 1 из обоих полуфиналов гарантированно проходят победители (с результатами 9840 и 9920), а оставшиеся места определяются по времени (эти места достанутся спортсменам, пробежавшим за 9860 и 9930 миллисекунд).
  • В случае k = 2 из обоих полуфиналов проходят по два первых места, это спортсмены с результатами 9840, 9860, 9920 и 9980 миллисекунд.