Description

Given a positive integer $k$, the character set size for this problem is $k$. We use positive integers $i$ to denote the $i$-th character in the set.

Given a positive integer $m$, a string $\mathcal{S}$ is defined as "harmonious" if and only if either:

• The length of $\mathcal{S}$ is less than $m + 2$ ,or
• After deleting any $m$ characters from $\mathcal{S}$, there exists no contiguous palindromic substring of length greater than $1$ in the resulting string.

You need to process $q$ queries. For each query, given a "harmonious" string $T$ of length $m + 2$ and a non-repeating character set $U$, determine the number of strings of length $n$ that satisfy the following conditions:

1. $T$ is a prefix of the string.
2. The string is "harmonious".
3. The last character of the string belongs to $U$.

Output the answer modulo $998244353$. For all queries in a test case, $k$ and $m$ remain the same.

Note: It is guaranteed that $k-m \ge 3$.

Input Format

The first line contains an integer $c$ representing the test case ID. In sample inputs, $c = 0$.

The second line contains four integers $q, k, m$, representing the number of queries, the character set size, and the constant used to define "harmonious" strings.

Each of the next $q$ lines describes a query, containing:

• An integer $n$,
• A sequence $T$ of $m + 2$ positive integers (the "harmonious" prefix),
• An integer $|U|$ (the size of set $U$), followed by $|U|$ distinct integers denoting the elements of $U$.

Output Format

For each query, output one integer per line representing the answer modulo $998244353$.

0
1 5 1
5 1 2 3 1 1

2

0
1 5 1
7 1 2 3 2 1 2

6

0
1 40 4
50 2 3 5 7 11 31 2 5 10

732767443

0
1 12 1
12 3 5 7 1 7

32390928

Hint

Sample 1 Explanation

The prefix is abc (encoded as 1 2 3), $U = \{a\}$, and the character set is $\{a,b,c,d,e\}$. The valid strings of length 5 are:

abcda  
abcea  

Hence the answer is 2.

Sample 2 Explanation

The prefix is abc, $U = \{a,b\}$. Among valid strings of length 7, exactly 6 meet the conditions.

abceadb
abcdeab
abcedba
abcdeba
abcedab
abcdaeb

Hence the answer is 6.

Constraints

For all test cases: $1 \leq n \leq 10^7$，$1 \leq q,m \leq 2 \times 10^3$，$m + 3 \leq k\le 10^9$，$U \subseteq [1,k]$，$T_i \in [1,k]$。