ARC--219参加記

$N$ 個の相異なる文字列 $S_1, \dots, S_N$ が与えられます。これらの文字列はいずれも、0, 1 のみからなる長さ $M$ の文字列です。
0, 1 のみからなる長さ $M$ の文字列 $T$ のうち、以下の条件を満たすものが存在するか判定し、あれば一例を構築してください。

• どの文字列 $S_i$ も、$T$ と少なくとも 1 箇所で文字が一致する。
  
• より厳密には、任意の整数 $i$ ($1 \le i \le N$) に対して、ある整数 $x_i$ ($1 \le x_i \le M$) が存在し、$S_i$ の $x_i$ 文字目と $T$ の $x_i$ 文字目が一致する。
  

制約

• $N, M$ は整数
  
• $1 \le N \le 2 \times 10^4$
  
• $1 \le M \le 100$
  
• $S_i$ は 0, 1 のみからなる長さ $M$ の文字列
  
• $S_1, \dots, S_N$ は相異なる
  

入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$
$S_1$
$\vdots$
$S_N$

出力
問題文中の条件を満たす $T$ が存在しないならば、No を出力せよ。
問題文中の条件を満たす $T$ が存在するならば、以下の形式で出力せよ。
Yes
$T$
条件を満たす $T$ が複数存在する場合、どれを出力しても正解と判定される。

整数 $N$ と $(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ が与えられます。 $(1,2,\ldots,N)$ の順列 $Q=(Q_1,Q_2,\ldots,Q_N)$ に対して、以下の操作をちょうど $1$ 回行うことにより得られる順列の中で辞書順最小の順列を $Q'=(Q_1',Q_2',\ldots,Q_N')$ とします：

• $1\le l\le r\le N$ を満たす整数の組 $(l,r)$ を選び、$Q_l,Q_{l + 1},\ldots,Q_r$ を反転させる。より厳密には、$Q$ を $(Q_1,Q_2,\ldots,Q_{l - 1} , Q_r,Q_{r - 1},\ldots,Q_l,Q_{r + 1},Q_{r + 2},\ldots,Q_N)$ で置き換える。 $Q'=P$ となる $(1,2,\ldots,N)$ の順列 $Q$ の個数を $998244353$ で割ったあまりを求めてください。 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1\le T$
• $1\le N\le 5\times 10^5$
• $P$ は $(1,2,\ldots,N)$ の順列
• 全てのテストケースにおける $N$ の総和は $5\times 10^5$ 以下
• 入力される値は全て整数

入力
入力は以下の形式で標準入力から与えられる。
$T$
$case_1$
$case_2$
$\vdots$
$case_T$
各テストケースは以下の形式で与えられる。
$N$
$P_1$ $P_2$ $\ldots$ $P_N$

出力
各テストケースに対する答えを順に改行区切りで出力せよ。