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

Условие

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

Система Интернет-банкинга Bank 2.0, используемая одним Очень Крупным Банком, использует следующий способ ввода пароля. Серверной частью системы случайно генерируются n строк s₁, …, 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₁, …, s_n совпадает с p.

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

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

Первая строка входного файла содержит целое число n (2 ≤ n ≤ 100). Каждая из последующих n строк содержит строки s₁, …, 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.

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

3
abc
cab
bca
acb

2
1 3 2
1 2 3

3
abc
cab
bca
acd

-1