Интернет-банкинг - это современная технология, которая позволяет клиентам банка получать доступ к информации о своих счетах с помощью сети Интернет из практически любой точки земного шара. Разумеется, при использовании интернет-банкинга большую роль играют вопросы безопасности. Поэтому для доступа к системе Интернет-банкинга пользователю необходимо ввести пароль.
Система Интернет-банкинга Bank 2.0, используемая одним Очень Крупным Банком, использует следующий способ ввода пароля. Серверной частью системы случайно генерируются n строк s
1,…,s
n, каждая из которых состоит из m строчных букв латинского алфавита (предполагается, что пароли состоят только из таких букв).
При вводе пароля пользователю разрешается выполнять такую операцию: выбрать из данных строк две (обозначим их как s
i и s
j, 1 ≤ i,j ≤ n, i≠j) и некоторую позицию k (1 ≤ k ≤ m) в них, после чего поменять местами k-е символы в s
i и s
j. Например, если s
i=abcde, s
j=vwxyz, k=3, то после выполнения этой операции будут верны следующие равенства: s
i=abxde и s
j=vwcyz. Для ввода пароля пользователю необходимо за минимальное число таких операций добиться состояния, в котором хотя бы одна из строк s
1,…,s
n совпадает с p.
Ваша задача состоит в том, чтобы написать программу, которая по заданному набору строк s1,…,sn и паролю пользователя p определит минимальное число операций указанного типа, которые необходимо выполнить для ввода пароля, а также найдет способ ввода пароля за такое число операций.
Входные данные
Первая строка содержит целое число n (2 ≤ n ≤ 100). Каждая из последующих n строк содержит строки s
1,…,s
n. Все они состоят только из строчных букв латинского алфавита и имеют одинаковую длину m (2 ≤ m ≤ 100).
Последняя строка содержит пароль пользователя p. Его длина равна m, и он состоит только из строчных букв латинского алфавита.
Выходные данные
Первая строка должна содержать минимальное число c операций, необходимых для ввода пароля. Если с помощью описанных в условии операций пароль ввести нельзя, то выведите в первой строке "−1".
В случае существования решения следующие c строк должны содержать описания операций. Операции должны быть перечислены в порядке их применения, каждая из строк должна содержать три целых числа: i, j и k (1 ≤ i,j ≤ n, i≠j, 1 ≤ k ≤ m). Эти числа означают, что соответствующая операция состоит в обмене k-ых символов строк s
i и s
j.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
abc
cab
bca
acb
|
2
1 3 2
1 2 3
|
|
2
|
3
abc
cab
bca
acd
|
-1
|