← 返回题目列表

Codeforces · 103/C

C. 俄罗斯轮盘赌

中文机器翻译题面 查看原题

在奥兰多发生的所有事件之后,萨沙和罗马决定找出谁仍然是球队最大的输家。值得庆幸的是,玛莎在某处发现了一把左轮手枪,其旋转圆筒有 n 个子弹槽,可以恰好容纳 k 颗子弹,现在男孩们有机会一劳永逸地解决这个问题。

Sasha 从 n 个槽位中选择任意 k 个槽位,并将子弹放在那里。 Roma 旋转圆柱体,使得 n 个可能的圆柱体移动中的每一个都是等概率的。然后游戏开始,玩家轮流,萨沙开始:他把枪抵在头上并射击。如果扳机前面没有子弹,气缸就会移动一个位置,并将武器交给罗马进行相同的移动。游戏一直持续到有人被枪杀为止,幸存者就是胜利者。

萨沙不想输,所以他必须以尽量减少自己损失的概率来选择子弹槽。在所有可能的变体中,他想要选择字典顺序最小的一个,其中空槽按字典顺序小于带电槽。

更正式地说,能够容纳 k 颗子弹的 n 个子弹槽的圆柱体可以表示为 n 个字符的字符串。其中 k 个为“X”(带电槽),其他为“.”。 (不收费的插槽)。

让我们描述一下一个镜头的过程。假设触发器位于字符串的第一个字符(第一个槽)的前面。如果射击没有杀死任何人并且圆柱体移动,那么绳子就会向左移动。因此第一个字符成为最后一个字符,第二个字符成为第一个字符,依此类推。但扳机不动。它将位于结果字符串的第一个字符的前面。

在所有给出最小丢失概率的字符串中,Sasha 选择了字典顺序最小的一个。根据这个字符串,他给枪充电。你必须帮助萨沙给枪充电。为此,必须回答每个 xi 查询:位置 xi 中是否有子弹?

输入

第一行包含三个整数 n、k 和 p (1 ≤ n ≤ 1018, 0 ≤ k ≤ n, 1 ≤ p ≤ 1000) — 圆柱体中的槽数、子弹数和查询数。然后按照p行;它们是查询。每一行包含一个整数 xi (1 ≤ xi ≤ n) 来描述槽的数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位数字。最好使用 cin、cout 流或 %I64d 指定器。

输出

对于每个查询打印“.”如果插槽应为空,则“X”表示插槽应充电。

示例

输入 #1

3 1 3
1
2
3

输出 #1

..X

输入 #2

6 3 6
1
2
3
4
5
6

输出 #2

.X.X.X

输入 #3

5 2 5
1
2
3
4
5

输出 #3

...XX

注意

现代编程语言中的字典顺序比较由 < 运算符执行。如果存在这样的 i (1 ≤ i ≤ n),且 ai < bi,并且对于任何 j (1 ≤ j < i) aj = bj,则 a 字符串按字典顺序小于 b 字符串。