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.