Gary works as a grid organizer at the local toy shop which sells grid shaped toys. The grid A has N rows and N columns where each cell contains a value in range \([0,N^2-1]\) and all values are DISTINCT. Here 0 denotes an empty cell. When a customer enters the store he/she plays with the grid and rearrange the values in the grid. So now its Gary's job to rearrange the grid to look good before the new customers visit the shop. But there are certain rules to rearrange the grid:

Rule 1: In one move Gary can swap the value of the empty cell with one of its adjacent cell (which share a side with empty cell). A move can be of 4 types: 1 for swapping with upper adjacent element, 2 for lower adjacent element, 3 for left adjacent element and 4 for right adjacent element.

Rule 2: All moves should be valid i.e. he can't swap values with cell that don't lie on the grid.

Rule 3: Gary can't make more than 10^5 moves.

After making the moves, let M be the number of moves made by Gary and K be the number of cells where A[I][J] is equal to N*(I-1)+Jfor a cell at position (I,J) ( 1-based indexing ) for \(1 \leq I,J \leq N\). Gary's score will be \(K^2 + \frac{10^5 - M}{100}\). Can you help Gary to maximize his score so that he can get salary bonus at the end of the month. Note that this is an approximate problem, so you do not need necessarily need to find an optimal sequence of moves.

Input Format

The first line of input will contain a single integer N. Next N lines contain N space separated integers denoting a row of the grid.

Output Format

The first line of Output should contain single integer M. Next M lines should contain an integer denoting the type of move.

Test case generation

N will be chosen uniformly at random between 200 and 400.