Spectrum Explorer#3050

Spectrum Explorer

1 secondo

64 megabyte

Molto facile

Spectrum Explorer is an interactive computer game where a physicist explores the properties of visible light. The game's starting screen displays a number of circular platforms painted with colours from the visible light spectrum. More than one platform may be painted with the same colour (defined by a certain frequency), except for the two colours red and violet. The display contains only one red platform (the lowest frequency of $400$ THz) and one violet platform (the highest frequency of $789$ THz). A platform may intersect, or even contain, another platform with a different colour, but never merely touch its boundary. The display also shows a figure representing the explorer standing on the red platform.

The game's objective is to walk the explorer from the red platform to the violet platform and return back to the red platform. The walk must observe the following rules:

If platform $α$ and platform $β$ have a common intersection and the frequency of the colour of platform $α$ is strictly smaller than the frequency of the colour of platform $β$ , then the explorer can walk from $α$ to $β$ during the walk from the red platform to the violet platform.
If platform $α$ and platform $β$ have a common intersection and the frequency of the colour of platform $α$ is strictly greater than the frequency of the colour of platform $β$ , then the explorer can walk from $α$ to $β$ during the walk from the violet platform to the red platform.
A coloured platform, with the exception of the red platform, disappears from display when the explorer walks away from it.

The developer of the game has programmed all the features of the game. All that is left is to ensure that the explorer has a chance to succeed in each instance of the game (that is, there is at least one valid walk from the red platform to the violet platform and then back again to the red platform). Your task is to write a program to check whether at least one valid path exists in each instance of the game.

Input

The input starts with an integer $K$ ( $1 \leq K \leq 50$ 1 \le K \le 50) indicating the number of scenarios, on a line by itself. The description for each scenario starts with an integer $N$ ( $2 \leq N \leq 300$ 2 \le N \le 300) indicating the number of platforms, on a line by itself, followed by $N$ lines that describe the colours, locations, and sizes of the $N$ platforms. Each line contains the frequency, followed by the $x$ - and $y$ -coordinates of the platform's center, and then the radius. The frequency is given as a real value with no more than three decimal places. The coordinates and radius are given, in meters, as integers. All values are separated by a single space. All integer values are in the range of $- 10000$ to $10000$ inclusive. In each scenario, all frequencies are in the range of $400.0$ to $789.0$ inclusive. Exactly one platform will have a frequency of $400.0$ and exactly one platform will have a frequency of $789.0$ .

Output

The output for each scenario consists of a single line that contains: Game is VALID, or Game is NOT VALID.

Esempi

Esempio 1