C. GG and YY's Game
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Two strategic players, GG and YY, are about to engage in a competitive game. The game takes place on an undirected graph, denoted as $$$G$$$. The graph is characterized by a parameter $$$t$$$ ($$$t \geq 1$$$) and comprises $$$n$$$ disjoint chains.

The rules of the game are as follows:

  • GG and YY take turns to make a move on graph $$$G$$$, with GG always going first.
  • During each turn, the player chooses one node, denoted as $$$s$$$, from the graph. Upon this selection, the player captures all nodes on the same chain as $$$s$$$ that are at a distance of at most $$$t$$$ from $$$s$$$, including $$$s$$$ itself.
  • Once a node is captured, it is eliminated from the graph, potentially causing the chain to break apart.
  • The game proceeds until all vertices are captured, at which point the game concludes.

Both GG and YY aim to capture the maximum number of nodes. Let $$$\text{cnt}_\text{GG}$$$ and $$$\text{cnt}_\text{YY}$$$ represent the number of nodes captured by GG and YY, respectively. Assuming both players, GG and YY, employ their optimal strategies, your task is to determine:

  • When $$$t=1$$$, what is the value of $$$\text{cnt}_\text{GG}-\text{cnt}_\text{YY}$$$?
  • When $$$t \gt 1$$$, which player wins the game?
Input

The first line contains one integer $$$T$$$ ($$$1\le T\le 100$$$), indicating the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$t$$$ ($$$1\le n\le 10^4$$$,$$$1\le t\le 10^{18}$$$), indicating the number of chains and the parameter.

The second line of each test contains $$$n$$$ integers $$$l_{1},l_2,\ldots,l_n$$$, where each $$$l_i$$$ ($$$1\le l_i\le 10^{18}$$$) indicates that a distinct chain of length $$$l_{i}$$$ exists in $$$G$$$.

Output

For each test, output the answer in a single line.

  • When $$$t=1$$$, output $$$\text{cnt}_\text{GG}-\text{cnt}_\text{YY}$$$.
  • When $$$t \gt 1$$$, output $$$\texttt{GG}$$$ if GG wins, or output $$$\texttt{YY}$$$ if YY wins, or output $$$\texttt{TIE}$$$ if the game results in a tie.
Example
Input
2
2 1
1 5
2 2
1 5
Output
2
GG