You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

$Diana$ 和 $Ava$ 正在玩游戏。

$Diana$ 和 $Ava$ 有一个集合 $S$ ，初始由互异的元素 $s_1,s_2,...,s_m$ 构成，还有一个队列 $b_1,b_2,...,b_k$ ， $Diana$ 和 $Ava$ 交替进行以下操作（由 $Diana$ 开始），直到队列 $b$ 为空：

• 把 $b$ 中的第一个数放入 $S$.

• 取走 $S$ 中的一个数 $x$ ，然后把它累积到自己的得分中。

$Diana$ 和 $Ava$ 都希望最大化自己的得分。

为了使游戏更具有趣味性，$Diana$ 和 $Ava$ 找来了一个元素互异的序列 $a_1,a_2,...,a_n$ ，保证 $a$ , $s$ 中没有相同元素。

她们将会进行 $q$ 场游戏。对于每场游戏，她们都会给小 $z$ 三个数 $l$ , $r$ , $x$ ，向小 $z$ 询问，若选用区间 $a_l,a_{l+1},...,a_r$ 作为 $b$ 进行一场游戏，在二者都采用最优策略的情况下，位置 $x$ 的元素 $a_x$ 是被谁取走的。

由于小 $z$ 不会，所以只好求助于学 $OI$ 的你。

输入格式

从文件 $game.in$ 中读入数据。

第一行三个正整数 $n$ , $m$ , $q$ 。

第二行 $n$ 个正整数 $a_1,a_2,...,a_n$ 。

第三行 $m$ 个正整数 $s_1,s_2,...,s_m$ 。

接下来 $q$ 行，每行三个正整数 $l$ , $r$ , $x$ 。

输出格式

输出到文件 $game.out$ 中。

共 $q$ 行，每行一个字符串表示答案。若 $Diana$ 取得了 $a_x$ ，则输出 $Diana$ ，若 $Ava$ 取得了 $a_x$ ，则输出 $Ava$ ，若无人取得 $a_x$ ，输出 $‐1$ 。

可以证明的是，在本题数据范围下，不存在某个数，使得其既可能被 $Diana$ 取走，又可能被 $Ava$ 取走。

样例 1 输入：

5 4 5
9 5 7 3 4
2 6 1 8
1 5 1
1 5 2
2 5 3
2 5 5
2 3 3

样例 1 输出：

Diana
Diana
Ava
-1
Ava

样例 2 ：

见右侧文件下的 $game2.in$ 与 $game2.ans$ 。

样例 3 ：

见右侧文件下的 $game3.in$ 与 $game3.ans$ 。

数据范围

对于所有测试数据，保证 $1≤n,m,q≤10^6$ ，$1≤a_i,s_i≤n+m$ ，$1≤l≤x≤r≤n$ ，保证将 $a$ , $s$ 拼接后得到的序列为 $1∼n+m$ 的一个排列。

每个测试点的具体限制见下表：

提.示：本题输入输出量较大，请使用较快的输入输出方式。