Lie or Truth

2000ms

262144K

Description:

Vasya has a sequence of cubes and exactly one integer is written on each cube. Vasya exhibited all his cubes in a row. So the sequence of numbers written on the cubes in the order from the left to the right equals to a₁, a₂, ..., a_n.

While Vasya was walking, his little brother Stepan played with Vasya's cubes and changed their order, so now the sequence of numbers written on the cubes became equal to b₁, b₂, ..., b_n.

Stepan said that he swapped only cubes which where on the positions between l and r, inclusive, and did not remove or add any other cubes (i. e. he said that he reordered cubes between positions l and r, inclusive, in some way).

Your task is to determine if it is possible that Stepan said the truth, or it is guaranteed that Stepan deceived his brother.

Input:

The first line contains three integers n, l, r (1 ≤ n ≤ 10⁵, 1 ≤ l ≤ r ≤ n) — the number of Vasya's cubes and the positions told by Stepan.

The second line contains the sequence a₁, a₂, ..., a_n (1 ≤ a_i ≤ n) — the sequence of integers written on cubes in the Vasya's order.

The third line contains the sequence b₁, b₂, ..., b_n (1 ≤ b_i ≤ n) — the sequence of integers written on cubes after Stepan rearranged their order.

It is guaranteed that Stepan did not remove or add other cubes, he only rearranged Vasya's cubes.

Output:

Print "LIE" (without quotes) if it is guaranteed that Stepan deceived his brother. In the other case, print "TRUTH" (without quotes).

Sample Input:

5 2 4
3 4 2 3 1
3 2 3 4 1

Sample Output:

TRUTH

Sample Input:

3 1 2
1 2 3
3 1 2

Sample Output:

LIE

Sample Input:

4 2 4
1 1 1 1
1 1 1 1

Sample Output:

TRUTH

Note:

In the first example there is a situation when Stepan said the truth. Initially the sequence of integers on the cubes was equal to [3, 4, 2, 3, 1]. Stepan could at first swap cubes on positions 2 and 3 (after that the sequence of integers on cubes became equal to [3, 2, 4, 3, 1]), and then swap cubes in positions 3 and 4 (after that the sequence of integers on cubes became equal to [3, 2, 3, 4, 1]).

In the second example it is not possible that Stepan said truth because he said that he swapped cubes only between positions 1 and 2, but we can see that it is guaranteed that he changed the position of the cube which was on the position 3 at first. So it is guaranteed that Stepan deceived his brother.

In the third example for any values l and r there is a situation when Stepan said the truth.

Informação

Provedor Codeforces

Código CF774D