题目描述

现有 $k$ 个人，你可以举办任意多次由三个人参加的聚会，现要求任意两个人都同时参加聚会恰好一次，试构造一组聚会方案。

可以说明，在给定的范围内一定有解。

输入格式

一行一个正整数 $k$ ($1 \le k \le 3000$)，保证 $k \bmod 6$ 为 $1$ 或 $3$。

输出格式

输出共 $\frac{k(k-1)}{6}$ 行，每行三个整数 $a,b,c$（你需要保证 $a,b,c$ 互不相等）表示一次聚会参加的三个人。

样例

输入

7

输出

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

数据范围与提示

对于 $100\%$ 的数据，$1 \le k \le 3000$，保证 $k \bmod 6$ 为 $1$ 或 $3$。

本题采用子任务捆绑测试。

• $\text{subtask1}$ ($4$ pts)：保证 $k=2^t-1$，$t$ 为正整数。
• $\text{subtask2}$ ($6$ pts)：保证 $k=3^t$，$t$ 为非负整数。
• $\text{subtask3}$ ($15$ pts)：保证 $k \equiv 1 \pmod {24}$。
• $\text{subtask4}$ ($7$ pts)：保证 $k \equiv 7 \pmod {24}$。
• $\text{subtask5}$ ($15$ pts)：保证 $k \equiv 13 \pmod {24}$。
• $\text{subtask6}$ ($7$ pts)：保证 $k \equiv 19 \pmod {24}$。
• $\text{subtask7}$ ($15$ pts)：保证 $k \equiv 3 \pmod {24}$。
• $\text{subtask8}$ ($7$ pts)：保证 $k \equiv 21 \pmod {24}$。
• $\text{subtask9}$ ($10$ pts)：保证 $k \equiv 9 \pmod {24}$。
• $\text{subtask10}$ ($7$ pts)：保证 $k \equiv 15 \pmod {24}$。
• $\text{subtask11}$ ($7$ pts)：无特殊性质。