D. Lie or Truth

Codeforces

IDCF774D

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsimplementationsortings

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_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_ ≤ 105, 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). [samples] ## 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.

Samples

Input #1

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

Output #1

TRUTH

Input #2

3 1 2
1 2 3
3 1 2

Output #2

LIE

Input #3

4 2 4
1 1 1 1
1 1 1 1

Output #3

TRUTH

API Response (JSON)

{
  "problem": {
    "name": "D. Lie or Truth",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF774D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments