A - Similarity Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

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 \leq N \leq 2 \times 10^4
  • 1 \leq M \leq 100
  • S_i は 0, 1 のみからなる長さ M の文字列
  • S_1, \dots, S_N は相異なる

入力

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

N M
S_1
\vdots
S_N

出力

問題文中の条件を満たす T が存在しないならば、No を出力せよ。

問題文中の条件を満たす T が存在するならば、以下の形式で出力せよ。

Yes
T

条件を満たす T が複数存在する場合、どれを出力しても正解と判定される。

入力例 1

5 3
000
111
110
100
011

出力例 1

Yes
101

T を 101 とすれば、以下が成り立ちます。

  • S_1 の 2 文字目と T の 2 文字目は一致する。
  • S_2 の 1 文字目と T の 1 文字目は一致する。
  • S_3 の 1 文字目と T の 1 文字目は一致する。
  • S_4 の 2 文字目と T の 2 文字目は一致する。
  • S_5 の 3 文字目と T の 3 文字目は一致する。

入力例 2

4 2
00
01
10
11

出力例 2

No

条件を満たす T は存在しません。

入力例 3

9 50
00001000011111100011111000011111000001000001111100
00010100010000010100000100100000100011000010000010
00100010010000010100000000000000100101000010000010
01000001011111100100000000011111000001000001111110
01111111010001000100000000100000000001000000000010
01000001010000100100000100100000000001000010000010
01000001010000010011111000111111100111110001111100
00000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111

出力例 3

Yes
10101010101010101010101011010101011010101101010101

Score : 400 points

Problem Statement

You are given N distinct strings S_1, \dots, S_N. Each of these strings is a string of length M consisting of 0 and 1.

Determine whether there exists a string T of length M consisting of 0 and 1 satisfying the following condition, and if so, construct one example.

  • Every string S_i matches T in at least one position.
    • More formally, for every integer i (1 \le i \le N), there exists an integer x_i (1 \le x_i \le M) such that the x_i-th character of S_i and the x_i-th character of T are the same.

Constraints

  • N and M are integers.
  • 1 \leq N \leq 2 \times 10^4
  • 1 \leq M \leq 100
  • S_i is a string of length M consisting of 0 and 1.
  • S_1, \dots, S_N are distinct.

Input

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

N M
S_1
\vdots
S_N

Output

If no T satisfying the condition in the problem statement exists, output No.

If a T satisfying the condition in the problem statement exists, output in the following format:

Yes
T

If multiple T satisfying the condition exist, any of them will be accepted.

Sample Input 1

5 3
000
111
110
100
011

Sample Output 1

Yes
101

If we set T to 101, the following holds:

  • The 2nd character of S_1 and the 2nd character of T are the same.
  • The 1st character of S_2 and the 1st character of T are the same.
  • The 1st character of S_3 and the 1st character of T are the same.
  • The 2nd character of S_4 and the 2nd character of T are the same.
  • The 3rd character of S_5 and the 3rd character of T are the same.

Sample Input 2

4 2
00
01
10
11

Sample Output 2

No

No T satisfies the condition.

Sample Input 3

9 50
00001000011111100011111000011111000001000001111100
00010100010000010100000100100000100011000010000010
00100010010000010100000000000000100101000010000010
01000001011111100100000000011111000001000001111110
01111111010001000100000000100000000001000000000010
01000001010000100100000100100000000001000010000010
01000001010000010011111000111111100111110001111100
00000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111

Sample Output 3

Yes
10101010101010101010101011010101011010101101010101