거짓말 탐지기

Andi는 경찰서에서 일하는 젊고 유능한 형사다. 범인을 추적하고 진실을 밝혀 사건을 해결하는 능력은 동료들을 항상 놀라게 한다. 어느 날 그는 어떤 사건을 수사하던 중 수상한 목격자 진술을 마주한다. 보통은 그런 믿기 어려운 진술을 무시하지만, 이번 사건에서는 목격자 진술이 무시하기에는 너무 중요하다. Andi는 이 상황을 해결하기 위해 기술, 즉 거짓말 탐지기를 사용하기로 한다.

Andi는 목격자 진술이 사실인지 판별하기 위해 거짓말 탐지기를 사용한다. 그런데 그가 사용한 거짓말 탐지기가 조작되었을 가능성이 있다는 것을 알아차리고, 첫 번째 거짓말 탐지기의 결과가 맞는지 판별하기 위해 두 번째 거짓말 탐지기를 사용한다. 이런 상황이 반복되어 Andi는 결국 모두 N대의 거짓말 탐지기를 사용하게 된다. i = 2..N에 대해 i번째 거짓말 탐지기는 (i−1)번째 거짓말 탐지기의 진위를 보고하고, 1번째 거짓말 탐지기는 목격자 진술의 진위를 보고한다.

결국 Andi는 마지막(N번째) 거짓말 탐지기가 조작되지 않았고 항상 진실을 정확히 보고한다는 것을 알고 있다. 이제 그는 모든 거짓말 탐지기의 결과가 주어졌을 때 목격자 진술이 사실인지 판별해야 한다.

예를 들어 N = 4이고 거짓말 탐지기의 결과가 (LIE, LIE, TRUTH, TRUTH)라고 하자.

• 4번째 거짓말 탐지기는 3번째 거짓말 탐지기가 TRUTH라고 보고한다. 4번째 거짓말 탐지기는 항상 진실을 정확히 보고하므로, 3번째 거짓말 탐지기의 결과는 그대로 맞다.
• 3번째 거짓말 탐지기는 2번째 거짓말 탐지기가 TRUTH라고 보고한다. 3번째 거짓말 탐지기의 결과가 그대로 맞으므로, 2번째 거짓말 탐지기의 결과도 그대로 맞다.
• 2번째 거짓말 탐지기는 1번째 거짓말 탐지기가 LIE라고 보고한다. 2번째 거짓말 탐지기의 결과가 그대로 맞으므로, 1번째 거짓말 탐지기의 결과는 틀리다.
• 1번째 거짓말 탐지기는 목격자 진술이 LIE라고 보고한다. 1번째 거짓말 탐지기의 결과가 틀리므로, 목격자 진술은 맞다. 다시 말해 목격자가 말하는 내용은 사실이다.

따라서 이 예에서 목격자 진술은 사실이다.

입력은 정수 N (2 ≤ N ≤ 100000)이 있는 한 줄로 시작한다. 다음 N개 줄에는 각각 i = 1..N에 대해 i번째 거짓말 탐지기의 출력을 나타내는 문자열 Si (TRUTH 또는 LIE)가 하나씩 주어진다.

목격자 진술이 사실인지 거짓인지에 따라 TRUTH 또는 LIE를 한 줄에 출력한다.