У Васи есть последовательность кубиков, на каждом из которых написано ровно одно целое число. Вася любит порядок, поэтому выставил все свои кубики в ряд. Таким образом, последовательность чисел, записанных на кубиках в порядке слева направо равна a1, a2, ..., an.
Пока Вася отсутствовал, его маленький брат Степан поиграл с кубиками и поменял местами некоторые из них, после чего последовательность чисел на кубиках стала выглядеть как b1, b2, ..., bn.
Степан утверждает, что трогал только кубики, стоящие на позициях с l по r, не убирал и не добавлял другие кубики (иными словами, он переставил кубики на позициях с l по r произвольным образом).
Перед вами стоит задача определить, возможна ли то, что Степан говорит правду, либо он гарантированно обманывает своего брата.
Выходные данные
Выведите «LIE» (без кавычек), если Степан гарантированно обманывает брата. В противном случае, выведите «TRUTH» (без кавычек).
Примечание
В первом примере возможна ситуация при которой Степан говорит правду. Изначально последовательность кубиков выглядит как [3, 4, 2, 3, 1]. Степан мог сначала поменять местами кубики в позициях 2 и 3 (после этого последовательность кубиков выглядела бы как [3, 2, 4, 3, 1]), а затем поменять местами кубики в позициях 3 и 4 (после этого последовательность кубиков выглядела бы как [3, 2, 3, 4, 1]).
Во втором примере невозможна ситуация, при которой Степан говорит правду, так как он сообщил, что менял местами только кубики с позиции 1 до позиции 2, но из примера видно, что он гарантированно переместил кубик, стоящий изначально в позиции 3. Поэтому Степан гарантированно обманывает своего брата.
В третьем примере при любых значениях l и r возможна ситуация, при которой Степан говорит правду.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 4
3 4 2 3 1
3 2 3 4 1
|
TRUTH
|
|
2
|
3 1 2
1 2 3
3 1 2
|
LIE
|
|
3
|
4 2 4
1 1 1 1
1 1 1 1
|
TRUTH
|