Tsawke的三月模拟赛

注意事项

1. 所有文件名均保证为小写（友情提示：请格外注意文件名）。

2. C++ 中 main() 函数返回值必须为 int 且为 $0$$0$。

3. C++ 编译器开启 C++14 标准及 O2 优化。

4. 提交的程序源文件需独立文件夹。

5. 结果比较方式为全文比较（忽略行末空格及行尾回车）。

6. 程序可使用的栈空间限制与对应题目内存限制一致。

7. 评测采用机器配置为：11th Gen Intel(R) Core(TM) i5-11320H @ 3.20GHz。注意：测评将在 Linux 虚拟机中进行，配置会有部分降低，对于造成影响的题目会增加部分时限测评将在 Windows 下进行，若使用到了 Linux 特性请提前告知。

8. 编译选项为：g++ -o sample sample.cpp -lm -Wl,--stack=2147483647 -std=c++14 -O2。

9. 对于本地 Linux 环境下调试时，可以添加编译选项：-fsanitize=undefined,signed-integer-overflow,address 以检测未定义行为、整数溢出，地址越界等问题。

10. 对于提答题请将 .out 为扩展名的文件统一放到子目录下。

最佳贪污（corruption）

题目背景

作为🐔🌲🌲🌲省最大的建筑承包商，tsawke 近日接到了 6Bit 的修建地铁的任务，tsawke 自然得到了大量的资金，但是 tsawke 不知道如何修建才能在完成最基础的任务（否则 tsawke 就要进🍊了）的前提下尽可能地贪污掉更多的💴，于是他来寻求聪明的你的帮助。

特别地，对于 tsawke 来讲，地铁轨道的长度并不会影响价格，因为他可以通过在换乘站将乘客打晕然后搬到下一个换乘站来模拟地铁的过程，所以你只需要尽可能地使 tsawke 可以更少地修建地铁换乘站。

题目描述

在地铁网络中我们认为有多条线路，当两条线路有交点时我们认为交点处必须修建且仅修建一个地铁换乘站。

特别地，保证没有线路是环线的，也没有线路与自身相交，亦没有线路存在重合的部分，具体地，对于如下四种情况都是显然不存在的：

但是此时 tsawke 经过实地勘察发现了一些事实，即有一部分换乘站已经被修建好了，具体地，对于已经存在的地铁 $0$$0$ 号线，其上有 $n$$n$ 个已经修建的换乘站分别连结到了 $a_i$$a_i$ 号线上，同时每条线路与地铁 $0$$0$ 号线最多有两个换乘站。

现在 tsawke 想请聪明的你帮忙规划一下如何设置剩下所有线路的路径才能使得按照要求而建造的换乘站最少。

tsawke 可以根据你给出的结果推演出方案，所以你只需输出最小值即可。

存在多组数据。

输入格式

第一行一个正整数 $T$$T$，表示测试数据组数。

对于每组测试数据：

第一行一个整数 $n$$n$ 表示 $0$$0$ 号线上换乘站个数。

接下来一行 $n$$n$ 个整数表示 $a_1,a_2,\cdots ,a_n$$a_1, a_2, \cdots, a_n$。

输出格式

对于每组数据，输出一行一个整数表示最小值。

数据范围

对于 $100\mathrm{\%}$$100\%$ 的数据，保证 $1\le T\le 100,1\le a_i\le n,1\le n\le 44$$1 \le T \le 100, 1 \le a_i \le n, 1 \le n \le 44$。

具体地，对于每个测试点的范围如下表所示：

Examples

Input_1

xxxxxxxxxx
9
1
4
2
4
3
1 2 1 2
4
8
5
1 2 3 4 1 2 3 4
6
5
7
5 4 3 3 5
8
8
9
1 2 3 4 1 3 2 4

Output_1

xxxxxxxxxx
4
1
0
2
0
3
0
4
1

Examples_2

见下发文件中 /corruption/*。

样例解释

对于样例 $1$$1$ 的前两组数据，一种可能的最有答案如图所示：

转置！转置！不择手段地转置！（transposition）

题目背景

威慑纪元 $62$$62$ 年，$11$$11$ 月 $28$$28$ 日，$16:00-16:17$$16:00-16:17$，地下 $45$$45$ 公里，莫霍不连续面下，威慑控制中心（引力波宇宙广播系统零号控制站）。

作为执剑人的你，已经再次与三体人对峙了六十多年，你本以为这样的生活将一直持续到生命的终结，你本以为超过 $90\mathrm{\%}$$90\%$ 威慑度的你一定不会使三体人发动攻击。但是面前显眼的警告标志与提示声无不说明你所等待六十余年的事最终还是发生了。

通过这六十年的发展，你可以得到精确到毫秒级的攻击确切发生时间，而你的使命，便是在攻击发生前进行黑暗森林打击，同时毁掉两个文明的未来。

但为了防止误操作触发黑暗森林威慑，威慑系统的启动需要你完成一个显然的计算，即矩阵的转置，你只有在规定的时空限制下完成这个计算，才能成功除法引力波威慑系统，为人类争取最后数十年的生活。

题目描述

具体地，你将被给定 $a,b$$a, b$ 两个整数，这表示了一个 $2^a\times 2^b$$2^a \times 2^b$ 的矩阵，你需要对其进行转置，在威慑系统中，该矩阵将会被存储为一个序列，具体地，按照第一行的元素、第二行的元素、第三行的元素 $\cdots$$\cdots$ 依次拼接存储，而你只能进行交换操作，即将两个元素在序列中进行交换，你需要计算出在最坏情况下，最少需要进行多少次交换才能使得原矩阵变为转置矩阵，输出最小值。

特别地，你将被给定 $T$$T$ 组 $a,b$$a, b$，你需要在时间限制内分别计算它们对应的答案并分别输出。

特别地，对于矩阵的转置，可以认为其是将整个矩阵按其补齐的正方形的主对角线进行对称。或者说将整个矩阵的行列互换，即原矩阵的第一列作为转置矩阵的第一行，原矩阵的第二列作为转置矩阵的第二行，以此类推。则不难发现对于 $n\times m$$n \times m$ 的矩阵将会转化为 $m\times n$$m \times n$ 的转置矩阵。

输入格式

第一行一个整数 $T$$T$。

接下来 $T$$T$ 行每行两个非负整数分别表示 $a,b$$a, b$。

输出格式

共 $T$$T$ 行，分别表示对应询问的答案。

注意答案需对 $1000003$$1000003$ 取模（已知 $1000003$$1000003$ 是一个质数）。

数据范围

对于 $10\mathrm{\%}$$10\%$ 的数据，满足 $T=1,0\le a,b\le 3$$T = 1, 0 \le a, b \le 3$。

对于 $30\mathrm{\%}$$30\%$ 的数据，满足 $T=1,0\le a,b\le 6$$T = 1, 0 \le a, b \le 6$。

对于 $70\mathrm{\%}$$70\%$ 的数据，满足 $1\le T\le {10}^2,0\le a+b\le 5\times {10}^5$$1 \le T \le 10^2, 0 \le a + b \le 5 \times 10^5$。

对于 $100\mathrm{\%}$$100\%$ 的数据，满足 $1\le T\le 4\times {10}^5,0\le a+b\le {10}^6$$1 \le T \le 4 \times 10^5, 0 \le a + b \le 10^6$

Examples

Input_1

xxxxxxxxxx
3
1
2
2
1 1
3
2 2

Output_1

xxxxxxxxxx
2
1
1
2
6

数据范围等同 $10\mathrm{\%}$$10\%$ 的数据。

Examples_2

见下发文件中 /transposition/transposition2.in，/transposition/transposition2.ans。

数据范围等同 $30\mathrm{\%}$$30\%$ 的数据。

Examples_3

见下发文件中 /transposition/transposition3.in，/transposition/transposition3.ans。

数据范围等同 $70\mathrm{\%}$$70\%$ 的数据。

Examples_4

见下发文件中 /transposition/transposition4.in，/transposition/transposition4.ans。

数据范围等同 $100\mathrm{\%}$$100\%$ 的数据。

Tips

对于本题请使用较快的读入，这里提供一份可能需要的快读：

xxxxxxxxxx
15
1
template < typename T = int >
2
inline T read(void){
3
    T ret(0);
4
    int flag(1);
5
    char c = getchar();
6
    while(c != '-' && !isdigit(c))c = getchar();
7
    if(c == '-')flag = -1, c = getchar();
8
    while(isdigit(c)){
9
        ret *= 10;
10
        ret += int(c - '0');
11
        c = getchar();
12
    }
13
    ret *= flag;
14
    return ret;
15
}

可以通过 read() 读入并返回一个 int 类型数，或 read < long long >() 返回 long long 类型。

学习？不可能！（slack_off）

题目背景

tsawke 不喜欢在家玩游戏，相比而言 tsawke 更喜欢在 jdfz 的机房中在 6Bit 旁边玩游戏，他认为这样才足够刺激，而他又不想被 6Bit 发现，tsawke 不知道该如何是好，请你帮帮他。

题目描述

tsawke 存在一个隐蔽度，初始为 $0$$0$。具体地，对于 $n$$n$ 单位时间（时刻从 $0$$0$ 到 $n$$n$）中的每单位时间，tsawke 可以有如下三种选择：

1. 刷题，会使得隐蔽度 $+1$$+1$。

2. 划水，会使得隐蔽度 $-1$$-1$。

3. 发呆，隐蔽度无变化。

在整个过程中的任意时刻，若 tsawke 的隐蔽度低于 $0$$0$，那么他将会被 6Bit 发现，而这是 tsawke 不希望发生的。

而 tsawke 又觉得过于这过于无聊，他希望在这 $n$$n$ 单位时间共 $n+1$$n + 1$ 个时刻中恰好有 $k$$k$ 次隐蔽度为 $0$$0$，同时要求在最后时刻隐蔽度必须为 $0$$0$。

tsawke 想让你告诉他共有多少种合法方案，答案对 $p$$p$ 取模。

输入格式

第一行两个整数三个整数，分别表示 $n,k,p$$n, k, p$。

输出格式

一行一个整数表示方案数（对 $p$$p$ 取模）。

数据范围

对于 $5\mathrm{\%}$$5\%$ 的数据，保证 $n<k$$n \lt k$。

对于 $30\mathrm{\%}$$30\%$ 的数据，保证 $1\le n,k\le 3\times {10}^2$$1 \le n, k \le 3 \times 10^2$。

对于 $60\mathrm{\%}$$60\%$ 的数据，保证 $1\le n,k\le {10}^5$$1 \le n, k \le 10^5$。

对于 $80\mathrm{\%}$$80\%$ 的数据，保证 $1\le n,k\le 2\times {10}^6,p=998244353$$1 \le n, k \le 2 \times 10^6, p = 998244353$。

对于 $100\mathrm{\%}$$100\%$ 的数据，保证 $1\le n,k\le {10}^7,n,k\le p\le 2^{31}-1$$1 \le n, k \le 10^7, n, k \le p \le 2^{31} - 1$，保证 $p$$p$ 为质数。

Examples

Input_1

xxxxxxxxxx
1
1
5 3 998244353

Output_1

xxxxxxxxxx
1
1
6

Input_2

xxxxxxxxxx
1
1
114 99 998244353

Output_2

xxxxxxxxxx
1
1
540295960

Input_3

xxxxxxxxxx
1
1
114514 111111 998244353

Output_3

xxxxxxxxxx
1
1
166683273

Input_4

xxxxxxxxxx
1
1
8888888 6666666 2000000659

Output_4

xxxxxxxxxx
1
1
1321092738