Миша и Аня сидят на скучном уроке. Чтобы хоть как-то скрасить ожидание перемены, они придумали интересную игру. Для игры необходима лишь строка $$$s$$$ и число $$$k$$$ ($$$0 \le k < |s|$$$).

Игра начинается с того, что на строке $$$s$$$ отмечается подстрока длины 1, ее левая граница $$$l$$$ и правая граница $$$r$$$ равны $$$k$$$ (то есть вначале игры $$$l=r=k$$$). Далее игроки ходят по очереди, расширяя подстроку по следующим правилам:

• Игрок выбирает индексы $$$l^{\prime}$$$ и $$$r^{\prime}$$$ такие, что $$$l^{\prime} \le l$$$, $$$r^{\prime} \ge r$$$ и $$$s[l^{\prime}, r^{\prime}]$$$ лексикографически меньше $$$s[l, r]$$$. После этого изменяет значения $$$l$$$ и $$$r$$$ следующим образом: $$$l := l^{\prime}$$$, $$$r := r^{\prime}$$$.
• Аня ходит первой.
• Проигрывает тот, кто не может сделать ход.

Напомним, что подстрокой $$$s[l, r]$$$ ($$$l \le r$$$) строки $$$s$$$ будем называть непрерывную подпоследовательность символов начинающуюся в позиции $$$l$$$ и заканчивающуюся в позиции $$$r$$$. Например «ehn» — подстрока ($$$s[3, 5]$$$) строки «aaaehnsvz», а «ahz» — нет.

Миша и Аня играли в игру так увлеченно, что не заметили как к ним подошел учитель. К большому удивлению обоих, он не стал их отчитывать, а сказал, что может определить победителя до начала игры, зная лишь $$$s$$$ и $$$k$$$!

К сожалению, Миша и Аня не разбираются в теории игр, поэтому попросили Вас написать программу, которая по заданной $$$s$$$ определяет победителя для всех возможных $$$k$$$.