该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

火焰车把 $ONE$ $PIECE$ 藏在了一道门后面，并给了你 $N$ 个编号为 $1, 2, \dots, N$ 的钥匙。

其中一些是真钥匙，另外的都是假钥匙。

在这扇门的上面你可以插入任意数量的钥匙，凡是只有插入至少 $K$ 把真钥匙后门才会打开。

你已经对这些钥匙进行了 $M$ 次测试。第 $i$ 次测试过程如下：

• 将 $C_i$ 把 $A_{i,1}, A_{i,2}, \dots, A_{i,C_i}$ 把钥匙插到门上。
• 测试结果用一个英文字母 $R_i$ 表示。
  • $R_i =$ o "表示在第 $i$ 次测试中，X 门打开了。
  • $R_i =$ x "表示在第 $i$ 次测试中，X 门没有打开。

有 $2^N$ 种可能的钥匙组合，其中哪些是真钥匙，哪些是假钥匙。在这些组合中，找出与任何测试结果都不矛盾的组合数。
给定的测试结果有可能是错误的，没有任何组合满足条件。在这种情况下，报告 $0$ 。

输入格式

第一行三个整数 $N,M,K$ 表示钥匙的数量、测试次数、需要几把真钥匙才能打开门

之后 $M$ 次测试，每一次测试先输入一个 $C$ 表示本次测试中使用了几把钥匙，然后输入 $C$ 把钥匙的编号，最后一个字符 $R$ 表示门有没有被打开。

输出格式

将答案输出为整数。

3 2 2
3 1 2 3 o
2 2 3 x

2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

0

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

8

数据范围

• $N$ 、 $M$ 、 $K$ 、 $C_i$ 和 $A_{i,j}$ 为整数。
• $1 \le K \le N \le 15$
• $1 \le M \le 100$
• $1 \le C_i \le N$
• $1 \le A_{i,j} \le N$
• $A_{i,j} \neq A_{i,k}$ 如果 $j \neq k$ .
• $R_i$ 是 o 或 x。