D. 电梯
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

宁宁现在在建设大楼！

在宁宁的规划中，大楼有 $$$n$$$ 层，从下到上依次为第 $$$1, 2, \cdots, n$$$ 层，她还要建设 $$$m$$$ 个电梯，每个电梯一定会停在第 $$$1$$$ 层和第 $$$n$$$ 层，她可以选择让这些电梯停在中间某些层（也可以不停）。她希望建设的这 $$$m$$$ 个电梯满足：对于任意不同的两层 $$$x, y$$$，存在一个电梯使 $$$x, y$$$ 可以直达（中间不经过任何可以停的层）。为了降低建造成本，她希望电梯数 $$$m$$$ 尽量小。

宁宁她不太聪明，于是她转过来求助你，希望你能告诉她 $$$m$$$ 的最小值并给出构造。

你不需要最小化停的总层数。但还是为了节约资源，你需要使得停的总层数不超过 $$$2 \times 10^6$$$。

Input

一行一个正整数 $$$n$$$ $$$(2 \le n \le 1000)$$$。

Output

第一行一个正整数 $$$m$$$，表示最少需要的电梯数。

接下来 $$$m$$$ 行，每行表示一个电梯的停层状况。具体来说，对于第 $$$i$$$ 行，你需要输出一个序列 $$$a_{i, 1}, a_{i, 2}, \cdots, a_{i, k_i}$$$，使得 $$$1 = a_{i, 1} \lt a_{i, 2} \lt \cdots \lt a_{i, k_i} = n$$$，且 $$$\sum\limits_{i=1}^m k_i \le 2 \times 10^6$$$。表示第 $$$i$$$ 个电梯会停在 $$$a_{i, 1}, a_{i, 2}, \cdots, a_{i, k_i}$$$ 层。

输出量较大，建议采用较快的输出方式。

Example
Input
4
Output
4
1 3 4
1 4
1 2 3 4
1 2 4
Note

可以证明 $$$m$$$ 的最小值为 $$$4$$$。

第 $$$1, 2$$$ 层可以通过电梯 $$$3, 4$$$ 直达，第 $$$1, 3$$$ 层可以通过电梯 $$$1$$$ 直达，第 $$$1, 4$$$ 层可以通过电梯 $$$2$$$ 直达，第 $$$2, 3$$$ 层可以通过电梯 $$$3$$$ 直达，第 $$$2, 4$$$ 层可以通过电梯 $$$4$$$ 直达，第 $$$3, 4$$$ 层可以通过电梯 $$$1, 3$$$ 直达。