Гвозден и Вукашин участвует в шахматной олимпиаде и хочет устроить тимбилдинг. Он собрал \(n\) игроков, где \(n\) является степенью \(2\), и предложил заняться спортом. Гвозден и Вукашин входит в число этих \(n\) человек.
Одно из спортивных мероприятий — перетягивание каната. Для каждого \(1\leq i \leq n\) сила \(i\)-го игрока равна \(s_i\). Гвозден будет проводить раунды на выбывание до тех пор, пока не останется один игрок. Мы назовем этого игрока абсолютным победителем.
В каждом раунде:
- Предположим, что \(m>1\) игроков все еще в игре, где \(m\) является степенью \(2\).
- Эти \(m\) игроков разбиваются на две команды равных размеров (т. е. по \(m/2\) в каждой команде). Сила команды равна сумме сил всех игроков.
- Если команды имеют равные значения силы, то Гвозден выбирает, кто выигрывает; иначе выигрывает более сильная команда.
- Все игроки в проигравшей команде выбывают, и остается \(m/2\) игроков.
Гвозден может выбирать, как образуются команды на в каждом раунде, и команду-победителя в случае равных сил. Гвозден знает силу каждого игрока и ему интересно, кто может стать абсолютным победителем, а кто не может. Ответьте на этот вопрос.
Выходные данные
В единственной строке выведите бинарную строку \(s\) длины \(n\): \(i\)-й символ \(s\) должен быть равен \(1\), если \(i\)-й игрок может стать абсолютным победителем, и \(0\) в противном случае.
Примечание
В первом примере игроки \(1\) и \(4\), имеющие силы \(60\) и \(87\), могут стать абсолютными победителями.
Опишем процесс для игрока \(1\). Изначально мы разделим игроков на команды \([1,3]\) и \([2,4]\). Силы команд равны \(60+59=119\) и \(32+87=119\). Так как они равны, то Гвозден может выбрать, кто выбывает, пусть это будет вторая команда.
Остаются два игрока \(1\) и \(3\). Так как у \(1\) сила больше (\(60>59\)), то он побеждает и становится абсолютным победителем.
В третьем примере силы остающихся игроков может быть \([8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8]\). Любой игрок с силой \(8\) может стать абсолютным победителем, и можно показать, что все остальные не могут.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
60 32 59 87
|
1001
|
|
2
|
4
100 100 100 100
|
1111
|
|
3
|
8
8 8 8 8 4 4 4 4
|
11110000
|
|
4
|
32
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
|
00000000000000001111111111111111
|
|
5
|
16
1 92875987325987 1 1 92875987325986 92875987325985 1 92875987325988 92875987325990 92875987325989 1 1 92875987325984 92875987325983 1 1
|
0100110111001000
|