В турнире по бегу только что прошли два полуфинала. В каждом полуфинале участвовало n человек. В финал проходят n человек, определяемых следующим образом: из каждого полуфинала выбираются k человек (0 ≤ 2k ≤ n), показавших наилучший результат в своем полуфинале, а все остальные места в финале достаются тем, кто не попал в первые k в своем полуфинале, но попал в число n - 2k лучших среди остальных.
Организаторы турнира пока не определили число k, поэтому участники хотят знать, у кого еще остались шансы попасть в финал, а кому уже можно отправляться домой.
Выходные данные
Выведите две строки, состоящие n символов, каждый из которых — «0» или «1». Первая строка должна соответствовать участникам первого полуфинала, а вторая — участникам второго полуфинала. i-ый символ в j-ой строке должен быть равен «1», если i-ый участник j-ого полуфинала имеет шансы пройти в финал, и «0» — иначе.
Примечание
Рассмотрим первый пример. В каждом полуфинале участвовало 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 миллисекунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
9840 9920
9860 9980
9930 10020
10040 10090
|
1110
1100
|
|
2
|
4
9900 9850
9940 9930
10000 10020
10060 10110
|
1100
1100
|