Throwing dice

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,...,a_m$ sides. For all integers $k$ and $l$ such that $1\le k\le m$ and $1\le l\le a_k$, the $k$-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 $p_a$ of having a strictly larger score than Bob, and Bob has a probability $p_b$ of having a strictly larger score than Alice. Which probability is the largest one?

Giriş verilənləri

The first line contains the numbers $m$ and $n(1\le n,m\le 10^5)$. The second line contains the numbers $a_1,a_2,\dots ,a_m(4\le a_k\le 10^9,1\le k\le m)$. The third line contains the numbers $b_1,b_2,\dots ,b_n(4\le b_k\le 10^9,1\le k\le n)$.

Çıxış verilənləri

Print a single uppercase word: "ALICE" if $p_a>p_b$, "TIED" if $p_a=p_b$, and "BOB" if $p_a<p_b$.

Nümunələr