303A.md (2174B)
1 Source: https://codeforces.com/problemset/problem/303/A 2 3 A. Lucky Permutation Triple 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 stdin 16 17 output 18 19 stdout 20 21 Bike is interested in permutations. A permutation of length *n* is an integer sequence such that each integer from 0 to (*n* - 1) appears exactly once in it. For example, [0, 2, 1] is a permutation of length 3 while both [0, 2, 2] and [1, 2, 3] is not. 22 23 A permutation triple of permutations of length *n* (*a*, *b*, *c*) is called a Lucky Permutation Triple if and only if . The sign *a**i* denotes the *i*-th element of permutation *a*. The modular equality described above denotes that the remainders after dividing *a**i* + *b**i* by *n* and dividing *c**i* by *n* are equal. 24 25 Now, he has an integer *n* and wants to find a Lucky Permutation Triple. Could you please help him? 26 27 Input 28 29 The first line contains a single integer *n* (1 ≤ *n* ≤ 105). 30 31 Output 32 33 If no Lucky Permutation Triple of length *n* exists print -1. 34 35 Otherwise, you need to print three lines. Each line contains *n* space-seperated integers. The first line must contain permutation *a*, the second line — permutation *b*, the third — permutation *c*. 36 37 If there are multiple solutions, print any of them. 38 39 Examples 40 41 Input 42 43 ``` 44 5 45 ``` 46 47 Output 48 49 ``` 50 1 4 3 2 0 51 1 0 2 4 3 52 2 4 0 1 3 53 ``` 54 55 Input 56 57 ``` 58 2 59 ``` 60 61 Output 62 63 ``` 64 -1 65 ``` 66 67 Note 68 69 In Sample 1, the permutation triple ([1, 4, 3, 2, 0], [1, 0, 2, 4, 3], [2, 4, 0, 1, 3]) is Lucky Permutation Triple, as following holds: 70 71 * ; 72 * ; 73 * ; 74 * ; 75 * . 76 77 In Sample 2, you can easily notice that no lucky permutation triple exists.