| Codeforces Round 147 (Div. 2) |
|---|
| Закончено |
Вам задана таблица a, состоящая из n строк, пронумерованных от 1 до n. В i-ой строке таблицы a содержится ci клеточек, при этом для всех i (1 < i ≤ n) выполняется ci ≤ ci - 1.
Обозначим за s общее количество клеточек таблицы a, то есть 
. Известно, что в каждой клеточке таблицы a записано единственное целое число от 1 до s, при этом все записанные числа различны.
Пусть клеточки i-той строки таблицы a пронумерованы от 1 до ci, тогда обозначим число, записанное в j-той клеточке i-той строки, за ai, j. Вам необходимо посредством нескольких операций обмена переупорядочить числа в таблице так, чтобы выполнялись следующие условия:
- для всех i, j (1 < i ≤ n; 1 ≤ j ≤ ci) выполняется ai, j > ai - 1, j;
- для всех i, j (1 ≤ i ≤ n; 1 < j ≤ ci) выполняется ai, j > ai, j - 1.
За одну операцию обмена разрешается выбрать две различных клеточки таблицы и поменять записанные в них числа местами, то есть число, которое до применения операции было записано в первой из выбранных клеток, после применения операции будет записано во второй. Аналогично, число, которое до применения операции было записано во второй из выбранных клеток, после применения операции будет записано в первой.
Переупорядочите числа требуемым способом. Учтите, что Вам разрешается выполнить любое количество операций не превосходящее s. Минимизировать количество операций не требуется.
В первой строке записано единственное целое число n (1 ≤ n ≤ 50), обозначающее количество строк в таблице. Во второй строке через пробел записаны n целых чисел ci (1 ≤ ci ≤ 50; ci ≤ ci - 1) — количества клеточек в соответствующих строках.
В следующих n строках задана таблица а. В i-той из них через пробел записаны ci целых чисел: j-тое число в этой строке обозначает ai, j.
Гарантируется, что все заданные числа ai, j положительны и не превосходят s. Гарантируется, что все ai, j различны.
В первой строке выведите единственное целое число m (0 ≤ m ≤ s), обозначающее количество произведенных операций обмена.
В следующих m строках выведите описание этих операций обмена. В i-той из них выведите через пробел четыре целых числа xi, yi, pi, qi (1 ≤ xi, pi ≤ n; 1 ≤ yi ≤ cxi; 1 ≤ qi ≤ cpi). Выведенные числа обозначают операцию обмена содержимого клеток axi, yi и api, qi. Обратите внимание, что операцией обмена можно менять содержимое различных клеток таблицы. Выводите обмены в том порядке, в котором они должны производиться.
3
3 2 1
4 3 5
6 1
2
2
1 1 2 2
2 1 3 1
1
4
4 3 2 1
2
1 1 1 4
1 2 1 3
