H. Color of Goods
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Snow wants to buy some goods to celebrate the Spring Festival.

He found that there were n kinds of goods in the store, and each kind of goods had several colors on it. (It means two goods have the same colors if they are of the same kind.) Each color will be represented as a number between 1 and m.

Snow wants to buy k goods so that the set of colors on those goods is exactly what he wants. Snow wants to know how many different plans he can buy. (Note that the good in the same kind is also different. For example, the first kind has 3 goods, and you want to choose 2 from the first kind, you have 3 plans, not 1.)

More formally, Snow will make q queries, each providing you with a set of colors. For each query, you must determine the number of plans that involve purchasing exactly k goods, with the color set on those goods equal to the provided set.

Because the answer may be so big that you need to modulo it by 998244353.

Input

The first line contains three integers m, n, and k. 1 ≤ k ≤ 100000, 1 ≤ n ≤ 200000, 1 ≤ m ≤ 16

Then n lines follow. The i-th of them contains two integers wi and ci, wi meaning the number of colors in this kind of goods, ci represents the number of goods in kind i,followed by wi distinct integers coli, 1, coli, 2, ..., coli, wi, where coli, j denotes the j-th color on i-th goods. 1 ≤ wi, coli, j ≤ m, 1 ≤ ci ≤ 109

Then one line contains an integer q, denotes the number of queries.(1 ≤ q ≤ 100000).

Then q lines follow. The i-th of them contains an integer |S| meaning the size of color, and followed by S distinct integers S1, S2, ..., S|S|, which denotes colors in this set.(1 ≤ |S|, Si ≤ m)

Output

For all queries, print an integer which means the number of plans modulo 998244353.

Examples
Input
4 8 2
3 1 1 2 3
2 1 2 4
1 1 4
3 1 1 2 4
2 1 1 3
4 1 1 2 3 4
1 1 3
2 1 1 3
2
4 1 2 3 4
3 2 3 4
Output
15
1
Input
4 1 1
1 3 1
1
1 1
Output
3
Note

For the first example, every kind only has one good.

For the first query, you can choose plans as follows:(1, 2),(1, 3),(1, 4),(1, 6),(2, 5),(2, 6),(2, 8),(3, 6),(4, 5),(4, 6),(4, 7),(4, 8),(5, 6),(6, 7),(6, 8).(Each plan is expressed in the form (i, j), indicating the selection of kind i and kind j).

For the second query, your only plan is (2,7).

For the second example, you want to choose 1 good in the first kind, and the first kind has 3 goods, so you have C31 = 3 plans.