Вася и Петя играют в следующую игру. Они взяли некоторую последовательность символов и дальше получают из нее новые последовательности, отбрасывая несколько первых символов исходной последовательности (разрешается в том числе не отбрасывать ни одного символа, но не разрешается отбрасывать сразу все символы). Каждый называет по одной такой последовательности. Выигрывает тот, чья последовательность будет идти раньше в алфавитном порядке.
Напомним, что если мы сравниваем две последовательности, и у них первые K символов совпадают, а (K+1)-е символы отличаются, то раньше будет идти по алфавиту та, в которой (K+1)-й символ идет раньше по алфавиту. Если же одна последовательность является началом другой, то раньше по алфавиту идет более короткая из них.
Напишите программу, которая по данной последовательности определит, что нужно назвать Васе, чтобы не проиграть Пете.
В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.
В выходной файл выведите выигрышную последовательность.
Примеры
| Входные данные | Выходные данные | Комментарии |
| 4 MAMA | A | Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A |
| 4 ALLO | ALLO | Выигрышной является исходная строка |
| 5 BBABB | ABB |
|
Васю угостили конфетами, а он решил частью конфет поделиться со своим младшим братом Петей. Однако он хочет разделить конфеты не поровну, а по-братски.
Для этого Вася решил сыграть сам с собой в следующую игру. Он разложил конфеты на столе в несколько кучек, которые расположил в ряд. Если кучек не меньше двух, то из первой и последней в этом ряду кучек он выбирает ту, в которой меньше конфет. Пусть в наименьшей кучке оказалось B конфет. Тогда он B конфет перекладывает из первой кучки во вторую, и также B конфет перекладывает из последней кучки в предпоследнюю. При этом, естественно, одна из кучек (или даже две, если в первой и последней кучках конфет было поровну) становится пустой, и Вася забывает про ее существование. Он повторяет эти операции до тех пор, пока на столе не останется одна или две кучки.
Если останется одна кучка, то Вася все конфеты съест сам, а если две — то конфеты из первой кучки он съест сам, а из второй кучки отдаст Пете.
Напишите программу, которая по исходному распределению конфет в кучках определит, чем закончится Васина игра.
Начальное расположение кучек конфет будет описываться K парами чисел Ai, Ni, которые обозначают, что на столе выложено подряд Ni кучек конфет, по Ai конфет в каждой.
Во входном файле задано сначала число K (1≤K≤105). Затем идет K пар чисел Ai, Ni (1≤Ai≤100, 1≤Ni≤108). Общее количество кучек так же не превысит 108.
В выходной файл выведите сначала 1 или 2 — количество кучек конфет, которые останутся в конце игры. Затем выведите соответственно одно или два числа — количества конфет в оставшихся кучках.
Комментарии к примерам тестов
1. Исходно конфеты расположены в следующих кучках: 2 кучки по 2 конфеты, две кучки из 3-х конфет и одна из 2-х:
2 2 3 3 2
Далее по 2 конфеты перекладывается из 1 и 5кучек во 2 и 4, при этом и 1 и 5 кучки становятся пустыми, т.е. на столе остается только 3 кучки:
4 3 5
Теперь по 4 конфеты перекладываются из 1 и 3 кучек во 2-ю и на столе остается две кучки, игра заканчивается с результатом 11 1
2. Изначальноу нас 7 кучек по 1 конфете в каждой. После первого перекладывания получится следующая конфигурация:
2 1 1 1 1 2
После второго:
3 1 3
После третьего останется одна кучка с 7 конфетами.
3. Изначально имеется 6 кучек:
1 2 3 4 5 5
После первого перекладывания получим:
3 3 4 6 4
После второго:
6 4 9 1
После третьего:
5 5 10
Наконец, получим:
15 5
3 2 2 3 2 2 1
2 11 1
1 1 7
1 7
5 1 1 2 1 3 1 4 1 5 2
2 15 5