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](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. 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/A

N/A

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