/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
Alice と Bob でゲームをします．
はじめ，Alice, Bob はそれぞれ N 枚のカードを持っていて，Alice が持っている i 番目のカードには整数 A_i が，Bob が持っている i 番目のカードには整数 B_i が書かれてます．
ゲームは以下の手順で行われます．
- 何も書かれていない黒板を用意する．
- Alice が持っているカードを一枚食べ，食べたカードに書かれた整数を黒板に書く．
- 次に，Bob が持っているカードを一枚食べ，食べたカードに書かれた整数を黒板に書く．
- 最後に，Alice が持っているカードを一枚食べ，食べたカードに書かれた整数を黒板に書く．
黒板に書かれた 3 個の整数を 3 辺の長さとする（非退化な）三角形が存在すれば Alice の勝ちで，そうでないとき Bob の勝ちです．
両者が最適な行動をするとき，どちらが勝つか判定してください．
T 個のテストケースが与えられるので，それぞれについて答えてください．
制約
- 1 \leq T \leq 10^5
- 2\leq N\leq 2\times 10^5
- 1\leq A_i,B_i\leq 10^9
- 入力される数値は全て整数
- 1 つの入力に含まれるテストケースについて，N の総和は 2\times 10^5 以下
入力
入力は以下の形式で標準入力から与えられる．
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各ケースは以下の形式で与えられる．
N A_1 \ldots A_N B_1 \ldots B_N
出力
T 行出力せよ．i 行目 (1 \leq i \leq T) には， i 番目のテストケースについて，Alice が勝つ場合 Alice を，Bob が勝つ場合 Bob を出力せよ．
入力例 1
3 3 1 2 3 4 5 6 4 6 1 5 10 2 2 4 5 10 3 1 4 1 5 9 2 6 5 3 2 7 1 8 2 8 1 8 2 8
出力例 1
Bob Alice Alice
1 番目のテストケースでは，例えばゲームは以下のように進行します．
- Alice が 2 を書かれたカードを食べ，黒板に 2 を書く．
- Bob が 4 を書かれたカードを食べ，黒板に 4 を書く．
- Alice が 1 を書かれたカードを食べ，黒板に 1 を書く．
- 黒板に書かれた数は 2,4,1 であり，3 辺の長さが 2,4,1 であるような三角形は存在しないので Bob の勝ちとなる．
このテストケースについて，上記の手順が必ずしも両者にとって最適な行動とは限りませんが，両者が最適な行動をした場合勝利するのは Bob であることが示せます．
Score: 700 points
Problem Statement
Alice and Bob will play a game.
Initially, Alice and Bob each have N cards, with the i-th card of Alice having the integer A_i written on it, and the i-th card of Bob having the integer B_i written on it.
The game proceeds as follows:
- Prepare a blackboard with nothing written on it.
- Alice eats one of her cards and writes the integer from the eaten card on the blackboard.
- Next, Bob eats one of his cards and writes the integer from the eaten card on the blackboard.
- Finally, Alice eats one more of her cards and writes the integer from the eaten card on the blackboard.
If it is possible to form a (non-degenerate) triangle with the side lengths of the three integers written on the blackboard, Alice wins; otherwise, Bob wins.
Determine who wins when both players act optimally.
Solve each of the T given test cases.
Constraints
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
- All input values are integers.
- The sum of N over all test cases in a single input is at most 2 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is given in the following format:
N A_1 \ldots A_N B_1 \ldots B_N
Output
Print T lines. The i-th line (1 \leq i \leq T) should contain Alice if Alice wins for the i-th test case, and Bob if Bob wins.
Sample Input 1
3 3 1 2 3 4 5 6 4 6 1 5 10 2 2 4 5 10 3 1 4 1 5 9 2 6 5 3 2 7 1 8 2 8 1 8 2 8
Sample Output 1
Bob Alice Alice
In the first test case, for example, the game could proceed as follows:
- Alice eats the card with 2 written on it and writes 2 on the blackboard.
- Bob eats the card with 4 written on it and writes 4 on the blackboard.
- Alice eats the card with 1 written on it and writes 1 on the blackboard.
- The numbers written on the blackboard are 2, 4, 1. There is no triangle with side lengths 2, 4, 1, so Bob wins.
For this test case, the above process is not necessarily optimal for the players, but it can be shown that Bob will win if both players act optimally.