星光微烁的巨塔，令旅人心驰神往。传说星塔会平等地眷顾所有登上塔顶的人，实现他们心中的愿望。

失忆的旅人小 B 也想登上星塔顶端，希望找回自己的记忆。经过调查，星塔的构造具有以下特征：

• 星塔中一共有 $n$ 个房间，编号为 $1, 2, \dots, n$。编号越小的房间所处的高度越高。
• 每一个编号大于 $1$ 的房间都恰有一个能通往房间高度更高的单向升降梯。也就是说，每一个编号为 $i$ $(i \ge 2)$ 的房间有且仅有一个单向通往编号为 $f_i$ $(1 \le f_i < i)$ 的升降梯。
• 编号为 $1$ 的房间会通往顶层。注意顶层不是 $1$ 号房间，且其它房间不能通往顶层。
• 星塔有且仅有一个入口，这个入口会直接通向 $n$ 个房间中的某一个。

容易发现，如果星塔构造不发生改变，那么登顶路线是固定且唯一的。为了防止旅人攻略星塔太过轻松，当一个人或者一支队伍探索完一次星塔后，星塔会重置自身的构造，改变每个房间升降梯通往的房间与入口通向的房间。具体来说，星塔会对 $i=2,\dots,n$，将 $i$ 号房间的升降梯通向的房间编号 $f_i$ 修改为任意一个在 $1 \sim i - 1$ 之间的正整数，并且把入口通向的房间修改为编号为 $1 \sim n$ 之间的任意房间。

因此，爬塔开始前，旅人们基本无法知道自己需要经过多少房间才能到达顶层。不过旅人们集结了自己的智慧，制造出了一台可以探测星塔构造的设备。但这台设备不够稳定，具体来说，这台设备可以探测到 $2, \dots, c$ 号房间升降梯通向的楼层编号 $f_2, \dots, f_c$，其中 $1 \le c \le n$。如果运气不好，可能一个房间都探测不到（也就是 $c = 1$）。注意，这台设备不能探测入口通向的房间编号。

为了达成目的，小 B 需要爬 $q$ 次塔。为了爱护这台设备以及保证自己的安全，小 B 约束自己在每次登塔前会用且只用一次设备进行探测。并且小 B 认为通过恰好 $k$ 个房间（不包括塔顶）之后到达顶层会带给自己最大的幸福感（房间数过多会觉得疲劳，过少会觉得无聊），因此每次探测结果出来之后，小 B 想知道，对于剩下的 $n - c$ 的房间的升降梯，以及入口通往的房间，有多少种方案能使得小 B 通过恰好 $k$ 个房间之后到达顶层。

小 B 虽然不会，但相信屏幕前的你一定知道怎么做，请你帮帮小 B。由于这个数很大，请你将答案对 $998244353$ 取模。

Input

第一行包含三个整数 $n, k, q$ $(2 \le n \le 2 \times 10^5, 1 \le k \le n, 1 \le q \le 2 \times 10^5)$，分别表示星塔的房间数，小 B 认为能带给自己最大的幸福感需要恰好经过的房间数，以及爬塔次数。对于每次爬塔：

第一行一个整数 $c$ $(1 \le c \le n, 1 \le \sum c \le 2 \times 10^6)$。其中 $\sum c$ 表示所有询问的 $c$ 的和。

如果 $c \ge 2$，则第二行包含 $c-1$ 个整数 $f_2,\dots f_c$ $(1 \le f_i \le i - 1)$，表示设备探测出来的值。否则，没有第二行。

由于输入量较大，建议采取较快的输入方式。

Output

对于每组数据，输出一行一个整数，表示答案。

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

对于第一组样例，$c = 1$ 表示没有探测到任何升降梯通往的房间。其中 $2$ 种方案可以是：$f_{2 \sim 5} = [1, 2, 3, 3]$，入口开在 $4$ 号或者 $5$ 号房间。以入口开在 $5$ 号房间为例，则从入口进入 $5$ 号房间，经过 $5 \rightarrow 3 \rightarrow 2 \rightarrow 1$，再从 $1$ 号房间通往塔顶。总共经过了 $4$ 个房间。

对于第五组询问，所有升降梯通往的房间都被探测出来了，只有入口未知。由于以任意一个房间为起点，最多经过 $3$ 个房间到达塔顶，因此不存在满足要求的方案。