AtCoder Regular Contest 178

A - Good Permutation 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

正整数 N と長さ M の正整数列 A=(A_{1},A_{2},\dots, A_{M}) が与えられます。

ここで、 A の全ての要素は 1 以上 N 以下の整数で、相異なります。

1\leq i\leq M を満たす全ての整数 i について以下の条件を満たす、 (1, 2, \dots, N) の順列 P = (P_{1}, P_{2}, \dots, P_{N}) を 良い順列 とします。

P のどの連続部分列も、(1, 2, \dots, A_{i}) の順列ではない。

良い順列 は存在するか判定し、存在するなら 良い順列 のうち、辞書式順序で最小のものを求めてください。

数列の辞書順とは？

数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。ここで、|S|, |T| はそれぞれ S, T の長さを表します。

|S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい。

制約

1\leq M\leq N\leq 2\times 10^{5}
1\leq A_{i}\leq N
A の要素は互いに相異なる
入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N M
A_{1} A_{2} \cdots A_{M}

出力

良い順列 が存在しない場合は -1 を出力してください。

存在するならば、良い順列 のうち、辞書式順序で最小のものを空白区切りで出力してください。

入力例 1

4 1
2

出力例 1

1 3 2 4

例えば (4,2,1,3) は、連続部分列として (2,1) を含むため、良い順列ではありません。

他にも (1,2,3,4),(3,4,2,1) などは良い順列ではありません。

良い順列 として、(4,1,3,2),(2,3,4,1) などがあり得ますが、その中で辞書式順序で最小のものは (1,3,2,4) なので、これを空白区切りで出力してください。

入力例 2

5 3
4 3 2

出力例 2

1 3 4 5 2

良い順列 の例として、(3,4,1,5,2),(2,4,5,3,1),(4,1,5,2,3) があります。

良い順列 ではないものの例として、(1,2,5,3,4),(2,3,4,1,5),(5,3,1,2,4) があります。

入力例 3

92 4
16 7 1 67

出力例 3

-1

良い順列 が存在しない場合は、-1 を出力してください。

入力例 4

43 2
43 2

出力例 4

-1

Score : 400 points

Problem Statement

You are given a positive integer N and a sequence of M positive integers A = (A_{1}, A_{2}, \dots, A_{M}).

Here, all elements of A are distinct integers between 1 and N, inclusive.

A permutation P = (P_{1}, P_{2}, \dots, P_{N}) of (1, 2, \dots, N) is called a good permutation when it satisfies the following condition for all integers i such that 1 \leq i \leq M:

No contiguous subsequence of P is a permutation of (1, 2, \dots, A_{i}).

Determine whether a good permutation exists, and if it does, find the lexicographically smallest good permutation.

What is lexicographical order?

A sequence S = (S_1, S_2, \ldots, S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1, T_2, \ldots, T_{|T|}) if one of the following conditions holds. Here, |S| and |T| denote the lengths of S and T, respectively.

|S| \lt |T| and (S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|}).
There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold:
- (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1}).
- S_i is smaller than T_i (as a number).

Constraints

1 \leq M \leq N \leq 2 \times 10^{5}
1 \leq A_{i} \leq N
All elements of A are distinct.
All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_{1} A_{2} \cdots A_{M}

Output

If a good permutation does not exist, print -1.

If it exists, print the lexicographically smallest good permutation, separated by spaces.

Sample Input 1

4 1
2

Sample Output 1

1 3 2 4

For example, (4, 2, 1, 3) is not a good permutation because it contains (2, 1) as a contiguous subsequence.

Other non-good permutations are (1, 2, 3, 4) and (3, 4, 2, 1).

Some good permutations are (4, 1, 3, 2) and (2, 3, 4, 1). Among these, the lexicographically smallest one is (1, 3, 2, 4), so print it separated by spaces.

Sample Input 2

5 3
4 3 2

Sample Output 2

1 3 4 5 2

Examples of good permutations include (3, 4, 1, 5, 2), (2, 4, 5, 3, 1), and (4, 1, 5, 2, 3).

Examples of non-good permutations include (1, 2, 5, 3, 4), (2, 3, 4, 1, 5), and (5, 3, 1, 2, 4).

Sample Input 3

92 4
16 7 1 67

Sample Output 3

-1

If a good permutation does not exist, print -1.

Sample Input 4

43 2
43 2

Sample Output 4

-1

B - 1 + 6 = 7

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

