реализовать сортировку (быстрая,слиянием)

[tori159]

В турнире по бегу только что прошли два полуфинала. В каждом полуфинале участвовало 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» — иначе.