ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Open Personal Contest 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. The Hobbit or There and Back Again

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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

Output

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.

Sample

inputoutput
4
1 4 2 3
1 3 4 2
Problem Author: Alexander Ipatov
Problem Source: VIII USU Open Personal Contest (March 3, 2007)
To submit the solution for this problem go to the Problem set: 1535. The Hobbit or There and Back Again