Throwing dice

Time limit1sMemory limit1024 MB

Summary

Given the side counts of Alice's and Bob's fair dice (each at least 4), decide whether Alice or Bob is more likely to get the strictly larger total, or whether the two chances are equal.

Level: Medium7 of 10
Topics: Probability, Math
Solved: No attempts yet

Problem

Alice and Bob are discussing penalty shoot-outs and their randomness. Alice says they might as well be throwing dice to decide the winner. They simulate penalty shoot-outs by each throwing dice, summing the numbers shown, and comparing the sums. The player with the larger sum wins. If the sums are equal, it is a tie.

Even so, a player may have an edge depending on which dice they throw. Alice and Bob want to know which of them has the better edge, judging only from the dice they are about to throw.

Alice has $M$ fair dice with $A_1, A_2, \dots, A_M$ sides. For every $1 \le k \le M$ and $1 \le \ell \le A_k$ , the $k$ th die shows face $\ell$ with probability $1/A_k$ . Alice's score is the sum of the numbers shown by her $M$ dice. Bob has $N$ fair dice with $B_1, B_2, \dots, B_N$ sides, and his score is defined the same way.

Alice has probability $\mathbb{P}_A$ of scoring strictly more than Bob, and Bob has probability $\mathbb{P}_B$ of scoring strictly more than Alice. Which probability is the largest?

Input

The input consists of three lines. The first line contains $M$ and $N$ . The second line contains $A_1, A_2, \dots, A_M$ . The third line contains $B_1, B_2, \dots, B_N$ .

Output

Print a single line with one 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$ .

Constraints

$1 \le M \le 100000$
$1 \le N \le 100000$
$4 \le A_k \le 10^9$ for all $k \le M$
$4 \le B_k \le 10^9$ for all $k \le N$

Examples2

Example 1
Input
```
8 1
4 4 4 4 4 4 4 4
6
```
Expected output
```
ALICE
```
Example 2
Input
```
2 2
6 4
4 6
```
Expected output
```
TIED
```