无名州立大学（NSU）正在为一种新型的程序设计竞赛做准备。在这场比赛中，每个大学只能由一支由两名学生组成的队伍代表。此外，还有一个官方的包含 $N$ 本书的清单，参赛者必须阅读这些书才能取得好成绩。距离比赛剩下的时间不多了，并不是每个学生都能及时读完所有的书。

每个学生都知道对于每一个书的集合，自己是否能够及时读完。在 NSU 有 $M$ 名学生愿意参加比赛。教练准备了一个包含 $K$ 支候选队伍的名单。为了为比赛选择一支队伍，她想知道每支队伍的阅读能力。

如果一支队伍中至少有一名成员读了某本书，就认为该队伍读了这本书。你的任务是，对于每支候选队伍以及每个书的集合，判断队伍成员是否可以规划他们的训练，使得该队伍能够及时读完该集合中的所有书。

输入格式

输入的第一行包含三个整数：$N$ — 书的数量，$M$ — 学生的数量，以及 $K$ — 候选队伍的数量（$1 \le N \le 21$，$2 \le M \le 6$，$1 \le K \le 6$）。本题中所有地方均使用从 0 开始的编号。

接下来的 $M$ 行中，第 $i$ 行定义了第 $i$ 个学生的阅读能力。学生的阅读能力用一个长度为 $2^N$ 且仅包含 0 和 1 的字符串 $S_i$ 描述。字符串的第 $k$ 个位置包含该学生是否能够及时阅读二进制掩码为 $k$ 的书集的信息。规则在下方详细说明。

我们将所有书从 $0$ 到 $N - 1$ 进行编号。设 $X$ 为一个书的集合。定义一个数组 $a_0, a_1, a_2, \dots, a_{N-1}$，使得如果第 $j$ 本书属于 $X$，则 $a_j = 1$，否则 $a_j = 0$。我们称数字

$$k = \sum_{j=0}^{N-1} a_j 2^j$$

为集合 $X$ 的二进制掩码。那么，第 $i$ 个学生能够及时阅读书集 $X$ 当且仅当字符串 $S_i$ 的第 $k$ 个字符等于 1。

接下来的 $K$ 行中，第 $t$ 行描述了第 $t$ 支候选队伍。队伍由两个整数 $a_t$ 和 $b_t$ 定义 — 队伍中学生的编号。（$0 \le a_t, b_t < M$，$a_t \ne b_t$，$t = 0 \dots K - 1$）。

关于每个学生的阅读能力，保证以下两点：

• 首先，如果一个学生能阅读某个书集，那么她也能阅读该集合的任何子集。
• 其次，学生总是能阅读空书集，即她的能力字符串的起始字符（第 0 个字符）总是等于 1。

输出格式

输出必须包含 $K$ 行，每行由 0 和 1 组成，且每行包含 $2^N$ 个字符。第 $t$ 行必须包含第 $t$ 支队伍的阅读能力，格式与输入中学生的阅读能力相同。即，第 $t$ 行的第 $k$ 个字符必须等于 1 当且仅当第 $t$ 支队伍能够及时阅读二进制掩码为 $k$ 的书集 $X$。

样例

输入格式 1

3 5 3
11111010
11000000
11001000
11101000
11101000
0 1
1 2
3 4

输出格式 1

11111111
11001100
11111110

说明

第 0 个学生可以阅读以下集合之一：$\emptyset$、$\{0\}$、$\{1\}$、$\{2\}$、$\{0, 1\}$、$\{1, 2\}$。第 1 个学生只能阅读第 0 本书（或什么都不读）。第 2 个学生可以阅读第 0 本书或编号为 2 的书（或什么都不读）。第 3 和第 4 个学生可以阅读任何单本书（或什么都不读）。

第 0 支队伍如果由第 0 个学生阅读书集 $\{1, 2\}$，且第 1 个学生阅读书 $0$，则共同能够阅读所有的书。很容易验证该队伍也可以阅读任何其他书集。

第 1 支队伍如果其成员阅读不同的书，则可以阅读书 $0$ 和 $2$。该队伍也可以阅读集合 $\{0, 2\}$ 的任何子集。

在第 2 支队伍中，任何成员都不能阅读超过一本的书。因此，该队伍共同可以阅读任何大小不超过两本书的集合。