English · Original
Chinese · Translation
Formal · Original
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.
Vasya 有一列立方体，每个立方体上恰好写有一个整数。Vasya 将他的所有立方体排成一行，因此立方体上写的数字从左到右的序列等于 $[a_1, a_2, ..., a_n]$。
当 Vasya 走开时，他的小弟弟 Stepan 玩弄了 Vasya 的立方体并改变了它们的顺序，现在立方体上的数字序列变为 $[b_1, b_2, ..., b_n]$。
Stepan 声称他只交换了位于位置 $[l]$ 到 $[r]$（包含两端）之间的立方体，没有移除或添加任何其他立方体（即，他仅在位置 $[l]$ 到 $[r]$（包含两端）之间以某种方式重新排列了立方体）。
你的任务是判断 Stepan 是否有可能说了真话，或者可以确定 Stepan 欺骗了他的哥哥。
第一行包含三个整数 $n$, $l$, $r$ ($1 ≤ n ≤ 10^5$, $1 ≤ l ≤ r ≤ n$) —— Vasya 的立方体数量以及 Stepan 所说的位置区间。
第二行包含序列 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ n$) —— Vasya 原始顺序中立方体上的整数序列。
第三行包含序列 $b_1, b_2, ..., b_n$ ($1 ≤ b_i ≤ n$) —— Stepan 重新排列后立方体上的整数序列。
保证 Stepan 没有移除或添加任何立方体，他仅重新排列了 Vasya 的立方体。
如果可以确定 Stepan 欺骗了他的哥哥，请输出 "_LIE_"（不含引号）；否则，输出 "_TRUTH_"（不含引号）。
在第一个例子中，存在 Stepan 说真话的情况。最初立方体上的数字序列为 _[3, 4, 2, 3, 1]_。Stepan 可以先交换位置 $[2]$ 和 $[3]$ 上的立方体（交换后序列变为 _[3, 2, 4, 3, 1]_），然后再交换位置 $[3]$ 和 $[4]$ 上的立方体（交换后序列变为 _[3, 2, 3, 4, 1]_）。
在第二个例子中，Stepan 不可能说真话，因为他声称只交换了位置 $[1]$ 和 $[2]$ 之间的立方体，但我们发现可以确定最初位于位置 $[3]$ 的立方体位置发生了改变。因此可以确定 Stepan 欺骗了他的哥哥。
在第三个例子中，对于任意的 $l$ 和 $r$，都存在 Stepan 说真话的情况。
## Input
第一行包含三个整数 $n$, $l$, $r$ ($1 ≤ n ≤ 10^5$, $1 ≤ l ≤ r ≤ n$) —— Vasya 的立方体数量以及 Stepan 所说的位置区间。第二行包含序列 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ n$) —— Vasya 原始顺序中立方体上的整数序列。第三行包含序列 $b_1, b_2, ..., b_n$ ($1 ≤ b_i ≤ n$) —— Stepan 重新排列后立方体上的整数序列。保证 Stepan 没有移除或添加任何立方体，他仅重新排列了 Vasya 的立方体。
## Output
如果可以确定 Stepan 欺骗了他的哥哥，请输出 "_LIE_"（不含引号）；否则，输出 "_TRUTH_"（不含引号）。
[samples]
## Note
在第一个例子中，存在 Stepan 说真话的情况。最初立方体上的数字序列为 _[3, 4, 2, 3, 1]_。Stepan 可以先交换位置 $[2]$ 和 $[3]$ 上的立方体（交换后序列变为 _[3, 2, 4, 3, 1]_），然后再交换位置 $[3]$ 和 $[4]$ 上的立方体（交换后序列变为 _[3, 2, 3, 4, 1]_）。在第二个例子中，Stepan 不可能说真话，因为他声称只交换了位置 $[1]$ 和 $[2]$ 之间的立方体，但我们发现可以确定最初位于位置 $[3]$ 的立方体位置发生了改变。因此可以确定 Stepan 欺骗了他的哥哥。在第三个例子中，对于任意的 $l$ 和 $r$，都存在 Stepan 说真话的情况。
Given:
- Two sequences $ a = [a_1, a_2, \dots, a_n] $ and $ b = [b_1, b_2, \dots, b_n] $, each of length $ n $.
- Two integers $ l, r $ with $ 1 \leq l \leq r \leq n $.
Define:
- $ A_{\text{out}} = \{ a_i \mid i \notin [l, r] \} $ — elements outside the interval $[l, r]$ in the original sequence.
- $ B_{\text{out}} = \{ b_i \mid i \notin [l, r] \} $ — elements outside the interval $[l, r]$ in the modified sequence.
- $ A_{\text{in}} = \{ a_i \mid i \in [l, r] \} $ — elements inside the interval $[l, r]$ in the original sequence.
- $ B_{\text{in}} = \{ b_i \mid i \in [l, r] \} $ — elements inside the interval $[l, r]$ in the modified sequence.
**Constraint:**
Stepan only rearranged elements within positions $[l, r]$. Therefore:
1. $ A_{\text{out}} = B_{\text{out}} $ (multisets must be equal).
2. $ A_{\text{in}} = B_{\text{in}} $ (multisets must be equal).
**Objective:**
Determine whether both conditions hold.
**Output:**
- If both conditions hold → print `TRUTH`.
- Otherwise → print `LIE`.
---
**Formal Statement:**
Let $ a, b \in \{1, 2, \dots, n\}^n $, and $ 1 \leq l \leq r \leq n $.
Define:
- $ S_{\text{out}} = \{(i, a_i) \mid i \in [1, n] \setminus [l, r]\} $
- $ T_{\text{out}} = \{(i, b_i) \mid i \in [1, n] \setminus [l, r]\} $
Then:
$$
\text{TRUTH} \iff \left( \text{multiset}\left( \{ a_i \mid i \notin [l, r] \} \right) = \text{multiset}\left( \{ b_i \mid i \notin [l, r] \} \right) \right) \land \left( \text{multiset}\left( \{ a_i \mid i \in [l, r] \} \right) = \text{multiset}\left( \{ b_i \mid i \in [l, r] \} \right) \right)
$$
Otherwise:
$$
\text{LIE}
$$
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": "CF795D"
},
"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"
},
{
"statement_type": "Markdown",
"content": "Vasya 有一列立方体，每个立方体上恰好写有一个整数。Vasya 将他的所有立方体排成一行，因此立方体上写的数字从左到右的序列等于 $[a_1, a_2, ..., a_n]$。\n\n当 Vasya 走开时，他的小弟弟 Stepan 玩弄了 Vasya 的立方体并改变了它们的顺序，现在立方体上的数字序列变为 $[b_1, b_2, ..., b_n]$。\n\nStepan 声称他只交换了位于位置 $...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Given: \n- Two sequences $ a = [a_1, a_2, \\dots, a_n] $ and $ b = [b_1, b_2, \\dots, b_n] $, each of length $ n $. \n- Two integers $ l, r $ with $ 1 \\leq l \\leq r \\leq n $. \n\nDefine: \n- $ A_{\\text{o...",
"is_translate": false,
"language": "Formal"
}
]
}