{"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 right equals to _a_1, _a_2, ..., _a__n_.\n\nWhile 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_.\n\nStepan 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).\n\nYour task is to determine if it is possible that Stepan said the truth, or it is guaranteed that Stepan deceived his brother.\n\n## Input\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nIt is guaranteed that Stepan did not remove or add other cubes, he only rearranged Vasya's cubes.\n\n## Output\n\nPrint \"_LIE_\" (without quotes) if it is guaranteed that Stepan deceived his brother. In the other case, print \"_TRUTH_\" (without quotes).\n\n[samples]\n\n## Note\n\nIn 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\\]_).\n\nIn 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.\n\nIn the third example for any values _l_ and _r_ there is a situation when Stepan said the truth.","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 声称他只交换了位于位置 $[l]$ 到 $[r]$（包含两端）之间的立方体，没有移除或添加任何其他立方体（即，他仅在位置 $[l]$ 到 $[r]$（包含两端）之间以某种方式重新排列了立方体）。\n\n你的任务是判断 Stepan 是否有可能说了真话，或者可以确定 Stepan 欺骗了他的哥哥。\n\n第一行包含三个整数 $n$, $l$, $r$ ($1 ≤ n ≤ 10^5$, $1 ≤ l ≤ r ≤ n$) —— Vasya 的立方体数量以及 Stepan 所说的位置区间。\n\n第二行包含序列 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ n$) —— Vasya 原始顺序中立方体上的整数序列。\n\n第三行包含序列 $b_1, b_2, ..., b_n$ ($1 ≤ b_i ≤ n$) —— Stepan 重新排列后立方体上的整数序列。\n\n保证 Stepan 没有移除或添加任何立方体，他仅重新排列了 Vasya 的立方体。\n\n如果可以确定 Stepan 欺骗了他的哥哥，请输出 \"_LIE_\"（不含引号）；否则，输出 \"_TRUTH_\"（不含引号）。\n\n在第一个例子中，存在 Stepan 说真话的情况。最初立方体上的数字序列为 _[3, 4, 2, 3, 1]_。Stepan 可以先交换位置 $[2]$ 和 $[3]$ 上的立方体（交换后序列变为 _[3, 2, 4, 3, 1]_），然后再交换位置 $[3]$ 和 $[4]$ 上的立方体（交换后序列变为 _[3, 2, 3, 4, 1]_）。\n\n在第二个例子中，Stepan 不可能说真话，因为他声称只交换了位置 $[1]$ 和 $[2]$ 之间的立方体，但我们发现可以确定最初位于位置 $[3]$ 的立方体位置发生了改变。因此可以确定 Stepan 欺骗了他的哥哥。\n\n在第三个例子中，对于任意的 $l$ 和 $r$，都存在 Stepan 说真话的情况。\n\n## Input\n\n第一行包含三个整数 $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 的立方体。\n\n## Output\n\n如果可以确定 Stepan 欺骗了他的哥哥，请输出 \"_LIE_\"（不含引号）；否则，输出 \"_TRUTH_\"（不含引号）。\n\n[samples]\n\n## Note\n\n在第一个例子中，存在 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 说真话的情况。","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{out}} = \\{ a_i \\mid i \\notin [l, r] \\} $ — elements outside the interval $[l, r]$ in the original sequence.  \n- $ B_{\\text{out}} = \\{ b_i \\mid i \\notin [l, r] \\} $ — elements outside the interval $[l, r]$ in the modified sequence.  \n- $ A_{\\text{in}} = \\{ a_i \\mid i \\in [l, r] \\} $ — elements inside the interval $[l, r]$ in the original sequence.  \n- $ B_{\\text{in}} = \\{ b_i \\mid i \\in [l, r] \\} $ — elements inside the interval $[l, r]$ in the modified sequence.  \n\n**Constraint:**  \nStepan only rearranged elements within positions $[l, r]$. Therefore:  \n1. $ A_{\\text{out}} = B_{\\text{out}} $ (multisets must be equal).  \n2. $ A_{\\text{in}} = B_{\\text{in}} $ (multisets must be equal).  \n\n**Objective:**  \nDetermine whether both conditions hold.  \n\n**Output:**  \n- If both conditions hold → print `TRUTH`.  \n- Otherwise → print `LIE`.  \n\n---\n\n**Formal Statement:**\n\nLet $ a, b \\in \\{1, 2, \\dots, n\\}^n $, and $ 1 \\leq l \\leq r \\leq n $.  \n\nDefine:  \n- $ S_{\\text{out}} = \\{(i, a_i) \\mid i \\in [1, n] \\setminus [l, r]\\} $  \n- $ T_{\\text{out}} = \\{(i, b_i) \\mid i \\in [1, n] \\setminus [l, r]\\} $  \n\nThen:  \n$$\n\\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)\n$$\n\nOtherwise:  \n$$\n\\text{LIE}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF795D","tags":["implementation","sortings"],"sample_group":[["5 2 4\n3 4 2 3 1\n3 2 3 4 1","TRUTH"],["3 1 2\n1 2 3\n3 1 2","LIE"],["4 2 4\n1 1 1 1\n1 1 1 1","TRUTH"]],"created_at":"2026-03-03 11:00:39"}}