There are $k$ people. You can host any number of parties, each attended by three people. The requirement is that every pair of people must attend a party together exactly once. Construct a set of parties that satisfies this condition.

It can be shown that a solution always exists within the given range.

Input

A single positive integer $k$ ($1 \le k \le 3000$), where $k \bmod 6$ is guaranteed to be $1$ or $3$.

Output

Output $\frac{k(k-1)}{6}$ lines, each containing three integers $a, b, c$ (you must ensure $a, b, c$ are distinct), representing the three people attending a party.

Examples

Input 1

7

Output 1

1 2 3
1 4 5
1 6 7
2 4 6
2 5 7
3 4 7
3 5 6

Constraints

For $100\%$ of the data, $1 \le k \le 3000$, and $k \bmod 6$ is guaranteed to be $1$ or $3$.

This problem uses subtask bundling.

$\text{subtask1}(4 \text{ pts})$: $k = 2^t - 1$, where $t$ is a positive integer.

$\text{subtask2}(6 \text{ pts})$: $k = 3^t$, where $t$ is a non-negative integer.

$\text{subtask3}(15 \text{ pts})$: $k \equiv 1 \pmod {24}$.

$\text{subtask4}(7 \text{ pts})$: $k \equiv 7 \pmod {24}$.

$\text{subtask5}(15 \text{ pts})$: $k \equiv 13 \pmod {24}$.

$\text{subtask6}(7 \text{ pts})$: $k \equiv 19 \pmod {24}$.

$\text{subtask7}(15 \text{ pts})$: $k \equiv 3 \pmod {24}$.

$\text{subtask8}(7 \text{ pts})$: $k \equiv 21 \pmod {24}$.

$\text{subtask9}(10 \text{ pts})$: $k \equiv 9 \pmod {24}$.

$\text{subtask10}(7 \text{ pts})$: $k \equiv 15 \pmod {24}$.

$\text{subtask11}(7 \text{ pts})$: No special properties.