塔防游戏是消磨时间的好游戏。在这类游戏中，玩家需要在某些候选位置建造塔楼，以保护基地免受怪物攻击。其难点在于，建造塔楼的预算通常非常紧张，玩家往往需要在棘手的位置建造塔楼，以便在节省资源的同时仍能消灭所有怪物。

Arduboy 简单 1 位塔防游戏截图。公有领域。

让我们考虑该游戏的一个简化版本：地图可以看作是一棵至少有两个节点的有根树，其中根节点是玩家需要保护的基地。怪物会出现在每个叶子节点。当怪物出现时，它会沿着树的边向上移动到根节点以攻击基地。玩家可以在树的任何节点（包括根节点）建造塔楼。在这个简化游戏中，我们假设塔楼威力足够强大，任何进入建有塔楼的节点的怪物都会被消灭。自然地，在不同节点建造塔楼的资源成本不同，你需要以最低的成本保护基地（消灭所有怪物）。

给定地图，计算最优解很容易。然而，这一次你不是在玩游戏，而是在为大学课程开发一个塔防游戏项目。你需要设计一张地图（你需要给出树的结构以及在每个节点建造塔楼的成本），使得保护基地的最优解恰好有 $K$ 个。当且仅当一种方案在所有能确保消灭所有怪物的建造方案中成本最低时，它才是最优解。如果两个方案中至少有一个节点在一种方案中建有塔楼，而在另一种方案中没有，则认为这两个方案不同。

输入格式

输入仅包含一组数据。 输入只有一行，包含一个整数 $K$ ($1 \le K \le 10^9$)，即你的地图需要拥有的最优解数量。

输出格式

设你构造的树的节点数为 $N$，并将节点标记为 $1$ 到 $N$，其中节点 $1$ 为根节点。设 $c_i$ ($1 \le i \le N$) 为在节点 $i$ 建造塔楼的成本。 输出应包含 3 行。第一行包含一个整数 $N$。第二行包含 $N-1$ 个空格分隔的整数，其中第 $i$ 个 ($1 \le i < N$) 整数表示节点 $i+1$ 的父节点编号。第三行包含 $N$ 个空格分隔的整数，其中第 $i$ 个 ($1 \le i \le N$) 整数表示 $c_i$。

你的解必须满足 $2 \le N \le 10^5$ 且对于所有 $1 \le i \le N$ 满足 $1 \le c_i \le 10^9$。保证至少存在一个解。如果存在多个有效解，则任何一个都将被接受。

样例

输入 1

2

输出 1

2
1
1 1

说明

样例输出只是样例数据的一种可能解。还存在其他有效解。