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 ≤ 10^5, 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).


-----Examples-----
Input
5 2 4
3 4 2 3 1
3 2 3 4 1

Output
TRUTH

Input
3 1 2
1 2 3
3 1 2

Output
LIE

Input
4 2 4
1 1 1 1
1 1 1 1

Output
TRUTH



-----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.

Difficulty: MEDIUM
Tags: Sorting

Implementation

Constructive algorithms
Skill types: Sorting

Starter code:

Solutions:
nlr = input().split()
a = input().split()
b = input().split()
if (a[:int(nlr[1]) - 1] != b[:int(nlr[1]) - 1]) | (a[int(nlr[2]) + 1:] != b[int(nlr[2]) + 1:]) | (sorted(a[int(nlr[1]) - 1:int(nlr[2])]) != sorted(b[int(nlr[1]) - 1:int(nlr[2])])):
	print('LIE')
else:
	print('TRUTH')


(n, l, r) = map(int, input().split())
l -= 1
a = input().split()
b = input().split()
if a[:l] == b[:l] and a[r:] == b[r:]:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
l = l - 1
r = r - 1
A = A[0:l] + A[r + 1:]
B = B[0:l] + B[r + 1:]
if A == B:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 'TRUTH'
for i in range(0, l - 1):
	if a[i] != b[i]:
		ans = 'LIE'
		break
for i in range(r, n):
	if a[i] != b[i]:
		ans = 'LIE'
		break
print(ans)


vals = lambda : map(int, input().split())
(n, l, r) = vals()
a1 = list(vals())
a2 = list(vals())
if a1[:l - 1] == a2[:l - 1] and a1[r:] == a2[r:]:
	print('TRUTH')
else:
	print('LIE')


i = lambda : map(int, input().split())
(n, l, r) = i()
a = list(i())
b = list(i())
a0 = a[0:l - 1]
a1 = a[l - 1:r]
a2 = a[r:n]
b0 = b[0:l - 1]
b1 = b[l - 1:r]
b2 = b[r:n]
a1.sort()
b1.sort()
print('TRUTH' if a0 == b0 and a1 == b1 and (a2 == b2) else 'LIE')


import sys

def main():
	yes = True
	array = sys.stdin.readline().strip().split(' ')
	array1 = sys.stdin.readline().strip().split(' ')
	array2 = sys.stdin.readline().strip().split(' ')
	for i in range(len(array1)):
		if i < int(array[1]) - 1 or i >= int(array[2]):
			if array1[i] != array2[i]:
				yes = False
				break
	if yes:
		print('TRUTH')
	else:
		print('LIE')
	return
main()


