配点 : 100 点
問題文
整数 N 和长度 N 整数序列 给出 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) 。 对于
Alice 和 Bob 各 N 卡。
爱丽丝拥有的卡片中, 第i 卡有 A_i 。
在鲍勃拥有的卡片中,i 卡有 B_i 。
Alice 和 Bob 都知道彼此卡的详细信息。
从现在开始,N 玩一轮纸牌游戏。起初,Alice 和 Bob 的分数都是 0 。在每一轮中,都会发生以下情况:
- Alice 和 Bob 同时打牌。 Alice 打出的牌上写的整数 a ,Bob 打出的牌上写的整数
根据 b 。a,b 的值,分数变化如下。
- a\ne b ,最好打出一张写有较大整数的牌。 |a-b| 获得…的分数。
- a=b ,两个玩家都没有得分。
- 此后发卡总数 裁判吃掉了 2 棋子。
N 回合结束时,得分最高的玩家获胜。但如果两队得分相同,则视为平局。
如果双方表现最优,则判断是否打平,如果不打平,则判定谁胜。
“最佳行动”是什么意思?
“表现最佳”是指按照以下方式行事。
- 如果无论对手如何行动都有可能让自己获胜,那么就以能让自己获胜的方式行动。
- 另一方面,如果无论对方如何行动,都可以防止自己失败,那么自己就会以不会失败的方式行事。
- 否则,随机执行该操作。
制約
- 1 \leq N\leq 2\times 10^5
- -10^9\leq A_i\leq 10^9 (1\leq i\leq N)
- -10^9\leq B_i\leq 10^9 (1\leq i\leq N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
如果是平局 Draw 如果爱丽丝赢了 Alice 如果鲍勃获胜
输出 Bob 。
在第
入力例 1
4 2 0 2 5 0 4 0 1
出力例 1
Alice
例如,游戏进行如下。
- 爱丽丝 鲍勃收到一张写有 2 的卡片。 打出一张写有 0 的牌。爱丽丝 打出一张写有 |2-0|=2 获得…的分数。
- 爱丽丝 鲍勃收到一张写有 2 的卡片。 打出一张写有 4 的牌。鲍勃 打出一张写有 |2-4|=2 获得…的分数。
- 爱丽丝 鲍勃收到一张写有 0 的卡片。 打出一张写有 0 的牌。他们俩都没有得分。
- 爱丽丝 鲍勃收到一张写有 5 的卡片。 打出一张写有 1 的牌。爱丽丝 打出一张写有 |5-1|=4 获得…的分数。
Alice的最终得分是 6 ,Bob 的分数是 2 所以爱丽丝赢了。
这并不一定意味着双方都表现最佳,但它表明即使双方表现最佳,Alice 仍然获胜。
入力例 2
1 3 3
出力例 2
Draw
显然是平局。 给出