The 0/1 knapsack problem is a classic combinatorial optimization problem in algorithmic competitions. Little w has learned a greedy algorithm to solve this problem. The definition of the 0/1 knapsack problem and little w's greedy algorithm are as follows.

0/1 Knapsack Problem

Given $n$ items, where the weight of each item is a positive integer $w_1, w_2, \dots, w_n$ and the value of each item is a positive integer $v_1, v_2, \dots, v_n$, and given a knapsack capacity $W$. We require $x_1, x_2, \dots, x_n$ ($\forall 1 \le i \le n, x_i \in \{0, 1\}$) such that:

$$\sum_{i=1}^{n} w_i x_i \le W$$

And maximize:

$$V = \sum_{i=1}^{n} v_i x_i$$

Greedy Algorithm

1. Sort the $n$ items in descending order of their $\frac{v_i}{w_i}$ values. If $\frac{v_i}{w_i}$ is the same, sort them in descending order of $w_i$.
2. Let $V_0$ be a variable initialized to 0. Iterate $i$ from 1 to $n$. If $V_0 + w_i \le W$, set $x_i \leftarrow 1$ and $V_0 \leftarrow V_0 + w_i$; otherwise, set $x_i \leftarrow 0$.
3. After the iteration, the resulting $x_1, x_2, \dots, x_n$ and $V$ are obtained.

You certainly know that this algorithm is incorrect, but little w does not believe it. Even if you provide some counterexamples, little w still believes that this algorithm can obtain the optimal $V$ for many different $W$. Therefore, you now wish to construct a set of $w_1, w_2, \dots, w_n$ and $v_1, v_2, \dots, v_n$ such that:

1. For any $2 \le W \le W_{lim}$ ($W_{lim}$ is a given constant), little w's algorithm fails to obtain the optimal $V$.
2. Subject to condition 1, $n$ is as small as possible.
3. Subject to conditions 1 and 2, $\max(w_1, w_2, \dots, w_n)$ is as small as possible.
4. Subject to conditions 1, 2, and 3, $\max(v_1, v_2, \dots, v_n)$ is as small as possible.

Now you need to construct a set of 0/1 knapsack items satisfying the above conditions to convince little w. Can you do it? If there are multiple construction methods, you may output any one of them.

Input

The input consists of a single line containing an integer $W_{lim}$ ($2 \le W_{lim} \le 5 \times 10^3$), representing the upper bound of $W$.

Output

The first line contains an integer $n$ ($1 \le n \le 10^4$), representing the number of items in the constructed 0/1 knapsack. The second line outputs $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le W_{lim}$), representing the weights of the items. The third line outputs $n$ integers $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 10^9$), representing the values of the items.

It can be proven that under the given problem and input conditions, a solution satisfying the above data ranges can always be found.

Examples

Input 1

2

Output 1

2
1 2
2 3