Codeforces Round 147 (Div. 2)
B
Young Table
Codeforces
1500
原题
← AC →
翻译中…

You've got table $*a*$, consisting of $*n*$ rows, numbered from 1 to $*n*$. The $*i*$-th line of table $*a*$ contains $*c*_{*i*}$ cells, at that for all $*i*$ $(1 < *i* ≤ *n*)$ holds $*c*_{*i*} ≤ *c*_{*i* - 1}$.

翻译中…

Let's denote $*s*$ as the total number of cells of table $*a*$, that is, image. We know that each cell of the table contains a single integer from $1$ to $*s*$, at that all written integers are distinct.

翻译中…

Let's assume that the cells of the $*i*$-th row of table $*a*$ are numbered from 1 to $*c*_{*i*}$, then let's denote the number written in the $*j*$-th cell of the $*i*$-th row as $*a*_{*i*, *j*}$. Your task is to perform several swap operations to rearrange the numbers in the table so as to fulfill the following conditions:

翻译中…
  1. for all $*i*, *j*$ $(1 < *i* ≤ *n*; 1 ≤ *j* ≤ *c*_{*i*})$ holds $*a*_{*i*, *j*} > *a*_{*i* - 1, *j*}$;
  2. for all $*i*, *j*$ $(1 ≤ *i* ≤ *n*; 1 < *j* ≤ *c*_{*i*})$ holds $*a*_{*i*, *j*} > *a*_{*i*, *j* - 1}$.
翻译中…

In one swap operation you are allowed to choose two different cells of the table and swap the recorded there numbers, that is the number that was recorded in the first of the selected cells before the swap, is written in the second cell after it. Similarly, the number that was recorded in the second of the selected cells, is written in the first cell after the swap.

翻译中…

Rearrange the numbers in the required manner. Note that you are allowed to perform any number of operations, but not more than $*s*$. You do not have to minimize the number of operations.

翻译中…

Input

翻译中…

The first line contains a single integer $*n*$ $(1 ≤ *n* ≤ 50)$ that shows the number of rows in the table. The second line contains $*n*$ space-separated integers $*c*_{*i*}$ $(1 ≤ *c*_{*i*} ≤ 50; *c*_{*i*} ≤ *c*_{*i* - 1})$ — the numbers of cells on the corresponding rows.

翻译中…

Next $*n*$ lines contain table $*а*$. The $*i*$-th of them contains $*c*_{*i*}$ space-separated integers: the $*j*$-th integer in this line represents $*a*_{*i*, *j*}$.

翻译中…

It is guaranteed that all the given numbers $*a*_{*i*, *j*}$ are positive and do not exceed $*s*$. It is guaranteed that all $*a*_{*i*, *j*}$ are distinct.

翻译中…

Output

翻译中…

In the first line print a single integer $*m*$ $(0 ≤ *m* ≤ *s*)$, representing the number of performed swaps.

翻译中…

In the next $*m*$ lines print the description of these swap operations. In the $*i*$-th line print four space-separated integers $*x*_{*i*}, *y*_{*i*}, *p*_{*i*}, *q*_{*i*}$ $(1 ≤ *x*_{*i*}, *p*_{*i*} ≤ *n*; 1 ≤ *y*_{*i*} ≤ *c*_{*x*_{*i*}}; 1 ≤ *q*_{*i*} ≤ *c*_{*p*_{*i*}})$. The printed numbers denote swapping the contents of cells $*a*_{*x*_{*i*}, *y*_{*i*}}$ and $*a*_{*p*_{*i*}, *q*_{*i*}}$. Note that a swap operation can change the contents of distinct table cells. Print the swaps in the order, in which they should be executed.

翻译中…

样例

Input #1
3
3 2 1
4 3 5
6 1
2
Output #1
2
1 1 2 2
2 1 3 1
InputCopy OutputCopy
Input #2
1
4
4 3 2 1
Output #2
2
1 1 1 4
1 2 1 3
InputCopy OutputCopy
题目信息
题号
237B
时间限制
2 s
内存限制
256 MB
标签
模拟
排序

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。