The giant tower with faintly shimmering starlight captivates travelers. Legend has it that the Star Tower will equally bless everyone who reaches its top and grant the wish in their hearts.

The amnesiac traveler Little B also wants to climb to the top of the Star Tower, hoping to regain his memories. After investigation, the structure of the Star Tower has the following features:

• The Star Tower has $n$ rooms in total, numbered $1, 2, \dots, n$. The smaller the room number, the higher the room is located.
• Every room with number greater than $1$ has exactly one one-way elevator leading to a room at a greater height. That is, every room numbered $i$ $(i \ge 2)$ has exactly one one-way elevator leading to room $f_i$ $(1 \le f_i < i)$.
• Room $1$ leads to the top. Note that the top is not room $1$, and no other room can lead to the top.
• The Star Tower has exactly one entrance, and this entrance leads directly to one of the $n$ rooms.

It is easy to see that if the Star Tower's structure does not change, the route to the top is fixed and unique. To prevent travelers from conquering the Star Tower too easily, after a person or a team finishes exploring the Star Tower once, the Star Tower resets its own structure, changing the room to which each room's elevator leads and the room to which the entrance leads. Specifically, for $i=2,\dots,n$, the Star Tower changes the room number $f_i$ to which room $i$'s elevator leads to any positive integer in the range $1 \sim i - 1$, and changes the room to which the entrance leads to any room numbered in the range $1 \sim n$.

Therefore, before climbing, travelers basically cannot know how many rooms they need to pass through to reach the top. However, the travelers pooled their wisdom and built a device that can detect the Star Tower's structure. But this device is not stable enough. Specifically, this device can detect the room numbers $f_2, \dots, f_c$ to which the elevators of rooms $2, \dots, c$ lead, where $1 \le c \le n$. If unlucky, it may not detect any room at all (that is, $c = 1$). Note that this device cannot detect the room number to which the entrance leads.

To achieve his goal, Little B needs to climb the tower $q$ times. To take care of this device and ensure his own safety, Little B restricts himself to using the device once and only once before each climb. Moreover, Little B believes that reaching the top after passing through exactly $k$ rooms (not including the top) brings him the greatest happiness (too many rooms would make him tired, and too few would make him bored). Therefore, after each detection result, Little B wants to know, for the elevators of the remaining $n - c$ rooms and the room to which the entrance leads, how many ways there are such that Little B reaches the top after passing through exactly $k$ rooms.

Little B does not know how, but he believes that you, in front of the screen, surely know what to do. Please help Little B. Since this number can be very large, please output the answer modulo $998244353$.

Input

The first line contains three integers $n, k, q$ $(2 \le n \le 2 \times 10^5, 1 \le k \le n, 1 \le q \le 2 \times 10^5)$, denoting respectively the number of rooms in the Star Tower, the number of rooms Little B believes he needs to pass through exactly to obtain the greatest happiness, and the number of climbs.

For each climb:

The first line contains an integer $c$ $(1 \le c \le n, 1 \le \sum c \le 2 \times 10^6)$. Here $\sum c$ denotes the sum of $c$ over all queries.

If $c \ge 2$, then the second line contains $c-1$ integers $f_2,\dots f_c$ $(1 \le f_i \le i - 1)$, the values detected by the device. Otherwise, there is no second line.

Since the amount of input is large, a faster input method is recommended.

Output

For each query, output a line containing one integer, the answer.

Examples

Input 1

5 4 5
1
2
1
3
1 1
4
1 2 3
5
1 2 1 2

Output 1

10
10
2
5
0

Note

For the first query in the sample, $c = 1$ means no elevator destination was detected. Two of the valid ways are: $f_{2 \sim 5} = [1, 2, 3, 3]$, with the entrance leading to room $4$ or room $5$. Take the entrance leading to room $5$ as an example: enter room $5$ from the entrance, go $5 \rightarrow 3 \rightarrow 2 \rightarrow 1$, and then from room $1$ to the top. In total, $4$ rooms are passed.

For the fifth query, all elevator destinations have been detected, and only the entrance is unknown. Since no matter which room is used as the starting point, at most $3$ rooms are passed before reaching the top, there is no way that satisfies the requirement.