Walk on Matrix

题意翻译

有这么一个问题: > 有一个 $n \times m$ 的矩阵 $a_{n, m}$,矩阵的每个位置都有一个数,要求寻找一个每次只能向右或向下走的从 $(1, 1)$ 至 $(n, m)$ 的路径,最大化路径上的数的按位与之和。 > > $1 \leq n, m \leq 500$,$0 \leq a_{i, j} \leq 3 \times 10^5$。 现在给出解决该问题的一个**错误** dp 算法(见题面图片),请构造一组数据,hack 掉这个算法,使得正确答案比错误的输出**恰好**大 $k$。 $0 \leq k \leq 10^5$。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#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. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1332D/f77be4abbc0e4a1768015d201a26d68f6c552a32.png)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!

输入输出格式

输入格式


The only line of the input contains one single integer $ 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.

输入输出样例

输入样例 #1

0

输出样例 #1

1 1
300000

输入样例 #2

1

输出样例 #2

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

说明

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 $ .