Russian Roulette

题意翻译

在Orlando发生了我们都知道的事情之后，Sasha和Roma决定找出谁仍然是球队最大的输家。谢天谢地，Masha在某个地方发现了一把左轮手枪，它的转轮上有$n$个弹槽，恰好可以装$k$个子弹，现在男孩们有机会一劳永逸地解决这个问题。 Sasha从$n$个弹槽中选择任意$k$个，然后把子弹放在那里。Roma旋转转轮，使得转轮的$n$种位置都是等概率的。然后游戏开始，玩家轮流操作，Sasha先手：他把枪顶着脑袋开枪。如果扳机前没有子弹，转轮会移动一个位置，手枪也会交给Roma，让Roma做出同样的动作。游戏一直持续到有人中枪，幸存者就是赢家。 Sasha不想输，所以他必须选择子弹放置的位置，这样才能把自己输的概率降到最低。 更正式地说，能够包含$k$子弹的$n$弹槽的圆柱体可以表示为$n$字符的字符串。其中$k$个是“X”（有子弹），其他是“.”（空弹槽）。定义“.”字典序小于“X”，在所有可能的方案中，他希望选择字典序最小的一个。 现在给出$p$个询问，要求你回答弹槽$x$是否有子弹。

题目描述

After all the events in Orlando we all know, Sasha and Roma decided to find out who is still the team's biggest loser. Thankfully, Masha found somewhere a revolver with a rotating cylinder of $ n $ bullet slots able to contain exactly $ k $ bullets, now the boys have a chance to resolve the problem once and for all. Sasha selects any $ k $ out of $ n $ slots he wishes and puts bullets there. Roma spins the cylinder so that every of $ n $ possible cylinder's shifts is equiprobable. Then the game starts, the players take turns, Sasha starts: he puts the gun to his head and shoots. If there was no bullet in front of the trigger, the cylinder shifts by one position and the weapon is given to Roma for make the same move. The game continues until someone is shot, the survivor is the winner. Sasha does not want to lose, so he must choose slots for bullets in such a way as to minimize the probability of its own loss. Of all the possible variant he wants to select the lexicographically minimal one, where an empty slot is lexicographically less than a charged one. More formally, the cylinder of $ n $ bullet slots able to contain $ k $ bullets can be represented as a string of $ n $ characters. Exactly $ k $ of them are "X" (charged slots) and the others are "." (uncharged slots). Let us describe the process of a shot. Suppose that the trigger is in front of the first character of the string (the first slot). If a shot doesn't kill anyone and the cylinder shifts, then the string shifts left. So the first character becomes the last one, the second character becomes the first one, and so on. But the trigger doesn't move. It will be in front of the first character of the resulting string. Among all the strings that give the minimal probability of loss, Sasha choose the lexicographically minimal one. According to this very string, he charges the gun. You have to help Sasha to charge the gun. For that, each $ x_{i} $ query must be answered: is there a bullet in the positions $ x_{i} $ ?

输入输出格式

输入格式

The first line contains three integers $ n $ , $ k $ and $ p $ ( $ 1<=n<=10^{18},0<=k<=n,1<=p<=1000 $ ) — the number of slots in the cylinder, the number of bullets and the number of queries. Then follow $ p $ lines; they are the queries. Each line contains one integer $ x_{i} $ ( $ 1<=x_{i}<=n $ ) the number of slot to describe. Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

输出格式

For each query print "." if the slot should be empty and "X" if the slot should be charged.

输入输出样例

输入样例 #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

说明

The lexicographical comparison of is performed by the < operator in modern programming languages. The $ a $ string is lexicographically less that the $ b $ string, if there exists such $ i $ ( $ 1<=i<=n $ ), that $ a_{i}&lt;b_{i} $ , and for any $ j $ ( $ 1<=j&lt;i $ ) $ a_{j}=b_{j} $ .