CF1332D.Walk on Matrix

Bob is playing a game named "Walk on Matrix".

In this game, player is given an $n \times m$ matrix $A=(a_{i,j})$, i.e. the element in the $i$-th row in the $j$-th column is $a_{i,j}$. Initially, player is located at position $(1,1)$ with score $a_{1,1}$.

To reach the goal, position $(n,m)$, player can move right or down, i.e. move from $(x,y)$ to $(x,y+1)$ or $(x+1,y)$, as long as player is still on the matrix.

However, each move changes player's score to the bitwise AND of the current score and the value at the position he moves to.

Bob can't wait to find out the maximum score he can get using the tool he recently learnt — dynamic programming. Here is his algorithm for this problem.

However, he suddenly realize that the algorithm above fails to output the maximum score for some matrix $A$. Thus, for any given non-negative integer $k$, he wants to find out an $n \times m$ matrix $A=(a_{i,j})$ such that

• $1 \le n,m \le 500$ (as Bob hates large matrix);
• $0 \le a_{i,j} \le 3 \cdot 10^5$ for all $1 \le i\le n,1 \le j\le m$ (as Bob hates large numbers);
• the difference between the maximum score he can get and the output of his algorithm is exactly $k$.

It can be shown that for any given integer $k$ such that $0 \le k \le 10^5$, there exists a matrix satisfying the above constraints.

Please help him with it!

鲍勃正在玩一个名为“矩阵行走”的游戏。

在这个游戏中，玩家会得到一个 $n \times m$ 的矩阵 $A=(a_{i,j})$，即第 $i$ 行第 $j$ 列的元素为 $a_{i,j}$。初始时，玩家位于位置 $(1,1)$，得分为 $a_{1,1}$。

为了到达目标位置 $(n,m)$，玩家每次只能向右或向下移动，即从 $(x,y)$ 移动到 $(x,y+1)$ 或 $(x+1,y)$，前提是移动后仍在矩阵范围内。

然而，每次移动都会将玩家当前得分更新为：当前得分与所移入位置处的矩阵元素值的按位与（bitwise AND）。

鲍勃迫不及待地想用自己最近学过的工具——动态规划——来求出他所能获得的最大得分。以下是他的算法：

然而，他突然意识到上述算法对某些矩阵 $A$ 并不能输出正确的最大得分。因此，对于任意给定的非负整数 $k$，他希望构造一个满足以下条件的 $n \times m$ 矩阵 $A=(a_{i,j})$：

• $1 \le n,m \le 500$（因为鲍勃讨厌过大的矩阵）；
• 对所有 $1 \le i\le n,\,1 \le j\le m$，均有 $0 \le a_{i,j} \le 3 \cdot 10^5$（因为鲍勃讨厌过大的数）；
• 玩家实际能获得的最大得分与他上述算法输出结果之间的差值恰好为 $k$。

可以证明：对任意满足 $0 \le k \le 10^5$ 的整数 $k$，均存在满足上述约束的矩阵。

请帮助他完成这一任务！

The only line of the input contains one single integer $k$ ($0 \le k \le 10^5$).

输入仅包含一行，其中有一个整数 $k$（$0 \le k \le 10^5$）。

Output two integers $n$, $m$ ($1 \le n,m \le 500$) in the first line, representing the size of the matrix.

Then output $n$ lines with $m$ integers in each line, $a_{i,j}$ in the $(i+1)$-th row, $j$-th column.

第一行输出两个整数 $n$、$m$（$1 \le n,m \le 500$），表示矩阵的大小。

随后输出 $n$ 行，每行包含 $m$ 个整数，其中第 $(i+1)$ 行第 $j$ 列的元素为 $a_{i,j}$。

In the first example, the maximum score Bob can achieve is $300000$, while the output of his algorithm is $300000$.

In the second example, the maximum score Bob can achieve is $7\&3\&3\&3\&7\&3=3$, while the output of his algorithm is $2$.

在第一个例子中，Bob 能够获得的最高分数为 $300000$，而他所用算法的输出结果也为 $300000$。

在第二个例子中，Bob 能够获得的最高分数为 $7\&3\&3\&3\&7\&3=3$，而他所用算法的输出结果为 $2$。