I. Throwing dice
time limit per test
1 second
memory limit per test
16 megabytes
input
standard input
output
standard output

Alice and Bob are discussing penalty shoot-outs and their randomness: "We might as well be throwing dice to determine the winner!", Alice said. And so they started simulating penalty shoot-outs by each throwing dice, summing the points indicated on their dice, and comparing these sums. The player with the largest sum wins; in case both sums are equal, there is a tie.

But even in such situations, some player might have an edge over their opponent, depending on which dice they throw. Thus, just by looking at the dice they are about to throw, Alice and Bob want to determine who has the better edge.

Alice has $$$M$$$ fair dice, with $$$A_1, A_2, \dots, A_M$$$ sides. For all integers $$$k$$$ and $$$l$$$ such that $$$1 \leq k \leq M$$$ and $$$1 \leq l \leq A_k$$$, the $$$k^\text{th}$$$ die of Alice has a probability $$$1/A_k$$$ of showing its face numbered $$$l$$$. Then, Alice's score is the sum of the numbers displayed by her $$$M$$$ dice. Similarly, Bob has $$$N$$$ fair dice, with $$$B_1, B_2, \dots, B_N$$$ sides.

Given these dice, Alice has a probability $$$\mathbb{P}_A$$$ of having a strictly larger score than Bob, and Bob has a probability $$$\mathbb{P}_B$$$ of having a strictly larger score than Alice. Which probability is the largest one?

Input

The input consists of three lines, each one containing space-separated integers. The first line contains the numbers $$$M$$$ and $$$N$$$. The second line contains the numbers $$$A_1, A_2, \dots, A_M$$$. The third line contains the numbers $$$B_1, B_2, \dots, B_N$$$.

Limits

  • $$$1 \leq M \leq 100~000$$$;
  • $$$1 \leq N \leq 100~000$$$;
  • $$$4 \leq A_k \leq 1~000~000~000$$$ for all $$$k \leq M$$$;
  • $$$4 \leq B_k \leq 1~000~000~000$$$ for all $$$k \leq N$$$;
Output

The output should contain a single line, consisting of a single uppercase word: ALICE if $$$\mathbb{P}_A > \mathbb{P}_B$$$, TIED if $$$\mathbb{P}_A = \mathbb{P}_B$$$, and BOB if $$$\mathbb{P}_A < \mathbb{P}_B$$$.

Examples
Input
8 1
4 4 4 4 4 4 4 4
6
Output
ALICE
Input
2 2
6 4
4 6
Output
TIED
Note

Sample Explanation 1

Since Alice has 8 dice, her score is always 8 or more; Bob's score is always 6 or less. Hence, Alice has a probability $$$\mathbb{P}_A = 100\%$$$ of beating Bob, and he has a probability $$$\mathbb{P}_B = 0\%$$$ of beating her. Consequently, $$$\mathbb{P}_A > \mathbb{P}_B$$$.

Sample Explanation 2

Alice has a probability $$$\mathbb{P}_A = 125/288$$$ of beating Bob; he also has a probability $$$\mathbb{P}_B = 125/288$$$ of beating her.