Игра JawBreaker

Цель этой популярной игры заключается в том, чтобы набрать максимальное количество очков, убирая фишки одного цвета, которые соприкасаются сторонами (по диагонали не считается), образуя цепочки и массивы. Чем больше фишек исчезает за один ход, тем больше начисляется за этот ход очков. Точное количество очков за ход описывается формулой N*(N-1) где N количество фишек (так 2*(2-1)=2, 10*(10-1)=90). При этом, соответственно, фишка, которая прикасается к остальным только одной стороной не менее ценная, чем та, которая со всех сторон окружена такими же. Если вы убрали фишки из середины поля, то верхние фишки падают вниз, закрывая собой пустоты. Игра заканчивается в тот момент, когда на поле больше не остается фишек, которые могут быть убраны.

В задаче вам будет дано поле и расставленные на нем фишки. Ваша цель набрать максимальное количество очков. Потренироваться и определиться со стратегией можно он-лайн (Замечание: он-лайн игра немного отличается от той, что описана в условии): http://www.bigfrog.net/jawbreaker/

Входные данные

t – число тестов, затем следуют t тестов. [t <= 500]
Каждый тест начинается с 3 целых чисел: H - количество рядов в головоломке, W - количество столбцов в головоломке и C - количество различных цветов, используемых, для раскраски фишек. [4 <= H, W <= 100] и [3 <= C <= 50]. Затем следуют H рядов по W чисел в каждом, разделенные пробелом. Каждое число принимает значения от 0 до C-1 и означает цвет фишки.

Выходные данные

Для каждого теста необходимо вывести на отдельной строчке букву Y если вы хотите решать этот тест или же N в противном случае. Далее в том случае если вы ответили Y, необходимо вывести набор строчек с двумя целыми числами в каждой x, y равными ряду и столбцу на поле. [0 <= x < H], [0 <= y < W]. Координаты отсчитываются от верхнего левого угла поля. После вашего последнего хода необходимо вывести строчку -1 -1. При этом вы получите статус Wrong Answer в случаях если координаты выходят за границы поля или же вы сделали неверный ход (то есть указали на пустое место или одиночную фишку).

Начисление очков

Количество очков полученное за данную задачу вычисляется по формуле: score = 200*total_score/(200+time), где total_score - суммарное количество очков за все тесты, а time - время работы программы в секундах.

Пример

Входные данные:
1
4 4 3
0 0 1 1
1 1 2 2
0 1 2 0
0 1 1 2

Выходные данные:
Y
1 0
1 0
3 2
-1 -1

Пояснение:
Начальное поле:

0 0 1 1
1 1 2 2
0 1 2 0
0 1 1 2

Поле после первого хода (убрали 5 единиц):

. . . 1
0 . 1 2
0 . 2 0
0 0 2 2

Поле после второго хода (убрали 4 нолика):

. . . 1
. . 1 2
. . 2 0
. . 2 2

Поле после третьего хода (убрали 3 двойки):

. . . .
. . . 1
. . . 2
. . 1 0


Начисление очков:
В данном случае total_score = 5*(5-1) + 4*(4-1) + 3*(3-1) = 20 + 12 + 6 = 38, 
положим также, что программа работала 10 секунд. В этом случае количество очков, 
полученных за программу будет равно 36.190476