Олимпиады по программированию

olympiads.ru

I Всероссийская заочная олимпиада школьников по информатике, 2006/07 учебный год

Задача J. Историки и археологи

Недавно археологической командой "Раскопай" были обнаружены остатки древней цивилизации. Особое внимание привлекла карта с месторасположением народов, живших в то время. Карта представляет собой прямоугольный лист, разлинованный горизонтальными линиями на M полос и вертикальными линиями на N столбцов. Таким образом формируются M*N клеток - древних поселений, которые заселялись сообществами. В каждой клетке этой карты написано натуральное число - идентификатор народа, к которому принадлежит это сообщество людей (рукопись с соответствием между идентификаторами и народами также была обнаружена).

Группа историков "Разузнай" имеет такую же карту, но только на тысячелетие древнее. Естественно, она может отличаться от той, которую нашли археологи - ведь за такой срок сообщества могли переселяться в другие поселения. Историками была высказана идея о механизме переселения народов.

Чтобы объяснить этот процесс введем систему координат на карте так, что границы карты параллельны осям координат. Пусть координаты (0,0) соответствуют самой верхней левой клетке, а (N-1, M-1) - самой нижней правой. Переселение народов проходит в несколько этапов. Опишем как проходит каждый этап.

Назовем квадратом множество всех поселений с координатами (x,y) такими, что x₁≤x≤x₂, y₁≤y≤y₂, где x₂-x₁=y₂-y₁. Соответственно клетка (x₁,y₁) является левой верхней клеткой квадрата, (x₂,y₂) -нижней правой.

На каждом этапе переселения переселяются сообщества внутри некоторого квадрата по следующему правилу. Если переселение происходит внутри квадрата, левой верхней клеткой которого является клетка (x₁,y₁), а правой нижней - (x₂,y₂), то сообщество, проживавшее в поселении с координатами (x,y) (x₁≤x≤x₂, y₁≤y≤y₂) переселяется в поселение с координатами (x₂-(y₂-y),y₂-(x₂-x)), при этом, возможно, что некоторые сообщества остаются на своих местах. Все сообщества, живущие вне квадрата, в котором происходит переселение, остаются на своих местах.

Историки из "Разузнай" хотят для подтверждения (или опровержения) своей теории переселений проверить, могла ли в результате таких переселений из карты, которая есть в распоряжении "Разузнай" получиться карта, которую нашли археологи. Помогите им - напишите программу, которая будет это делать.

Формат входных данных

На первой строке входного файла заданы через пробел 2 натуральных числа M и N, где M - количество строк, а N - количество столбцов (1≤M≤30, 1≤N≤30). Далее описывается карта историков. После нее записана карта археологов.

Каждая карта описывается в M строках, в каждой из которых записано по N чисел - идентификаторы народов, проживающих в соответствующих поселениях. В первой строке описания записаны народы, проживающие в поселениях с координатами (0,0), (1,0), (2,0),...,(N-1,0), во второй - в поселениях (0,1), (1,1), (2,1),...,(N-1,1), в M-ой - с координатами (0, M-1), (1,M-1),...,(N-1,M-1). Идентификаторы народов - натуральные числа, не превышающие 2*10⁹. Некоторые идентификаторы могут не использоваться (например, на карте могут встречаться народы с номерами 1 и 3, и не встречаться народ с идентификатором 2).

Формат выходных данных

Если гипотеза историков подтверждается, то в выходной файл выведите количество этапов переселения народов и дальше сами эти этапы, в результате которых из карты историков получается карта археологов. Каждый этап должен быть описан четырьмя числами - x₁, y₁, x₂, y₂ (координатами углов квадрата, который переселяется). Обратите внимание, что добиваться минимального количества переселений всех народов, или же минимального количества этапов не требуется. Важно, чтобы общее число этапов не превышало 10000 (математики из общества "Докажи" доказали, что в указанных ограничениях это всегда возможно).

Если гипотеза историков неверна, т.е. из карты историков карта археологов с помощью только таких переселений получиться не могла, то выведите в выходной файл одно число -1 (минус один).

Примеры

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

2
2 0 3 1
0 0 2 2

2 2
6 8 
5 8 
6 8 
5 9

-1

Пояснение к примеру 1

Переселение проходит в 2 этапа: на рисунке ниже закрашены квадраты, в которых происходили переселения сообществ.