Задача №113694. Интернет-банкинг
Интернет-банкинг - это современная технология, которая позволяет клиентам банка получать доступ к информации о своих счетах с помощью сети Интернет из практически любой точки земного шара. Разумеется, при использовании интернет-банкинга большую роль играют вопросы безопасности. Поэтому для доступа к системе Интернет-банкинга пользователю необходимо ввести пароль.
Система Интернет-банкинга 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\).
3 abc cab bca acb
2 1 3 2 1 2 3
3 abc cab bca acd
-1