Команда Москвы на Всероссийской олимпиаде по информатике 2017 года оказалась настолько велика, что помещается только в 2 вагона. Некоторые школьники испытывают друг к другу такую личную неприязнь, что не могут есть, находясь в одном вагоне. Поскольку не есть в поезде нельзя (это противоречит СанПиНам), то участников олимпиады надо рассадить так, чтобы школьники, испытывающие взаимную неприязнь, ехали в разных вагонах. Если это невозможно, никто никуда не поедет.

Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\))), в одной клетке которого находится клад, в \(K\) клетках находятся входы в лабиринт).

Требуется вывести искомый путь.

На плоскости задано множество точек (x, y), где x, y – целые числа, 1≤x≤M, 1≤y≤N. Из каждой точки выходит ровно один из следующих векторов: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Каждый вектор соединяет одну целочисленную точку плоскости с другой. Например, если из точке (2, 5) выходит вектор (1, 1), то он соединяет эту точку с (3, 6), но не наоборот.

Последовательность из двух и более точек плоскости a₁, a₂,…, a_k назовем циклом, если каждая точка a_i соединена вектором с a_i+1 (1≤i≤k-1), и a_k соединена вектором с a₁. Циклы считаются разными если они отличаются хотя бы одной вершиной.

Напишите программу, которая по информации о векторах, выходящих из точек плоскости, находит количество различных циклов.