{"problem":{"name":"四暗刻单骑","description":{"content":"Alice 和 Bob 很喜欢打麻将。他们在对麻将规则熟悉后，开始对「四暗刻单骑」感兴趣。而在这局游戏中，Alice 和 Bob 都已经集齐了四暗刻，处于听牌状态并准备「四暗刻单骑」，于是我们将这样的局面简化如下： - 一张麻将牌可以用一个范围在 $[1, k]$ 内的正整数表示，数字相同的牌相同，数字不同的牌不相同。 - Alice 和 Bob 手中各有 $1$ 张牌作为手牌。两人轮流进行摸牌","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9839"},"statements":[{"statement_type":"Markdown","content":"Alice 和 Bob 很喜欢打麻将。他们在对麻将规则熟悉后，开始对「四暗刻单骑」感兴趣。而在这局游戏中，Alice 和 Bob 都已经集齐了四暗刻，处于听牌状态并准备「四暗刻单骑」，于是我们将这样的局面简化如下：\n\n- 一张麻将牌可以用一个范围在 $[1, k]$ 内的正整数表示，数字相同的牌相同，数字不同的牌不相同。\n- Alice 和 Bob 手中各有 $1$ 张牌作为手牌。两人轮流进行摸牌，每次摸牌的玩家会得到一张牌堆顶部的牌，Alice 先进行。摸牌后会有 $2$ 张手牌，此时需要选择一张牌打出。打出的牌双方可见。\n- 当摸牌时两张手牌相同时，或当前对方打出的牌和自己目前手牌相同时，该玩家「和牌」并获胜，游戏结束。\n\n若牌摸完后无玩家「和牌」，则判为「荒牌流局」，此时判定两位玩家平局。\n\n现在 Alice 和 Bob 都绝顶聪明，并且已经得知了牌堆顶部的所有牌，以及对方手牌。他们都希望自己可以「和牌」并获胜，若自己无法「和牌」就会尽可能阻止对方「和牌」。\n\n你现在拿到了 $n$ 张麻将牌组成的 $a$ 数组，下标依次为 $1\\dots n$。现在有 $m$ 次询问，每次会给定 $x, y, l, r$ 表示：若目前 Alice 手牌为 $x$，Bob 手牌为 $y$，且 **按顺序** 取出 $a$ 中下标为 $[l, r]$ 的所有牌作为游戏牌堆，其中牌 $a_l$ 位于牌堆顶部，Alice 和 Bob 按要求进行游戏，最后结局如何。\n\n询问之间相互独立。特别地，**保证 $l$ 为奇数**。\n\n## Input\n\n从标准输入中读入数据。\n\n第一行三个正整数 $n, m, k$。\n\n接下来一行 $n$ 个正整数，依次表示 $a_1, a_2 \\dots a_n$。\n\n接下来 $m$ 行，每行四个正整数 $x,y,l,r$，表示一次询问。\n\n## Output\n\n输出到标准输出。\n\n对于每次询问，输出一行一个字符：如果 Alice 获胜，输出 `A`；如果 Bob 获胜，输出 `B`；如果平局，输出 `D`。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n在第 $1$ 组询问中，牌堆自顶至底依次是 $3, 4$，Alice 手牌为 $1$，Bob 手牌为 $2$。不难发现此局面会导致「荒牌流局」。 \n\n在第 $2$ 组询问中，牌堆自顶至底依次是 $1, 3, 1, 5, 4, 3$，Alice 手牌为 $5$，Bob 手牌为 $5$。此时 Bob 只需要一直保留这张 $5$，就可以在摸上下一张 $5$ 时「和牌」；而 Alice 不能打出 $5$，因为一旦打出就会导致 Bob 立刻「和牌」。\n\n在第 $3$ 组询问中，牌堆自顶至底依次是 $1, 2, 3, 4, 1$，Alice 手牌为 $3$，Bob 手牌为 $4$。Alice 第一局摸上一张 $1$，她打出这张 $1$。Bob 第一局摸上一张 $2$，他无论是否打出这张 $2$，Alice 都可以在下回合「和牌」。 \n\n---\n\n#### 【样例 3】\n\n见附件下的 $\\verb!mahjong/mahjong3.in!$ 与 $\\verb!mahjong/mahjong3.ans!$。\n\n---\n\n#### 【样例 4】\n\n见附件下的 $\\verb!mahjong/mahjong4.in!$ 与 $\\verb!mahjong/mahjong4.ans!$。\n\n---\n\n**【数据范围】**\n\n| 测试点编号 | $n\\le$ | $m\\le$ | $k\\le$ | 特殊性质 |\n| :--------: | :----: | :----: | :----: | :------: |\n| $1$ | $3$ | $3$ | $3$ | A, B |\n| $2$ | $5$ | $5$ | $5$ | 无 |\n| $3\\sim 5$ | $100$ | $100$ | $100$ | 无 |\n| $6\\sim 7$ | $2000$ | $2000$ | $2000$ | 无 |\n| $8\\sim 10$ | $5\\times 10^4$ | $50$ | $5\\times 10^4$ | 无 |\n| $11$ | $2\\times 10^5$ | $2\\times 10^5$ | $2$ | 无 |\n| $12$ | $2\\times 10^5$ | $2\\times 10^5$ | $80$ | 无 |\n| $13$ | $2\\times 10^5$ | $2\\times 10^5$ | $2\\times 10^5$ | A, B |\n| $14\\sim 15$ | $2\\times 10^5$ | $2\\times 10^5$ | $2\\times 10^5$ | B |\n| $16$ | $2\\times 10^5$ | $2\\times 10^5$ | $2\\times 10^5$ | C |\n| $17\\sim 20$ | $10^5$ | $10^5$ | $10^5$ | 无 |\n| $21\\sim 25$ | $2\\times 10^5$ | $2\\times 10^5$ | $2\\times 10^5$ | 无 |\n\n+ 特殊性质 A：保证每次询问 $l = 1$。\n+ 特殊性质 B：保证每次询问 $r = n$。\n+ 特殊性质 C：保证每次询问 $x = y$。\n\n对于 $100\\%$ 的数据，保证 $3 \\leq n \\leq 2\\times 10^5$，$1 \\leq m \\leq 2\\times 10^5$，$1 \\leq a_i, x, y \\leq k \\leq n$，$1 \\leq l \\leq r \\leq n$，**保证 $l$ 是奇数**。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9839","tags":["贪心","树形数据结构","博弈论","线段树","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["12 3 5\n2 3 1 2 3 4 1 3 1 5 4 3\n1 2 5 6\n5 5 7 12\n3 4 3 7","D\nB\nA"],["7 6 3\n2 3 3 3 1 3 3 \n1 2 5 7\n1 1 5 6\n1 3 1 6\n2 3 7 7\n1 3 3 5\n1 2 1 4","A\nA\nB\nD\nB\nD\n"]],"created_at":"2026-03-03 11:09:25"}}