| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Петя и Вася играют в шпионов. Главная цель этой игры --- обмениваться секретными сообщениями, сохраняя конспирацию. Для этого Петя и Вася используют особый шифр.
Метод шифровки и дешифровки очень прост: каждой букве $\alpha$ русского алфавита сопоставляется некоторая последовательность букв латинского алфавита $p_{\alpha}$. Затем в сообщении все вхождения каждой буквы $\alpha$ заменяются на соответствующее ей $p_{\alpha}$. А чтобы совсем запутать вероятного противника, Петя и Вася договорились, что значимым в исходном сообщении должно быть только лексикографически минимальное слово. Напомним, что строка $a$ лексикографически меньше строки $b,ドル если существует такое $i,ドル что для любого $j < i$ выполняется равенство $a_j = b_j$ и при этом $a_i < b_i,ドル или строка $a$ является префиксом строки $b$.
Недавно Петя предложил Васе использовать следующую таблицу преобразования букв:
Однако теперь Вася не успевает дешифровывать сообщения Пети вовремя и просит вас помочь ему --- определить номер слова, которое до шифрования, записанное русскими буквами, было лексикографически минимальным.
Первая строка входного файла содержит одно целое число $n$ (1ドル \le n \le 1000$) --- количество слов в шифровке. Следующие $n$ строк содержат по одному слову, состоящему из маленьких латинских букв --- текст шифровки, которую получил Вася. Длина слова не превышает 50ドル$.
В выходной файл выведите номер слова шифровки, которое до шифрования было лексикографически минимальным в русском алфавите. Шифровки нумеруются с единицы в порядке появления во входном файле.
6 yolka jeti yabloko segodnya schtab kaktus
1
Пояснение к примеру: исходное сообщение состояло из слов <<ёлка>>, <<йети>>, <<яблоко>>, <<сегодня>>, <<штаб>>, <<кактус>>.