402194: GYM100694 D Unfair Game

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Unfair Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The game with abstract n-faced dice is described by the following rules. The inventory used in the game is a certain number of abstract n-faced dice, each of their faces has its own integer number, such that all numbers on all faces are distinct. Two players take part in the game. At the beginning the first player chooses his dice. After that, the second player, knowing the first player's choice, chooses his dice (of course, he can't choose the first player's dice). Then players throw their dice simultaneously, and the player with the bigger number on his dice wins.

Constantine wants to play an infinite number of games against Mike. For this purpose, he needs to create three n-faced dice having the following properties: whichever dice is chosen by the first player, the second player always can choose his dice in such a way that the probability of his victory is strictly greater than . Constantine is planning to give Mike the first move: being the second player, he will win more frequently by choosing the right dice, and will earn an infinite amount of money.

Mike has agreed with these conditions, but the choice of number of faces n is after him. Help Constantine to create the needed set of n-faced dice.

Input

The only line contains one integer n (1 ≤ n ≤ 1000) — the number of faces of the dice.

Output

If the required set of abstract n-faced dice doesn't exist, output «FAIL».

Otherwise in the first line output «WIN», and in each of the next three lines output n integers — the numbers on the faces of the corresponding dice. All 3n numbers must be distinct and belong to the interval from 1 to 3n. If there are many possible solutions, output any of them.

ExamplesInput
1
Output
FAIL
Input
5
Output
WIN
1 3 7 14 15
2 6 10 11 13
4 5 8 9 12
Input
6
Output
WIN
4 6 8 9 11 18
2 3 7 13 15 17
1 5 10 12 14 16

加入题单

上一题 下一题 算法标签: