题目描述

皮娅正在研究一个大小为 $n\times n$ 的生命棋盘。

棋盘上每个格子的状态只能是 $0$ 或 $1$。设第 $d$ 天棋盘中第 $i$ 行、第 $j$ 列格子的状态为

$$a^{(d)}_{i,j}\in\{0,1\}.$$

对于每个满足 $1\le i,j<n$ 的位置，给定一个固定值 $c_{i,j}\in\{0,1\}$。无论在哪一天，棋盘都必须满足：

$$a^{(d)}_{i,j}\oplus a^{(d)}_{i+1,j}\oplus a^{(d)}_{i,j+1}\oplus a^{(d)}_{i+1,j+1}=c_{i,j},$$

其中 $\oplus$ 表示按位异或。

也就是说，对每个相邻的 $2\times2$ 子棋盘，其中四个格子状态的异或值必须等于给定的 $c_{i,j}$。

接下来给出 $m$ 条限制。每条限制由五个整数

$$s,e,x,y,v$$

组成，表示在第 $s,s+1,\ldots,e$ 天中，格子 $(x,y)$ 的状态必须为 $v$，即

$$a^{(d)}_{x,y}=v\qquad(s\le d\le e).$$

不同天的棋盘可以分别选择；对于每一天，只需要判断是否存在一个满足以下全部条件的 $n\times n$ 二进制棋盘：

1. 所有相邻 $2\times2$ 子棋盘均满足给定的异或条件；
2. 所有在当天有效的限制均得到满足。

请对第 $1,2,\ldots,t$ 天分别判断这样的棋盘是否存在。

输入格式

第一行包含三个整数 $n,m,t$，分别表示棋盘的边长、限制数量以及天数。

接下来 $n-1$ 行，每行包含一个长度为 $n-1$ 的二进制字符串。

第 $i$ 个字符串的第 $j$ 个字符表示 $c_{i,j}$。

接下来 $m$ 行，每行包含五个整数

$$s,e,x,y,v,$$

表示从第 $s$ 天到第 $e$ 天（包含两端），格子 $(x,y)$ 的状态必须为 $v$。

输出格式

输出一个长度为 $t$ 的二进制字符串。

对于每个 $1\le d\le t$：

• 如果第 $d$ 天存在满足全部条件的棋盘，则输出字符串的第 $d$ 个字符为 1；
• 否则，第 $d$ 个字符为 0。

样例

样例输入

2 1 1
1
1 1 2 2 0

样例输出

1

样例说明

棋盘大小为 $2\times2$，唯一一个相邻 $2\times2$ 子棋盘的四个格子异或值必须为 $1$。

第 $1$ 天还要求格子 $(1,2)$ 的状态为 $0$。例如，可以选择棋盘

$$\begin{matrix} 0 & 0\\ 0 & 1 \end{matrix},$$

四个格子的异或值为

$$0\oplus0\oplus0\oplus1=1,$$

并且格子 $(1,2)$ 的状态确实为 $0$，因此第 $1$ 天存在合法棋盘，输出 1。

数据范围

$$2\le n\le 3000,$$ $$1\le m,t\le 100000,$$ $$1\le s\le e\le t,$$ $$1\le x,y\le n,$$ $$v\in\{0,1\}.$$

所有 $c_{i,j}$ 均为 0 或 1。