Given a one-indexed array ~a~ of ~N~ integers, you can perform the following operation an infinite number of times:

• Choose an index ~i~ ~(1 \le i \le N-3)~ and swap ~a_i~ and ~a_{i+3}~.

Find the lexicographically smallest array after performing this operation any number of times.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~, the number of elements.

The second line will contain ~N~ integers, ~a_i~ ~(1 \le a_i \le 10^9)~, the elements of the array.

Output Specification

Output the lexicographically smallest array after performing the operation described above any number of times.

Sample Input

5
2 4 7 1 3

Sample Output

1 3 7 2 4