Макс узнал, что одной из областей, где в настоящее время активно применяются эффективные вычислительные алгоритмы, является молекулярная биология и генетика. Макс заинтересовался этой сферой и решил больше выяснить о том, как кодируется ДНК — основа всего живого.
Спираль ДНК формируется из азотистых оснований — аденина (A), цитозина (C), гуанина (G) и тимина (T). Примечательно, что связи образуют только пары аденин–тимин и цитозин–гуанин. Участок двойной спирали может выглядеть, например, так:
AAGCACTC
||||||||
TTCGTGAG
Так как по одной половине спирали всегда можно однозначно восстановить другую, для кодирования данного участка достаточно строки AAGCACTC или TTCGTGAG. При этом участок может читаться как слева направо, так и справа налево, поэтому также возможна запись CTCACGAA или GAGTGCTT.
Макс только что получил строку, описывающую неизвестный участок генома. Чтобы определить, какому организму принадлежит этот участок, Максу нужно найти соответствующую строку в базе образцов ДНК. Хранящиеся в базе строки можно заменять на эквивалентные по описанным выше правилам.
Помогите Максу найти в базе запись об имеющемся у него участке ДНК.
Выходные данные
Выведите одно целое число — номер распознанного образца, соответствующего имеющемуся у Макса. Гарантируется, что такой образец существует.
Распознанные образцы нумеруются от 1 до $$$N$$$ в порядке описания во входных данных.