우리는 모든 $0 \le k \le n$에 대하여 $\binom{n}{k} = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+2) \cdot (n-k+1)}{1 \cdot 2 \cdot \dots \cdot (k-1) \cdot k}$가 정수라는 것을 알고 있습니다. 하지만 분자와 분모의 인수들 사이의 매칭을 제공함으로써 이를 증명할 수 있다면 좋지 않을까요?

각 부분에 $k$개의 정점을 가진 이분 그래프를 구성해 봅시다. 왼쪽 부분의 $i$번째 정점은 분자의 인수 $(n + 1 - i)$에 대응하고, 오른쪽 부분의 $j$번째 정점은 분모의 인수 $j$에 대응합니다. $j$가 $(n + 1 - i)$를 나눌 때에만 $i$와 $j$ 사이에 간선이 존재합니다. 이 이분 그래프에 완전 매칭이 존재한다면, 수 $k$는 $n$에 대해 증명 가능(provable)하다고 합니다.

$n$이 주어질 때, $0 \le k \le n$을 만족하는 각 $k$에 대해 $k$가 증명 가능한지 확인하십시오.

입력

한 줄에 정수 $n$ ($0 \le n \le 10^{18}$)이 주어집니다.

출력

길이가 $(n + 1)$인 '0'과 '1'로 이루어진 문자열을 출력하십시오. $(k + 1)$번째 문자는 $k$가 $n$에 대해 증명 가능할 때에만 '1'이어야 합니다.

이대로 출력하면 Output Limit Exceeded가 발생할 것 같다고요? 음... 좋습니다. 문자열을 압축해 봅시다.

$s_0 = \text{"0"}$이고 $s_1 = \text{"1"}$이라고 합시다. $s_2, s_3, \dots, s_t$를 정의할 수 있습니다. 문자열 $s_i$는 이전에 정의된 여러 문자열을 이어 붙인 것이어야 합니다. 형식적으로, 모든 $i(2 \le i \le t)$에 대하여 $s_i = s_{j_1} + s_{j_2} + \dots + s_{j_{k_i}}$이며, 여기서 $1 \le k_i$이고, 모든 $r(1 \le r \le k_i)$에 대하여 $j_r < i$입니다. 문자열 $s_t$가 문제의 정답이어야 합니다.

첫 번째 줄에 정수 $t$ ($2 \le t \le 500$)를 출력하십시오.

다음 $t - 1$개의 줄에 $s_i$에 대한 설명을 출력하십시오. 각 설명은 $k_i \ j_1 \ j_2 \ \dots \ j_{k_i}$의 형식이어야 하며, $1 \le k_i$이고 $0 \le j_r < i$를 만족해야 합니다.

모든 설명의 총 길이는 $10\,000$을 초과해서는 안 됩니다: $\sum_{i=2}^{t} k_i \le 10\,000$.

모든 유효한 테스트 케이스에 대해 위 제한 사항을 모두 준수하면서 정답 문자열을 구성하는 방법이 존재함을 보일 수 있습니다. 가능한 방법이 여러 가지라면, 그중 아무거나 출력하십시오. $t$나 모든 설명의 총 길이를 최소화할 필요는 없습니다.

예제

입력 1

1

출력 1

2
2 1 1

입력 2

0

출력 2

2
1 1

입력 3

7

출력 3

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

참고

세 번째 예제에서: $s_2 = s_1 + s_1 = \text{"1"} + \text{"1"} = \text{"11"}$, $s_3 = s_1 + s_2 + s_0 + s_0 = \text{"1"} + \text{"11"} + \text{"0"} + \text{"0"} = \text{"11100"}$, $s_4 = s_3 + s_1 + s_2 = \text{"11100"} + \text{"1"} + \text{"11"} = \text{"11100111"}$입니다.