CF1332D Walk on Matrix

Bob 正在玩一个名为「Walk on Matrix」的游戏。 在这个游戏中，玩家会得到一个 $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）。 Bob 迫不及待地想用他最近学到的工具——动态规划，来求出他能获得的最大得分。以下是他为这个问题设计的算法。  然而，他突然发现上述算法在某些矩阵 $A$ 上无法输出最大得分。因此，对于任意给定的非负整数 $k$，他想构造一个 $n \times m$ 的矩阵 $A=(a_{i,j})$，使得 - $1 \le n,m \le 500$（因为 Bob 不喜欢大矩阵）； - $0 \le a_{i,j} \le 3 \cdot 10^5$，对于所有 $1 \le i \le n, 1 \le j \le m$（因为 Bob 不喜欢大数）； - 他能获得的最大得分与他的算法输出的得分之差恰好为 $k$。 可以证明，对于任意 $0 \le k \le 10^5$ 的整数，都存在满足上述条件的矩阵。 请你帮助他完成这个任务！

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

输出第一行为两个整数 $n$ 和 $m$（$1 \le n,m \le 500$），表示矩阵的大小。 接下来输出 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列为 $a_{i,j}$。

在第一个样例中，Bob 能获得的最大得分是 $300000$，而他的算法输出也是 $300000$。 在第二个样例中，Bob 能获得的最大得分是 $7\&3\&3\&3\&7\&3=3$，而他的算法输出为 $2$。 由 ChatGPT 4.1 翻译