Пахом на воде
Pahom on Water — это интерактивная компьютерная игра, вдохновленная рассказом Льва Толстого о бедняке, который в своей жажде земли теряет всё. На стартовом экране игры отображается несколько круглых площадок, окрашенных в цвета видимого спектра света. Более одной площадки может быть окрашено в один и тот же цвет (определяемый определенной частотой), за исключением двух цветов: красного и фиолетового. На экране отображается только одна красная площадка (с самой низкой частотой 400 ТГц) и одна фиолетовая площадка (с самой высокой частотой 789 ТГц). Площадки могут пересекаться или даже содержать друг друга, но никогда не касаться только границами. На экране также показана фигура, представляющая Пахома, стоящая на красной площадке.
Цель игры — провести фигуру Пахома от красной площадки к фиолетовой и вернуться обратно на красную площадку. Прогулка должна соблюдать следующие правила:
Если площадка α и площадка β имеют общую область пересечения, и частота цвета площадки α строго меньше частоты цвета площадки β, то фигура Пахома может перейти с α на β во время прогулки от красной площадки к фиолетовой.
Если площадка α и площадка β имеют общую область пересечения, и частота цвета площадки α строго больше частоты цвета площадки β, то фигура Пахома может перейти с α на β во время прогулки от фиолетовой площадки к красной.
Окрашенная площадка, за исключением красной, исчезает с экрана, когда фигура Пахома уходит с неё.
Разработчик игры запрограммировал все сложные функции игры. Осталось только убедиться, что у Пахома есть шанс на успех в каждом случае игры (то есть существует хотя бы один допустимый путь от красной площадки к фиолетовой и обратно к красной). Ваша задача — написать программу, чтобы проверить, существует ли хотя бы один допустимый путь в каждом случае игры.
Входные данные
Ввод начинается с целого числа K (1 ≤ K ≤ 50), указывающего количество сценариев в отдельной строке. Описание каждого сценария начинается с целого числа N (2 ≤ N ≤ 300), указывающего количество площадок, в отдельной строке, за которым следуют N строк, описывающих цвета, местоположения и размеры N площадок. Каждая строка содержит частоту, за которой следуют x- и y-координаты центра площадки, а затем радиус. Частота задается как вещественное число с не более чем тремя десятичными знаками. Координаты и радиус задаются в метрах как целые числа. Все значения разделены одним пробелом. Все целые значения находятся в диапазоне от -10000 до 10000 включительно. В каждом сценарии все частоты находятся в диапазоне от 400.0 до 789.0 включительно. Ровно одна площадка будет иметь частоту "400.0", и ровно одна площадка будет иметь частоту "789.0".
Выходные данные
Вывод для каждого сценария состоит из одной строки, содержащей: Game is VALID, или Game is NOT VALID.