Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

This round has an unusual addition to the rules. For each problem you must use distinct language. Thus, if you have a submission that has passed at least one test or is being tested at the moment, then for this task you can use only this language and can not use it for other tasks. More details can be read by the link. Different implementations of the same language are considered to be the same language (for example, in C++ you can only solve one problem, regardless of the exact chosen compiler).

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Lie or Truth

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya 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*_{1}, *a*_{2}, ..., *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*_{1}, *b*_{2}, ..., *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^{5}, 1 ≤ *l* ≤ *r* ≤ *n*) — the number of Vasya's cubes and the positions told by Stepan.

The second line contains the sequence *a*_{1}, *a*_{2}, ..., *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*_{1}, *b*_{2}, ..., *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).

Examples

Input

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/16/2021 15:18:59 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|