正の整数 A_{1}, A_{2}, A_{3} が与えられます。以下の条件を全て満たす正の整数の組 (X_{1}, X_{2}, X_{3}) の場合の数を 998244353 で割ったあまりを求めてください。

X_{1} は 10 進法で A_{1} 桁の正の整数
X_{2} は 10 進法で A_{2} 桁の正の整数
X_{3} は 10 進法で A_{3} 桁の正の整数
X_{1} + X_{2} = X_{3}

1 つの入力ファイルにつき T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

1\leq T\leq 10^{5}
1\leq A_{i}\leq 10^{9}
入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}

各ケースは以下の形で与えられます。

A_{1} A_{2} A_{3}

出力

T 行出力してください。i 行目には \text{case}_{i} に対する答えを出力してください。

入力例 1

4
1 1 1
1 6 7
167 167 167
111 666 777

出力例 1

1 つ目のケースについて、(X_{1}, X_{2}, X_{3}) = (1, 6, 7), (2, 1, 3) などが条件を満たします。

(X_{1}, X_{2}, X_{3}) = (6, 7, 13), (3, 4, 5) などは条件を満たしません。

条件を満たす (X_{1}, X_{2}, X_{3}) の組は 36 通りあるので 36 を出力してください。

3 つ目のケースについて、答えを 998244353 で割ったあまりを出力することに注意してください。

4 つ目のケースについて、条件を満たす (X_{1}, X_{2}, X_{3}) の組が存在しないこともあります。

Score : 600 points

Problem Statement

You are given positive integers A_{1}, A_{2}, A_{3}. Find the number, modulo 998244353, of tuples of positive integers (X_{1}, X_{2}, X_{3}) that satisfy all of the following conditions.

X_{1} is a positive integer with A_{1} digits in decimal notation.
X_{2} is a positive integer with A_{2} digits in decimal notation.
X_{3} is a positive integer with A_{3} digits in decimal notation.
X_{1} + X_{2} = X_{3}.

You are given T test cases per input file; solve each of them.

Constraints

1 \leq T \leq 10^{5}
1 \leq A_{i} \leq 10^{9}
All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}

Each case is given in the following format:

A_{1} A_{2} A_{3}

Output

Print T lines. The i-th line should contain the answer for \text{case}_{i}.

Sample Input 1

4
1 1 1
1 6 7
167 167 167
111 666 777

Sample Output 1

For the first case, tuples such as (X_{1}, X_{2}, X_{3}) = (1, 6, 7), (2, 1, 3) satisfy the conditions.

On the other hand, tuples such as (X_{1}, X_{2}, X_{3}) = (6, 7, 13), (3, 4, 5) do not.

There are 36 tuples (X_{1}, X_{2}, X_{3}) that satisfy the conditions, so print 36.

For the third case, remember to print the result modulo 998244353.

For the fourth case, there may be no tuples (X_{1}, X_{2}, X_{3}) that satisfy the conditions.

C - Sum of Abs 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

正整数 N,L と長さ N の正整数列 A = (A_{1}, A_{2}, \dots , A_{N}) が与えられます。

i = 1, 2, \dots , N について、以下の問いに答えてください。

\displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i} を満たす、長さ L の非負整数列 B = (B_{1}, B_{2}, \dots B_{L}) が存在するか判定し、存在するならそのような B に対する \max(B) の最小値を求めてください。

制約

1\leq N \leq 2 \times 10 ^ {5}
2\leq L \leq 2 \times 10 ^ {5}
1\leq A_{i} \leq 2 \times 10 ^ {5}
入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N L
A_{1} A_{2} \cdots A_{N}

出力

N 行出力してください。 k 行目には i=k としたときに、条件を満たす B が存在しないなら -1 を、存在するなら \max(B) の最小値を出力してください。

入力例 1

2 4
10 5

出力例 1

3
-1

A_{1} = 10 について、 B=(1,0,2,3) としたとき、\displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = 10 となり、このとき \max(B) = 3 となります。 \max(B) < 3 かつ、条件を満たす非負整数列 B は存在しないので、1 行目には 3 を出力してください。

A_{2} = 5 について、条件を満たす非負整数列 B は存在しないので、 2 行目には -1 を出力してください。

入力例 2

6 8
167 924 167167 167924 116677 154308

出力例 2

Score : 600 points

Problem Statement

