Recently, Jiajia has become obsessed with a fun little game: antbuster.

The rules of the game are very simple: on a map, the top-left corner is an ant nest, and the bottom-right corner is a cake. Ants continuously crawl out from the nest, attempting to carry the cake back to the nest. Your task is to use your initial funds and the prize money earned from killing ants to build defensive towers and eliminate these ants that are trying to steal your cake.

To achieve the highest possible score, Jiajia has designed many tower-building strategies. However, after trying a small portion of them, Jiajia found that this game is too time-consuming. To save time, Jiajia decided to write a program to simulate the game process for each strategy and judge the quality of the strategy based on the results.

Based on experience accumulated in the game and some parameters found online, Jiajia guessed the algorithm for ant movement and assumed that the ants in the game also choose their routes according to these rules:

1. At the beginning of each second, every ant is at some integer coordinate on the plane. If an ant is not carrying the cake, it leaves 2 units of pheromones at that point; otherwise, it leaves 5 units of pheromones. Then, the ant chooses one of the four directions—North, South, East, or West—to crawl to.
2. The rules for choosing a direction are: First, the point reached after crawling one unit length cannot contain another ant or a defensive tower, and that point cannot be the point where the ant was in the previous second (unless the ant was stuck in the previous moment and still cannot move at this moment). Of course, the ant will not crawl outside the boundaries of the map (we define these points as unreachable). If there are multiple choices at this time, the ant will choose the point with the most pheromones to crawl to.
3. If there are still multiple choices, the ant first faces East. If East is not a selectable direction, it turns 90° clockwise and checks again. If it is still not selectable, it turns another 90°... until it finds a direction it can go.
4. If we take the time an ant appears at the nest entrance as the 1st second of its activity, then whenever the number of seconds of this ant's activity is a multiple of 5, it first determines a direction according to rules 1–3, then turns 90° counter-clockwise from that direction. If it would walk to an unreachable point along the current direction, it will keep turning 90° counter-clockwise until it faces a reachable point. The direction determined this way is the final direction the ant will crawl.
5. If all four directions around the ant are unreachable, the ant will choose to stay at the current point for this second. When determining the movement direction in the next second, the point it was at in the previous second is its current stationary point.
6. You can assume that after the ant selects a direction, it instantly moves to its target point and stays at the target point for the remainder of that second.
7. Ants move in the order of their birth; ants born earlier move first.

Here is some information about the map:

1. Every second, all points on the map lose 1 unit of pheromones, if there are any pheromones at that point.
2. Some places on the map are turrets. The coordinates of the turrets are given in the input.
3. The length and width of the map are given in the input. For an $n \times m$ map, the top-left corner coordinate is $(0, 0)$ and the bottom-right corner coordinate is $(n, m)$. The ant nest is at $(0, 0)$ and the cake is at $(n, m)$.
4. You can treat an ant as a circle with a diameter of 1 unit, with its center at the integer coordinate where the ant is located.
5. At the start of the game, there are no ants on the map, and the pheromone content at every point is 0.

Information about Turrets

1. Turrets are placed at integer coordinates on the map.
2. For simplicity, we assume these turrets are laser towers. The firing rate of a laser tower is 1 second/shot, its attack damage is $d$/shot, and its attack range is $r$. You can assume that the tower starts attacking only after the ants have finished moving each second. Furthermore, a tower can only hit an ant if the straight-line distance between the center of the circle representing the ant and the tower is no more than $r$.
3. If an ant is carrying the cake, it becomes the target, meaning any tower that can reach it will aim its muzzle at it. If the cake is safely in its original place, each tower will choose the nearest ant to attack; if there are multiple such ants, it will choose the one born earliest.
4. Laser towers have a peculiar characteristic: once they have selected a target, as long as the target is within range, all ants on the line segment connecting the tower to the center of the target ant (here, the "hit" judgment is changed to the line segment representing the laser having a common point with the circle representing the ant) will be hit and lose $d$ health, but the laser will not penetrate its target to hit ants behind it.
5. Although in the real game, towers can be upgraded, here we assume that the layout and levels of the towers are fixed and will not change.

