Задача A. Интернет-банкинг

Автор:Антон Феськов, Фёдор Царёв   Ограничение времени:2 сек
Входной файл:bank.in   Ограничение памяти:256 Мб
Выходной файл:bank.out  

Условие

Интернет-банкинг — это современная технология, которая позволяет клиентам банка получать доступ к информации о своих счетах с помощью сети Интернет из практически любой точки земного шара. Разумеется, при использовании интернет-банкинга большую роль играют вопросы безопасности. Поэтому для доступа к системе Интернет-банкинга пользователю необходимо ввести пароль.

Система Интернет-банкинга Bank 2.0, используемая одним Очень Крупным Банком, использует следующий способ ввода пароля. Серверной частью системы случайно генерируются n строк s1, …, sn, каждая из которых состоит из m строчных букв латинского алфавита (предполагается, что пароли состоят только из таких букв).

При вводе пароля пользователю разрешается выполнять такую операцию: выбрать из данных строк две (обозначим их как si и sj, 1 ≤ i, j ≤ n, i ≠ j) и некоторую позицию k (1 ≤ k ≤ m) в них, после чего поменять местами k-е символы в si и sj. Например, если si=abcde, sj=vwxyz, k=3, то после выполнения этой операции будут верны следующие равенства: si=abxde и sj=vwcyz. Для ввода пароля пользователю необходимо за минимальное число таких операций добиться состояния, в котором хотя бы одна из строк s1, …, sn совпадает с p.

Ваша задача состоит в том, чтобы написать программу, которая по заданному набору строк s1, …, sn и паролю пользователя p определит минимальное число операций указанного типа, которые необходимо выполнить для ввода пароля, а также найдет способ ввода пароля за такое число операций.

Формат входного файла

Первая строка входного файла содержит целое число n (2 ≤ n ≤ 100). Каждая из последующих n строк содержит строки s1, …, sn. Все они состоят только из строчных букв латинского алфавита и имеют одинаковую длину m (2 ≤ m ≤ 100).

Последняя строка входного файла содержит пароль пользователя p. Его длина равна m, и он состоит только из строчных букв латинского алфавита.

Формат выходного файла

Первая строка выходного файла должна содержать минимальное число c операций, необходимых для ввода пароля. Если с помощью описанных в условии операций пароль ввести нельзя, то выведите в первой строке 1.

В случае существования решения следующие c строк должны содержать описания операций. Операции должны быть перечислены в порядке их применения, каждая из строк должна содержать три целых числа: i, j и k (1 ≤ i, j ≤ n, i ≠ j, 1 ≤ k ≤ m). Эти числа означают, что соответствующая операция состоит в обмене k-ых символов строк si и sj.

Примеры тестов

Входной файл (bank.in) Выходной файл (bank.out)
1
3
abc
cab
bca
acb
2
1 3 2
1 2 3
2
3
abc
cab
bca
acd
-1

0.041s 0.007s 15