P14748 点灯游戏

NIT 正沉迷于做点灯游戏，点灯游戏是在一个 $n$ 行 $m$ 列的矩阵中，每个格子都有一个灯，NIT 要想办法将所有灯点亮，初始每个灯都是暗的。 NIT 可以选择任意个灯将它们依次翻转，翻转一个灯的时候这个灯和它的相邻的上下左右一共五个灯都会同时变化。即亮变暗，暗变亮。 点灯游戏有一个非常棒的做法：只要确定了第一行，那就可以确定第二行，一直到第 $n$ 行，若第 $n$ 行灯全亮了那就成功。 NIT 觉得这东西一定有规律，于是 NIT 想要通过"打表"找出规律。于是 NIT 开始了枚举，NIT 不断的枚举第一行的选法。为了加速 NIT 的解题过程，你决定帮助 NIT。 给出 $q$ 个询问，每个询问给出第一行 NIT 的选法，你给出最后一行灯的状态。 形式化的说，你需要使得第一行的操作为 NIT 选定的操作，其他地方的操作自选，使得第 $1$ 至 $n-1$ 行的灯全亮。 然后输出第 $n$ 行灯的状态，可以证明此时第 $n$ 行灯的状态是唯一的。

第一行两个正整数 $n, m\ (2\leq n\leq 3\times10^5, 1\leq m\leq 3000)$ 表示 NIT 正在解决的点灯游戏的行数和列数。 接下来一行一个整数 $q\ (1\leq q\leq 100)$，表示询问数量。 接下来 $q$ 行每行 $m$ 个字符，表示一次询问，第 $i$ 个字符为 $0$ 表示 NIT 不准备翻转第一行第 $i$ 个灯，为 $1$ 表示 NIT 准备翻转第一行第 $i$ 个灯。

输出 $q$ 行，每行 $m$ 个字符，第 $i$ 个字符表示经过操作后第 $n$ 行第 $i$ 列的灯的状态，$0$ 表示暗，$1$ 表示亮。

样例 $1$ 第 $1$ 问解释： NIT 翻转了第一行第一列的灯，于是灯的状态就变成了 |$1$|$1$|$0$| |:-:|:-:|:-:| |$1$|$0$|$0$| |$0$|$0$|$0$| 不难发现，为了使得第一行和第二行都亮，需要此时翻转第二行第三列的灯，于是灯的状态变成 |$1$|$1$|$1$| |:-:|:-:|:-:| |$1$|$1$|$1$| |$0$|$0$|$1$| 于是输出第三行灯的状态 $001$。