Information about the Ant Nest

1. If there are fewer than 6 ants on the map and there is no ant at the nest entrance, one ant will crawl out of the nest every second until there are 6 ants on the map.
2. A newly born ant stands at the nest entrance.
3. Each ant has a level, which determines its health. The health of an ant of level $k$ is $\text{int}(4 \times 1.1^k)$ (where $\text{int}(x)$ denotes the floor of $x$). Each time it is hit by a tower, the ant's health decreases by $d$. Note that an ant with 0 health can still crawl around energetically; only when an ant's health is reduced to a negative value is it considered dead.
4. The level of an ant is calculated as follows: the first 6 ants born are level 1, the 7th–12th are level 2, and so on.

Information about the Cake

1. For simplicity, you can assume that there is only one last piece of cake left. If an ant walks to the location of the cake and the cake has not been carried away, this ant will carry the cake. If the ant is killed, the cake returns to its original position.
2. If an ant carrying the cake walks to the location of the ant nest, we consider that the ant has successfully stolen the cake, and the game ends.
3. When an ant picks up the cake, its health increases by $\text{int}(\text{initial health of the ant} / 2)$, but it will not exceed the maximum limit.

Summary of Events in 1 Second

At the beginning of the second, if there are fewer than 6 ants on the map, an ant is born at the nest entrance. Next, the ants leave some pheromones at their current locations and then consider moving. Ants born earlier move first. After movement is complete, if an ant is at the cake's location and the cake has not been taken, it picks up the cake, its health increases, and it is set as the target by all towers at this moment. Then all towers start attacking simultaneously. If the ant carrying the cake dies after the attack, the cake instantly returns to its original position. After the attack, if it is found that the ant carrying the cake is not dead and is at the nest's location, it is considered that the ant has stolen the cake. The game also ends at this moment. Finally, all points on the map lose 1 unit of pheromones. All ants' ages increase by 1. The long 1 second ends here.

Input

The first line contains 2 space-separated integers, $n$ and $m$, representing the length and width of the map. The second line contains 3 space-separated integers, $s$, $d$, and $r$, representing the number of turrets, the damage per attack, and the attack range, respectively. The next $s$ lines each contain 2 space-separated integers $x$ and $y$, describing the position of a turret. Of course, there will never be a turret at the nest entrance or the cake's location. The last line is a positive integer $t$, representing the first $t$ seconds of the game we are simulating.

Output

If an ant steals the cake at or before the $t$-th second, output a line "Game over after x seconds", where $x$ is the time the game ended. Otherwise, output "The game is going on". If the game ends at or before the $t$-th second, output the information of all ants at the time the game ends; otherwise, output the information of all ants after $t$ seconds. The format is as follows: The first line is an integer $s$, representing the total number of living ants at that time. The next $s$ lines each contain 5 integers, representing an ant's age (in seconds), level, current health, and position on the map $(a, b)$, in order. The output should be sorted by the ants' age in descending order.

Examples

Input 1

3 5
1 1 2
2 2
5

Output 1

The game is going on
5
5 1 3 1 4
4 1 3 0 4
3 1 3 0 3
2 1 3 0 2
1 1 4 0 1

Note

In a $3 \times 5$ map, there is 1 laser turret with a damage of 1 and an attack range of 2, located at $(2, 2)$. We simulate the first 5 seconds of the game. Within 5 seconds, 5 ants are born, all crawling East. Among them, the 1st to 4th ants were hit by the laser turret for 1 point of health while passing through point $(0, 2)$. At the 5th second, the earliest born ant was supposed to move East according to movement rules 1–3, but due to rule 4, after discovering that moving North and West would lead to unreachable points, it finally chose to move South.

Constraints

100% of the data satisfies $1 \le n, m \le 8$, $s \le 20$, $t \le 200,000$.