题目描述

给定一个整数 $N$ 。

请按照字典序升序打印所有满足 $x+y+z\leq\ N$ 的非负整数三元组 $(x,y,z)$。

一个非负整数三元组$(x,y,z)$ 被称为字典序小于$(x',y',z')$ ，

当且仅当以下条件之一成立：

1. $x \lt x′$；或者

2. $x=x′$ 且 $y \lt y$；或者

3. $x = x ′$ 且 $y=y′$ 且 $z \lt z′$。

这个定义描述了如何比较两个三元组的顺序。它首先比较第一个元素，如果相等则比较第二个元素，如果第二个元素也相等则比较第三个元素。

这种比较方法类似于字典中单词的排序方式，因此被称为"字典序"。

输入格式

输入 $N$。

输出格式

按字典序升序打印所有满足 $x+y+z \le N$ 的非负整数三元组 $(x,y,z)$，

每个三元组占一行，$x$、$y$、$z$ 用空格分隔。

样例

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

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$ 是整数