给定两个 $0, 1, \dots, M-1$ 的排列 $p_0, p_1, \dots, p_{M-1}$ 和 $q_0, q_1, \dots, q_{M-1}$，其中 $M = 2^N$．

对每个位置 $0 \le i < M$，定义 $t_i = \sum_{j=0}^{i-1} [p_j < p_i] \cdot [q_j < q_i]$，其中 $[P]$ 在命题 $P$ 成立时为 $1$，否则为 $0$．

你需要求出所有 $i \cdot t_i$ 按位异或后的结果．

输入格式

输入文件采用二进制格式，即文件由连续的字节组成，不包含空格、换行或其他分隔符．

文件的第一个字节存储整数 $N$．

接下来的 $4M$ 个字节依次存储 $p_0, p_1, ..., p_{M-1}$．每个整数占用四个字节，并采用小端序存储：一个整数的最低有效字节放在最前面．例如，整数 0x12345678 的四个字节依次为 0x78、0x56、0x34、0x12．这些整数构成 $0$ 至 $M-1$ 的一个排列．

最后的 $4M$ 个字节依次存储 $q_0, q_1, ..., q_{M-1}$．每个整数占用四个字节，并采用小端序存储：一个整数的最低有效字节放在最前面．例如，整数 0x12345678 的四个字节依次为 0x78、0x56、0x34、0x12．这些整数构成 $0$ 至 $M-1$ 的一个排列．

输出格式

输出一行一个十进制整数字面量，表示答案．

评测方式

你的 C/C++ 源代码将被编译成一种名为 WebAssembly (WASM) 的格式．WebAssembly 是一种字节码执行格式：程序在沙箱化的线性内存中运行，不依赖操作系统时钟或线程调度；每条指令的消耗以 tick 精确计量，内存使用以线性内存的字节数计量．因此，同一个程序对同一份数据的 tick 数与内存消耗完全可复现，评测结果不受机器负载或真实时钟波动的影响，成绩稳定且可横向对比．

为了兼容 UOJ 的 API，本题测评时，Hull 的 UOJ target 会把评测结果映射到 UOJ 的字段：顶层 time 取所有测试点 tick 的最大值，并经过单调的 $31$ 位伪浮点编码压入 UOJ 所使用的整数时间字段；顶层 memory 取所有测试点内存消耗（字节）的最大值；每个测试点按 $0$ 到 $100$ 分制上报，即把「评分方式」一节中的原始得分 $[0,1]$ 乘以 $100$．每个测试点详情中的 time 仍保留真实 tick 值，不受编码影响．

UOJ 的时间字段是 $32$ 位有符号整数，而本题的 tick 可以接近 $10^{10}$，超出其表示范围，无法直接存放．因此评测器把最大 tick 近似表示成一个 $31$ 位整数，使其既能放进 UOJ 字段，又保持大小关系不变：高 $6$ 位存放指数 $e = \lfloor \log_2(\mathrm{tick}) \rfloor$，低 $25$ 位存放 tick 的最高 $25$ 个有效位（尾数，当 $e \le 25$ 时向左对齐，否则向右截断）．由于指数段之间和同一指数段内部编码值都随 tick 增大而增大，该编码是单调的：tick 更大的测试一定得到更大的编码值，排序与比较关系被完整保留．编码后再整体加 $1$（用于区分 tick 为 $0$ 与 $1$ 的情形），并截断到 $2^{31}-1$．该编码损失了部分精度，仅用于 UOJ 的显示与排序．

自测方式

为方便选手做题，本题提供两种自测方式：

你可以使用 UOJ 的「自定义测试」功能来测试你的代码．自定义测试输入格式即为「输入格式」章节中介绍的格式．

你也可以在本地编译运行你的程序．下载本题的附件包，附件包由 Hull 的 cnoiParticipant target 生成，内置了与正式评测完全一致的编译器和评测环境（同一份 WASM 工具链与评测器）．解压后，把源文件放入目录 submission/d3/（例如 submission/d3/d3.cpp），然后在附件目录下运行：

./selfeval submission

即可获得自测报告．该自测只会运行题目附带的样例数据与随机数据，不会运行完整测试集，结果仅供参考．

数据范围

• $1 \le N \le 24$．
• $M = 2^N$．
• $0 \le p_i < M$．
• $p_0, p_1, \dots, p_{M-1}$ 构成一个排列．
• $0 \le q_i < M$．
• $q_0, q_1, \dots, q_{M-1}$ 构成一个排列．
• 输入中的整数使用四个字节的小端序表示．

评分方式

• 如果输出错误，该测试点得分为 $0$．
• 如果输出正确且程序运行了 $t$ 个 tick，该测试点得分为 $1 - t/(16 \cdot 10^{10})$，结果限制在区间 $[0, 1]$ 内．
• 得分至少为 $0.5$ 的测试点在评测结果中显示为 Accepted．

编译器信息

评测采用 Hull 的 UOJ 目标．

各组件版本如下：

• Hull：git commit f3a680a1f8696288a09cdd81a7df175d07f045b5．
• Clang（wasm32-wasi-wasip1-clang / wasm32-wasi-wasip1-clang++）：21.1.8．
• libc（wasi-libc）：32．
• libstdc++（GCC）：15.2.0．
• Wasmtime：47.0.2．

编译参数

源代码统一编译为 WASM 模块：C 使用 wasm32-wasi-wasip1-clang，C++ 使用 wasm32-wasi-wasip1-clang++．

默认 -std 由所选择的语言决定：选择 C++17 则默认编译为 C++ 17，选择 C++26 则默认编译为 C++ 26，C 语言同理；其余参数对所有语言使用相同的默认值．默认参数如下：

• optimize：优化级别，对应 -O，可选 0/1/2/3/g/s/z，默认 3．
• standard：语言标准，对应 -std，默认值随所选语言变化．
• stackSize：WASM 调用栈大小（字节），对应 -Wl,-z,stack-size，默认 67108864（64 MiB）．
• pageSize：WASM 线性内存页大小，对应 -Wl,--page-size，默认 65536．
• globalBase：全局数据起始地址，对应 -Wl,--global-base，默认 1024．
• standardIncludes：是否使用标准头文件搜索路径，关闭时追加 -nostdinc，默认开启．
• standardLibraries：是否链接标准库（-lm 及 C++ 运行库），关闭时追加 -nostdlib，默认开启．
• freestanding：是否以 freestanding 模式编译（对应 -ffreestanding），默认关闭．
• fastMath：是否启用快速数学优化（对应 -ffast-math），默认关闭．

此外会自动追加 -fno-exceptions --target=wasm32-wasi-wasip1 -mcpu=mvp -Wl,--strip-debug．

选手可以在源代码顶部添加 // hull_source_config { ... } 注释，自定义部分编译参数，例如：

// hull_source_config {"optimize":"3","standard":"c++26","stackSize":67108864}

该注释的优先级高于所选语言对应的默认值：注释中显式给出的选项按注释中的值编译，未出现的选项仍使用默认值；特别地，standard 可以覆盖所选语言决定的 -std．取值必须是合法值（如 standard 必须是受支持的 c/c++/gnu/gnu++ 标准、optimize 必须是 0/1/2/3/g/s/z 之一），否则编译失败．

选择其他不受支持的语言结果为编译错误．

限制与约定

• 时间限制：$16 \cdot 10^{10}$ ticks．
• 空间限制：$1$ GiB．