#J0004. 打扑克【CSP-J模拟赛T0】

打扑克【CSP-J模拟赛T0】

时间限制:1s1s,空间限制:512mb512mb

题目描述

小明今天放学后,在家与父母一起打扑克玩,但是小明并不会玩扑克游戏,于是只能现场玩一个叫猜牌的游戏。

具体地说,猜牌的规则是这样的:

一开始,小明的爸爸把nn张牌摆成一行。

接下来,小明的爸爸会执行TT次洗牌操作,每次洗牌,小明的爸爸会把当前第1,3,5,7,...1,3,5,7,...张牌挑出来,放到前面,然后把第2,4,6,8,...2,4,6,8,...张牌放到后面。

比如,一开始牌是[1,2,3,4,5,6,7,8][1,2,3,4,5,6,7,8],那么,执行第一次洗牌后,就变成了[1,3,5,7,2,4,6,8][1,3,5,7,2,4,6,8],再执行一次洗牌,就变成了[1,5,2,6,3,7,4,8][1,5,2,6,3,7,4,8]

执行完这TT次洗牌以后,小明的爸爸会指定QQ张牌b1,b2,...,bQb_1,b_2,...,b_Q,让小明猜,在洗牌以前的第bib_i张牌,现在是第几张牌。

小明觉得这还不简单?写个程序轻松搞定!

但是,小明开始写的时候却发现这个问题对他来说不简单,于是小明把这个问题交给了你。

输入格式

第一行输入三个正整数n,T,Qn,T,Q

接下来一行,输入QQ个整数b1,b2,...,bQb_1,b_2,...,b_Q

输出格式

输出QQ个数字表示答案。

样例输入 #1

8 2 8
1 2 3 4 5 6 7 8

样例输出 #1

1 3 5 7 2 4 6 8

样例解释 #1

最后的牌的样子是[1,5,2,6,3,7,4,8][1,5,2,6,3,7,4,8]。第11张牌还在11,第22张牌去了第33个位置,第33张牌去了第55个位置,...

样例输入 #2

1000 10000 8
1 2 3 4 5 6 7 8

样例输出 #2

1 257 513 769 26 282 538 794

数据范围

一共2020个测试点。

对于测试点1-8 :n,T1000n,T\leq 1000

对于测试点9-12 :T106T\leq 10^6

对于测试点13-16 :n1000n\leq 1000

对于测试点17-20 :无特别限制。

对于100%的数据:n106,T1018,Q10n\leq 10^{6},T\leq 10^{18},Q\leq 10

额外地:本题原来的数据范围其实是Q106Q\leq 10^6