시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1915 984 892 57.511%

문제

동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 써있다.

동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만드려고 한다.

  1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
  2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
  3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
  4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
  5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 조각에 써 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.

출력

두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.

예제 입력 1

2 1 5 3 4

예제 출력 1

1 2 5 3 4
1 2 3 5 4
1 2 3 4 5
W3sicHJvYmxlbV9pZCI6IjI5NDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHVjODcwXHVhYzAxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHViMDk4XHViYjM0IFx1Yzg3MFx1YWMwMVx1Yzc0NCA1XHVhYzFjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjA5OFx1YmIzNCBcdWM4NzBcdWFjMDFcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCA1XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MCBcdWM5MTEgXHVkNTU4XHViMDk4XHVhYzAwIFx1YzRmMFx1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWIyZTRcdWMxMmYgXHVjODcwXHVhYzAxIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM1ZDBcdWI5Y2MgXHVjMzY4XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHViMDk4XHViYjM0IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjNzBcdWNjZDBcdWMxMWMgMSwgMiwgMywgNCwgNSBcdWMyMWNcdWMxMWNcdWI4NWMgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWMyMThcdWFjMDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMThcdWJjZjRcdWIyZTQgXHVkMDZjXHViMmU0XHViYTc0LCBcdWI0NThcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzExY1x1Yjg1YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODcwXHVhYzAxXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzIxOFx1YmNmNFx1YjJlNCBcdWQwNmNcdWIyZTRcdWJhNzQsIFx1YjQ1OFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjMTFjXHViODVjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM4NzBcdWFjMDFcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjEyNCBcdWJjODhcdWM5ZjggXHVjMjE4XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNFx1YmE3NCwgXHViNDU4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWMxMWNcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIxMjQgXHViYzg4XHVjOWY4IFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWMyMThcdWFjMDAgXHViMmU0XHVjMTJmIFx1YmM4OFx1YzlmOCBcdWMyMThcdWJjZjRcdWIyZTQgXHVkMDZjXHViMmU0XHViYTc0LCBcdWI0NThcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzExY1x1Yjg1YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCBcdWMyMWNcdWMxMWNcdWFjMDAgMSwgMiwgMywgNCwgNSBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0IDEgXHViMmU4XHVhY2M0XHViODVjIFx1YjJlNFx1YzJkYyBcdWFjMDRcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjYzk4XHVjNzRjIFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzA0XHVjZTU4XHViOTdjIFx1YmMxNFx1YWZjMCBcdWI1NGMgXHViOWM4XHViMmU0IFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzg3MFx1YWMwMVx1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMmJcdWM3OTBcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCA1XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3M2NcdWJhNzAsIFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Y2M5OFx1Yzc0YyBcdWMyMWNcdWMxMWNcdWIyOTQgMSwgMiwgMywgNCwgNVx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViNDUwIFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHViYzE0XHViMDE0XHViNTRjIFx1YjljOFx1YjJlNCBcdWM4NzBcdWFjMDFcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTQ3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTUpFSFVSSUMiLCJkZXNjcmlwdGlvbiI6IjxwPkdvcmFuIGhhcyBmaXZlIHdvb2RlbiBwaWVjZXMgYXJyYW5nZWQgaW4gYSBzZXF1ZW5jZS4gVGhlcmUgaXMgYSBudW1iZXIgYmV0d2VlbiAxIGFuZCA1IGluc2NyaWJlZCBvbiBldmVyeSBwaWVjZSwgc28gdGhhdCBldmVyeSBudW1iZXIgYXBwZWFycyBvbiBleGFjdGx5IG9uZSBvZiB0aGUgZml2ZSBwaWVjZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdvcmFuIHdhbnRzIHRvIG9yZGVyIHRoZSBwaWVjZXMgdG8gZm9ybSB0aGUgc2VxdWVuY2UgMSwgMiwgMywgNCwgNSBhbmQgZG9lcyBpdCBsaWtlIHRoaXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+SWYgdGhlIG51bWJlciBvbiB0aGUgZmlyc3QgcGllY2UgaXMgZ3JlYXRlciB0aGFuIHRoZSBudW1iZXIgb24gdGhlIHNlY29uZCBwaWVjZSwgc3dhcCB0aGVtLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JZiB0aGUgbnVtYmVyIG9uIHRoZSBzZWNvbmQgcGllY2UgaXMgZ3JlYXRlciB0aGFuIHRoZSBudW1iZXIgb24gdGhlIHRoaXJkIHBpZWNlLCBzd2FwIHRoZW0uJm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIHRoZSBudW1iZXIgb24gdGhlIHRoaXJkIHBpZWNlIGlzIGdyZWF0ZXIgdGhhbiB0aGUgbnVtYmVyIG9uIHRoZSBmb3VydGggcGllY2UsIHN3YXAgdGhlbS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgdGhlIG51bWJlciBvbiB0aGUgZm91cnRoIHBpZWNlIGlzIGdyZWF0ZXIgdGhhbiB0aGUgbnVtYmVyIG9uIHRoZSBmaWZ0aCBwaWVjZSwgc3dhcCB0aGVtLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JZiB0aGUgcGllY2VzIGRvbiYjMzk7dCBmb3JtIHRoZSBzZXF1ZW5jZSAxLCAyLCAzLCA0LCA1LCBnbyB0byBzdGVwIDEuJm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBpbml0aWFsIG9yZGVyaW5nIG9mIHRoZSBwaWVjZXMsIG91dHB1dHMgdGhlIG9yZGVyaW5nIGFmdGVyIGVhY2ggc3dhcC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGZpdmUgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMsIHRoZSBvcmRlcmluZyBvZiB0aGUgcGllY2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbnVtYmVycyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgNSAoaW5jbHVzaXZlKSBhbmQgdGhlcmUgd2lsbCBiZSBubyBkdXBsaWNhdGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaW5pdGlhbCBvcmRlcmluZyB3aWxsIG5vdCBiZSAxLCAyLCAzLCA0LCA1LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkFmdGVyIGFueSB0d28gcGllY2VzIGFyZSBzd2FwcGVkLCBvdXRwdXQgdGhlIG9yZGVyaW5nIG9mIHRoZSBwaWVjZXMsIG9uIGEgc2luZ2xlIGxpbmUgc2VwYXJhdGVkIGJ5IHNwYWNlcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=