You are given positive integers N and L, and a sequence of positive integers A = (A_{1}, A_{2}, \dots , A_{N}) of length N.

For each i = 1, 2, \dots , N, answer the following question:

Determine if there exists a sequence of L non-negative integers B = (B_{1}, B_{2}, \dots, B_{L}) such that \displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i}. If it exists, find the minimum value of \max(B) for such a sequence B.

Constraints

1 \leq N \leq 2 \times 10^{5}
2 \leq L \leq 2 \times 10^{5}
1 \leq A_{i} \leq 2 \times 10^{5}
All input values are integers.

Input

The input is given from Standard Input in the following format:

N L
A_{1} A_{2} \cdots A_{N}

Output

Print N lines. The k-th line should contain -1 if no sequence B satisfies the condition for i=k; otherwise, it should contain the minimum value of \max(B) for such a sequence B.

Sample Input 1

2 4
10 5

Sample Output 1

3
-1

For A_{1} = 10, if we take B = (1, 0, 2, 3), then \displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = 10, where \max(B) = 3. No non-negative integer sequence B satisfies the condition with \max(B) < 3, so print 3 in the first line.

For A_{2} = 5, there is no non-negative integer sequence B that satisfies the condition, so print -1 in the second line.

Sample Input 2

6 8
167 924 167167 167924 116677 154308

Sample Output 2

D - Delete Range Mex

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

正整数 N と長さ M の非負整数列 A=(A_{1},A_{2},\dots, A_{M}) が与えられます。

ここで、 A の全ての要素は 0 以上 N 未満の整数で、相異なります。

(0, 1, \dots , N - 1) の順列 P のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

数列 B = (B_{1}, B_{2}, \dots , B_{N}) を P で初期化した後、以下の操作を好きな回数繰り返すことで B = A にすることができる。
- 1\leq l\leq r\leq |B| を満たす l,r を選び、 \mathrm{mex}(\{B_{l},B_{l+1},\dots ,B_{r}\}) が B に含まれているなら、それを B から削除する。

\mathrm{mex}(X) とは？

非負整数からなる有限集合 X に対し，x\notin X を満たす最小の非負整数 x を \mathrm{mex}(X) と定義します．

制約

1\leq M\leq N\leq 500
0\leq A_{i}< N
A の要素は互いに相異なる
入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N M
A_{1} A_{2} \cdots A_{M}

出力

答えを出力してください。

入力例 1

4 2
1 3

出力例 1

B = (2, 1, 0, 3) で初期化したのち、以下の手順で B=A とすることが可能です。

(l,r) = (2, 4) を選び、B から \mathrm{mex}(\{1,0,3\}) = 2 を削除し、B=(1,0,3) とする。
(l,r) = (3, 3) を選び、B から \mathrm{mex}(\{3\}) = 0 を削除し、B=(1, 3) とする。

よって、P=(2, 1, 0, 3) は条件を満たします。

条件を満たす P はこれを含めて 8 通りあるので、8 を出力してください。

入力例 2

4 4
0 3 2 1

出力例 2

P = (0, 3, 2, 1) のときのみ条件を満たします。

入力例 3

16 7
9 2 4 0 1 6 7

出力例 3

入力例 4

92 4
1 67 16 7

出力例 4

726870122

998244353 で割ったあまりを求めてください。

Score : 700 points

Problem Statement

You are given a positive integer N and a sequence of M non-negative integers A = (A_{1}, A_{2}, \dots, A_{M}).

Here, all elements of A are distinct integers between 0 and N-1, inclusive.

Find the number, modulo 998244353, of permutations P of (0, 1, \dots, N-1) that satisfy the following condition.

After initializing a sequence B = (B_{1}, B_{2}, \dots, B_{N}) to P, it is possible to make B = A by repeating the following operation some number of times:
- Choose l and r such that 1 \leq l \leq r \leq |B|, and if \mathrm{mex}(\{B_{l}, B_{l+1}, \dots, B_{r}\}) is contained in B, remove it from B.

What is \mathrm{mex}(X)?

For a finite set X of non-negative integers, \mathrm{mex}(X) is defined as the smallest non-negative integer that is not in X.

Constraints

1 \leq M \leq N \leq 500
0 \leq A_{i} < N
All elements of A are distinct.
All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_{1} A_{2} \cdots A_{M}

Output

Print the answer.

Sample Input 1

4 2
1 3

Sample Output 1

