/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は、 H 行 W 列の座席表を管理しています。座席表の第 i 行第 j 列の座席を座席 (i, j) と呼びます。各座席にはアルファベット小文字 1 文字で表されるグループ名が割り当てられており、座席 (i, j) のグループ名を G_{i,j} とします。
高橋君は、座席表の中から「ユニークな座席」を見つけたいと考えています。座席 (i, j) が「ユニークな座席」であるとは、以下の 2 つの条件を同時に満たすことを意味します。
- 行における一意性： 第 i 行の W 個の座席の中で、グループ名が G_{i,j} であるものは座席 (i, j) のみである。すなわち、G_{i,k} = G_{i,j} を満たす k (1 \leq k \leq W) は k = j のみである。
- 列における一意性： 第 j 列の H 個の座席の中で、グループ名が G_{i,j} であるものは座席 (i, j) のみである。すなわち、G_{k,j} = G_{i,j} を満たす k (1 \leq k \leq H) は k = i のみである。
高橋君は、すべてのユニークな座席のグループ名を、行番号の小さい順に、同じ行の中では列番号の小さい順に読み取り、連結した文字列を作りたいと考えています。
座席表の情報が与えられるので、上記の文字列を求めてください。ユニークな座席が 1 つも存在しない場合は、空文字列を求めてください。
制約
- 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}
- 1 行目には、座席表の行数 H と列数 W が、スペース区切りで与えられる。
- 続く H 行にわたって、座席表の各行の情報が与えられる。その i 番目 (1 \leq i \leq H) の行には、第 i 行の座席のグループ名を連結した W 文字の文字列 G_{i,1}G_{i,2}\cdots G_{i,W} が与えられる。
出力
ユニークな座席のグループ名を、行番号の小さい順に、同じ行の中では列番号の小さい順に連結した文字列を 1 行で出力せよ。ユニークな座席が 1 つも存在しない場合は、空文字列を出力せよ（すなわち、空の行を出力せよ）。
入力例 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
Score : 300 pts
Problem Statement
Takahashi is managing a seating chart with H rows and W columns. The seat at row i and column j of the seating chart is called seat (i, j). Each seat is assigned a group name represented by a single lowercase letter, and the group name of seat (i, j) is denoted G_{i,j}.
Takahashi wants to find all "unique seats" in the seating chart. A seat (i, j) is a "unique seat" if and only if it satisfies both of the following conditions simultaneously:
- Uniqueness in the row: Among the W seats in row i, seat (i, j) is the only one with group name G_{i,j}. That is, the only k (1 \leq k \leq W) satisfying G_{i,k} = G_{i,j} is k = j.
- Uniqueness in the column: Among the H seats in column j, seat (i, j) is the only one with group name G_{i,j}. That is, the only k (1 \leq k \leq H) satisfying G_{k,j} = G_{i,j} is k = i.
Takahashi wants to read the group names of all unique seats in order of increasing row number, and within the same row in order of increasing column number, and concatenate them into a single string.
Given the seating chart information, determine the above string. If no unique seats exist, determine the empty string.
Constraints
- 1 \leq H \leq 2000
- 1 \leq W \leq 2000
- H, W are integers.
- G_{i,j} (1 \leq i \leq H, 1 \leq j \leq W) is a lowercase letter (
athroughz).
Input
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}
- The first line contains the number of rows H and the number of columns W of the seating chart, separated by a space.
- The following H lines give the information for each row of the seating chart. The i-th (1 \leq i \leq H) of these lines contains a string of W characters G_{i,1}G_{i,2}\cdots G_{i,W}, which is the concatenation of the group names of the seats in row i.
Output
Output in a single line the string obtained by concatenating the group names of the unique seats in order of increasing row number, and within the same row in order of increasing column number. If no unique seats exist, output the empty string (that is, output an empty line).
Sample Input 1
3 3 abc bca cab
Sample Output 1
abcbcacab
Sample Input 2
2 2 aa aa
Sample Output 2
Sample Input 3
4 6 abcdef aghijk almnop aqrstu
Sample Output 3
bcdefghijklmnopqrstu
Sample Input 4
8 10 abcdefghij abcdefghij klmnopqrst klmnopqrst uvwxabcdef uvwxabcdef ghijklmnop ghijklmnop
Sample Output 4
Sample Input 5
1 1 z
Sample Output 5
z