WoW
В зоопарке центрального парка Нью-Йорка среди его обитателей очень популярна массовая многопользовательская ролевая двумерная онлайн-игра Wonders of Worlds. Мир игры представляет из себя бесконечную плоскость, разбитую на одинаковые клетки единичного размера. Каждая клетка задается двумя целыми координатами — x и y. Одной из самых увлекательных особенностей данной игры для игроков наивысшего (85–го) уровня являются бои друг против друга на специальной турнирной арене. Арена представляет из себя прямоугольную площадку, состоящую из n×m клеток. В дальнейшем будем предполагать, что левый нижний край арены находится в клетке (0, 0), а верхний правый — в клетке (n-1, m-1). В каждой клетке арены одновременно может находиться не более одного игрока. Игроки делают ходы по очереди. В течение одного хода игрок может или атаковать противника своими способностями, или переместиться в какой-нибудь сектор площадки.
Сегодня Рико, играющий за ангела смерти, решил вызвать на бой Шкипера, играющего за мага. В WoW, при вызове на бой действует следующее правило — вызывающий на бой ходит вторым. Таким образом, первым свой ход выполнит Шкипер.
Незадолго до выхода на арену наших бойцов, Ковальски, который состоит в игровой гильдии с Рико, сообщил Шкиперу, что его противник нашел критическую ошибку в движке игры, которая позволяет ему своим персонажем, с полным запасом здоровья, моментально уничтожать противника одной способностью. Чтобы не оказаться столь бесцеремонно поверженным, у Шкипера остаётся единственный выход — атаковать Рико.
Система заклинаний у мага в WoW уникальна. Любой маг обладает набором из k базовых заклинаний. Каждое базовое заклинание i задаётся последовательностью перемещений, которая определяется набором из d_i векторов с целыми координатами. Будучи произнесённым, базовое заклинание стартует из некоторой начальной точки, поочерёдно перемещаясь на вектор из набора. После выполнения всех перемещений заклинание взрывается и наносит ненулевой урон противнику, если он находится в той точке, в которой закончились перемещения.
Ключевой особенностью мага является то, что он может комбинировать различные базовые заклинания. Комбинация заключается в последовательном применении некоторых базовых заклинаний. В этом случае, после окончания перемещений первого заклинания, оно не взрывается, а вместо этого второе заклинание начинает свои перемещения из той точки, в которой закончилось первое. После окончания перемещений второго заклинания, используются перемещения третьего и т. д. После окончания перемещений последнего заклинания в комбинации, заклинание взрывается в той точке, в которой оно оказалось.
Заметим, что арена для боёв ограничена непроницаемым антимагическим барьером. Таким образом, базовое заклинание может быть применено только если при перемещениях оно не выходит за границы арены. Аналогично комбинация может быть применена только в том случае, если входящие в неё базовые заклинания могут быть применены в указанном порядке.
Так как количество всевозможных комбинаций велико, Шкипер просит Вас помочь в выборе комбинации базовых заклинаний общим количеством не более 10^6, которые можно применить подряд и нанести урон Рико, либо определить, что этого сделать невозможно.
Гарантируется, что если ответ на задачу существует, то он не требует комбинирования более 10^6 базовых заклинаний.
Входные данные
В первой строке входного файла содержится три целых числа n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 50) — размеры арены и количество базовых заклинаний. Во второй строке находятся целые числа x_1, y_1, x_2, y_2 (1 ≤ i ≤ 2, 0 ≤ x_i ≤ _n, 0 ≤ y_i ≤ m) (x_1, y_1) ≠ (x_2, y_2) — координаты Шкипера и Рико на арене соотвественно. Далее в k строках следует описание базовых заклинаний. В (i+2)–й строке входного файла находится целое число d_i (1 ≤ d_i ≤ 5·10^5) — количество перемещений в базовом заклинании. Далее перечислены d_i пар целых чисел x_j, y_j (1 ≤ j ≤ d_i, -n < x_j < n, -m < y_j < m) — координаты векторов, задающих перемещения. Суммарное количество векторов во всех базовых заклинаниях не превышает 5·10^5. Все числа расположенные в пределах одной строки и разделяются одним пробелом.
Выходные данные
В случае существования комбинации из не более чем 10^6 базовых заклинаний достигающей поставленной цели, выведите в выходной файл в первой строке целое число p — количество базовых заклинаний в найденной комбинации. На второй строке выведите p чисел, разделённых одним пробелом — номера базовых заклинаний в порядке их применения. Базовые заклинания нумеруются с единицы в порядке их описания во входном файле. Если решений несколько, выведите любое.
В случае отсутствия решения выведите в первой строке число -1.