아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Fail Them All!

시간 제한2초메모리 제한1024 MB

요약
각 학생이 맞힌 답이 많아도 하나가 되도록 T/F 정답표를 만들고, 사전순으로 가장 앞선 정답표를 구한다. 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
백트래킹, 그리디, 비트 연산
정답자
아직 제출이 없습니다

문제

You are an instructor for an algorithms course, and your students have been saying mean things about you on social media. Those jerks! Being a vengeful and dishonest instructor, you are going to make them pay.

You have given your students a True/False exam. For each question, each student is allowed to either answer the question or leave the question blank. Each student has answered at least two questions. You want to make sure that every student fails the test, so you are going to alter the answer key so that no student gets more than one answer correct.

Is there an answer key such that every person has at most one submitted answer that is correct? If so, compute the lexicographically minimal such answer key.

입력

The first line of input contains two integers nn (1≤n≤1001 \le n \le 100) and kk (2≤k≤1002 \le k \le 100), where nn is the number of students in the class, and kk is the number of questions on the test.

Each of the next nn lines contains a string ss (∣s∣=k|s| = k, s∈T,F,X\*s \in \\{\texttt{T}, \texttt{F}, \texttt{X}\\}^\*), which are the answers to the questions, in order, for each student, where 'T' means True, 'F' means False, and 'X' means the student didn't answer the question. Every student's answers will have at least two which are not 'X'.

출력

If such an answer key can be constructed, output a string of length kk consisting of only the characters 'T' and 'F', which is the answer key. If more than one such key is possible, output the one which comes first alphabetically ('F' < 'T'). If no such key exists, instead output -1.

예제3

  1. 예제 1

    입력
    3 3
    FFX
    XFF
    FXF
    
    예상 출력
    FTT
    
  2. 예제 2

    입력
    3 3
    FTX
    XFT
    TXF
    
    예상 출력
    FFF
    
  3. 예제 3

    입력
    4 3
    TTX
    XTT
    TXT
    FFF
    
    예상 출력
    -1