← 返回题目列表

Codeforces · 1332/D

D. 在矩阵上行走

中文机器翻译题面 查看原题

Bob 正在玩一款名为“Walk on Matrix”的游戏。

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

为了到达目标,位置$$$(n,m)$$$,玩家可以向右或向下移动,即从$$$(x,y)$$$移动到$$$(x,y+1)$$$或$$$(x+1,y)$$$,只要玩家仍在矩阵上。

然而,每次移动都会将玩家的得分更改为当前得分与他移动到的位置处的值的按位与。

Bob 迫不及待地想知道使用他最近学习的工具——动态规划,他能得到的最高分。这是他解决这个问题的算法。

然而,他突然意识到上面的算法无法输出某个矩阵$$$A$$$的最大分数。因此,对于任何给定的非负整数 $$$k$$$,他想找出一个 $$$n \times m$$$ 矩阵 $$$A=(a_{i,j})$$$ 使得

- $$$1 \le n,m \le 500$$$ (因为鲍勃讨厌大矩阵);
- $$$0 \le a_{i,j} \le 3 \cdot 10^5$$$ 对于所有 $$$1 \le i\le n,1 \le j\le m$$$ (因为 Bob 讨厌大数字);
- 他可以获得的最大分数与算法输出之间的差异恰好是 $$$k$$$。

可以证明,对于任何给定的整数$$$k$$$,使得$$$0 \le k \le 10^5$$$,存在满足上述约束的矩阵。

请帮助他!

输入

输入的唯一一行包含一个整数 $$$k$$$ ($$$0 \le k \le 10^5$$$)。

输出

第一行输出两个整数$$$n$$$, $$$m$$$ ($$$1 \le n,m \le 500$$$),代表矩阵的大小。

然后输出$$$n$$$行,每行有$$$m$$$个整数,$$$a_{i,j}$$$在$$$(i+1)$$$行,$$$j$$$第列。

示例

输入 #1

0

输出 #1

1 1
300000

输入 #2

1

输出 #2

3 4
7 3 3 1
4 8 3 6
7 7 7 3

注意

在第一个示例中,Bob 可以获得的最大分数是 $$$300000$$$,而他的算法的输出是 $$$300000$$$。

在第二个示例中,Bob 可以获得的最大分数是 $$$7\&3\&3\&3\&7\&3=3$$$,而他的算法的输出是 $$$2$$$。