Problem B
Widget Tree

Alice got bored when staying at home for several months due to the pandemic and decided to learn about front-end development. She learnt that project components are often modeled as a widget, and decided to write a program to calculate the cost of building and updating them.

In a particular project that she is interested in, there are $N$ types of widgets numbered from $0$ to $N-1$. Each widget may depend on at most $10$ other distinct types of widget. All dependencies of a widget must be built before the widget itself could be built.

Firstly, Alice is interested in calculating the cost of building widget $0$, which is equivalent to the size of its dependency tree.

In the example above, $N = 3$, widget type $0$ depends on two widgets of type $1$, and widget type $1$ depends on two widgets of type $2$. The size of the dependency tree is $7$, which is also the required cost of building widget $0$.

Secondly, Alice is interested in calculating the cost of maintaining widget type $0$ when updates occur. There are $Q$ update queries in total. In each query, there are $X_ i$ ($1 \leq i \leq Q$) types of widgets to be updated. Note that there might be multiple widgets associated with a particular type and Alice only cares for widgets that belong to the dependency tree of widget type $0$.

For each query, you need to output the number of widgets that need to be rebuilt. A rebuild must be performed for a widget if it satisfies at least one of the following conditions:

1. The widget type is updated in the query.

2. At least one of its descendants or ancestors in the dependency tree has a widget type that needs to be updated in the query.

In the example above, the cost of initial build for this dependency tree is $7$. Next, suppose that there is a query where widgets with type $2$ and $3$ need to be updated. Based on the first condition, we know that there are two widgets that need to be rebuilt, which are those of type $2$ and $3$. Afterward, based on the second condition, we discover four more widgets that need to be rebuilt:

• Two widgets of type $4$, which are the descendants of widget with type $2$.

• One widget of type $1$, which is the ancestor of widget with type $3$.

• One widget of type $0$, which is the ancestor of widget with type $2$ and $3$.

Hence, in total, there are $6$ widgets that should be rebuilt. As this value may be large when we have a bigger dependency tree, you only need to output the value in modulo of $M$.

If it is impossible to build widget $0$, you only need to output a single line of string “Invalid”.

Input

The first line of the input consists of two integers $N$ ($1 \leq N \leq 1\, 000$) and $M$ ($1 \leq M \leq 10^{9}$). Each of the next $N$ lines consists of a single integer $C_ i$ ($0 \leq C_ i \leq 200$), the number of dependencies for widget of type $i$. It is followed by $C_ i$ integers, where $D_{i,j}$ ($0 \leq D_{i,j} \leq N-1$) is the $j$-th dependency for widget of type $i$. There are at most $10$ distinct types of widget among the dependencies of a single widget.

The next line of the input will contain two integers $Q$ ($0 \leq Q \leq 1\, 000$) and $T$ ($T = 0$ or $1$, explained in the output section). Each of the next $Q$ lines consists of a single integer $X_ i$ ($0 \leq X_ i \leq 200$), the number of widget types to be updated for query $i$. It is followed by $X_ i$ integers, where $Y_{i,j}$ ($0 \leq Y_{i,j} \leq N-1$) is the $j$-th type that needs to be updated for the $i$-th query.

Output

For $T = 0$:

If it is not possible to build widget $0$, output a single line with string “Invalid”. Otherwise:

The first line of the output must consist of a single integer, the cost of the initial build in modulo $M$. The next $Q$ lines of the output must also consist of a single integer, the answer for each query in modulo $M$.

For $T = 1$, $Q$ is always $0$:

If it is not possible to build widget $0$, output a single line with string “Invalid”. Otherwise, output a single line with string “Valid”.

Subtasks

1. ($3$ Points): Sample.

2. ($10$ Points): $T = 1$ and $Q = 0$.

3. ($25$ Points): $T = 0$ and $Q = 0$.

4. ($22$ Points): $T = 0$ and $N \leq 10$ and $C_ i \leq 3$ ($0 \leq i \leq N-1$).

5. ($25$ Points): $T = 0$ and $N \leq 500$ and $C_ i \leq 20$ ($0 \leq i \leq N-1$).

6. ($15$ Points): $T = 0$.

Visualization

To help you visualize the input in the given sample test cases, you can refer to the following images which represent the dependency tree of widget $0$ for sample $1$, $2$, and $3$, respectively.

Warning

The I/O files are large. Please use fast I/O methods.

3 1000000
1 1
1 2
1 0
0 0

Invalid

7 1000000
2 1 2
2 4 2
2 3 4
0
0
3 1 4 3
3 2 3 4
3 0
1 4
2 2 3
2 3 4

9
7
8
9

8 1000000
2 5 3
1 6
2 6 1
2 4 6
2 5 7
0
3 5 5 5
1 6
10 0
2 7 3
3 4 3 1
1 2
2 1 4
1 5
2 2 5
1 6
1 5
1 5
3 1 7 5

14
13
13
0
9
14
14
12
14
14
14