Искандер и Оля любят придумывать ребусы. Но больше, чем придумывать ребусы, они любят придумывать какие-нибудь игры на строках. Вот и сейчас им в голову пришла забавная игра со следующими правилами:
Вы обожаете портить другим людям их любимые развлечения, поэтому решили написать программу, которая будет определять исход игры по заданному набору запрещённых строк и стартовой строке s.
В первой строке входных данных записаны два целых числа n и m (0 ≤ n ≤ 100 000, 0 ≤ m ≤ 1 000 000) — количество запрещённых строк и изначальная длина строки s.
В каждой из последующих n строк содержится одна запрещённая строка. Гарантируется, что все эти строки непусты, состоят из символов «0» и «1» и никакая из них не является подстрокой строки s. Дополнительно гарантируется, что суммарная длина всех запрещённых строк не превосходит 1 000 000.
В последней строке входных данных записана стартовая строка s длины m, состоящая только из символов «0» и «1». Обратите внимание, строка s может быть пустой, в этом случае соответствующая строка входных данных отсутствует (в том числе символ перевода строки). Длина s не превосходит 1 000 000.
В зависимости от результата игры при оптимальной игре обоих игроков выведите:
1 0
1
Friendship
3 1
000
001
011
0
Olya
2 3
1001
000
100
Iskander
В первом примере строка s изначально пустая. Любой из игроков может не проиграть на любом ходу просто приписав к s символ «0».
