WoW#2741
In the Central Park Zoo of New York, the two-dimensional online game "Wonders of Worlds" is very popular. The game takes place on an infinite plane divided into unit cells. Each cell is specified by two integers, and , representing its coordinates. One of the main features, especially for players of the highest (85th) level, is duels in a special tournament arena. The arena is a rectangle of size n \times m cells. The bottom-left corner of the arena is , and the top-right corner is (n-1, m-1). Only one player may occupy a cell at any given time. Players take turns; on a turn, a player can either attack their opponent or move to another cell of the arena.
Today, Rico, playing as the Angel of Death, challenges Skipper, who plays as a mage. According to WoW rules, the challenger moves second, so Skipper makes the first move.
Before the battle begins, Kowalski, who is in Rico's guild, warns Skipper that Rico has found a bug in the game engine that allows him to instantly defeat his opponent with a single ability. Skipper's only chance is to attack Rico first.
The magic system for mages in WoW is unique: each mage has a set of basic spells. Each basic spell consists of a sequence of d_i vectors with integer coordinates. When a spell is cast, it starts from a certain point and moves sequentially by each vector in the set. After all movements are completed, the spell explodes, damaging the opponent if they are at the arrival point.
A mage can combine basic spells by applying several of them in sequence. The next spell starts from the endpoint of the previous one, and only after the sequence of all spells is completed does the spell explode.
The battle arena is surrounded by an impenetrable anti-magic barrier. A basic spell can be applied if none of the movements leaves the arena boundaries. The same is true for combinations of spells.
Since the number of possible combinations is very large, Skipper asks you to find a combination of at most 10^6 basic spells that can be applied one after another and harm Rico, or to determine if this is impossible.
It is guaranteed that if a solution exists, it does not require more than 10^6 spells in the combination.
The first line contains three integers , , and (1 \leq n, m \leq 1000, 1 \leq k \leq 50) — the size of the arena and the number of basic spells. The second line contains integers x_1, y_1, x_2, y_2 (0 \leq x_i \leq n, 0 \leq y_i \leq m, (x_1, y_1) \neq (x_2, y_2)) — the coordinates of Skipper and Rico. Then, blocks follow describing the basic spells. In the (i+2)-th line there is an integer d_i (1 \leq d_i \leq 5 \cdot 10^5), the number of movements in the -th basic spell, followed by d_i pairs of integers x_j, y_j (-n < x_j < n, -m < y_j < m) describing the vectors. The total number of vectors across all spells does not exceed 5 \cdot 10^5. All numbers are separated by a single space.
If a combination of at most 10^6 basic spells exists to achieve the goal, output the integer , the number of spells in the combination, in the first line. In the second line, output integers separated by spaces — the indices of the spells in the order they are applied (spells are numbered from one in the order given in the input). If there are several solutions, output any one.
If it is not possible, output in the first line.
Example 1