After initializing B = (2, 1, 0, 3), it is possible to make B = A using the following steps:

Choose (l, r) = (2, 4), remove \mathrm{mex}(\{1, 0, 3\}) = 2 from B, making B = (1, 0, 3).
Choose (l, r) = (3, 3), remove \mathrm{mex}(\{3\}) = 0 from B, making B = (1, 3).

Thus, P = (2, 1, 0, 3) satisfies the condition.

There are eight permutations P that satisfy the condition, including the above, so print 8.

Sample Input 2

4 4
0 3 2 1

Sample Output 2

Only P = (0, 3, 2, 1) satisfies the condition.

Sample Input 3

16 7
9 2 4 0 1 6 7

Sample Output 3

Sample Input 4

92 4
1 67 16 7

Sample Output 4

726870122

Find the count modulo 998244353.

E - Serval Survival

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1000 点

問題文

長さ L の橋の上にサーバルが N 匹います。

i 匹目のサーバルは橋の左から A_{i} の位置にいます。

ここで、 0 < A_{1} < A_{2} < \cdots < A_{N} < L が成り立ちます。

i = 1, 2, \dots , N について、以下の問いに答えてください。

サーバルたちは以下の 3 つの行動を順番に行います。

行動 1 : i 匹目のサーバルを除く N - 1 匹のサーバルが左右のいずれかの方を向く。

行動 2 : i 匹目のサーバルが左右いずれかの方を向く。

行動 3 : 全てのサーバルが一斉に動き出す。全てのサーバルは常に 1 単位時間につきちょうど 1 の距離を進む速さで動く。サーバルが橋の端に辿り着いたら、橋の上から去ってしまう。 2 匹のサーバルがぶつかると、どちらのサーバルも進む向きを反転して動き続ける。

i 匹目のサーバルは賢く、この橋のことが好きなので、行動 2 で方向を選ぶとき、他の N-1 匹の向いている方を見て、行動 3 の際により長く橋の上にいられる方を選ぶとします。行動 1 で N-1 匹のサーバルが向いている方の組み合わせは 2^{N-1} 通りありますが、その全てにおける、i 匹目のサーバルが橋の上にいられる時間の総和を 998244353 で割ったあまりを求めてください。なお、出力すべき値は整数になることが証明できます。

制約

1\leq N\leq 10^{5}
0 < A_{1} < A_{2} < \cdots < A_{N} < L \leq 10^{9}
入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N L
A_{1} A_{2} \cdots A_{N}

出力

N 行出力してください。k 行目には i=k としたときの答えを出力してください。

入力例 1

2 167
9 24

出力例 1

182
301

i = 1 のときは、常に右を向くのが最適です。

i = 2 のときは、1 匹目のサーバルと反対の方を向くのが最適です。

入力例 2

1 924
167

出力例 2

入力例 3

10 924924167
46001560 235529797 272749755 301863061 359726177 470023587 667800476 696193062 741860924 809211293

出力例 3

Score : 1000 points

Problem Statement

There are N servals on a bridge of length L.

The i-th serval is located at position A_{i} from the left end of the bridge.

Here, 0 < A_{1} < A_{2} < \cdots < A_{N} < L holds.

For each i = 1, 2, \dots, N, answer the following question:

The servals will perform the following three actions in order:

Action 1: The N - 1 servals other than the i-th serval face left or right.

Action 2: The i-th serval faces left or right.

Action 3: All servals start moving simultaneously. All servals move at a constant speed of exactly 1 unit distance per unit time. When a serval reaches the end of the bridge, it leaves the bridge. If two servals collide, they both reverse their direction and continue moving.

The i-th serval is smart and loves this bridge, so when choosing a direction in Action 2, it will observe the directions of the other N-1 servals and choose the direction that allows it to stay on the bridge the longer during Action 3. There are 2^{N-1} possible combinations of directions for the N-1 servals in Action 1. Find the sum, modulo 998244353, over all these combinations, of the durations the i-th serval can stay on the bridge. It can be proved that the output value is an integer.

Constraints

1 \leq N \leq 10^{5}
0 < A_{1} < A_{2} < \cdots < A_{N} < L \leq 10^{9}
All input values are integers.

Input

The input is given from Standard Input in the following format:

N L
A_{1} A_{2} \cdots A_{N}

Output

Print N lines. The k-th line should contain the answer for i=k.

Sample Input 1

2 167
9 24

Sample Output 1

182
301

