← 返回题目列表

Codeforces · 234/D

D. 电影院

中文机器翻译题面 查看原题

Berland 总共有 m 个演员。每个演员都有一个个人标识符——一个从 1 到 m 的整数(不同的演员有不同的标识符)。 Vasya 喜欢和 Berland 演员一起看 Berland 电影,他有 k 个最喜欢的演员。他观看了下个月的电影预告片,并为每部电影写下了以下信息:电影名称、主演人数以及这些演员的标识符。此外,他还抄下了电影的片名和主演人数,但有些演员的身份他却没能记下来。瓦夏查看他的记录,想知道哪些电影可能是他最喜欢的,哪些电影可能不是。一旦 Vasya 了解了所有电影的确切演员阵容,他最喜欢的电影将按如下方式确定:如果 Vasya 列表中没有其他电影拥有更多最喜欢的演员,则该电影将成为最喜欢的电影。

帮助男孩确定每部电影的以下内容:

- 这是否一定是他最喜欢的电影;
- 这是否肯定不会是他最喜欢的电影;
- 可以是最喜欢的也可以不是。

输入

输入的第一行包含两个整数 m 和 k (1 ≤ m ≤ 100, 1 ≤ k ≤ m) — Berland 的演员数量和 Vasya 最喜欢的演员数量。

第二行包含 k 个不同的整数 ai (1 ≤ ai ≤ m) — Vasya 最喜欢的演员的标识符。

第三行包含一个整数 n (1 ≤ n ≤ 100) — Vasya 列表中的电影数量。

然后是 n 行块,每个块包含一个电影的描述。第 i 部电影的描述包含三行:

- 第一行包含字符串 si (si 由小写英文字母组成,长度可以为 1 到 10 个字符(含)) - 电影的标题,
- 第二行包含一个非负整数 di (1 ≤ di ≤ m) - 主演这部电影的演员人数,
- 第三行有 di 整数 bi, j (0 ≤ bi, j ≤ m) — 这部电影中主演的演员的标识符。如果bi, j = 0,则Vasya不记得第j个演员的标识符。保证电影的演员列表不包含相同的演员。

所有电影都有不同的名称。行上的数字由单个空格分隔。

输出

在输出中打印 n 行。在第i行打印:

- 0,如果第 i 部电影肯定是最喜欢的;
- 1,如果第 i 部电影不一定是最喜欢的;
- 2,如果第 i 部电影可以是最喜欢的,也可以不是最喜欢的。

示例

输入 #1

5 3
1 2 3
6
firstfilm
3
0 0 0
secondfilm
4
0 0 4 5
thirdfilm
1
2
fourthfilm
1
5
fifthfilm
1
4
sixthfilm
2
1 0

输出 #1

2
2
1
1
1
2

输入 #2

5 3
1 3 5
4
jumanji
3
0 0 0
theeagle
5
1 2 3 4 0
matrix
3
2 4 0
sourcecode
2
2 4

输出 #2

2
0
1
1

注意

第二个示例注意事项:

- 电影《勇敢者游戏》理论上可以有 1 到 3 个 Vasya 最喜欢的演员。
- 电影《theeagle》拥有全部三位最喜欢的演员,但演员 Vasya 不记得了,只能有标识符 5。
- 电影矩阵可以恰好有一位最喜欢的演员。
- 电影源代码没有任何最喜欢的演员。

因此,电影《theeagle》肯定会是最喜欢的,电影矩阵和源代码肯定不会是最喜欢的,而电影《勇敢者游戏》可以是最喜欢的(如果它拥有所有三个最喜欢的演员),也可以不是最喜欢的。