← 返回题目列表

AtCoder · awc0024_c

C. 独特的座位

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

分数: 300 分

问题陈述

Takahashi 正在管理座位表 H 行和 W 列。排的座位 i 和专栏 座位表的 j 称为座位 (i, j)。每个座位分配有一个由单个小写字母表示的组名,以及座位的组名 (i, j) 表示 G_{i,j}.

高桥想要找到座位表中的所有“独特座位”。一个座位 (i, j) 是一个“独特的座位”当且仅当它满足 两者 同时满足以下条件:

  • 行中的唯一性: 其中 W 排座位 i, 座位 (i, j) 是唯一一个有组名的 G_{i,j}。也就是说,唯一 k (1 \leq k \leq W) 满意 G_{i,k} = G_{i,j} is k = j.
  • 列中的唯一性: 其中 H 列中的座位 j, 座位 (i, j) 是唯一一个有组名的 G_{i,j}。也就是说,唯一 k (1 \leq k \leq H) 满意 G_{k,j} = G_{i,j} is k = i.

Takahashi 想要按行号递增的顺序读取所有唯一座位的组名称,并按列号递增的顺序读取同一行中的所有唯一座位的组名称,并将它们连接成一个字符串。

给定座位表信息,确定上述字符串。如果不存在唯一的座位,则确定空字符串。

约束

  • 1 \leq H \leq 2000
  • 1 \leq W \leq 2000
  • H, W 是整数。
  • G_{i,j} (1 \leq i \leq H, 1 \leq j \leq W) 是一个小写字母 (a 通过 z).

输入

H W
G_{1,1}G_{1,2}\cdots G_{1,W}
G_{2,1}G_{2,2}\cdots G_{2,W}
\vdots
G_{H,1}G_{H,2}\cdots G_{H,W}
  • 第一行包含行数 H 和列数 座位表的 W ,以空格分隔。
  • 以下 H 行提供座位表中每一行的信息。的 这些行的 i-th (1 \leq i \leq H) 包含一串 W 字符 G_{i,1}G_{i,2}\cdots G_{i,W},这是行中座位的组名称的串联 i.

输出

在单行中输出通过按行号递增的顺序连接唯一座位的组名称而获得的字符串,并在同一行中按列号递增的顺序输出。如果不存在唯一的座位,则输出空字符串(即输出空行)。


示例输入 1

3 3
abc
bca
cab

示例输出 1

abcbcacab

示例输入 2

2 2
aa
aa

示例输出 2



示例输入 3

4 6
abcdef
aghijk
almnop
aqrstu

示例输出 3

bcdefghijklmnopqrstu

示例输入 4

8 10
abcdefghij
abcdefghij
klmnopqrst
klmnopqrst
uvwxabcdef
uvwxabcdef
ghijklmnop
ghijklmnop

示例输出 4



示例输入 5

1 1
z

示例输出 5

z