21400번 - Интернет-банкинг 스페셜 저지다국어

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

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

При вводе пароля пользователю разрешается выполнять такую операцию: выбрать из данных строк две (обозначим их как $s_i$ и $s_j$, $1 \le i, j \le n$, $i \ne j$) и некоторую позицию $k$ ($1 \le k \le m$) в них, после чего поменять местами $k$-е символы в $s_i$ и $s_j$. Например, если $s_i=$<<abcde>>, $s_j=$<<vwxyz>>, $k=3$, то после выполнения этой операции будут верны следующие равенства: $s_i=$<<abxde>> и $s_j=$<<vwcyz>>. Для ввода пароля пользователю необходимо за минимальное число таких операций добиться состояния, в котором хотя бы одна из строк $s_1, \ldots, s_n$ совпадает с $p$.

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

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

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

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

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