WoW#2741

WoW

1 секунда

256 мегабайтів

Дуже складна

У зоопарку Центрального парку Нью-Йорка серед його мешканців дуже популярна двовимірна онлайн-гра "Wonders of Worlds". Гра проходить на нескінченній площині, розбитій на одиничні клітини. Кожна клітина визначається двома цілими координатами $x$ і $y$ . Однією з головних особливостей, зокрема для гравців найвищого (85-го) рівня, є дуелі на спеціальній турнірній арені. Арена — це прямокутник розміром $n \times m$ n \times m клітин. Лівий нижній кут арени — $(0, 0)$ , а правий верхній — $(n - 1, m - 1)$ (n-1, m-1). У кожен момент часу лише один гравець може займати одну клітину. Гравці ходять по черзі; під час свого ходу гравець може або атакувати суперника, або переміститися в іншу клітину арени.

Сьогодні Ріко, граючи за Ангела Смерті, викликає на поєдинок мага Скіпера. За правилами WoW, викликаючий ходить другим, отже перший хід робить Скіпер.

Перед початком битви Ковальскі, який перебуває у гільдії з Ріко, попереджає Скіпера, що Ріко знайшов баг у рушії гри, який дозволяє йому моментально знищити опонента однією здатністю. Єдина надія Скіпера — атакувати першим.

Магічна система у WoW унікальна: кожен маг має набір з $k$ базових заклять. Кожне $i$ -те базове закляття складається з послідовності $d_{i}$ d_i векторів із цілими координатами. Коли закляття використовується, воно починається з певної точки та послідовно здійснює рухи за кожним вектором із набору. Після завершення всіх рухів закляття вибухає, завдаючи шкоди опоненту, якщо той знаходиться у точці прильоту.

Маг може комбінувати базові закляття, застосовуючи їх одне за одним. Наступне закляття починає свій рух із точки завершення попереднього, і лише після виконання всієї послідовності циклу відбувається вибух.

Бойова арена оточена непроникним антимагічним бар'єром. Базове закляття можна застосувати лише якщо жоден із рухів не виходить за межі арени. Те саме стосується комбінацій заклять.

Оскільки кількість можливих комбінацій дуже велика, Скіпер просить знайти комбінацію з не більш ніж $1 0^{6}$ 10^6 базових заклять, які можна застосувати підряд і завдати шкоди Ріко, або визначити, що це неможливо.

Гарантується, що якщо рішення існує, воно не потребує більше $1 0^{6}$ 10^6 заклять у комбінації.

Вхідні дані

Перший рядок містить три цілі числа $n$ , $m$ , $k$ ( $1 \leq n, m \leq 1000$ 1 \leq n, m \leq 1000, $1 \leq k \leq 50$ 1 \leq k \leq 50) — розміри арени та кількість базових заклять. Другий рядок містить $x_{1}$ x_1, $y_{1}$ y_1, $x_{2}$ x_2, $y_{2}$ y_2 ( $0 \leq x_{i} \leq n$ 0 \leq x_i \leq n, $0 \leq y_{i} \leq m$ 0 \leq y_i \leq m, $(x_{1}, y_{1}) \neq = (x_{2}, y_{2})$ (x_1, y_1) \neq (x_2, y_2)) — координати Скіпера та Ріко. Потім слідують $k$ блоків опису заклять. В рядку номер $(i + 2)$ (i+2) вказано $d_{i}$ d_i ( $1 \leq d_{i} \leq 5 \cdot 1 0^{5}$ 1 \leq d_i \leq 5 \cdot 10^5) — кількість рухів у $i$ -му базовому заклятті, далі йдуть $d_{i}$ d_i пар цілих чисел $x_{j}$ x_j, $y_{j}$ y_j ( $- n < x_{j} < n$ -n < x_j < n, $- m < y_{j} < m$ -m < y_j < m) — вектори рухів. Загальна кількість векторів для всіх заклять не перевищує $5 \cdot 1 0^{5}$ 5 \cdot 10^5. Всі числа розділені одним пробілом.

Вихідні дані

Якщо існує комбінація не більше ніж із $1 0^{6}$ 10^6 базових заклять, що досягає цілі, виведіть у першому рядку $p$ — кількість заклять у комбінації. В другому рядку виведіть $p$ чисел — індекси заклять у порядку застосування (нумерація з одиниці за порядком у вхідних даних), розділених пробілом. Якщо розв'язків декілька — виведіть будь-який.

Якщо це неможливо, виведіть у першому рядку $- 1$ .

Приклади

Приклад 1