В кооперативную игру играют \(m\) человек. В игре есть \(3m\) листков бумаги: \(m\) листков с буквой «w», \(m\) листков с буквой «i» и \(m\) листков с буквой «n».
Изначально каждому игроку дают три листка (возможно, с одинаковыми буквами).
Цель игры — сделать так, чтобы каждый из \(m\) человек мог сложить из своих листков бумаги слово «win». Другими словами, у каждого игрока должен оказаться один листок с буквой «w», один листок с буквой «i» и один листок с буквой «n».
Чтобы достичь цели, игроки могут производить обмены. В каждом обмене участвуют два игрока. Каждый из них выбирает ровно один из своих листков бумаги, и потом игроки обмениваются выбранными листками.
Найдите кратчайшую последовательность обменов, после которой у каждого игрока будет одна буква «w», одна буква «i» и одна буква «n».
Выходные данные
Для каждого набора входных данных выведите неотрицательное целое число \(k\) — наименьшее число обменов, необходимое для того, чтобы у каждого игрока оказалась одна буква «w», одна буква «i» и одна буква «n».
В каждой из следующих \(k\) строк выведите четыре токена \(a_1\) \(c_1\) \(a_2\) \(c_2\), описывающих обмены в хронологическом порядке (\(1 \le a_1, a_2 \le m\); \(a_1 \ne a_2\); \(c_1, c_2\) — символы из \(\{\mathtt{w}, \mathtt{i}, \mathtt{n}\}\)): игрок номер \(a_1\) отдаёт листок с буквой \(c_1\) игроку номер \(a_2\), а игрок номер \(a_2\) одновременно с этим отдаёт листок с буквой \(c_2\) игроку номер \(a_1\).
Если существует несколько решений, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
nwi
inw
3
inn
nww
wii
4
win
www
iii
nnn
|
0
2
2 w 3 i
3 w 1 n
3
2 w 3 i
2 w 4 n
3 i 4 n
|