← 返回题目列表

Codeforces · 774/D

D. 谎言还是真相

中文机器翻译题面 查看原题

Vasya 有一系列立方体,每个立方体上都写有一个整数。瓦夏(Vasya)连续展示了他所有的立方体。因此,按从左到右的顺序写在立方体上的数字序列等于a1,a2,...,an。

瓦夏走路的时候,他的弟弟斯捷潘把玩瓦夏的立方体,改变了它们的顺序,所以现在立方体上写的数字顺序变成了b1,b2,...,bn。

Stepan 说他只交换了 l 和 r(含)之间位置的立方体,并且没有删除或添加任何其他立方体(即他说他以某种方式对位置 l 和 r(含)之间的立方体进行了重新排序)。

你的任务是确定Stepan是否有可能说真话,或者是否可以保证Stepan欺骗了他的兄弟。

输入

第一行包含三个整数 n、l、r (1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ n) — Vasya 立方体的数量以及 Stepan 告诉的位置。

第二行包含序列 a1, a2, ..., an (1 ≤ ai ≤ n) — 按照 Vasya 顺序写在立方体上的整数序列。

第三行包含序列 b1, b2, ..., bn (1 ≤ bi ≤ n) — Stepan 重新排列顺序后写在立方体上的整数序列。

可以保证Stepan没有删除或添加其他立方体,他只是重新排列了Vasya的立方体。

输出

如果可以保证 Stepan 欺骗了他的兄弟,则打印“LIE”(不带引号)。在其他情况下,打印“TRUTH”(不带引号)。

示例

输入 #1

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

输出 #1

TRUTH

输入 #2

3 1 2
1 2 3
3 1 2

输出 #2

LIE

输入 #3

4 2 4
1 1 1 1
1 1 1 1

输出 #3

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 上的立方体的位置。所以可以肯定,斯捷潘欺骗了他的兄弟。

在第三个例子中,对于任何值 l 和 r,都会出现 Stepan 说真话的情况。