
ZOJ Problem Set  3798
Alice and Bob is playing a game, and this time the game is all about the absolute value! Alice has N different positive integers, and each number is not greater than N. Bob has a lot of blank paper, and he is responsible for the calculation things. The rule of game is pretty simple. First, Alice chooses a number a_{1} from the N integers, and Bob will write it down on the first paper, that's b_{1}. Then in the following kth rounds, Alice will choose a number a_{k} (2 ≤ k ≤ N), then Bob will write the number b_{k}=a_{k}b_{k1} on the kth paper. x means the absolute value of x. Now Alice and Bob want to kown, what is the maximum and minimum value of b_{N}. And you should tell them how to achieve that! InputThe input consists of multiple test cases; For each test case, the first line consists one integer N, the number of integers Alice have. (1 ≤ N ≤ 50000) OutputFor each test case, firstly print one line containing two numbers, the first one is the minimum value, and the second is the maximum value. Then print one line containing N numbers, the order of integers that Alice should choose to achieve the minimum value. Then print one line containing N numbers, the order of integers that Alice should choose to achieve the maximum value. Attention: Alice won't choose a integer more than twice. Sample Input2 Sample Output1 1 1 2 2 1 Author: ZHANG, Ruixiang Source: ZOJ Monthly, August 2014 