For i = 1, it is always optimal to face right.

For i = 2, it is optimal to face the opposite direction from the first serval.

Sample Input 2

1 924
167

Sample Output 2

Sample Input 3

10 924924167
46001560 235529797 272749755 301863061 359726177 470023587 667800476 696193062 741860924 809211293

Sample Output 3

F - Long Sequence Inversion

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1000 点

問題文

正の整数 N, M, K と、長さ M の非負整数列 A=(A_{0}, A_{1},\dots A_{M-1}) が与えられます。ここで、2^{N - 1}\leq K < 2^{N} が成り立ちます。

入力において、K は 2 進法表記で N 桁の数として与えられ、その他の整数は 10 進法表記で与えられます。

また、A は入力では直接与えられず、i=0,1,\dots ,M - 1 について、A_{i}=\sum_{j=0}^{L_{i}-1} 2^{X_{i,j}} となるような、長さ L_{i} の整数列 X_{i}=(X_{i,0},X_{i,1},\dots ,X_{i,L_{i}-1}) が与えられます。ここで、0\leq X_{i,0}<X_{i,1}<\cdots <X_{i,L_{i}-1}<N が成り立ちます。

以下のように定義される、長さ MK の数列 B=(B_{0},B_{1},\dots ,B_{MK-1}) の転倒数を 998244353 で割ったあまりを求めてください。

任意の 0 以上 K 未満の整数 a と任意の 0 以上 M 未満の整数 b に対して以下が成り立つ。
- B_{aM+b} は \operatorname{popcount}(a\operatorname{AND}A_{b}) を 2 で割ったあまりに等しい。

\operatorname{AND} とは？

整数 A, B のビット単位 \operatorname{AND}、A\ \operatorname{AND}\ B は以下のように定義されます。

A\ \operatorname{AND}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。

例えば、3\ \operatorname{AND}\ 5 = 1 となります (二進表記すると: 011\ \operatorname{AND}\ 101 = 001)。一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \operatorname{AND} は (\dots ((p_1\ \operatorname{AND}\ p_2)\ \operatorname{AND}\ p_3)\ \operatorname{AND}\ \dots\ \operatorname{AND}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。

\operatorname{popcount}とは？

非負整数 x について \operatorname{popcount}(x) とは、x を 2 進法で表記したときの 1 の個数です。より厳密には、非負整数 x について \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) が成り立っているとき \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i です。例えば、13 を 2 進法で表記すると 1101 なので、 \operatorname{popcount}(13)=3 となります。

制約

1\leq N\leq 2\times 10 ^ {5}
1\leq M\leq 2\times 10 ^ {5}
2^{N-1}\leq K< 2^{N}
0\leq L_{i}\leq N
\sum L_{i}\leq 2\times 10 ^ {5}
0\leq X_{i,0}<X_{i,1}<\cdots<X_{i,L_{i}-1}<N
入力は全て整数
K は 2 進法表記で与えられる。
K を除く数は 10 進法表記で与えられる。

入力

入力は以下の形式で標準入力から与えられます。

N M
K
L_{0} X_{0,0} X_{0,1} \cdots X_{0,L_{0}-1}
L_{1} X_{1,0} X_{1,1} \cdots X_{1,L_{1}-1}
\vdots
L_{M-1} X_{M-1,0} X_{M-1,1} \cdots X_{M-1,L_{M-1}-1}

出力

答えを出力してください。

入力例 1

出力例 1

A=(1, 3, 0, 2), B = (0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1) となります。

入力例 2

出力例 2

A = (6, 3, 1), B = (0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0) となります。

入力例 3

16 7
1101010000100110
11 0 1 2 3 7 10 11 12 13 14 15
7 4 6 8 10 11 12 13
6 0 1 6 8 10 12
8 0 3 5 6 10 11 12 13
10 0 1 2 3 4 5 6 8 12 13
9 3 4 5 6 8 9 11 14 15
8 0 4 7 9 10 11 13 14

出力例 3

97754354

入力例 4

92 4
10101100101111111111011101111111101011001011111110011110111111101111111110100111100010111011
23 1 2 5 13 14 20 28 32 34 39 52 56 59 60 62 64 67 69 71 78 84 87 91
20 15 17 22 28 36 40 43 47 52 53 57 67 72 77 78 81 87 89 90 91
23 7 8 9 10 11 13 16 19 22 23 30 33 42 49 51 52 58 64 71 73 76 79 83
22 1 13 19 26 27 28 29 35 39 40 41 46 55 60 62 64 67 74 79 82 89 90

出力例 4

291412708

998244353 で割ったあまりを求めてください。

Score : 1000 points

Problem Statement

You are given positive integers N, M, and K, and a sequence of M non-negative integers A = (A_{0}, A_{1}, \dots, A_{M-1}). Here, 2^{N - 1} \leq K < 2^{N} holds.

In the input, K is given as an N-digit number in binary notation, while the other integers are given in decimal notation.

Additionally, A is not given directly in the input. Instead, for each i = 0, 1, \dots, M - 1, you are given a sequence of L_i integers X_{i} = (X_{i,0}, X_{i,1}, \dots, X_{i,L_{i}-1}) such that A_{i} = \sum_{j=0}^{L_{i}-1} 2^{X_{i,j}}. Here, 0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_{i}-1} < N holds.

Find the inversion number, modulo 998244353, of the sequence B = (B_{0}, B_{1}, \dots, B_{MK-1}) defined as follows.

For any integer a such that 0 \leq a < K and any integer b such that 0 \leq b < M, the following holds:
- B_{aM+b} is equal to the remainder when \operatorname{popcount}(a \operatorname{AND} A_{b}) is divided by 2.

What is \operatorname{AND}?

The bitwise \operatorname{AND} of integers A and B, denoted as A \operatorname{AND} B, is defined as follows:

In the binary representation of A \operatorname{AND} B, the digit at the 2^k (k \geq 0) place is 1 if and only if the digits at the 2^k place in the binary representations of both A and B are 1; otherwise, it is 0.

For example, 3 \operatorname{AND} 5 = 1 (in binary: 011 \operatorname{AND} 101 = 001). Generally, the bitwise \operatorname{AND} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \operatorname{AND} p_2) \operatorname{AND} p_3) \operatorname{AND} \dots \operatorname{AND} p_k), and it can be proved that this is independent of the order of p_1, p_2, p_3, \dots, p_k.

What is \operatorname{popcount}?

For a non-negative integer x, \operatorname{popcount}(x) is the number of 1s in the binary representation of x. More precisely, for a non-negative integer x such that \displaystyle x = \sum_{i=0}^{\infty} b_i 2^i\ (b_i \in {0, 1}), it holds that \displaystyle \operatorname{popcount}(x) = \sum_{i=0}^{\infty} b_i. For example, 13 is 1101 in binary, so \operatorname{popcount}(13) = 3.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
2^{N-1} \leq K < 2^{N}
0 \leq L_{i} \leq N
\sum L_{i} \leq 2 \times 10^5
0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_{i}-1} < N
All input values are integers.
K is given in binary notation.
All numbers except K are given in decimal notation.

Input

The input is given from Standard Input in the following format:

N M
K
L_{0} X_{0,0} X_{0,1} \cdots X_{0,L_{0}-1}
L_{1} X_{1,0} X_{1,1} \cdots X_{1,L_{1}-1}
\vdots
L_{M-1} X_{M-1,0} X_{M-1,1} \cdots X_{M-1,L_{M-1}-1}

Output

Print the answer.

Sample Input 1

Sample Output 1

A = (1, 3, 0, 2), B = (0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1).

Sample Input 2

Sample Output 2

A = (6, 3, 1), B = (0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0).

Sample Input 3

16 7
1101010000100110
11 0 1 2 3 7 10 11 12 13 14 15
7 4 6 8 10 11 12 13
6 0 1 6 8 10 12
8 0 3 5 6 10 11 12 13
10 0 1 2 3 4 5 6 8 12 13
9 3 4 5 6 8 9 11 14 15
8 0 4 7 9 10 11 13 14

Sample Output 3

97754354

Sample Input 4

92 4
10101100101111111111011101111111101011001011111110011110111111101111111110100111100010111011
23 1 2 5 13 14 20 28 32 34 39 52 56 59 60 62 64 67 69 71 78 84 87 91
20 15 17 22 28 36 40 43 47 52 53 57 67 72 77 78 81 87 89 90 91
23 7 8 9 10 11 13 16 19 22 23 30 33 42 49 51 52 58 64 71 73 76 79 83
22 1 13 19 26 27 28 29 35 39 40 41 46 55 60 62 64 67 74 79 82 89 90

Sample Output 4

291412708

Find the number modulo 998244353.