题目描述

给定一个整数 $N$。

请按字典序从小到大输出所有满足 $x+y+z\leq N$ 的非负整数三元组 $(x, y, z)$。

什么是非负整数三元组的字典序？非负整数三元组 $(x, y, z)$ 比 $(x', y', z')$ 的字典序小，指的是满足以下任一条件：

• $x < x'$
• $x = x'$ 且 $y < y'$
• $x = x'$ 且 $y = y'$ 且 $z < z'$

输入格式

输入以如下格式从标准输入读入。

$N$

输出格式

请按字典序从小到大输出所有满足 $x+y+z\leq N$ 的非负整数三元组 $(x, y, z)$，每行输出一组 $x\ y\ z$，用空格分隔。

样例 1

输入

3

输出

0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 3 0
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 2 0
2 0 0
2 0 1
2 1 0
3 0 0

样例 2

输入

4

输出

0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 1 0
0 1 1
0 1 2
0 1 3
0 2 0
0 2 1
0 2 2
0 3 0
0 3 1
0 4 0
1 0 0
1 0 1
1 0 2
1 0 3
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 3 0
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 2 0
3 0 0
3 0 1
3 1 0
4 0 0

说明/提示

限制

• $0 \leq N \leq 21$
• $N$ 是整数。

由 ChatGPT 4.1 翻译