#P11865. 「o.OI R1」飞起来

「o.OI R1」飞起来

题目背景

小 C 和小 T 居住在一个反重力星球上。

他们还喜欢各自在自己家的窗台上向下抛物。

自然而然地物体会向上飞。

题目描述

小 C 有一个长度为 nn 的序列 CC,小 T 有一个长度也为 nn 的序列 TT,保证两个序列中的 2n2n 个数互不相同。

小 C 和小 T 想要玩一个游戏,过程如下,按顺序执行:

  • 游戏开始时,两人都会知道自己的序列和对方的序列的内容。
  • 小 C 从他的序列 CC 中选择两个不同的数,设为 aacc(需要满足 a<ca<c),并将这两个数告诉小 T
  • 小 T 从他的序列 TT 中选择两个不同的数,设为 bbdd(需要满足 b<db<d),并将这两个数告诉小 C
  • 小 C 选择一个实数,设为 xcx_c(需要满足 axcca\leq x_c\leq c),并将其告诉小 T
  • 小 T 选择一个实数,设为 xtx_t(需要满足 bxtdb\leq x_t\leq d),并将其告诉小 C
  • x=xc+xt2x=\dfrac{x_c+x_t}{2},小 C 的得分为 (xa)(xc)(x-a)(x-c),小 T 的得分为 (xb)(xd)(x-b)(x-d)
  • 得分大的一方赢,得分相同则平局。

你需要求出在两人都采取最优策略时谁会赢,并给出一种小 C 选择数字 aacc 的方案。

最优策略是指尽量让自己赢,如果不行尽量平局。

输入格式

本题有多组数据。

第一行一个正整数 TT,代表数据组数。

对于每组数据:

  • 第一行一个整数 nn
  • 第二行 nn 个整数,第 ii 个整数表示 CiC_i
  • 第三行 nn 个整数,第 ii 个整数表示 TiT_i

输出格式

对于每组数据输出一行:

  • 如果小 C 必胜,先输出一个字符 C
  • 如果小 T 必胜,先输出一个字符 T
  • 如果两人将平局,先输出 Draw
  • 接下来输出两个整数,代表小 C 可以选择的两个数字 aacc

输出的两个数需要保证可以达成给出的结果。

输入数据 1

3
2
3 7
2 4
3
-3 1 2
-2 -1 5
3
2 9 15
17 -9 18

输出数据 1

T 3 7
Draw 1 2
C 2 15

提示

可能有其他的策略,但是最后结果是一样的。

「样例解释 #1」

小 C 只能选择 3377,小 T 只能选择 2244

接下来小 T 可以选择 3.83.8,这样小 C 怎么做选择都会输。

「样例解释 #2」

小 C 如果选择 1122,小 T 只能选择 2-21-1 才可以达成平局。

「样例解释 #3」

小 C 可以选择 221515,小 T 无论如何选择都会输。

「数据范围」

本题采用捆绑测试与 Special Judge。

n\sum n 为一个数据点所有 nn 的和。

对于所有测试数据,保证:

  • 2n,n1062\leq n,\sum n \leq 10^6
  • 109Ci,Ti109-10^{9}\leq C_i,T_i\leq 10^{9}
子任务 n\sum n Ci,Ti\lvert C_i\rvert,\lvert T_i\rvert 特殊性质 分值
00 20\leq 20 100\leq 100 1010
11 300\leq 300 109\leq 10^9 1515
22 2000\leq 2000
33 105\leq 10^5 109\leq 10^{9} A 1010
44 B 1515
55
66 106\leq 10^6 2020
  • 特殊性质 A:Cn<T1C_{n}<T_1,且对于任意的整数 i(1i<n)i(1\le i< n) 都有 Ci<Ci+1C_{i}<C_{i+1}Ti<Ti+1T_{i}<T_{i+1}
  • 特殊性质 B:C1<T1C_1<T_1,且对于任意的整数 i(1i<n)i(1\le i< n) 都有 Ti<Ci+1<Ti+1T_i<C_{i+1}<T_{i+1}