← 返回题目列表

AtCoder · arc219_a

A. 相似性

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

你被给予 N 不同的字符串 S_1, \dots, S_N。这些字符串中的每一个都是一个长度的字符串 M 组成 0 和 1.

判断是否存在字符串 T 长度 M 组成 0 和 1 满足以下条件,如果满足,则构造一个示例。

  • 每个字符串 S_i 匹配 T 至少有一个位置。
    • 更正式地说,对于每个整数 i (1 \le i \le N),存在一个整数 x_i (1 \le x_i \le M)这样 x_i- 第一个字符 S_i 和 x_i- 第一个字符 T 是相同的。

约束

  • N 和 M 是整数。
  • 1 \leq N \leq 2 \times 10^4
  • 1 \leq M \leq 100
  • S_i 是一个长度为的字符串 M 组成 0 和 1.
  • 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 to 101,以下成立:

  • 的 2第一个字符 S_1 和 2第一个字符 T 是相同的。
  • 的 1st 字符 S_2 和 1st 字符 T 是相同的。
  • 的 1st 字符 S_3 和 1st 字符 T 是相同的。
  • 的 2第一个字符 S_4 和 2第一个字符 T 是相同的。
  • 的 3rd 字符 S_5 和 3rd 字符 T 是相同的。

示例输入 2

4 2
00
01
10
11

示例输出 2

No

No T 满足条件。


示例输入 3

9 50
00001000011111100011111000011111000001000001111100
00010100010000010100000100100000100011000010000010
00100010010000010100000000000000100101000010000010
01000001011111100100000000011111000001000001111110
01111111010001000100000000100000000001000000000010
01000001010000100100000100100000000001000010000010
01000001010000010011111000111111100111110001111100
00000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111

示例输出 3

Yes
10101010101010101010101011010101011010101101010101