题目描述

$n$ 只小花猫从 $0$ 到 $n-1$ 编号，按顺序坐成一圈，$0$ 号与 $n-1$ 号相邻。

每只小猫都有一张写着数字 $\texttt{0}$ 或 $\texttt{1}$ 的卡片。每只小猫都可以看到除了相邻的两只小猫以外所有小猫的卡片数字，也可以看到自己的。

游戏共进行 $m$ 回合。第 $i$ 回合琳妮特会向所有小猫公布 $k_i$ 条信息，有以下三种形式的信息：

• 若 $op=0$，将给出某个小猫集合卡片的逻辑或值。
• 若 $op=1$，将给出某个小猫集合卡片的逻辑与值。
• 若 $op=2$，将给出某个小猫集合卡片的逻辑异或值。

公布完信息之后：

• 如果某只小猫手里的卡片写着 $\texttt 0$，且她可以通过推断确定相邻的两只小猫卡片数字逻辑或的值，她就会宣布胜利。
• 如果某只小猫手里的卡片写着 $\texttt 1$，且她可以通过推断确定相邻的两只小猫卡片数字逻辑异或的值，她就会宣布胜利。

小猫们都非常聪明，只要依据她已知的信息能够推断出结果，她一定会宣布胜利。回合结束时，能够推断结果的小猫会同时宣布胜利（这意味着小猫不能听别的小猫宣布之后再宣布）。然后本回合结束，进入下一回合。

除此之外小猫们没有任何交流。现在给出每只小猫的卡片数字和琳妮特需要公布的所有信息，绮良良想知道每只小猫第一次宣布胜利是在第几回合。

输入格式

第一行两个整数 $n$ 和 $m$，表示猫的数量和回合数。

第二行 $n$ 个整数，表示小猫卡片上的数字。

接下来有 $m$ 个部分，第 $i$ 部分描述了第 $i$ 回合琳妮特公布的信息。

第 $i$ 部分的第一行包括一个非负整数 $k_i$，表示第 $i$ 回合公布的信息条数。

接下来 $k_i$ 行，每行第一个正整数 $op$，表示该信息的类型；第二个正整数 $w$，表示该集合卡片数字的逻辑或/与/异或的值；第三个正整数 $p$，表示集合中小猫的数量；接下来 $p$ 个互不相同的整数表示集合里所有小猫的编号。

输出格式

一行 $n$ 个整数，表示编号 $0$ 到 $n-1$ 的小猫第一次宣布胜利时的回合数。如果她自始自终都没有宣布胜利，输出 -1。

输入输出样例

输入 #1

3 2
1 1 0
2
0 1 2 0 2
0 1 1 1
0

输出 #1

2 2 1

输入 #2

3 2
1 1 1
1
0 1 3 0 1 2
0

输出 #2

2 2 2

说明/提示

样例 #1

该组样例满足子任务 1 的限制。

样例 #2

该组样例满足子任务 2 的限制。

样例 #3

见下发的 ex_game3.in/.out。

该组样例满足子任务 1 的限制。

样例 #4

见下发的 ex_game4.in/.out。

该组样例满足子任务 2 的限制。

样例 #5

见下发的 ex_game5.in/.out。

该组样例满足子任务 3 的限制。

样例 #6

见下发的 ex_game6.in/.out。

该组样例满足子任务 4 的限制。

样例 #7

见下发的 ex_game7.in/.out。

该组样例满足子任务 5 的限制。

样例 #8

见下发的 ex_game8.in/.out。

该组样例满足子任务 6 的限制。

数据范围

对于所有测试数据，满足 $3 \le n \le 16$，$1 \le m \le 100$，$1\le \sum k ,\sum p\le 1000$。

子任务编号	分值	限制	满足特殊性质
$1$	$15$	$n \le 5,m\le 10,1\le \sum k\le 20$	无
$2$	$10$	$n\le 10,m\le 10,1\le \sum k\le 50$	$\text{A}$
$3$		$m \le 5$	无
$4$		$p=1$
$5$		$1\le \sum k ,\sum p\le 100$
$6$	$45$	无

特殊性质 $\text{A}$：真实卡牌集合全为 $1$ 或 $0$。