Distinct Adjacent Sums

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka is wondering if there exists an array of \(n\) elements such that all elements are distinct integers from 1 to \(n\) inclusive, and the remainder values modulo \(n\) of the sums of adjacent elements are all distinct.

More formally, the girl wants to know if there exists a permutation \(a\) of the numbers \(1, 2, \dots, n\) such that all values of \((a_i+a_{i+1})\%n\) are distinct, where \(\%\) is the modulo operation.

Zenyk wants to help Marichka find such a permutation.

Input

The single line contains a single integer \(n\).

Output

Output \(n\) integers — the desired permutation. Such a permutation is guaranteed to exist.

Constraints

\(2 \le n \le 2 \cdot 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4	2 4 3 1

Notes

In the example:

• The remainder of \((2+4) \% 4\) is 2,

• The remainder of \((4+3) \% 4\) is 3,

• The remainder of \((3+1) \% 4\) is 0.

All these values are distinct.