304027: CF774D. Lie or Truth

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Lie or Truthtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 a1, a2, ..., an.

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 b1, b2, ..., bn.

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 ≤ 105, 1 ≤ l ≤ r ≤ n) — the number of Vasya's cubes and the positions told by Stepan.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ n) — the sequence of integers written on cubes in the Vasya's order.

The third line contains the sequence b1, b2, ..., bn (1 ≤ bi ≤ 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).

ExamplesInput
5 2 4
3 4 2 3 1
3 2 3 4 1
Output
TRUTH
Input
3 1 2
1 2 3
3 1 2
Output
LIE
Input
4 2 4
1 1 1 1
1 1 1 1
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.

Input

加入题单

上一题 下一题 算法标签: