#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

After showing you his awesome, *eye catching* dance, **Guan** has suddenly ended up in another room in the dance arena.

In this room are **p** people, of two kinds, **Liars** and **Truth Tellers**. **Liars** __always lie__ and **Truth Tellers** __always__ tell the truth.

Each of the people in this room will make multiple statements about the other people in this room and there will be **n** statements in total.

Each person will either state that another person is telling the **truth or lying** (Each person knows every other person's identities and A liar will state that another person who tells the truth is lying) or he(/she) will state that the other person is either of **the same or of a different type.**

After hearing so many statements, **Guan** is confused and has hurt himself in his confusion :-(

**Guan** would like you to help him find out which people are definitely liars or truth tellers so that he can know who to trust.

An Illustration

## Input

The first line of the input will be the number of people, **p** followed by the number of statements, **n**

The rest of the lines of input will consist of a single integer, **i** indicating the id of the person who said the statement, followed by another integer **j** indicating the id of the person he(/she) is referring to and finally, a string saying either **TRUTH, LIAR, SAME or DIFFERENT** to indicate whether he(/she) says the other person is telling the truth, lies or is of the same type as herself or of a different type to herself.

It is guaranteed that there will be no **contradictory or repeated** statements and people may comment about themselves

Note: A person can comment on him(/her)self

## Output

A single of characters which indicate 'T' if a person is definitely a truth teller, 'F' if he(/she) is definitely a liar and '?' otherwise

## Subtasks

Subtask 1 (11%) p,n<=20

Subtask 2 (18%) p,n<=1000

Subtask 3 (9%) p,n<=1000000, there will be no SAME or DIFFERENT statements

Subtask 4 (17%) p,n<=1000000, there will be no TRUTH or LIAR statements

Subtask 5 (45%) p,n<=1000000, no further restrictions

Subtask 6 (0%) will be the sample testcases

## Sample Testcase 1

Input

5 5 1 2 TRUTH 1 3 LIAR 1 4 DIFFERENT 4 1 SAME 1 5 TRUTHOutput

TTFFT

## Explanation

1 always tells the truth, so he will say 2 is telling the truth, 3 is lying, 4 is different and 5 is telling the truth. 4 is lying, so he will say 1 is the same. No other combination of 5 people results in the same pairs of statements

## Sample Testcase 2

Input

3 2 1 2 SAME 2 1 SAMEOutput

TT?

## Explanation

Either TTF or TTT satisfy the above statements, so, we do not know whether the 3rd person is telling the truth or lying

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 11 | 10 | 2s | 64MB | Minimum |

2 | 18 | 10 | 2s | 64MB | Minimum |

3 | 9 | 10 | 2s | 64MB | Minimum |

4 | 17 | 10 | 2s | 64MB | Minimum |

5 | 45 | 10 | 2s | 64MB | Minimum |

6 | 0 | 2 | 2s | 64MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o truthandlies -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512