这是一道交互题，仅支持 C++11 及以上标准的 C++ 语言。

English Statement

题目背景

__int128 皇帝陛下，向天下昭告，他将编纂一套世间最快的 OI 模板库，命名为《我的 OI 人生》，并以模意义下矩阵的 XOR 卷积作为开篇之作。

你，作为负责此项重任的朝臣，本已夜以继日地投入其中。然而，朝中奸佞为图陷害，竟以不识“洋文”为借口，将皇帝诏令中“XOR 卷积”的“XOR”删除！因此，你只得实现了一个普通的卷积算法。当你辛勤完成，正欲呈报之时，才赫然发现这桩阴谋。

如今，距离呈交期限仅剩三十个时辰。更令人绝望的是，皇帝陛下至今未曾告知矩阵运算所需的模数。在这内忧外患之际，你，能否在如此短时间内，完成这项看似不可能的任务？

题目描述

交互库提供两个长度为 $2^N$ 的矩阵序列 $A, B$，下标范围 $[0, 2^N - 1]$。序列中每个元素均为 $m \times m$ 的矩阵，运算在模 $M$ 意义下进行（$m, M$ 对你不可见）。

你需要利用交互库提供的接口，计算序列 $C$，满足： $$ C_k = \sum_{i \oplus j = k} A_i B_j $$ 其中 $\oplus$ 表示按位异或。

交互接口

交互库实现了一个类 class mat，并维护当前操作的总花费 $\mu$。你需要通过以下接口进行运算：

1. 构造函数
   • mat(uint32_t x = 0)：生成一个主对角线为 $x$、其余位置为 $0$ 的标量矩阵。
2. 基础运算
   • 加减：operator+, +=, operator-, -=
     • 代价：$\mu_{\rm add} = \mu_{\rm sub} = 1$。
   • 乘法：operator*, *=
     • 代价：$\mu_{\rm mul}$（正整数，随 Subtask 变化，见数据范围）。
3. 卷积运算
   • vector<mat> convolution(vector<mat> a, vector<mat> b)
     • 功能：计算两个序列 $a, b$ 的加法卷积 $c$，即 $c_k = \sum_{i + j = k} a_i b_j$。
     • 代价：$\mu_{\rm conv} = \max\{200, |a| \cdot |b|\}$。
     • 注意：代价仅取决于序列长度，与 $\mu_{\rm mul}$ 无关。你应当保证 $0 < |a|, |b| < \sqrt{10^9}$。

选手不应该试图获取类 mat 的实例的矩阵元。任何与之相关的行为都将被判定为作弊。

你需要确保总花费 $\mu \le 10^9$。

实现细节

选手应确保提交的程序包含头文件 xor.h，可在程序开头加入以下代码实现：

#include "xor.h"

你不需要实现 main 函数，只需实现以下函数：

vector<mat> xor_convolution(vector<mat> a, vector<mat> b, int subtask_id);

• subtask_id：当前测试点的子任务编号。
• 返回值：包含 $2^N$ 个 mat 的 vector，即计算结果 $C$。

样例说明

当 $N = 2, m = 1, M = 10$ 时： 若 $A = [1, 1, 4, 5]$，$B = [0, 7, 2, 1]$，则返回的四个元素应为 $[0, 1, 8, 1]$。

下发文件提供了 xor_ex1 至 xor_ex5 共 5 组样例，第 $i$ 组符合第 $i$ 个 Subtask 的限制条件。你可以在 UOJ 的“自定义测试”功能中验证你的程序。

样例格式说明

• 输入：包含四个自然数，依次为 $N, m, \text{sid}$ 和随机种子。
• 输出：包含 8 个自然数，代表结果序列 $C$ 的 Hash 值。

交互库错误代码

除正常的 Hash 输出外，评测机还可能返回以下错误信息：

• RE：程序运行时发生异常（Runtime Error）。
• Length：返回的序列 $C$ 长度不符合要求（应为 $2^N$）。
• Cost：操作总花费 $\mu$ 超出 $10^9$ 的限制。

数据范围

对于 $100\%$ 的数据，$1 \le N \le 19$，$1 \le \mu_{\rm mul} \le 100$，$m \in \{1, 2\}$，$1 < M < 2^{31}$。 保证每个测试点你的程序仅被运行一次。

时间与空间限制：

• 时间限制：$20\ \text{s}$（若操作代价 $\mu \le 10^9$，交互库运行时间保证不超过 $16\ \text{s}$）。
• 空间限制：$2\ \text{GiB}$。