Three‐Valued Logic Fixed Point

In this problem, you are given n three‐valued logic variables \(x_1, x_2, \ldots, x_n\). Each variable can take one of the three values: \(\mathit{True}\) (denoted by T), \(\mathit{False}\) (denoted by F), or \(\mathit{Unknown}\) (denoted by U).

Three‐valued logic also allows you to define logical operations. Here you only need to consider the logical NOT operator \(\lnot\), whose operation is defined as:

$$\lnot \mathit{T}=\mathit{F},\quad \lnot \mathit{F}=\mathit{T},\quad \lnot \mathit{U}=\mathit{U}.$$

Initially, an assignment (called the initial value) is given for every variable. Then, a sequence of m statements is executed in order. There are three types of statements:

1. \(x_i \leftarrow v\), where \(v\) is one of \(\mathit{T},\, \mathit{F},\, \mathit{U}\).
2. \(x_i \leftarrow x_j\).
3. \(x_i \leftarrow \lnot x_j\).

After executing all the statements, the final value of each variable (the result of sequentially applying the statements) is compared to its initial value. Your task is to choose an initial assignment for all variables such that after executing all statements, every variable’s final value equals its initial value and, among all such assignments, the number of variables initially assigned \(\mathit{Unknown}\) is minimized.

You may assume that for every test case a solution exists.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 10^5\)), representing the number of variables and statements.

Each of the following \(m\) lines describes a statement in one of the following formats:

• 1 i v — meaning \(x_i \leftarrow v\), where v is one of T, F, or U.
• 2 i j — meaning \(x_i \leftarrow x_j\).
• 3 i j — meaning \(x_i \leftarrow \lnot x_j\).

Variables are 1-indexed. It is guaranteed that the input is valid.

outputFormat

Output a string of length \(n\) consisting only of the characters T, F, and U. The \(i\)th character represents the initial value assigned to \(x_i\), and it must be the same as its final value after executing all statements. The assignment should use as few U's as possible.

sample

3 3
1 1 T
2 2 1
3 3 2

TTF