题目描述

问题背景

$01$ 背包问题是算法竞赛中经典的组合优化问题，小 $W$ 学会了一种求解该问题的贪心算法。现需要构造一组数据，证明该贪心算法在指定范围内无法得到最优解，并满足一系列优化条件。

01背包问题定义

给定 $n$ 个物品，物品的重量为正整数 $w_{1}, w_{2}, ..., w_{n}$，价值为正整数 $v_{1}, v_{2}, ..., v_{n}$，背包容量为 $W$。要求选择物品（$x_{i} \in \{0,1\}$，$1$ 表示选择第 $i$ 个物品，$0$ 表示不选择），满足：

并最大化价值总和：

小W的贪心算法

1. 将 $n$ 个物品按 $\frac{v_{i}}{w_{i}}$（价值重量比）从大到小排序；若比值相同，则按重量 $w_{i}$ 从大到小排序。
2. 初始化变量 $V_{0}=0$（注：原文此处变量名疑似笔误，结合算法逻辑应为累计重量变量），从 $1$ 到 $n$ 枚举物品：若当前物品重量与 $V_{0}$ 之和不超过 $W$，则选择该物品（$x_{i}=1$），并更新 $V_{0} = V_{0} + w_{i}$；否则不选择（$x_{i}=0$）。
3. 枚举结束后，得到选择结果及对应的价值 $V$。

构造要求

需构造一组 $w_{1},...,w_{n}$ 和 $v_{1},...,v_{n}$，满足以下条件（优先级从高到低）：

1. 对于任意 $2 \leq W \leq W_{lim}$（$W_{lim}$ 为给定常数），小 $W$ 的贪心算法均无法得到最优价值 $V$。
2. 在满足条件 $1$ 的前提下，物品数量 $n$ 尽量小。
3. 在满足条件 $1$、$2$ 的前提下，物品最大重量 $max(w_{1},...,w_{n})$ 尽量小。
4. 在满足条件 $1$、$2$、$3$ 的前提下，物品最大价值 $max(v_{1},...,v_{n})$ 尽量小。

情况可能有多种，要求输出按照w~i~升序的结果

输入格式

一行包含一个整数 $W_{lim}$（$2 \leq W_{lim} \leq 5 \times 10^{3}$），表示背包容量 $W$ 的上界。

输出格式

• 第一行：整数 $n$（$1 \leq n \leq 10^{4}$），表示物品数量。
• 第二行：$n$ 个整数 $w_{1},...,w_{n}$（$1 \leq w_{i} \leq W_{lim}$），表示物品重量。
• 第三行：$n$ 个整数 $v_{1},...,v_{n}$（$1 \leq v_{i} \leq 10^{9}$），表示物品价值。

样例

样例输入 1

2

样例输出 1

2
1 2
2 3

提示

说明：可以证明，在给定数据范围约束下，总能找到满足要求的解，输出按照w~i~升序的结果。