import math
import bisect
from collections import defaultdict
from collections import OrderedDict
from itertools import combinations
import heapq
from collections import deque
(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
at = a[l - 1:r]
al = a[:l - 1]
ar = a[r:]
bt = b[l - 1:r]
bl = b[:l - 1]
br = b[r:]
if sorted(at) == sorted(bt) and ar == br and (al == bl):
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
l -= 1
r -= 1
a = list(map(int, input().split()))
b = list(map(int, input().split()))
f = True
for i in range(0, l):
	if a[i] != b[i]:
		f = False
		break
for i in range(r + 1, n):
	if a[i] != b[i]:
		f = False
		break
c = []
d = []
for i in range(l, r + 1):
	c.append(a[i])
	d.append(b[i])
c.sort()
d.sort()
if c != d:
	f = False
if f:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().strip().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
l = l - 1
for i in range(n):
	if (i < l or i >= r) and a[i] != b[i]:
		print('LIE')
		exit()
a = a[l:r]
b = b[l:r]
a.sort()
b.sort()
if a == b:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if a[0:l - 1] == b[0:l - 1] and a[r:] == b[r:] and (sorted(a[l - 1:r]) == sorted(b[l - 1:r])):
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l -= 1
r -= 1
(ma, mb) = ([], [])
for i in range(0, n):
	if not (l <= i and i <= r):
		if a[i] != b[i]:
			print('LIE')
			exit(0)
	else:
		ma.append(a[i])
		mb.append(b[i])
ma.sort()
mb.sort()
if ma == mb:
	print('TRUTH')
else:
	print('LIE')


(n, l, d) = [int(x) for x in input().split()]
a = list(input().split())
b = list(input().split())
x = 0
for i in range(n):
	if i + 1 < l or i + 1 > d:
		if a[i] != b[i]:
			x = 1
if x == 1:
	print('LIE')
else:
	print('TRUTH')


(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a1 = list()
b1 = list()
u = 1
for i in range(0, n):
	if i >= l - 1 and i <= r - 1:
		a1.append(a[i])
		b1.append(b[i])
	elif a[i] != b[i]:
		u = 0
		break
a1.sort()
b1.sort()
if a1 != b1 or u == 0:
	print('LIE')
else:
	print('TRUTH')


(n, l, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
f = True
for i in range(l - 1):
	if a[i] != b[i]:
		f = False
for i in range(r, n):
	if a[i] != b[i]:
		f = False
a1 = []
b1 = []
for i in range(l - 1, r):
	b1.append(b[i])
	a1.append(a[i])
a1.sort()
b1.sort()
for i in range(len(a1)):
	if a1[i] != b1[i]:
		f = False
if f:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = [int(num) for num in input().split(' ')]
a = [None] + [int(num) for num in input().split(' ')]
b = [None] + [int(num) for num in input().split(' ')]
aS = a[l:r + 1]
bS = b[l:r + 1]
aS.sort()
bS.sort()
a = a[1:l] + aS + a[r + 1:]
b = b[1:l] + bS + b[r + 1:]
if a == b:
	print('TRUTH')
else:
	print('LIE')


(n, a, b) = map(int, input().split())
ar1 = list(map(int, input().split()))
ar2 = list(map(int, input().split()))
truth = True
for i in range(n):
	if i not in range(a - 1, b):
		if ar1[i] != ar2[i]:
			truth = False
			break
if truth:
	nums = dict()
	for i in range(a - 1, b):
		if ar1[i] in nums:
			nums[ar1[i]] += 1
		else:
			nums[ar1[i]] = 1
		if ar2[i] in nums:
			nums[ar2[i]] -= 1
		else:
			nums[ar2[i]] = -1
	for x in nums:
		if nums[x] is not 0:
			truth = False
			break
	if truth:
		print('TRUTH')
	else:
		print('LIE')
else:
	print('LIE')


def main():
	s = input().split()
	n = int(s[0])
	l = int(s[1])
	r = int(s[2])
	s = input().split()
	arr1 = []
	for i in range(n):
		k = int(s[i])
		arr1.append(k)
	s = input().split()
	for i in range(n):
		k = int(s[i])
		if arr1[i] != k and (i + 1 < l or i + 1 > r):
			print('LIE')
			return
	print('TRUTH')
	return

def __starting_point():
	main()
__starting_point()


(n, l, r) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
if a[0:l - 1] + a[r:] == b[0:l - 1] + b[r:]:
	print('TRUTH')
else:
	print('LIE')


import sys
from collections import defaultdict
N = []
N1 = []
M = defaultdict(int)
M1 = defaultdict(int)
(n, l, r) = map(int, input().split())
N = list(map(int, input().split()))
N1 = list(map(int, input().split()))
Pass = True
for i in range(l - 1):
	if N[i] != N1[i]:
		Pass = False
		break
if Pass is True:
	for i in range(r, n):
		if N[i] != N1[i]:
			Pass = False
			break
if Pass is True:
	for i in range(l - 1, r):
		M[N[i]] += 1
		M1[N1[i]] += 1
	for i in range(n + 1):
		if M[i] != M1[i]:
			Pass = False
			break
if Pass:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []
isOk = 0
for i in range(0, l - 1):
	if a[i] != b[i]:
		isOk = 1
for i in range(r, n):
	if a[i] != b[i]:
		isOk = 1
for i in range(l - 1, r):
	c.append(a[i])
	d.append(b[i])
c.sort()
d.sort()
if c != d:
	isOk = 1
if isOk == 1:
	print('LIE')
else:
	print('TRUTH')


N = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = set()
b = set()
for i in range(N[1] - 1, N[2]):
	a.add(A[i])
	b.add(B[i])
flag = True
for i in range(N[1] - 1):
	if A[i] != B[i]:
		flag = False
for i in range(N[2], N[0]):
	if A[i] != B[i]:
		flag = False
if a != b:
	flag = False
if flag == True:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
l = l - 1
r = r - 1
l3 = []
l4 = []
c = 0
for i in range(l, r + 1):
	l3.append(l1[i])
	l4.append(l2[i])
for i in range(0, l):
	if l1[i] != l2[i]:
		c = c + 1
for i in range(r + 1, n):
	if l1[i] != l2[i]:
		c = c + 1
l3.sort()
l4.sort()
for i in range(0, r - l + 1):
	if l3[i] != l4[i]:
		c = c + 1
if c == 0:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
flg = 0
l = l - 1
r = r - 1
for i in range(0, n):
	if i < l or i > r:
		if a[i] != b[i]:
			flg = 1
if flg:
	print('LIE')
else:
	print('TRUTH')


(l, a, b) = map(int, input().split())
before = list(map(int, input().split()))
after = list(map(int, input().split()))
if sorted(before[a - 1:b]) != sorted(after[a - 1:b]):
	print('LIE')
elif before[:a - 1] != after[:a - 1]:
	print('LIE')
elif before[b:] != after[b:]:
	print('LIE')
else:
	print('TRUTH')


(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0 for i in range(100005)]
for i in range(l - 1, r):
	c[a[i]] += 1
	c[b[i]] -= 1
t = True
for i in range(0, l - 1):
	if a[i] != b[i]:
		t = False
for i in range(r, n):
	if a[i] != b[i]:
		t = False
for i in c:
	if i != 0:
		t = False
if t:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = list(map(int, input().split()))
l -= 1
r -= 1
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = 1
for i in range(0, l):
	if a[i] != b[i]:
		c = 0
for i in range(r + 1, n):
	if a[i] != b[i]:
		c = 0
if c == 1:
	print('TRUTH')
else:
	print('LIE')
import time, sys
sys.stderr.write('{0:.3f} ms\n'.format(time.clock() * 1000))


A = list(map(int, input().split()))
n = A[0]
l = A[1]
r = A[2]
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 1
for i in range(0, l - 1):
	if a[i] != b[i]:
		ans = 0
for i in range(r, n):
	if a[i] != b[i]:
		ans = 0
if ans == 0:
	print('LIE')
else:
	print('TRUTH')


lmap = lambda f, x: list(map(f, x))
(n, l, r) = lmap(int, input().split())
l -= 1
a = lmap(int, input().split())
b = lmap(int, input().split())
a1 = a[l:r]
a2 = b[l:r]
good = sorted(a1) == sorted(a2) and a[:l] == b[:l] and (a[r:] == b[r:])
if good:
	print('TRUTH')
else:
	print('LIE')


import sys
(n, l, r) = list(map(int, sys.stdin.readline().split(' ')))
a = list(map(int, sys.stdin.readline().split(' ')))
b = list(map(int, sys.stdin.readline().split(' ')))
l -= 1
for i in range(0, l):
	if a[i] != b[i]:
		print('LIE')
		return
for i in range(r, n):
	if a[i] != b[i]:
		print('LIE')
		return
print('TRUTH')


(n, x1, x2) = [int(i) for i in input().split()]
a = input().split()
a = a[:x1 - 1] + a[x2:]
b = input().split()
b = b[:x1 - 1] + b[x2:]
check = True
for i in range(len(a)):
	if a[i] != b[i]:
		check = False
		break
if check:
	print('TRUTH')
else:
	print('LIE')


(n, l, r) = map(int, input().split())
l -= 1
r -= 1
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(n):
	if b[i] != a[i] and (i < l or i > r):
		print('LIE')
		break
else:
	print('TRUTH')


n = list(map(int, input().split(' ')))
ai = list(map(int, input().split(' ')))
bi = list(map(int, input().split(' ')))
flag = True
for i in range(n[1] - 1):
	if ai[i] != bi[i]:
		flag = False
		print('LIE')
		break
if flag:
	for i in range(n[0] - n[2]):
		if ai[n[2] + i] != bi[n[2] + i]:
			flag = False
			print('LIE')
			break
if flag == True:
	print('TRUTH')