774D.md (2809B)
1 Source: https://codeforces.com/problemset/problem/774/D 2 3 D. Lie or Truth 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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*. 22 23 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*. 24 25 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). 26 27 Your task is to determine if it is possible that Stepan said the truth, or it is guaranteed that Stepan deceived his brother. 28 29 Input 30 31 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. 32 33 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. 34 35 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. 36 37 It is guaranteed that Stepan did not remove or add other cubes, he only rearranged Vasya's cubes. 38 39 Output 40 41 Print "LIE" (without quotes) if it is guaranteed that Stepan deceived his brother. In the other case, print "TRUTH" (without quotes). 42 43 Examples 44 45 Input 46 47 ``` 48 5 2 4 49 3 4 2 3 1 50 3 2 3 4 1 51 ``` 52 53 Output 54 55 ``` 56 TRUTH 57 ``` 58 59 Input 60 61 ``` 62 3 1 2 63 1 2 3 64 3 1 2 65 ``` 66 67 Output 68 69 ``` 70 LIE 71 ``` 72 73 Input 74 75 ``` 76 4 2 4 77 1 1 1 1 78 1 1 1 1 79 ``` 80 81 Output 82 83 ``` 84 TRUTH 85 ``` 86 87 Note 88 89 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]). 90 91 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. 92 93 In the third example for any values *l* and *r* there is a situation when Stepan said the truth.