题目描述

The only difference between the easy version and the hard version of the game is the size of the game.

After solving Alice's problem, Youmu keeps on her way. Now she comes to the Mayohiga.

Chen is the leader of Mayohiga, she's bored now, and is playing some kind of game called Lianliankan.

LianLiankan is a famous Chinese game, which is devised by yijin Chen and chengzhi Jian from Taiwan. Nowadays, there are many types of Lianliankan in the Internet, many of them have many special types of rules to play, but Chen likes to play the traditional rules of the Lianliankan.

The rule of Lianliankan is quite simple to learn.

The Lianliankan can be acknowledged as a $n \ imes n$ matrix, which $n$ is even.

Every entry of the matrix is a special image, and the same image can be eliminated by just click on both of them, but we must notice that, the route from one image to another MUST NOT exceed three lines.

Which is, for example, just assume that this is our circumstance after eliminating a lot of other entries.

In this condition, we can eliminate entry embedded image 1 on it at position $(1,1)$ with position $(1,3)$ as you can see that we can have a route with just three lines.

But, we can't eliminate entry embedded image 1 at position $(1,1)$ with position $(2,2)$ because we use more than tree lines of route to eliminate them.

We can not eliminate entry embedded image 2 on it at position $(1,2)$ with neither position $(2,1)$ nor position $(2,3)$ either.

The goal of the game is quite obvious, we must eliminate all the entries, but many times we have to observe the whole entries and find two legal same image entries and eliminate them, which is some kind of waste of time.

So, as a given Lianliankan game, Chen wants to win it as soon as possible, so she counts on Youmu. Youmu can write a program for it. Can you write a program for the game, too?

输入格式

First line of input contains one positive integer $n=4$ indicating the size of the Lianliankan.

Then follows $n$ lines, each line contains $n$ lowercase English characters $a$ and $b$ only, indicating the images embedded in the entries, the same character can be seen as the same image.

输出格式

If the Lianliankan can be eliminated all, print YES, and print $\\frac{n^2}{2}$ lines, each line contains two positive integers pairs $x_i,y_i$ indicating the way to eliminate them.

Otherwise, just print NO

If there are multiple ways to eliminate the Lianliankan, you can print any of them.

样例

4 
aabb 
bbaa 
aaaa 
aabb

YES 
1 1 1 2 
1 3 1 4 
2 1 2 2 
2 3 2 4 
3 1 3 2 
3 3 3 4 
4 1 4 2 
4 3 4 4