时间限制：$1s$，空间限制：$512mb$

题目描述

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

具体地说，猜牌的规则是这样的：

一开始，小明的爸爸把$n$张牌摆成一行。

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

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

执行完这$T$次洗牌以后，小明的爸爸会指定$Q$张牌$b_1,b_2,...,b_Q$，让小明猜，在洗牌以前的第$b_i$张牌，现在是第几张牌。

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

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

输入格式

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

接下来一行，输入$Q$个整数$b_1,b_2,...,b_Q$。

输出格式

输出$Q$个数字表示答案。

样例输入 #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$张牌还在$1$，第$2$张牌去了第$3$个位置，第$3$张牌去了第$5$个位置，...

样例输入 #2

1000 10000 8
1 2 3 4 5 6 7 8

样例输出 #2

1 257 513 769 26 282 538 794

数据范围

一共$20$个测试点。

对于测试点1-8 ：$n,T\leq 1000$。

对于测试点9-12 ：$T\leq 10^6$。

对于测试点13-16 ：$n\leq 1000$。

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

对于100%的数据：$n\leq 10^{6},T\leq 10^{18},Q\leq 10$。

额外地：本题原来的数据范围其实是$Q\leq 10^6$。

时间限制：$1.5s$，空间限制：$512mb$

题目描述

在$3202$年，小明发明了一个自动AC机。这个机器特别厉害，可以做任何题目。

可惜这个机器还在验证正确性的阶段，如果通过了验证阶段，才能说明这个机器真的管用。

今天，小明给这个机器投喂了这样一道题目。

小明有一个数字，这个数字$f$在第$1$天的值$f_1$是$1$，第$2$天的值$f_2$是$1$，第$i(i\geq 3)$天的值$f_i$是$(f_{i-1}+f_{i-2})\mod P$。

那么，第$n$天的值是多少呢？

输入格式

第一行输入两个正整数$n,P$。

输出格式

输出一个数字表示答案。

样例输入 #1

10 998244353

样例输出 #1

55

样例解释 #1

前$10$项分别是$1,1,2,3,5,8,13,21,34,55$。

样例输入 #2

998244353 997

样例输出 #2

950

数据范围

一共$20$个测试点。

对于测试点1-8 ：$n\leq 10^5$。

对于测试点9-10 ：$n\leq 10^9$。（提示：小常数$1e9$的做法是可以过的）

对于测试点11-17 ：$P\leq 1000$。

对于测试点18-20 ：无特别限制。

对于100%的数据：$n\leq 10^{12},3\leq P\leq 998244353$。

时间限制：$1s$，空间限制：$512mb$

题目描述

小明有一个$n\times m$的中国象棋棋盘。

在中国象棋的规则里，马这种棋子的行走规则是日字形，马的攻击范围如图所示：

我们不需要考虑实际下棋中“蹩马腿”的规则。

小明比较好奇：在这样一个$n\times m$的棋盘上，最多可以放多少个马，使得他们之间互相无法攻击的到，以及，在满足最多的前提条件下，有多少种合法的放置方法。

输入格式

第一行输入两个正整数$n,m$。

输出格式

输出两个数字，第一个数字表示最多的马的个数，第二个数字表示答案。

样例输入 #1

2 2

样例输出 #1

4 1

样例解释 #1

显然，在$2\times 2$的棋盘上，全放上马是一定合法的。

样例输入 #2

2 3

样例输出 #2

4 4

样例解释 #2

最多只能放4匹马，方案如下图。

数据范围

一共$20$个测试点。

对于测试点1-2 ：$n,m\leq 2$。

对于测试点3-4 ：$n,m\leq 3$。

对于测试点5-6 ：$n,m\leq 4$。

对于测试点7-8 ：$n,m\leq 5$。

对于测试点9-10 ：$n,m\leq 6$。

对于测试点11-12 ：$n,m\leq 7$。

对于测试点13-14 ：$n,m\leq 8$。

对于测试点15-17 ：$n,m\leq 9$。

对于测试点18-20 ：$n,m\leq 10$。

对于100%的数据：$1\leq n,m\leq 10$，保证数据点中一定出现过$n=m$的所有取值。

题目描述

小明有一个机器人，一开始在坐标原点，方向是朝着$X$轴正方向的。

一共有$N$秒，在第$i$秒，小明可以决定，让机器人顺时针或者逆时针转$90°$，然后沿着当前方向行走$A_i$的距离，其中，顺指针旋转的代价是$L_i$，逆时针旋转的代价是$R_i$。

小明希望结束行走时，机器人离坐标系原点的欧几里得距离最小，问：小明最少要付出多少代价。

输入格式

第一行输入$N$。

第二、第三、第四行分别输入$A_i,L_i,R_i$。

输出格式

输出一个数字表示答案。

样例输入 #1

2
1 1
10 1
1 10

样例输出 #1

2

样例解释 #1

小明随便怎么选，最终都会停留在$±1,±1$坐标上，距离原点的距离永远是一样的，还不如选便宜的。

样例输入 #2

3
1 1 1
10 1 10
1 10 20

样例输出 #2

12

样例解释 #2

小明第一秒选择逆指针旋转，花费$1$，走到了$(0,1)$，第二秒选择顺时针旋转，花费$1$，走到了$(1,1)$，第三秒选择顺时针旋转，花费$10$，走到了$(1,0)$。一共花费$12$。

样例输入 #3

10
1 2 4 8 16 16 8 4 2 1
10 54 12 45 1 45 12 45 12 45
65 45 78 45 12 5 12 32 12 12

样例输出 #3

197

数据范围

对于20%的数据：$N\leq 20$。

对于65%的数据：$A_i\leq 35$。

对于100%的数据：$2\leq N\leq 40,1\leq L_i,R_i,A_i\leq 10^7$。