We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Fun Game

Fun Game

Kyle and Mike are bored on a rainy day and decide to pass the time by creating a new game having the following rules:

  • The game starts with two -sized integer arrays, and , and is played by two players, and .
  • The players move in alternating turns, with always moving first. During each move, the current player must choose an integer, , such that . If the current player is , then receives points; if the current player is , then receives points.
  • Each value of can be chosen only once. That is, if a value of is already chosen by some player, none of the player can re-use it. So, game always ends after moves.
  • The player with the maximum number of points wins.
  • The arrays A and B are accessible to both the players P1 and P2. So the players make a optimal move at every turn.

Given the values of , , and , can you determine the outcome of the game? Print if will win, if will win, or if they will tie. Assume both players always move optimally.

Input Format

The first line of input contains a single integer, , denoting the number of test cases. Each of the subsequent lines describes a test case. A single test case is defined over the following three lines:

  1. An integer, , denoting the number of elements in arrays and .
  2. space-separated integers, , where each describes the element at index of array .
  3. space-separated integers, , where each describes the element at index of array .

Constraints

Output Format

For each test case, print one of the following predicted outcomes of the game on a new line:

  • Print if will win.
  • Print if will win.
  • Print if the two players will tie.

Sample Input

3
3
1 3 4
5 3 1
2
1 1
1 1
2
2 2
3 3

Sample Output

First
Tie
Second

Explanation

Test Case 0: , The players make the following moves:

  1. chooses and receives points.
  2. chooses and receives points. Note that will not choose , because this would cause to win.
  3. chooses (which is the only remaining move) and receives points.

As all moves have been made, the game ends. 's score is points and 's score is points, so is the winner and we print on a new line.

Test Case 1: , Because both players will only make move and all possible point values are , the players will end the game with equal scores. Thus, we print on a new line.

Test Case 1: ,
Because both players will only make move and all the possible point values for are greater than all the possible point values for , will win the game. Thus, we print on a new line.