Old Bilbo collects songs and sagas of all races of Middle-earth. That is why he wants to leave Rivendell for a year, travel through N cities of Middle-earth, and return to Rivendell after that. The cities are numbered from 1 to N (Rivendell has number 1). At the entrance to each city there is a warder who asks travellers from which city they have come and requires an entrance fare depending on that. Wise Elvish King Elrond told Bilbo that if a traveller had come to city P from city Q then the warder would require to pay PQ golden coins. Before the start of the travel Bilbo wants to find an order of visiting the cities for which the money paid to the warders is minimal and an order for which it is maximal.

The input contains the number of cities N, 2 ≤ N ≤ 50000.

In the first line output N integers that show the order of visiting the cities that minimizes the total entrance fare. In the second line output the order of visiting the cities that maximizes the fare. Remember that Bilbo starts his travel from the city with number 1, visits each city exactly once and returns to the city with number 1 in the end. If there are several solutions, you may output any one of them.