Mr. Plow King

difficulty: EASY

source: open kattis

raw_problem:
In the kingdom of Winterfield, there are several cities and
    each pair of cities is connected by exactly one old dirt road.
    The king of Winterfield has decided that he will upgrade some
    of those roads. The set of roads that he upgrades must be such
    that it is possible to get from any city in the kingdom to any
    other city via some sequence of upgraded roads.

Because there is so much snow in Winterfield, the king has
    also decided to plow some of those upgraded roads. The local
    plow company, Mr. Plow, and the king
    have agreed on the following: the king labels each of the
    upgraded roads $1, 2, \dots ,
    m$ (the label of each road is the number of gold pieces
    it costs to plow that road) and each road must receive a
    distinct label. Mr. Plow will plow a set of upgraded roads so
    that it is possible to get from any city to any other city via
    some sequence of plowed roads. Mr. Plow will select the
    cheapest possible set of roads that satisfies the above
    condition.

For example, if the kingdom has six cities and the king
    decides to upgrade and label the 8 bolded dirt roads as
    follows, then Mr. Plow will then plow the roads with labels 1,
    2, 3, 4 and 6 (costing a total of 16 gold pieces).

The king has decided on the number of roads to upgrade, but
    he is not sure how to label them, so he has turned to Barney
    (the kingdom’s mathematician) to help decide. However, the king
    is unaware that Barney is actually invested in Mr. Plow, so
    Barney will choose the set of roads to upgrade and how to label
    them so that the total cost is as large as possible. What is
    the maximum cost of plowing the roads?

Input

The input consists of a single line containing two integers
    $n$ ($2 \leq n \leq 1\, 000\, 000$), which
    is the number of cities, and $m$ ($n-1 \leq m \leq \frac{n(n-1)}{2}$),
    which is the number of roads to be upgraded.

Output

Display the maximum possible cost of plowing the roads
    following the rules above.

Sample Input 1
Sample Output 1

4 3

6

Sample Input 2
Sample Output 2

6 8

22

Sample Input 3
Sample Output 3

9 12

56

question:
In the kingdom of Winterfield, there are several cities and each pair of cities is connected by exactly one old dirt road. The king of Winterfield has decided that he will upgrade some of those roads. The set of roads that he upgrades must be such that it is possible to get from any city in the kingdom to any other city via some sequence of upgraded roads.
Because there is so much snow in Winterfield, the king has also decided to plow some of those upgraded roads. The local plow company,Mr. Plow, and the king have agreed on the following: the king labels each of the upgraded roads$1, 2, \dots , m$(the label of each road is the number of gold pieces it costs to plow that road) and each road must receive a distinct label. Mr. Plow will plow a set of upgraded roads so that it is possible to get from any city to any other city via some sequence of plowed roads. Mr. Plow will select the cheapest possible set of roads that satisfies the above condition.
For example, if the kingdom has six cities and the king decides to upgrade and label the 8 bolded dirt roads as follows, then Mr. Plow will then plow the roads with labels 1, 2, 3, 4 and 6 (costing a total of 16 gold pieces).
![image](1.png)The king has decided on the number of roads to upgrade, but he is not sure how to label them, so he has turned to Barney (the kingdom’s mathematician) to help decide. However, the king is unaware that Barney is actually invested in Mr. Plow, so Barney will choose the set of roads to upgrade and how to label them so that the total cost is as large as possible. What is the maximum cost of plowing the roads?

Input
The input consists of a single line containing two integers$n$($2 \leq n \leq 1\, 000\, 000$), which is the number of cities, and$m$($n-1 \leq m \leq \frac{n(n-1)}{2}$), which is the number of roads to be upgraded.

Output
Display the maximum possible cost of plowing the roads following the rules above.
Sample Input 1
4 3

Sample Output 1
6

Sample Input 2
6 8

Sample Output 2
22

Sample Input 3
9 12

Sample Output 3
56

data_split: test


D. Walk on Matrix

problem_index: D

time_limit: 2 seconds

memory_limit: 512 megabytes

solutions: ["k = int(input())\narr = [[0, k, 0], [0, 0, k]]\nlength = 0\nt = k\nwhile t > 0:\n\tt >>= 1\n\tlength += 1\narr[1][1] = (1 << length) + k\narr[1][0] = (1 << length) + ((1 << length) - 1 ^ k)\narr[0][0] = (1 << length + 1) - 1\nprint(2, 3)\nfor i in arr:\n\tprint(*i)\n", "n = int(input())\nprint(3, 4)\na = [[262143, 262143, 262143, 1], [262143, 262143, n, 131072], [262143, 131072, 262143, n]]\nfor i in a:\n\tprint(*i)\n", "import io\nimport os\nfrom collections import Counter, defaultdict, deque\n\ndef solve(K):\n\tif K == 0:\n\t\treturn '1 1\\n' + str(0)\n\n\tdef bob(a):\n\t\tn = len(a)\n\t\tm = len(a[0])\n\t\tdp = [[0 for j in range(m + 1)] for i in range(n + 1)]\n\t\tdp[0][1] = a[0][0]\n\t\tfor i in range(1, n + 1):\n\t\t\tfor j in range(1, m + 1):\n\t\t\t\tdp[i][j] = max(dp[i - 1][j] & a[i - 1][j - 1], dp[i][j - 1] & a[i - 1][j - 1])\n\t\tprint('dp', dp)\n\t\treturn dp[n][m]\n\tmaxBit = 1\n\twhile maxBit <= K:\n\t\tmaxBit *= 2\n\ta = [[maxBit + K, K, K, 0], [maxBit, 0, K, 0], [maxBit + K, maxBit + K, maxBit + K, K]]\n\tans = [str(len(a)) + ' ' + str(len(a[0]))]\n\tfor row in a:\n\t\tans.append(' '.join((str(cell) for cell in row)))\n\treturn '\\n'.join(ans)\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(K,) = [int(x) for x in input().split()]\nans = solve(K)\nprint(ans)\n", "import sys\ninput = sys.stdin.readline\nn = int(input())\nprint('2 3')\nprint((1 << 18) - 1, n, 0)\nprint(1 << 17, (1 << 18) - 1, n)\n", "n = int(input())\nd = 2\nwhile d < 10 ** 5:\n\td *= 2\nprint(2, 3)\nprint(n + d, d, d)\nprint(n, n + d, n)\n", "k = int(input())\ny = 1\nwhile y <= k:\n\ty <<= 1\nX = k + y\nm = [[X, y, y], [k, y, y], [k, X, k]]\nprint(3, 3)\nfor arr in m:\n\tprint(' '.join([str(x) for x in arr]))\n", "k = int(input())\nprint(3, 3)\nprint(2 ** 18 - 1, k, k)\nprint(2 ** 17, 2 ** 17, 2 ** 18 - 1)\nprint(0, 0, k)\n", "n = int(input())\nprint('2 3')\nx = 2 ** 17\nprint(x + n, x, 0)\nprint(n, x + n, n)\n", "k = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\n\texit(0)\nq = bin(100000)\nt = pow(2, len(q) - 1) - 1\nrem = bin(k)\nrem = rem[2:]\nrem = '0' * (len(bin(t)) - 2 - len(rem)) + rem\nalpha = 0\nfor i in range(len(rem)):\n\tif rem[i] == '0':\n\t\talpha += pow(2, len(rem) - i - 1)\nans = [t, k, 0]\ngns = [alpha, t, 0]\ntns = [0, k, k]\nprint(3, 3)\nprint(*ans)\nprint(*gns)\nprint(*tns)\n", "from collections import defaultdict as dd\nimport sys\ninput = sys.stdin.readline\n\ndef bro(k):\n\twhile k & k - 1 != 0:\n\t\tk = k & k - 1\n\treturn 2 * k\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\tb = bro(k)\n\tprint(3, 3)\n\tprint(k + b, b, b)\n\tprint(k + b, k, k + b)\n\tprint(b, k + b, k)\n", "import bisect\nimport heapq\nimport math\nimport random\nimport sys\nfrom collections import Counter, defaultdict, deque\nfrom decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal\nfrom functools import lru_cache, reduce\nfrom itertools import combinations, combinations_with_replacement, product, permutations\nfrom operator import add, mul, sub\nsys.setrecursionlimit(100000)\ninput = sys.stdin.readline\nINF = 2 ** 62 - 1\n\ndef read_int():\n\treturn int(input())\n\ndef read_int_n():\n\treturn list(map(int, input().split()))\n\ndef read_float():\n\treturn float(input())\n\ndef read_float_n():\n\treturn list(map(float, input().split()))\n\ndef read_str():\n\treturn input().strip()\n\ndef read_str_n():\n\treturn list(map(str, input().split()))\n\ndef error_print(*args):\n\tprint(*args, file=sys.stderr)\n\ndef mt(f):\n\timport time\n\n\tdef wrap(*args, **kwargs):\n\t\ts = time.time()\n\t\tret = f(*args, **kwargs)\n\t\te = time.time()\n\t\terror_print(e - s, 'sec')\n\t\treturn ret\n\treturn wrap\n\n@mt\ndef slv(K):\n\tN = 2\n\tM = 3\n\tA = (1 << K.bit_length()) + K\n\tB = 1 << K.bit_length()\n\tG = [[A, B, 0], [K, A, K]]\n\tprint(N, M)\n\tprint(*G[0])\n\tprint(*G[1])\n\ndef main():\n\tK = read_int()\n\tslv(K)\nmain()\n", "import sys\ninput = sys.stdin.readline\nk = int(input())\na = 1 << k.bit_length()\nprint(2, 3)\nprint(a | k, k, 0)\nprint(a, a | k, k)\n", "import sys\nfrom collections import Counter\n\ndef input():\n\treturn sys.stdin.readline().strip()\n\ndef list2d(a, b, c):\n\treturn [[c] * b for i in range(a)]\n\ndef list3d(a, b, c, d):\n\treturn [[[d] * c for j in range(b)] for i in range(a)]\n\ndef list4d(a, b, c, d, e):\n\treturn [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]\n\ndef ceil(x, y=1):\n\treturn int(-(-x // y))\n\ndef INT():\n\treturn int(input())\n\ndef MAP():\n\treturn map(int, input().split())\n\ndef LIST(N=None):\n\treturn list(MAP()) if N is None else [INT() for i in range(N)]\n\ndef Yes():\n\tprint('Yes')\n\ndef No():\n\tprint('No')\n\ndef YES():\n\tprint('YES')\n\ndef NO():\n\tprint('NO')\nINF = 10 ** 18\nMOD = 10 ** 9 + 7\nK = INT()\ngrid = list2d(3, 3, (1 << 18) - 1)\ngrid[0][2] = grid[2][0] = 1 << 17\ngrid[1][1] = K\ngrid[2][2] = (1 << 17) - 1\nprint(3, 3)\nfor i in range(3):\n\tprint(*grid[i])\n", "mod = 10 ** 9 + 7\nimport math\nfrom bisect import bisect_left as bl\nfrom collections import Counter\nfrom itertools import combinations\n\ndef ain():\n\treturn map(int, input().split())\n\ndef fain():\n\treturn map(float, input().split())\n\ndef mc2(s):\n\treturn s * (s - 1) // 2\nfor _ in range(1):\n\tk = int(input())\n\tx = math.log2(2 * 10 ** 5)\n\tv = 2 ** int(x)\n\tprint(3, 3)\n\tprint(v + k, v + k, v)\n\tprint(v + k, k, v)\n\tprint(v, v + k, k)\n", "n = int(input())\nprint('3 3')\nprint(262143, end=' ')\nprint(262143, end=' ')\nprint(n)\nprint('0 131072 262143')\nprint('0 0', end=' ')\nprint(n)\n", "k = int(input())\n\ndef high(a):\n\tans = 1\n\ta >>= 1\n\twhile a != 0:\n\t\ta >>= 1\n\t\tans *= 2\n\treturn ans\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\tt = high(k)\n\tt = t << 1\n\ta = t + k\n\ta1 = t\n\tA = [[0 for i in range(4)] for i in range(3)]\n\tfor i in range(3):\n\t\tA[0][i] = k\n\tfor i in range(3):\n\t\tA[i][0] = a1\n\tfor i in range(3):\n\t\tA[-1][i] = a1\n\tfor i in range(3):\n\t\tA[i][-2] = k\n\tA[0][0] = a\n\tA[-1][-1] = k\n\tA[-1][-2] = a\n\tprint(3, 4)\n\tfor i in A:\n\t\tfor j in i:\n\t\t\tprint(j, end=' ')\n\t\tprint()\n", "n = int(input())\ndegree = 2 ** 17\nprint(2, 3)\nprint(degree ^ n, degree, 0)\nprint(n, degree ^ n, n)\n", "import sys\nfrom functools import lru_cache\nfrom heapq import merge, heapify, heappop, heappush\nfrom math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf\nfrom collections import defaultdict as dd, deque, Counter as c\nfrom itertools import combinations as comb, permutations as perm\nfrom bisect import bisect_left as bl, bisect_right as br, bisect\nmod = pow(10, 9) + 7\nmod2 = 998244353\n\ndef data():\n\treturn sys.stdin.readline().strip()\n\ndef out(var):\n\tsys.stdout.write(str(var))\n\ndef outln(var):\n\tsys.stdout.write(str(var) + '\\n')\n\ndef l():\n\treturn list(sp())\n\ndef sl():\n\treturn list(ssp())\n\ndef sp():\n\treturn map(int, data().split())\n\ndef ssp():\n\treturn map(str, data().split())\n\ndef l1d(n, val=0):\n\treturn [val for i in range(n)]\n\ndef l2d(n, m, val=0):\n\treturn [l1d(n, val) for j in range(m)]\nk = int(data())\noutln('2 3')\noutln(str(pow(2, 17) + k) + ' ' + str(pow(2, 17)) + ' 0')\noutln(str(k) + ' ' + str(pow(2, 17) + k) + ' ' + str(k))\n", "import sys\nimport os\nfrom io import BytesIO, IOBase\n\ndef cel(n, k):\n\treturn n // k + (n % k != 0)\n\ndef ii():\n\treturn int(input())\n\ndef mi():\n\treturn map(int, input().split())\n\ndef li():\n\treturn list(map(int, input().split()))\n\ndef lcm(a, b):\n\treturn abs(a * b) // math.gcd(a, b)\n\ndef prr(a, sep=' '):\n\tprint(sep.join(map(str, a)))\n\ndef dd():\n\treturn defaultdict(int)\n\ndef ddl():\n\treturn defaultdict(list)\n\ndef ddd():\n\treturn defaultdict(defaultdict(int))\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom collections import defaultdict\nfrom math import gcd\nfor _ in range(1):\n\tk = ii()\n\tif k == 0:\n\t\tprint(1, 1)\n\t\tprint(300000)\n\telse:\n\t\tprint(2, 3)\n\t\tprint(2 ** 17 + k, k, 0)\n\t\tprint(2 ** 17, 2 ** 17 + k, k)\n", "from sys import stdin, stdout\n\ndef cout(x):\n\tprint(x, end=' ')\n\treturn\nk = int(input())\na = 2 ** 18 - 1\nb = 2 ** 17\nprint('3 3')\nprint(str(a) + ' ' + str(a) + ' ' + str(b))\nprint(str(b) + ' ' + str(k) + ' ' + str(a))\nprint(str(b) + ' ' + str(a) + ' ' + str(k))\n", "import os, sys, bisect, copy\nfrom collections import defaultdict, Counter, deque\nfrom functools import lru_cache\nif os.path.exists('in.txt'):\n\tsys.stdin = open('in.txt', 'r')\nif os.path.exists('out.txt'):\n\tsys.stdout = open('out.txt', 'w')\n\ndef input():\n\treturn sys.stdin.readline()\n\ndef mapi(arg=0):\n\treturn map(int if arg == 0 else str, input().split())\nk = int(input())\nx = 1\nwhile x <= k:\n\tx <<= 1\nprint(2, 3)\nprint(x ^ k, x, 0)\nprint(k, x ^ k, k)\n", "k = int(input())\np = 2 ** 17\nprint(2, 3)\nprint(p + k, p, 0)\nprint(k, p + k, k)\n", "import sys\ninput = sys.stdin.readline\nfrom sys import stdin, stdout\nimport math\n\ndef max_bit(k):\n\tn = int(math.log(k, 2)) + 1\n\treturn 2 ** n\n\ndef main():\n\tk = int(input())\n\tif k != 0:\n\t\tx1 = max_bit(k)\n\telse:\n\t\t(x1, y1) = (0, 0)\n\ty1 = k + x1\n\tprint(3, 4)\n\tarr = [[0 for i in range(4)] for j in range(3)]\n\tarr[0][0] = y1\n\tarr[2][2] = y1\n\tarr[0][1] = k\n\tarr[0][2] = k\n\tarr[1][2] = k\n\tarr[2][3] = k\n\tarr[1][0] = x1\n\tarr[2][0] = x1\n\tarr[2][1] = x1\n\tfor i in range(3):\n\t\tfor j in range(4):\n\t\t\tprint(arr[i][j], end=' ')\n\t\tprint()\nmain()\n", "n = int(input())\nprint('3 3')\nprint((1 << 17) + n, n, 0)\nprint(1 << 17, (1 << 17) + n, n)\nprint(0, n, n)\n", "k = int(input())\nd = 1 << min(k.bit_length() + 1, 17)\nprint(2, 3)\nprint(d + k, d, 0)\nprint(k, d + k, k)\n", "from sys import stdin, stdout\nimport math\nimport heapq\nt = 1\n\ndef aint():\n\treturn int(input().strip())\n\ndef lint():\n\treturn list(map(int, input().split()))\n\ndef fint():\n\treturn list(map(int, stdin.readline().split()))\n\ndef main():\n\tk = aint()\n\tprint('3 3')\n\tprint(pow(2, 18) - 1, pow(2, 18) - 1, pow(2, 17))\n\tprint(pow(2, 18) - 1, pow(2, 17) - 1, pow(2, 18) - 1)\n\tprint(pow(2, 17), pow(2, 17), k)\nfor i in range(t):\n\tmain()\n", "k = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(300000)\n\texit()\nprint(2, 3)\nprint(2 ** 18 - 1, 2 ** 17, 2 ** 17)\nprint(k, 2 ** 18 - 1, k)\n", "k = int(input())\nres = [[0 for _ in range(4)] for _ in range(4)]\nres[0][0] = (1 << 18) - 1\nres[0][1] = (1 << 18) - 1\nres[0][2] = 1 << 17\nres[0][3] = 1 << 17\nres[1][0] = 1 << 17\nres[1][1] = (1 << 18) - 1\nres[1][2] = k\nres[1][3] = 1 << 17\nres[2][0] = 1 << 17\nres[2][1] = k\nres[2][2] = (1 << 17) - 1\nres[2][3] = 1 << 17\nres[3][0] = 1 << 17\nres[3][1] = 1 << 17\nres[3][2] = (1 << 18) - 1\nres[3][3] = (1 << 17) - 1\nprint(4, 4)\nfor i in res:\n\tprint(*i)\n", "k = int(input())\nb = bin(k)\nk1 = int(b[:2] + '1' + b[2:], 2)\ntwo = int(b[:2] + '1' + '0' * len(b[2:]), 2)\nprint(2, 3)\nprint(k1, k, 0)\nprint(two, k1, k)\n", "from sys import stdin\ninput = stdin.readline\n\ndef A():\n\tt = int(input())\n\tfor _ in range(t):\n\t\t(a, b, c, d) = map(int, input().split())\n\t\t(x, y, x1, y1, x2, y2) = map(int, input().split())\n\t\tnetr = b - a\n\t\tnetu = d - c\n\t\tif x1 == x2 and (a > 0 or b > 0):\n\t\t\tprint('No')\n\t\t\tcontinue\n\t\tif y1 == y2 and (c > 0 or d > 0):\n\t\t\tprint('No')\n\t\t\tcontinue\n\t\tif netr + x < x1 or netr + x > x2:\n\t\t\tprint('No')\n\t\t\tcontinue\n\t\tif netu + y < y1 or netu + y > y2:\n\t\t\tprint('No')\n\t\t\tcontinue\n\t\tprint('Yes')\n\ndef B():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tm = int(input())\n\t\ta = list(map(int, input().split()))\n\t\tc = [0] * m\n\t\tp = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]\n\t\tused = [False] * 11\n\t\tfor i in range(m):\n\t\t\tj = 0\n\t\t\twhile a[i] % p[j] != 0:\n\t\t\t\tj += 1\n\t\t\tused[j] = True\n\t\t\tc[i] = j\n\t\tused[0] = int(used[0])\n\t\tfor i in range(1, 11):\n\t\t\tused[i] = int(used[i]) + used[i - 1]\n\t\tfor i in range(m):\n\t\t\tc[i] = used[c[i]]\n\t\tprint(max(used))\n\t\tprint(*c)\n\ndef C():\n\tt = int(input())\n\tfor _ in range(t):\n\t\t(n, k) = map(int, input().split())\n\t\ts = [ord(x) - 97 for x in input().rstrip()]\n\t\tl = [[0 for i in range(26)] for j in range(k)]\n\t\tfor i in range(n):\n\t\t\tl[i % k][s[i]] += 1\n\t\tfor i in range(k // 2):\n\t\t\tfor j in range(26):\n\t\t\t\tl[i][j] += l[k - i - 1][j]\n\t\tfor i in range((k + 1) // 2):\n\t\t\tn -= max(l[i])\n\t\tprint(n)\n\ndef D():\n\tk = int(input())\n\tif k == 0:\n\t\tprint('1 1\\n1')\n\telse:\n\t\tt = 1\n\t\twhile t <= 2 * k:\n\t\t\tt *= 2\n\t\tprint('3 2')\n\t\tprint(str(t - 1) + ' ' + str(t // 2))\n\t\tprint(str(k) + ' ' + str(t - 1))\n\t\tprint('0 ' + str(t // 2 - 1))\nD()\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nimport threading\nfrom bisect import bisect_right\nfrom heapq import heapify, heappush, heappop\n\ndef main():\n\tfor _ in range(1):\n\t\tn = int(input())\n\t\tmat = [[0] * 3 for i in range(3)]\n\t\tmat[0][0] = mat[1][1] = 2 ** 18 - 1\n\t\tmat[0][1] = 2 ** 17\n\t\tmat[1][0] = mat[2][1] = mat[2][2] = n\n\t\tprint(3, 3)\n\t\tfor li in mat:\n\t\t\tprint(*li)\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "import sys, math\nfrom heapq import *\nfrom collections import defaultdict as dd\ninput = lambda : sys.stdin.readline().strip()\ninp = lambda : list(map(int, input().split()))\n(n,) = inp()\ns = 0\nfor i in range(18):\n\ts += 2 ** i\nk = 2 ** 17\nans = [[s, k, k], [n, k, k], [n, k + n, n]]\nprint(3, 3)\nfor i in ans:\n\tprint(*i)\n", "import os, sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom math import ceil, log2\nmod = 10 ** 9 + 7\nn = int(input())\nz = 131072 * 2 - 1\nans = n ^ z\nprint(3, 3)\nprint(z, n, z)\nprint(ans, z, z)\nprint(ans, ans, n)\n", "k = int(input())\nc = 1 << 17\nx = c + k\nl = [[x, k, k, 0], [c, 0, k, 0], [c, c, x, k]]\nprint(3, 4)\nfor r in l:\n\tprint(*r)\n", "k = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(100)\nelse:\n\tprint(3, 3)\n\tprint(2 ** 18 - 1, 2 ** 18 - 1, 2 ** 17)\n\tprint(2 ** 18 - 1, k, 2 ** 17 + k)\n\tprint(2 ** 17, 2 ** 17 + k, k)\n", "import collections\nimport time\nimport os\nimport sys\nimport bisect\nimport heapq\nfrom typing import List\nk = int(input())\nx = 2 ** 17\nprint(2, 3)\nprint(x ^ k, x, 0)\nprint(k, x ^ k, k)\n", "n = int(input())\nif n == 0:\n\tprint(1, 1)\n\tprint(1234)\n\texit()\nb = bin(n)[2:]\nc = len(b) * '0'\nb = '1' + b\nnw = int(b, 2)\nc = '1' + c\nnw1 = int(c, 2)\nprint(3, 3)\nprint(nw, n, n)\nprint(nw, nw1, nw)\nprint(nw, nw1, n)\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().strip()\n\ndef iinput():\n\treturn int(input())\n\ndef rinput():\n\treturn map(int, input().split())\n\ndef rlinput():\n\treturn list(map(int, input().split()))\n\ndef main():\n\n\tdef pro(a, b, x, x1, x2):\n\t\tif (a == -2 * b or x != x1 or x != x2 or (b == 0)) and x1 <= x - a + b <= x2:\n\t\t\treturn True\n\t\treturn False\n\tk = iinput()\n\tprint(3, 2)\n\tprint(2 ** 18 - 1, k)\n\tprint(2 ** 17, 2 ** 18 - 1)\n\tprint(0, k)\nfor i in range(1):\n\tmain()\n", "n = 4\nm = 4\nk = int(input())\na = [[131072 + k, k, k, k], [131072, 0, k, k], [131072, 0, k, 0], [131072, 131072, 131072 + k, k]]\nprint(n, m)\nfor row in a:\n\tprint(*row)\n", "n = int(input())\nq = 1 << 17\nmat = [[q + n, n], [q, q + n], [q, q - 1]]\nprint(3, 2)\nprint(*mat[0])\nprint(*mat[1])\nprint(*mat[2])\n", "k = int(input())\nif k == 0:\n\tprint('1 1')\n\tprint('5')\nelse:\n\tprint('3 2')\n\tp2 = 1\n\twhile p2 <= k:\n\t\tp2 *= 2\n\tones = p2 * 2 - 1\n\tprint(ones, k)\n\tprint(p2, ones)\n\tprint(0, k)\n", "import os\nfrom io import BytesIO, IOBase\nimport sys\nfrom collections import defaultdict, deque, Counter\nfrom bisect import *\nfrom math import sqrt\nimport math\nfrom itertools import permutations\n\ndef main():\n\tk = int(input())\n\td = 1 << min(k.bit_length() + 1, 17)\n\tprint(2, 3)\n\tprint(d + k, d, 0)\n\tprint(k, d + k, k)\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "k = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\ttemp = k\n\tcnt = 0\n\twhile temp > 0:\n\t\tcnt += 1\n\t\ttemp = temp >> 1\n\tarr = []\n\tfor x in range(3):\n\t\tarr.append([k, k, k, k])\n\tarr[1][0] = arr[1][1] = 1 << cnt\n\tarr[0][3] = arr[1][3] = 0\n\tarr[0][0] = (1 << cnt + 1) - 1\n\tarr[2][0] = arr[0][0]\n\tarr[2][1] = arr[0][0]\n\tarr[2][2] = arr[0][0]\n\tprint(3, 4)\n\tfor x in arr:\n\t\tfor y in x:\n\t\t\tprint(y, end=' ')\n\t\tprint()\n", "import math\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(0)\n\texit()\na = 2 ** 18 - 1\nprint(3, 4)\nt = int(math.log(k, 2)) + 1\nt = 2 ** t\nl = [[a, k, k, 0], [t, 0, k, 0], [a, a, a, k]]\nfor i in l:\n\tprint(*i)\n", "k = int(input())\ntrump = pow(2, 17)\nmask = pow(2, 18) - 1\nprint(3, 3)\nans = [[0 for i in range(3)] for j in range(3)]\nans[0][0] = mask\nans[0][1] = k\nans[0][2] = 0\nans[1][0] = trump\nans[1][1] = mask\nans[1][2] = k\nans[2][0] = 0\nans[2][1] = k\nans[2][2] = k\nfor i in range(3):\n\tfor j in range(3):\n\t\tprint(ans[i][j], end=' ')\n\tprint()\ndp = [[0 for i in range(4)] for j in range(4)]\ndp[0][1] = mask\nfor i in range(1, 4):\n\tfor j in range(1, 4):\n\t\tdp[i][j] = max(dp[i - 1][j] & ans[i - 1][j - 1], dp[i][j - 1] & ans[i - 1][j - 1])\n", "from sys import stdin\ninput = stdin.readline\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(300000)\nelse:\n\tprint(3, 4)\n\tprint(2 ** 18 - 1, 2 ** 17 - 1, 2 ** 17 - 1, 1)\n\tprint(2 ** 17, 2 ** 18, 2 ** 17 - 1, 0)\n\tprint(2 ** 18 - 1, 2 ** 18 - 1, 2 ** 18 - 1, k)\n", "print(2, 3)\nk = int(input())\nt = 2 ** 17\nprint(t + k, k, 0)\nprint(t, t + k, k)\n", "from __future__ import division, print_function\nfrom fractions import Fraction\nimport sys\nimport os\nfrom io import BytesIO, IOBase\nfrom functools import cmp_to_key\nfrom heapq import *\nfrom math import gcd, factorial, floor, ceil, sqrt\nfrom copy import deepcopy\nfrom collections import deque\nfrom bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom bisect import bisect\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\ndef print(*args, **kwargs):\n\t(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))\n\tat_start = True\n\tfor x in args:\n\t\tif not at_start:\n\t\t\tfile.write(sep)\n\t\tfile.write(str(x))\n\t\tat_start = False\n\tfile.write(kwargs.pop('end', '\\n'))\n\tif kwargs.pop('flush', False):\n\t\tfile.flush()\nif sys.version_info[0] < 3:\n\t(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))\nelse:\n\t(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\nfrom types import GeneratorType\n\ndef iterative(f, stack=[]):\n\n\tdef wrapped_func(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\tto = f(*args, **kwargs)\n\t\twhile True:\n\t\t\tif type(to) is GeneratorType:\n\t\t\t\tstack.append(to)\n\t\t\t\tto = next(to)\n\t\t\t\tcontinue\n\t\t\tstack.pop()\n\t\t\tif not stack:\n\t\t\t\tbreak\n\t\t\tto = stack[-1].send(to)\n\t\treturn to\n\treturn wrapped_func\n\ndef inp():\n\treturn sys.stdin.readline().rstrip('\\r\\n')\n\ndef out(var):\n\tsys.stdout.write(str(var))\n\ndef lis():\n\treturn list(map(int, inp().split()))\n\ndef stringlis():\n\treturn list(map(str, inp().split()))\n\ndef sep():\n\treturn map(int, inp().split())\n\ndef strsep():\n\treturn map(str, inp().split())\n\ndef zerolist(n):\n\treturn [0] * n\n\ndef nextline():\n\tout('\\n')\n\ndef testcase(t):\n\tfor pp in range(t):\n\t\tsolve(pp)\n\ndef printlist(a):\n\tfor p in range(0, len(a)):\n\t\tout(str(a[p]) + ' ')\n\ndef google(p):\n\tprint('Case #' + str(p) + ': ', end='')\n\ndef lcm(a, b):\n\treturn a * b // gcd(a, b)\n\ndef power(x, y, p):\n\ty %= p - 1\n\tres = 1\n\tx = x % p\n\tif x == 0:\n\t\treturn 0\n\twhile y > 0:\n\t\tif y & 1 == 1:\n\t\t\tres = res * x % p\n\t\ty = y >> 1\n\t\tx = x * x % p\n\treturn res\n\ndef ncr(n, r):\n\treturn factorial(n) // (factorial(r) * factorial(max(n - r, 1)))\n\ndef isPrime(n):\n\tif n <= 1:\n\t\treturn False\n\tif n <= 3:\n\t\treturn True\n\tif n % 2 == 0 or n % 3 == 0:\n\t\treturn False\n\ti = 5\n\twhile i * i <= n:\n\t\tif n % i == 0 or n % (i + 2) == 0:\n\t\t\treturn False\n\t\ti = i + 6\n\treturn True\ninf = pow(10, 20)\nmod = 10 ** 9 + 7\n\ndef solve(case):\n\tk = int(inp())\n\ttemp = int('1' * (len(bin(100000)) - 1), 2)\n\tval = '1' + '0' * (len(bin(k)) - 2)\n\tval = int(val, 2)\n\tprint(3, 3)\n\tg = [[temp, k, 0], [val, temp, 0], [0, k, k]]\n\tfor i in range(3):\n\t\tprint(*g[i])\ntestcase(1)\n", "import sys\nsys.setrecursionlimit(10 ** 6)\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep='\\n')\n\ndef II():\n\treturn int(sys.stdin.readline())\n\ndef MI():\n\treturn map(int, sys.stdin.readline().split())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef SI():\n\treturn sys.stdin.readline()[:-1]\n\ndef main():\n\tk = II()\n\ta = (1 << 18) - 1\n\tb = 1 << 17\n\tprint(3, 3)\n\tprint(a, b - 1, 0)\n\tprint(b, a, a)\n\tprint(0, 0, k)\nmain()\n", "n = int(input())\nB = [0] * 4\nfor i in range(4):\n\tB[i] = [0] * 4\nx = 18\nB[0][0] = (1 << x) - 1\nfor i in range(4):\n\tfor j in range(4):\n\t\tB[i][j] = B[0][0]\nB[1][1] = (1 << x - 1) - 1\nB[2][0] = B[1][1] + 1\nB[1][2] = 2 * B[2][0]\nB[2][2] = n\nprint(3, 3)\nfor i in range(3):\n\tfor j in range(3):\n\t\tprint(B[i][j], end=' ')\n\tprint()\n", "k = int(input())\nprint('2 3\\n' + str(k + 2 ** 17) + ' ' + str(k) + ' 0\\n' + str(2 ** 17) + ' ' + str(k + 2 ** 17) + ' ' + str(k))\n", "import os\nimport heapq\nimport sys, threading\nimport math as mt\nimport operator\nfrom copy import copy\nfrom collections import defaultdict, deque\nfrom io import BytesIO, IOBase\nsys.setrecursionlimit(2 * 10 ** 5)\n\ndef gcd(a, b):\n\tif b == 0:\n\t\treturn a\n\telse:\n\t\treturn gcd(b, a % b)\n\ndef inpt():\n\treturn [int(k) for k in input().split()]\n\ndef main():\n\tk = int(input())\n\t(n, m) = (3, 3)\n\tprint(n, m)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif i == n - 1 and j == m - 1:\n\t\t\t\tprint(k, end=' ')\n\t\t\t\tbreak\n\t\t\tif i == 0:\n\t\t\t\tif j == m - 1:\n\t\t\t\t\tprint(2 ** 17 - 1, end=' ')\n\t\t\t\telse:\n\t\t\t\t\tprint(2 ** 18 - 1, end=' ')\n\t\t\telif j == m - 1:\n\t\t\t\tprint(2 ** 18 - 1, end=' ')\n\t\t\telse:\n\t\t\t\tprint(2 ** 17, end=' ')\n\t\tprint()\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "k = int(input())\nt = k\nt = t | t >> 1\nt = t | t >> 2\nt = t | t >> 4\nt = t | t >> 8\nt = t | t >> 16\nt = t | t >> 32\nt = t + 1\ntemp = t | k\nans = [[temp, k], [t, temp], [0, k]]\nprint(3, 2)\nfor i in range(3):\n\tprint(*ans[i])\n", "import sys\ninput = lambda : sys.stdin.readline().strip()\nipnut = input\nk = int(ipnut())\nt = 1\nif k == 1:\n\tprint('3 4\\n7 3 3 1\\n4 8 3 6\\n7 7 7 3')\n\texit(0)\nwhile t <= k:\n\tt *= 2\nt1 = 2 * t - 1\nprint(2, 3)\nprint(t1, k, 0)\nprint(t, t1, k)\n", "k = int(input())\nA = str(int('0b111111111111111111', 2))\nB = str(k)\nC = str(int('0b100000000000000000', 2))\nprint('2 3')\nprint('{} {} 0'.format(A, B))\nprint('{} {} {}'.format(C, A, B))\n", "k = int(input())\nA = 131071\nB = A - k\nC = 2 * A + 1\nD = C - A\nprint(3, 3)\nm = [[C, A, B], [D, C, B], [0, C, A]]\nfor l in m:\n\tprint(*l)\n", "import sys\ninp = sys.stdin.readline\n\ndef input():\n\treturn inp().strip()\n\ndef iin():\n\treturn int(input())\n\ndef lin():\n\treturn list(map(int, input().split()))\n\ndef main():\n\tT = 1\n\twhile T:\n\t\tT -= 1\n\t\tk = iin()\n\t\tprint(2, 3)\n\t\tmx = 262143\n\t\tinv = mx - k\n\t\ta = [[mx, k, 0], [inv, mx, k]]\n\t\tfor i in a:\n\t\t\tprint(*i)\nmain()\n", "import sys\nfrom collections import defaultdict\nfrom copy import deepcopy\nk = int(sys.stdin.readline().strip())\nprint(2, 3)\nprint(k + 2 ** 17, k, 0)\nprint(2 ** 17, k + 2 ** 17, k)\n", "k = int(input())\nA = (1 << 18) - 1\nB = 1 << 17\nans = [[A, A, A], [B, k, B], [B, B + k, k]]\nprint(3, 3)\n[print(*i) for i in ans]\n", "import sys\ninput = sys.stdin.readline\nfrom math import *\nmod = 10 ** 9 + 7\n\ndef bo(i):\n\treturn ord(i) - ord('a')\nk = int(input())\np = k\nc = 1\nwhile p > 0 and p // 2 > 0:\n\tc += 1\n\tp //= 2\nif k == 0 or k == 1:\n\tc = 1\na = [[(1 << c + 1) - 1, 1 << c], [k, (1 << c + 1) - 1], [0, k]]\nprint(3, 2)\nfor i in a:\n\tprint(*i)\n", "k = int(input())\npow2 = 0\npow2x = 1\nwhile pow2x <= k * 2:\n\tpow2 += 1\n\tpow2x *= 2\none = pow2x - 1\nzer = pow2x // 2\nkek = k\nans = [[one, one, one, one, zer], [one, 0, one, kek, zer], [one, one, 0, kek, one], [one, kek, kek, 0, kek], [zer, zer, one, kek, kek]]\nprint(5, 5)\nfor line in ans:\n\tprint(*line)\n", "d = int(input())\np = 1\nwhile p - 1 < d:\n\tp *= 2\np *= 2\nfull = p - 1\ntop = p // 2\nprint('3 3')\nprint(full, d, top)\nprint(top, d, top)\nprint(top, full, d)\n", "k = int(input())\n(n, m) = (2, 3)\nmat = [[0] * 3 for i in range(2)]\nkbits = 0\nx = k\nwhile x:\n\tx >>= 1\n\tkbits += 1\nstart = 1\nfor i in range(kbits):\n\tstart = (start << 1) + 1\nx = 1 << kbits\nmat[0][0] = start\nmat[0][1] = x\nmat[1][0] = k\nmat[1][1] = x + k\nmat[1][2] = k\nprint(n, m)\nfor row in mat:\n\tprint(*row)\n", "ones = 262143\nguard = 131072\nk = int(input())\nmat = [[ones, k], [ones - k, ones], [0, k]]\nprint(3, 2)\nfor row in mat:\n\tprint(*row)\n", "k = int(input())\nk = bin(k)[2:]\nl = len(k)\na = '1' * (l + 1)\na = int(a, 2)\nk = int(k, 2)\np = a - k\nif k == 0:\n\tprint(1, 1)\n\tprint(12)\nelse:\n\tprint(3, 4)\n\tprint(a, a, a, p)\n\tprint(p, 0, k, p)\n\tprint(p, p, a, k)\n", "import sys\ninput = sys.stdin.readline\nK = int(input())\nres = [[0] * 3 for _ in range(2)]\nres[0][0] = (1 << 18) - 1\nres[1][1] = (1 << 18) - 1\nres[0][1] = K\nres[-1][-1] = K\nres[1][0] = (1 << 18) - 1 - K\nprint(2, 3)\nprint(*res[0])\nprint(*res[1])\n", "from sys import stdin, stdout\n\ndef main():\n\tn = int(stdin.readline())\n\tif n == 0:\n\t\tstdout.write('1 1\\n300')\n\telse:\n\t\tstdout.write('3 3\\n')\n\t\tpw = 1\n\t\twhile pw <= n:\n\t\t\tpw *= 2\n\t\tstart = pw + n\n\t\tstdout.write(str(start) + ' ' + str(pw) + ' ' + str(pw) + '\\n')\n\t\tstdout.write(str(n) + ' ' + str(pw) + ' ' + str(pw) + '\\n')\n\t\tstdout.write(str(n) + ' ' + str(start) + ' ' + str(n) + '\\n')\nmain()\n", "k = int(input())\nfull_bit = 2 ** 18 - 1\nlarge_bit = 2 ** 17\na = [[full_bit, full_bit, 0], [large_bit, k, 0], [large_bit, full_bit, full_bit - large_bit]]\nprint(3, 3)\nfor row in a:\n\tprint(*row)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nimport math\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(0)\nelse:\n\tn = 2\n\tm = 3\n\tp1 = 17\n\tp2 = 0\n\tv0 = 2 ** p1 + k\n\tmaze = [[v0, k, 0], [2 ** p1, v0, k]]\n\tprint(n, m)\n\tfor s in range(n):\n\t\tprint(*maze[s])\n", "import math\nk1 = int(input())\nif k1 == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\tprint(2, 3)\n\tz = 131072\n\tprint(z + k1, z, z)\n\tprint(k1, z + k1, k1)\n", "from math import log2\n\ndef main(K):\n\tif K == 0:\n\t\tprint(1, 1)\n\t\tprint(10)\n\t\treturn\n\tM = int(2 ** (int(log2(K)) + 1))\n\tL = K | M\n\tprint(3, 3)\n\tprint(L, M, M)\n\tprint(L, K, M)\n\tprint(M, L, K)\nmain(int(input()))\n", "k = int(input())\ndp = []\nc = 2 ** 17\ndp.append([c + k, k, k])\ndp.append([c, k + c, k + c])\ndp.append([k, k + c, k])\nprint(3, 3)\nfor (a, b, c) in dp:\n\tprint(a, b, c)\n", "k = int(input())\nprint(3, 3)\nx = 1\nwhile x <= k:\n\tx *= 2\nprint(2 * x - 1, 0, 0)\nprint(2 * x - 1, k, 0)\nprint(x, x + k, k)\n", "import math\nimport sys\ninput = sys.stdin.readline\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\tprint(2, 3)\n\tprint(2 ** 18 - 1, 2 ** 17 - 1, 0)\n\tprint(2 ** 17, 2 ** 18 - 1, k)\n", "k = int(input())\nprint(3, 3)\nprint(2 ** 17 + k, k, 2 ** 17)\nprint(2 ** 17, 2 ** 17 + k, k)\nprint(k, k, k)\n", "import os, sys\nfrom io import IOBase, BytesIO\npy2 = round(0.5)\nif py2:\n\tfrom future_builtins import ascii, filter, hex, map, oct, zip\n\trange = xrange\nBUFSIZE = 8192\n\nclass FastIO(BytesIO):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._file = file\n\t\tself._fd = file.fileno()\n\t\tself.writable = 'x' in file.mode or 'w' in file.mode\n\t\tself.write = super(FastIO, self).write if self.writable else None\n\n\tdef _fill(self):\n\t\ts = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\tself.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])\n\t\treturn s\n\n\tdef read(self):\n\t\twhile self._fill():\n\t\t\tpass\n\t\treturn super(FastIO, self).read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\ts = self._fill()\n\t\t\tself.newlines = s.count(b'\\n') + (not s)\n\t\tself.newlines -= 1\n\t\treturn super(FastIO, self).readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.getvalue())\n\t\t\t(self.truncate(0), self.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tif py2:\n\t\t\tself.write = self.buffer.write\n\t\t\tself.read = self.buffer.read\n\t\t\tself.readline = self.buffer.readline\n\t\telse:\n\t\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nimport sys\n\nclass ostream:\n\n\tdef __lshift__(self, a):\n\t\tsys.stdout.write(str(a))\n\t\treturn self\ncout = ostream()\nendl = '\\n'\n\ndef get_input(a=str):\n\treturn a(input())\n\ndef get_int_input():\n\treturn get_input(int)\n\ndef get_input_arr(a):\n\treturn list(map(a, input().split()))\n\ndef get_int_input_arr():\n\treturn get_input_arr(int)\n\ndef solve():\n\tdif = get_int_input()\n\ta = 2 ** 17 - 1\n\td = a\n\tb = dif\n\te = dif\n\tc = 2 ** 17 - 1\n\tele = b\n\tnum = 1\n\twhile ele:\n\t\tif ele & 1:\n\t\t\tc = c & ~(1 << num - 1)\n\t\tnum += 1\n\t\tele = ele >> 1\n\tif b > c:\n\t\ta += 2 ** 17\n\t\tc += 2 ** 17\n\t\td += 2 ** 17\n\tcout << 2 << ' ' << 3 << endl\n\tcout << a << ' ' << b << ' ' << 0 << endl\n\tcout << c << ' ' << d << ' ' << e << endl\n\ndef main():\n\tsolve()\nmain()\n", "k = int(input())\nx = 2 ** 17\nprint(2, 3)\nprint(x ^ k, k, 0)\nprint(x, x ^ k, k)\n", "k = int(input())\nprint(2, 3)\nprint(131072 + k, 131072, 131072)\nprint(k, 131072 + k, k)\n", "k = int(input())\nprint('4 4\\n262143 131071 131071 0\\n131072 0 131071 0\\n131072 131072 262143 0\\n0 0 131071 %d' % k)\n", "import sys\nreader = (s.rstrip() for s in sys.stdin)\ninput = reader.__next__\nt = int(input())\nprint('2 3')\nprint(str(131072 + t) + ' ' + str(t) + ' ' + str(131072))\nprint(str(131072) + ' ' + str(131072 + t) + ' ' + str(t))\n", "k = int(input())\ns = bin(k)[2:]\na = (1 << len(s)) + k\nb = 1 << len(s)\nprint(2, 3)\nprint(a, b, b)\nprint(k, a, k)\n", "def f():\n\tk = int(input())\n\tfull = (1 << 18) - 1\n\tfake = 1 << 17\n\tM = [[full, fake, full], [k, full, full], [full, full, k]]\n\tprint('3 3')\n\tfor row in M:\n\t\tprint(' '.join((str(num) for num in row)))\nf()\n", "(K,) = map(int, input().split())\nln = len(bin(K)) - 2\nprint(3, 2)\nprint((1 << ln + 1) - 1, 1 << ln)\nprint(K, (1 << ln + 1) - 1)\nprint(0, K)\n", "k = int(input())\nprint(3, 3)\na = [[0 for _ in range(3)] for _ in range(3)]\nCONST = 1\nwhile CONST < 100000:\n\tCONST = CONST << 1\n\tCONST = CONST | 1\nCONST = CONST << 1 | 1\na[0][0] = CONST\na[0][1] = CONST\na[1][0] = CONST\na[2][1] = CONST\na[1][1] = k\na[2][2] = k\na[2][0] = CONST ^ k\nfor i in range(len(a)):\n\tfor j in range(len(a[i])):\n\t\tprint(a[i][j], end=' ')\n\tprint()\n", "k = int(input())\ns = bin(k)[2:]\nl = len(s)\na = 2 ** l\nb = k + a\nmatrix = [[b] * 3 for i in range(3)]\nmatrix[0][1] = k\nmatrix[1][0] = a\nmatrix[2][2] = k\nprint(3, 3)\nfor i in range(3):\n\tprint(' '.join((str(x) for x in matrix[i])))\n", "import sys\nfrom math import ceil\nk = int(input())\nprint(3, 2)\ninf = 2 ** 18 - 1\nm = 2 ** 17\nprint(inf, k)\nprint(m, inf)\nprint(0, k)\n", "import math\n\ndef calc(a):\n\tn = len(a)\n\tm = len(a[0])\n\tdp = [[0 for i in range(m)] for j in range(n)]\n\tdp[0][0] = a[0][0]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif i == 0 and j == 0:\n\t\t\t\tcontinue\n\t\t\tif i != 0 and j != 0:\n\t\t\t\tdp[i][j] = max(dp[i - 1][j] & a[i][j], dp[i][j - 1] & a[i][j])\n\t\t\telif i == 0:\n\t\t\t\tdp[i][j] = dp[i][j - 1] & a[i][j]\n\t\t\telse:\n\t\t\t\tdp[i][j] = dp[i - 1][j] & a[i][j]\n\tprint(dp)\n\treturn dp[i][j]\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(2)\nelse:\n\tx = math.floor(math.log(k, 2)) + 1\n\ty = 2 ** x\n\tz = k\n\tprint(4, 4)\n\tans = [[262143, z, z, 0], [y, 0, z, 0], [y, 0, z, 0], [y, y, 262143, z]]\n\tfor i in ans:\n\t\tprint(*i)\n", "n = int(input())\nprint(2, 3)\nprint(n + 2 ** 17, end=' ')\nprint(n, end=' ')\nprint(0)\nprint(2 ** 17, end=' ')\nprint(n + 2 ** 17, end=' ')\nprint(n)\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline()[:-1]\nk = int(input())\nx = 2 ** 17\nprint(2, 3)\nprint(x + k, x, 0)\nprint(k, x + k, k)\n", "big = 1 << 17\nk = int(input())\nprint(3, 2)\nprint(*[k + big, k])\nprint(*[big, k + big])\nprint(*[0, k])\n", "import sys\ninput = sys.stdin.readline\nk = int(input())\nprint(3, 3)\nprint((1 << 18) - 1, k, 0)\nprint(1 << 17, (1 << 18) - 1, k)\nprint(0, k, k)\n", "from math import ceil, log\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\tp = 2 ** ceil(log(k, 2))\n\tif p == k:\n\t\tp *= 2\n\tprint(3, 3)\n\tprint(2 ** 18 - 1, p, 0)\n\tprint(k, 2 ** 18 - 1, 0)\n\tprint(0, k, k)\n", "k = int(input())\nn = len(bin(k)) - 2\nmine = 2 ** n - 1\nbob = k ^ mine\nprint(2, 3)\nprint(2 ** n + mine, 2 ** n + bob, bob)\nprint(mine, 2 ** n + mine, mine)\n", "MOD = 998244353\nT = 1\nfor t in range(1, T + 1):\n\tk = int(input())\n\tif k == 0:\n\t\tprint(1, 1)\n\t\tprint(1)\n\telse:\n\t\tprint(3, 4)\n\t\tx = 1 << 17\n\t\ta = [[x + k, k, k, k], [x, k, k, x], [x, x, x + k, k]]\n\t\tfor i in range(3):\n\t\t\tfor j in range(4):\n\t\t\t\tprint(a[i][j], end=' ')\n\t\t\tprint('')\n", "import sys\ninput = sys.stdin.readline\nk = int(input())\nlarge = 2 ** 17\nsmall = k\nans = [[large | small, small, 0], [large, large | small, small]]\nprint(2, 3)\nfor line in ans:\n\tprint(*line)\n", "from bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom heapq import heappush, heappop\nimport math\nfrom collections import *\nfrom functools import reduce, cmp_to_key\nimport sys\ninput = sys.stdin.readline\nM = mod = 998244353\n\ndef factors(n):\n\treturn sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))\n\ndef inv_mod(n):\n\treturn pow(n, mod - 2, mod)\n\ndef li():\n\treturn [int(i) for i in input().rstrip('\\n').split()]\n\ndef st():\n\treturn input().rstrip('\\n')\n\ndef val():\n\treturn int(input().rstrip('\\n'))\n\ndef li2():\n\treturn [i for i in input().rstrip('\\n')]\n\ndef li3():\n\treturn [int(i) for i in input().rstrip('\\n')]\nk = val()\na = [[0] * 3 for i in range(3)]\nbi = 1 << 17\na[0][0] = a[1][0] = a[2][1] = 262143\na[2][0] = k\na[1][1] = bi\na[-1][-1] = k\nprint(3, 3)\nfor i in a:\n\tprint(*i)\n", "from math import *\nfrom bisect import bisect_left, bisect_right\nfrom sys import stdin, stdout, setrecursionlimit\nfrom collections import Counter\ninput = lambda : stdin.readline().strip()\nprint = stdout.write\nk = int(input())\nif k == 0:\n\tprint('1 1\\n1\\n')\nelse:\n\ta = ['1']\n\tb = ['1']\n\tn = len(bin(k)[2:])\n\tfor i in range(n):\n\t\ta.append('1')\n\t\tb.append('0')\n\tprint('3 3\\n')\n\tprint(str(int(''.join(a), 2)) + ' ')\n\tprint(str(k) + ' ')\n\tprint('0\\n')\n\tprint(str(int(''.join(b), 2)) + ' ')\n\tprint(str(int(''.join(a), 2)) + ' ')\n\tprint(str(k) + '\\n')\n\tprint('0 ')\n\tprint(str(k) + ' ')\n\tprint(str(k) + '\\n')\n", "k = int(input())\ntmp = 2 ** 17\nprint('2 3')\nprint(k + tmp, tmp, 0)\nprint(k, tmp + k, k)\n", "k = int(input())\nprint('2 3\\n')\nx = 1 << 17\nprint(x ^ k, x, 0)\nprint(k, x ^ k, k)\n", "def main():\n\timport sys\n\tinput = sys.stdin.readline\n\tK = int(input())\n\tprint(3, 3)\n\tX = (1 << K.bit_length() + 1) - 1\n\tY = 1 << K.bit_length()\n\tprint(X, K, 0)\n\tprint(Y, X, X)\n\tprint(0, X, K)\nmain()\n", "n = int(input())\ni = 2 ** 17\nprint(2, 3)\nprint(i ^ n, i, 0)\nprint(n, i ^ n, n)\n", "import io, os\nR = lambda : map(int, input().split())\nk = int(input())\nprint(3, 3)\ninf = 2 << 16\nprint(inf + k, k, k)\nprint(inf, inf, inf + k)\nprint(inf, inf, k)\n", "from sys import stderr\n\ndef print_mx(mx):\n\tprint(len(mx), len(mx[0]))\n\tfor row in mx:\n\t\tprint(*row)\n\ndef find_breaking_mx(k):\n\tif k == 0:\n\t\treturn ((0,),)\n\ti_bit = 0\n\twhile k >> i_bit & 1:\n\t\ti_bit += 1\n\ta = k | 1 << i_bit\n\ta_prime = 1 << i_bit\n\twhile a >> i_bit:\n\t\ti_bit += 1\n\tb = 1 << i_bit\n\tx = a | b\n\treturn ((x, a, a, a - k), (b, 0, a, a - k), (x, x, x, a))\nk = int(input())\nprint_mx(find_breaking_mx(k))\n", "def isKthBitSet(n, k):\n\tif n & 1 << k - 1:\n\t\treturn True\n\telse:\n\t\treturn False\nk = int(input())\nls = [0 for i in range(18)]\nfor i in range(18):\n\tif isKthBitSet(k, i + 1):\n\t\tls[i] = 1\nk_ = 0\nfor i in range(18):\n\tif ls[i] == 0:\n\t\tk_ += 2 ** i\nprint(3, 3)\nprint(k + 2 ** 17, k + 2 ** 17, k_)\nprint(k_, k, k + 2 ** 17)\nprint(k_, k + 2 ** 17, k)\n", "def main():\n\tk = int(input())\n\tx = 2 ** 17\n\tprint(2, 3)\n\tprint(x ^ k, x, 0)\n\tprint(k, x ^ k, k)\nmain()\n", "import sys\nk = int(sys.stdin.readline())\narr = [[0 for _ in range(3)] for x in range(3)]\narr[2][2] = k\nx = len(bin(k)) - 2\ny = 2 ** x + k\narr[2][1] = y\narr[2][0] = k\narr[1][0] = k\narr[0][0] = y\narr[0][1] = 2 ** x\narr[0][2] = 2 ** x\narr[1][2] = 2 ** x\narr[1][1] = 2 ** x\nprint(3, 3)\nfor i in range(3):\n\tprint(*arr[i])\n", "import sys\ninput = sys.stdin.readline\n\ndef main():\n\tK = int(input())\n\tif K == 0:\n\t\tprint(1, 1)\n\t\tprint(300000)\n\telse:\n\t\tprint(3, 3)\n\t\tprint(131072 + K, 131072 + K, 131072)\n\t\tprint(131072, K, 131072)\n\t\tprint(131072, 131072 + K, K)\nmain()\n", "k = int(input())\nprint('3 3')\nprint('{} {} {}'.format((1 << 18) - 1, k, 0))\nprint('{} {} {}'.format(1 << 17, (1 << 18) - 1, k))\nprint('{} {} {}'.format(0, k, k))\n", "import sys\ninput = sys.stdin.readline\nB = 262144\nK = int(input())\nprint(3, 2)\nprint(B - 1, K)\nprint(B // 2, B - 1)\nprint(0, B // 2 - 1)\n", "import sys, math, cmath\ninput = sys.stdin.readline\n\ndef inp():\n\treturn int(input())\n\ndef inlt():\n\treturn list(map(int, input().split()))\n\ndef insr():\n\ts = input()\n\treturn s[:len(s) - 1]\n\ndef invr():\n\treturn map(int, input().split())\nt = 1\nfor tt in range(t):\n\tn = inp()\n\tprint(2, 3)\n\tprint((1 << 18) - 1, n, 0)\n\tprint(1 << 17, (1 << 18) - 1, (1 << 17) - 1)\n", "k = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(0)\nelse:\n\tcnt = 1\n\twhile cnt <= k:\n\t\tcnt *= 2\n\tres = [[0 for i in range(3)] for j in range(3)]\n\tmx = pow(2, 18) - 1\n\tres[0][2] = res[2][0] = cnt\n\tres[1][2] = res[2][1] = mx\n\tres[0][0] = res[0][1] = res[1][0] = mx\n\tres[2][2] = res[1][1] = k\n\tprint(3, 3)\n\tfor i in range(3):\n\t\tprint(' '.join(map(str, res[i])))\n", "from sys import stdin, stdout\n\ndef outputmatrix(k):\n\tif k == 0:\n\t\tstdout.write('1 1\\n')\n\t\tstdout.write('1\\n')\n\t\treturn\n\tm = 1\n\twhile m <= k:\n\t\tm *= 2\n\tl = m - 1\n\to = l - k\n\tn = l + m\n\tr1 = [n, l, l, 0]\n\tr2 = [m, 0, l, o]\n\tr3 = [m, m, n, l]\n\tstdout.write('3 4\\n')\n\tstdout.write(' '.join(map(str, r1)) + '\\n')\n\tstdout.write(' '.join(map(str, r2)) + '\\n')\n\tstdout.write(' '.join(map(str, r3)) + '\\n')\nk = int(stdin.readline())\noutputmatrix(k)\n", "k = int(input())\nif k == 0:\n\tprint('1 1')\n\tprint('300000')\nelse:\n\tprint('3 2')\n\ta = int(1 << 17)\n\tprint('%d %d' % (a + k, k))\n\tprint('%d %d' % (a, a + k))\n\tprint('%d %d' % (a, k))\n", "k = int(input())\nif k == 0:\n\tprint('1 1\\n1')\nelse:\n\tprint('3 2')\n\tupper = 1\n\twhile upper <= k:\n\t\tupper = upper * 2\n\tprint(upper + k, k)\n\tprint(upper, upper * 2 - 1)\n\tprint(0, k)\n", "k = int(input())\nn = 2 ** 17\nif k == 0:\n\tprint('{} {}'.format(1, 1))\n\tprint(k)\nelse:\n\tprint('{} {}'.format(2, 3))\n\tprint('{} {} {}'.format(n + k, k, n))\n\tprint('{} {} {}'.format(n, n + k, k))\n", "k = int(input())\nc = 0\nwhile k + 1 >= 2 ** c:\n\tc += 1\nholder = k + 1\nif (k + 1) % 2 == 0:\n\tholder = k + 2\nsolution = [[2 ** (c + 1) - 1, holder, 1], [2 ** c, k + 1, 1], [2 ** c, 2 ** c + holder, holder]]\nprint('3 3')\nfor i in range(3):\n\tprint(' '.join(map(str, solution[i])))\n", "import sys\ninput = sys.stdin.readline\ninputi = lambda : map(int, input().split())\nfrom math import *\nfrom bisect import *\nfrom functools import reduce, lru_cache\nfrom collections import Counter, defaultdict\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\td = k.bit_length()\n\tt = (1 << d + 1) - 1\n\tl = [[t, k, 0], [1 << d, t, k]]\n\tt = 1 << d + 1\n\tprint(2, 3)\n\tprint(*l[0])\n\tprint(*l[1])\n", "i = 0\nts = [1]\nwhile ts[-1] <= 10 ** 5:\n\ti += 1\n\tts.append(2 ** i)\n\ndef slv(k):\n\tif k == 0:\n\t\tprint(1, 1)\n\t\tprint(1)\n\t\treturn\n\tt = 0\n\tfor i in ts:\n\t\tif i > k:\n\t\t\tt = i\n\t\t\tbreak\n\tt = t * 2 - 1\n\tprint(3, 3)\n\tprint(t, k, t)\n\tprint(t - k, t - k, t)\n\tprint(t, t, k)\nk = int(input())\nslv(k)\n", "k = int(input())\np = 1\nwhile p <= k:\n\tp *= 2\nprint(2, 3)\nprint(p + k, k, 0)\nprint(p, p * 2 - 1, k)\n", "k = int(input())\nb = 1 << k.bit_length()\nprint(3, 4)\nprint(*[k + b, k, k, 0])\nprint(*[b, 0, k, 0])\nprint(*[b, b, k + b, k])\n", "import sys\ninput = lambda : sys.stdin.readline().rstrip()\nk = int(input())\nn = k.bit_length()\nprint(3, 4)\nprint(2 ** n + k, k, k, 0)\nprint(2 ** n, 0, k, 0)\nprint(2 ** n, 2 ** n, 2 ** n + k, k)\n", "k = int(input())\ns = k.bit_length()\nprint(2, 3)\nprint(2 ** s + k, k, 0)\nprint(2 ** s, 2 ** s + k, k)\n", "from sys import stdin, stdout\nfrom math import gcd, sqrt, factorial, pi, inf\nfrom collections import deque, defaultdict\nfrom bisect import bisect, bisect_left\nfrom time import time\nfrom itertools import permutations as per\nfrom heapq import heapify, heappush, heappushpop\ninput = stdin.readline\nR = lambda : map(int, input().split())\nI = lambda : int(input())\nS = lambda : input().rstrip('\\r\\n')\nL = lambda : list(R())\nP = lambda x: stdout.write(str(x) + '\\n')\nlcm = lambda x, y: x * y // gcd(x, y)\nnCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N\ninv = lambda x: pow(x, N - 2, N)\nsm = lambda x: (x ** 2 + x) // 2\nN = 10 ** 9 + 7\na = 'z y 0\\nx y 0\\nx z y'\nn = I()\nif not n:\n\tprint(1, 1)\n\tprint(1)\n\texit()\np = 1\nwhile p <= n:\n\tp <<= 1\nz = str(n + p)\ny = str(n)\nx = str(p)\nprint(3, 3)\nprint(a.replace('z', z).replace('x', x).replace('y', y))\n", "I = lambda : list(map(int, input().split()))\n(n,) = I()\nx = 2 ** 17\nprint(2, 3)\nprint(x + n, x, 0)\nprint(n, x + n, n)\n", "k = int(input(''))\nprint('2 3')\na = 2 ** 17 + k\nb = 2 ** 17\nx = k\nc = 2 ** 18 - 1\nd = k\ne = 0\nprint(str(a) + ' ' + str(b) + ' ' + str(e))\nprint(str(x) + ' ' + str(c) + ' ' + str(d))\n", "import sys\nfrom math import log2, floor, ceil, sqrt\nRi = lambda : [int(x) for x in sys.stdin.readline().split()]\nri = lambda : sys.stdin.readline().strip()\n\ndef input():\n\treturn sys.stdin.readline().strip()\n\ndef list2d(a, b, c):\n\treturn [[c] * b for i in range(a)]\n\ndef list3d(a, b, c, d):\n\treturn [[[d] * c for j in range(b)] for i in range(a)]\n\ndef list4d(a, b, c, d, e):\n\treturn [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]\n\ndef ceil(x, y=1):\n\treturn int(-(-x // y))\n\ndef INT():\n\treturn int(input())\n\ndef MAP():\n\treturn map(int, input().split())\n\ndef LIST(N=None):\n\treturn list(MAP()) if N is None else [INT() for i in range(N)]\n\ndef Yes():\n\tprint('Yes')\n\ndef No():\n\tprint('No')\n\ndef YES():\n\tprint('YES')\n\ndef NO():\n\tprint('NO')\nINF = 10 ** 18\nMOD = 10 ** 9 + 7\nk = int(ri())\nprint(2, 3)\nprint(2 ** 17 + k, k, 0)\nprint(2 ** 17, 2 ** 17 + k, k)\n", "k = int(input())\nmaxx = 262143\nprint(3, 4)\nprint(maxx, maxx, maxx, 0)\nprint(maxx ^ k, 0, k, 0)\nprint(maxx, maxx, maxx, k)\n", "import sys\nline = sys.stdin.readline()\nn = int(line.strip())\n\ndef solve(n):\n\tif n == 0:\n\t\tprint('1 1')\n\t\tprint('1')\n\t\treturn\n\tprint('3 3')\n\tarr = [[0 for _ in range(3)] for _ in range(3)]\n\tp = len(bin(n)[2:])\n\tarr[0][0] = 2 ** (p + 1) - 1\n\tarr[0][1] = 2 ** (p + 1) - 1\n\tarr[1][0] = 2 ** (p + 1) - 1\n\tarr[1][2] = 2 ** (p + 1) - 1\n\tarr[2][1] = 2 ** (p + 1) - 1\n\tarr[1][1] = 2 ** p - 1\n\tarr[2][2] = 2 ** p - 1\n\tsmall = 2 ** (p + 1) - 1 - n\n\tarr[0][2] = small\n\tarr[2][0] = small\n\tfor i in range(3):\n\t\tprint(' '.join(map(str, arr[i])))\nsolve(n)\n", "printn = lambda x: print(x, end='')\ninn = lambda : int(input())\ninl = lambda : list(map(int, input().split()))\ninm = lambda : map(int, input().split())\nins = lambda : input().strip()\nDBG = True\nBIG = 10 ** 18\nR = 10 ** 9 + 7\n\ndef ddprint(x):\n\tif DBG:\n\t\tprint(x)\nk = inn()\nif k == 0:\n\tprint('1 1')\n\tprint(3)\n\texit()\nq = 2 ** 17\nprint('3 4')\nprint('{} {} {} {}'.format(q + k, k, k, 0))\nprint('{} {} {} {}'.format(q, 0, k, 0))\nprint('{} {} {} {}'.format(q, q, q + k, k))\n", "import math\ni = input()\nn = 2 ** (int(math.log(int(i) + 1, 2)) + 1)\nprint('2 3')\nprint(str(2 * n - 1) + ' ' + str(n - 1) + ' 0')\nprint(str(n) + ' ' + str(2 * n - 1) + ' ' + i)\n", "k = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(0)\n\texit()\nmaxx = 3 * 10 ** 5\nfor a in range(1, maxx):\n\tif a + k <= maxx and a + k & a == a:\n\t\tr = a + k\n\t\tm = r + 1\n\t\tp = m | r\n\t\tif r & m < a:\n\t\t\tprint(3, 4)\n\t\t\tprint(p, r, r, r)\n\t\t\tprint(m, 0, r, a)\n\t\t\tprint(p, p, p, r)\n\t\t\texit()\n", "from collections import Counter\nimport bisect\nimport sys\ninput = sys.stdin.readline\n\ndef solve(k):\n\ta = 2 ** (len(bin(k)) - 2)\n\tb = 2 * a - 1\n\tprint(2, 3)\n\tprint(b, k, 0)\n\tprint(a, b, k)\n\ndef main():\n\tk = int(input())\n\tsolve(k)\nmain()\n", "k = int(input())\nmatrix = [[262143, k, k, 0], [131072, 0, k, 0], [131072, 262143, 262143, k]]\nprint('3 4')\nfor x in matrix:\n\tprint(*x)\n", "def pow(base, exp):\n\tres = 1\n\twhile exp > 0:\n\t\tif exp % 2:\n\t\t\tres = res * base\n\t\texp //= 2\n\t\tbase = base * base\n\treturn res\n\ndef main():\n\tmaxi = pow(2, 18)\n\tk = int(input())\n\ta = [[] for i in range(4)]\n\ta[0] = [maxi - 1 for i in range(4)]\n\ta[1] = [maxi // 2, maxi // 2, maxi // 2 - 1, maxi]\n\ta[2] = [maxi - 1, maxi - 1, maxi - 1, k]\n\tprint(3, 4)\n\tfor i in a:\n\t\tprint(*i)\n\treturn\nmain()\n", "a = int(input())\nx = 131072\nprint(2, 3)\nprint(x + a, x, 0)\nprint(a, x + a, a)\n", "k = int(input())\nif k != 0:\n\tprint(3, 3)\n\tprint(2 ** 18 - 1, 2 ** 18 - 1 - k, 2 ** 18 - 1 - k)\n\tprint(k, k, 2 ** 18 - 1)\n\tprint(2 ** 18 - 1 - k, 2 ** 18 - 1 - k, k)\nelse:\n\tprint(1, 1)\n\tprint(300000)\n", "k = int(input())\nprint(3, 4)\nprint(262143, k, k, 0)\nprint(131072, 0, k, 0)\nprint(131072, 131072, 262143, 131071)\n", "k = int(input())\nsz = 1\nwhile sz <= k:\n\tsz *= 2\nprint(2, 3)\nprint(k + sz, sz, sz)\nprint(k, k + sz, k)\n", "a = int(input())\np = 1\nwhile p <= a:\n\tp *= 2\nprint(3, 3)\nprint(p + a, a, 0)\nprint(p, a, 0)\nprint(p + a, p + a, a)\n", "k = int(input())\nans = [[0] * 3 for _ in range(3)]\nans[0][0] = 2 ** 18 - 1\nans[0][1] = 2 ** 17\nans[1][0] = 2 ** 17 - 1\nans[1][1] = 2 ** 18 - 1\nans[1][2] = k\nans[2][1] = k\nans[2][2] = k\nprint(3, 3)\nfor ans_i in ans:\n\tprint(*ans_i)\n", "from bisect import bisect_left as bl, bisect_right as br, insort\nimport sys\nimport heapq\nfrom collections import defaultdict as dd, deque\n\ndef data():\n\treturn sys.stdin.readline().strip()\n\ndef mdata():\n\treturn map(int, data().split())\nk = int(data())\nx = len(bin(k)[2:])\nt = pow(2, x)\nm = [[k + t, k + t, k + t, t], [k + t, k, k, k + t], [t, k + t, k + t, k]]\nprint(3, 4)\nfor i in range(3):\n\tprint(*m[i])\n", "k = int(input())\nmx18 = (1 << 18) - 1\nmx17 = (1 << 17) - 1\nprint(2, 3)\nprint(mx18, k, mx17 + 1)\nprint(mx17 + 1, mx18, mx17)\n", "import math\nk = input()\nk = int(k)\nbine = bin(k)\nn = int(len(bine) - 1)\nn = 2 ** (n - 1)\nprint(2, 3)\nprint(n + k, k, n)\nprint(n, n + k, k)\n", "def getMaxBinOnes(n):\n\tf = n\n\tb = 1\n\twhile b < n:\n\t\tn = n | b\n\t\tb *= 2\n\tb *= 2\n\treturn (b - 1, b - 1 - f)\nk = int(input())\n(bait, trap) = getMaxBinOnes(k)\nmatrix = []\nmatrix.append([bait, bait, bait, 0])\nmatrix.append([trap, 0, k, 0])\nmatrix.append([bait, bait, bait, k])\nif k == 0:\n\tmatrix = [[2, 2, 2, 2], [2, 2, 2, 2], [2, 2, 2, 2]]\nelif k == 1:\n\tmatrix = [[7, 7, 7, 0], [4, 0, 1, 0], [7, 7, 7, 1]]\nprint('3 4')\nfor row in matrix:\n\tfor i in row:\n\t\tprint(i, end=' ')\n\tprint()\n", "from math import *\nk = int(input())\nd = 0\nb = 0\nx = [int(i) for i in bin(k)[2:]]\nx.reverse()\nd = 2 ** len(x)\nx = d * 2 - 1\ne = d * 2 - 1\nb = k\nf = k\nc = 0\nn = 2\nm = 3\nprint(n, m)\nprint(x, b, c)\nprint(d, e, f)\n", "k = int(input())\nif k < k ^ 2 ** 18 - 1:\n\tk ^= 2 ** 18 - 1\nprint(2, 3)\nprint(2 ** 18 - 1, k ^ 2 ** 18 - 1, k)\nprint(k, 2 ** 18 - 1, k ^ 2 ** 18 - 1)\n", "k = int(input())\nprint(3, 2)\nprint(262143, k)\nprint(262143 ^ k, 262143)\nprint(262143 ^ k, k)\n", "def findpow2(integer):\n\tpow2 = 1\n\twhile pow2 <= integer:\n\t\tpow2 *= 2\n\treturn pow2\nk = int(input())\nB = findpow2(k)\nA = 2 * B\nprint(3, 3)\nprint(A - 1, A - 1, B - 1)\nprint(A - 1, B, A - 1)\nprint(B - 1, A - 1, k)\n", "k = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\tst2 = 1\n\tprint(3, 4)\n\twhile st2 <= k:\n\t\tst2 *= 2\n\ta = [[0] * 4 for i in range(3)]\n\ta = [[2 * st2 - 1, st2 - 1, st2 - 1, 0], [2 * st2 - 1 - k, 0, st2 - 1, 0], [2 * st2 - 1, 2 * st2 - 1, 2 * st2 - 1, st2 - 1]]\n\tfor i in a:\n\t\tprint(*i)\n", "import sys\nreadline = sys.stdin.readline\nK = int(readline())\nJ = 1 << K.bit_length()\nprint(3, 4)\nprint(K + J, K, K, 0)\nprint(J, 0, K, 0)\nprint(J, J, J + K, K)\n", "n = int(input())\nk = len(bin(n)) - 2\nA = [2 ** (k + 1) - 1, 2 ** (k + 1) - 1, 2 ** k]\nB = [2 ** (k + 1) - 1, n, 2 ** (k + 1) - 1]\nC = [2 ** k, 2 ** (k + 1) - 1, n]\nprint(3, 3)\nprint(*A)\nprint(*B)\nprint(*C)\n", "K = int(input())\na = 2 ** 18 - 1\nb = 2 ** 17\nc = 2 ** 17 - 1\nprint(3, 4)\nprint(a, a, b, b)\nprint(b, K, c, b)\nprint(b, b, a, c)\n", "from math import log\nk = int(input())\nprint(2, 3)\nif k >= 1:\n\tx = int(pow(2, int(log(k, 2)) + 1))\n\ty = 2 * x - 1\nelse:\n\tx = 1\n\ty = 2 * x - 1\nlst = [[y, x, y], [k, y, k]]\nfor i in lst:\n\tprint(*i)\n", "k = int(input())\nprint(3, 4)\ninf = 2 ** 18 - 1\nx = inf ^ k\ny = inf >> 1\npattern = [[inf, inf, inf, 0], [inf, 0, y, 0], [inf, x, inf, y]]\nfor i in range(3):\n\tprint(*pattern[i])\n", "k = int(input())\nmx = (1 << 18) - 1\nll = 1 << 17\nprint('2 3')\nprint(mx, k, 0)\nprint(ll, mx, k)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nimport heapq as h\nfrom bisect import bisect_left, bisect_right\nfrom types import GeneratorType\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\timport os\n\t\tself.os = os\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tself.os.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom collections import defaultdict as dd, deque as dq\nimport math, string\n\ndef getInts():\n\treturn [int(s) for s in input().split()]\n\ndef getInt():\n\treturn int(input())\n\ndef getStrs():\n\treturn [s for s in input().split()]\n\ndef getStr():\n\treturn input()\n\ndef listStr():\n\treturn list(input())\nMOD = 10 ** 9 + 7\n\ndef solve():\n\tK = getInt()\n\tprint(3, 2)\n\tprint(2 ** 17 + K, K)\n\tprint(2 ** 17, 2 ** 17 + K)\n\tprint(0, K)\n\treturn\nsolve()\n", "k = int(input())\ns = bin(k)[2:]\nprint(2, 3)\nprint(int('1' + s, 2), k, 0)\nprint(int('1' + '0' * len(s), 2), int('1' + s, 2), k)\n", "import math\nimport sys\nk = int(input())\none = 2 ** 17\nans = [[k + one, k], [one, k + one], [k, k]]\nprint('3 2')\nfor line in ans:\n\tprint(' '.join(map(str, line)))\n", "k = int(input())\nprint(2, 3)\ne = 1 << 17\nprint(e + k, e, 0)\nprint(k, e + k, k)\n", "k = int(input())\nprint(3, 4)\nx = 131071 - k\nprint(262143, 131071, 131071, x)\nprint(131072, 262144, 131071, x)\nprint(262143, 262143, 262143, 131071)\n", "k = int(input())\nallone = 2 ** 18 - 1\nprint(3, 2)\nprint(allone, k)\nprint(2 ** 17, allone)\nprint(allone, allone - 2 ** 17)\n", "from sys import stdin\nfrom collections import deque\nmod = 10 ** 9 + 7\nimport sys\nimport random\nsys.setrecursionlimit(10 ** 6)\nfrom queue import PriorityQueue\nfrom bisect import bisect_right\nfrom bisect import bisect_left\nfrom collections import defaultdict\nfrom math import sqrt, factorial, gcd, log2, inf, ceil\nimport heapq\ninput = lambda : sys.stdin.readline().rstrip()\nfrom sys import stdin, stdout\nfrom heapq import heapify, heappush, heappop\nfrom itertools import permutations\nfrom math import factorial as f\n\ndef ncr(n, r, p):\n\tnum = den = 1\n\tfor i in range(r):\n\t\tnum = num * (n - i) % p\n\t\tden = den * (i + 1) % p\n\treturn num * pow(den, p - 2, p) % p\nfor _ in range(10 ** 5):\n\tpass\nfor _ in range(10 ** 5):\n\tpass\ng = int(input())\nif g == 0:\n\tprint(1, 1)\n\tprint(0)\nelse:\n\tcnt = 1\n\twhile cnt <= g:\n\t\tcnt *= 2\n\tres = [[0 for i in range(3)] for j in range(3)]\n\tmx = pow(2, 18) - 1\n\tres[0][2] = res[2][0] = cnt\n\tres[1][2] = res[2][1] = mx\n\tres[0][0] = res[0][1] = res[1][0] = mx\n\tres[2][2] = res[1][1] = g\n\tprint(3, 3)\n\tfor i in range(3):\n\t\tprint(' '.join(map(str, res[i])))\n", "k = int(input())\nbits = bin(k)[2:]\ntop = int('1' * (len(bits) + 1), 2)\nleft = int('1' + '0' * len(bits), 2)\nprint(2, 3)\nprint(top, k, 0)\nprint(left, top, k)\n", "k = int(input())\nlis = [[0] * 4 for i in range(3)]\na = 1 << 17\nlis[0][0] = a + k\nlis[0][1] = k\nlis[0][2] = k\nlis[0][3] = 0\nlis[1][0] = a\nlis[1][1] = 1\nlis[1][2] = k\nlis[1][3] = 0\nlis[2][0] = a\nlis[2][1] = a\nlis[2][2] = k + a\nlis[2][3] = k\nprint(3, 4)\nfor i in lis:\n\tprint(*i)\n", "standard_input = '94619'\nk = int(input())\nv = 1\nwhile k >= v:\n\tv *= 2\nm = v * 2 - 1\nif k == 0:\n\tprint('1 1\\n0')\nelse:\n\tprint('3 3')\n\tprint('%i %i 0' % (m, k))\n\tprint('%i %i %i' % (v, m, k))\n\tprint('0 %i %i' % (k, m))\n", "import math\nk = input()\nk = int(k)\nif k == 0:\n\tn = 2\nelse:\n\tn = math.log(k, 2)\n\tn = int(n)\n\tn = n + 2\nn = 2 ** (n - 1)\nprint(2, 3)\nprint(n + k, k, n)\nprint(n, n + k, k)\n", "k = int(input())\nk_ = int('1' + '0' * (len(bin(k)) - 2), 2)\nk_or = k_ | k\nprint('3 3')\nprint(str(k_or) + ' ' + str(k_) + ' ' + str(k_))\nprint(str(k) + ' ' + str(k_) + ' ' + str(k_))\nprint(str(k) + ' ' + str(k_or) + ' ' + str(k))\n", "k = int(input())\nstart = 2\nwhile start - 1 <= k:\n\tstart *= 2\nprint(2, 3)\nprint(start * 2 - 1, start, start)\nprint(k, start + k, k)\n", "n = int(input())\nprint(2, 3)\nprint(131072 + n, 131072, 0)\nprint(n, 131072 + n, n)\n", "k = int(input())\nprint(2, 3)\nprint(262143, k, 0)\nprint(131072, 262143, 131071)\n", "from math import ceil, sqrt, log, gcd\n\ndef ii():\n\treturn int(input())\n\ndef si():\n\treturn input()\n\ndef mi():\n\treturn map(int, input().split())\n\ndef li():\n\treturn list(mi())\nn = ii()\nx = 2 ** 17\nprint(2, 3)\nprint(x ^ n, x, 0)\nprint(n, x ^ n, n)\n", "k = int(input())\nmaxx = 262143\nprint(2, 3)\nprint(maxx, k, 0)\nprint(maxx ^ k, maxx, k)\n", "import io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nimport sys\nprint = sys.stdout.write\nk = int(input())\nx = 2 ** 17\nprint('2 3\\n')\nprint(str(x + k) + ' ' + str(x) + ' ' + str(0) + '\\n')\nprint(str(k) + ' ' + str(x + k) + ' ' + str(k))\n", "k = int(input().strip())\nprint('2 3')\nprint('{} {} {}'.format((2 << 16) + k, k, 0))\nprint('{} {} {}'.format(2 << 16, (2 << 16) + k, k))\n", "import atexit\nimport io\nimport sys\n_INPUT_LINES = sys.stdin.read().splitlines()\ninput = iter(_INPUT_LINES).__next__\n_OUTPUT_BUFFER = io.StringIO()\nsys.stdout = _OUTPUT_BUFFER\n\n@atexit.register\ndef write():\n\tsys.__stdout__.write(_OUTPUT_BUFFER.getvalue())\nimport math\nk = int(input())\nif k == 0:\n\tprint(1, 1)\n\tprint(1)\nelse:\n\tn = int(math.ceil(math.log(k, 2)))\n\tif 2 ** n == k:\n\t\tn += 1\n\ta = 2 ** n\n\tb = k\n\tprint('3 3')\n\tprint('{} {} {}'.format(a + b, a, 0))\n\tprint('{} {} {}'.format(b, a, 0))\n\tprint('{} {} {}'.format(b, a + b, b))\n", "import sys\ninput = sys.stdin.readline\nk = int(input())\nbase = 1\nnk = base + k\nwhile k != 0 and base | nk == nk:\n\tbase <<= 1\n\tnk = base + k\nbig = 1 << 17\nprint('3 2')\nprint('{} {}'.format(big | base | nk, nk))\nprint('{} {}'.format(big | base, big | base | nk))\nprint('{} {}'.format(0, base | nk))\n", "k = int(input())\nb = k.bit_length()\nall_1 = (1 << b + 1) - 1\nfirst_1 = 1 << b\nother_1 = first_1 - 1\na = [[all_1, first_1, 0], [other_1, all_1, k]]\nprint(2, 3)\nfor row in a:\n\tprint(*row)\n"]

source: codeforces

raw_problem:
D. Walk on Matrix

time limit per test
2 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

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!

Input

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

Output

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.

Examples

Input

0

Output

1 1
300000

Input

1

Output

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

Note

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

question:
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.
 ![image](1.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!

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

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

Examples
Input
0

Output
1 1
300000

Input
1

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

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

tags: ['Bit manipulation', 'Mathematics', 'Constructive algorithms']

skill_types: ['Bit manipulation']

raw_tags: ['bitmasks', 'math', 'constructive algorithms']

data_split: test


One-Stroke Sketch

source: 20th PC Koshien, Final

raw_problem:
一筆書き

  PCK君が画用紙に絵を描いている。PCK君は以下のように絵を描く。

一回の動作で、１つの線分を描く。

既に描かれている線分に触れる場合は、お互いの端点だけで重なる。

この動作を繰り返すと、画用紙にはいくつかの図形が現れる。ここでは、連結した線分のグループを１つの図形とする。たとえば、図(a)には、それぞれ５本と１本の線分からなる２つの図形が描かれている。図(a)に1本の線分を追加して図(b)のように描くと、７本の線分からなる１つの図形になる。

画用紙に描かれている図形の中で、一筆書きが可能なものはいくつあるだろうか？一筆書きとは、筆記具を画用紙から一度も離さず、同じ線を二度なぞらずに線図形を描くことである。ただし、同じ端点を何回通っても構わない。たとえば、図の(a)、(b)、(c)の順に描いていったとき、それぞれで一筆書きが可能な図形は、２個、０個、１個ある。

PCK君が線分を描く動作の情報が順番に与えられる。動作が終わるごとに、画用紙に含まれる一筆書きが可能な図形の数を報告するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$
$segment_1$
$segment_2$
:
$segment_N$

１行目に、線分の数$N$ ($1 \leq N \leq 200,000$)が与えられる。続く$N$行に、$i$番目の動作で描く線分の情報が与えられる。ただし、同じ線分が与えられることはない。各線分は以下の形式で与えられる。

$x_1$ $y_1$ $x_2$ $y_2$

線分の始点の座標$x_1$, $y_1$ ($0 \leq x_1,y_1 \leq 1,000,000,000$)と終点の座標$x_2$, $y_2$ ($0 \leq x_2, y_2 \leq 1,000,000,000$)が整数で与えられる。ただし、始点と終点の座標が同じものが与えられることはない（$x_1 \ne x_2$ または $y_1 \ne y_2$）。

出力

各動作の後に、一筆書きが可能な図形の個数を１行に出力する。

入出力例

入力例

8
5 0 8 3
5 6 2 3
10 5 10 1
2 3 5 0
5 0 5 6
8 3 5 6
8 3 10 1
10 5 8 3

出力例

1
2
3
2
2
2
0
1

source: aizu

question:
One Stroke Drawing

PCK-kun is drawing on a piece of drawing paper. PCK-kun draws pictures in the following way.

- With one action, he draws one line segment.
- If the drawn line segment touches an already drawn line segment, they overlap only at their endpoints.

![image](1.png)

Repeating this action, several shapes appear on the drawing paper. Here, a group of connected line segments is considered one shape. For example, in figure (a), there are two shapes drawn, each consisting of five and one line segments, respectively. If you add one line segment to figure (a) to make it look like figure (b), it becomes one shape consisting of seven line segments.

Among the shapes drawn on the drawing paper, how many can be drawn with one stroke? One stroke drawing means drawing the line shape without lifting the writing instrument from the paper once and without tracing the same line twice. However, it doesn't matter how many times the same endpoint is passed through. For example, when drawn in the order of figure (a), (b), and (c), the number of shapes that can be drawn with one stroke is two, zero, and one, respectively.

The information about PCK-kun’s actions of drawing line segments is given in order. Create a program that reports the number of one-stroke drawable shapes contained on the drawing paper after each action.

Input

The input is given in the following format.

$N$
$segment_1$
$segment_2$
:
$segment_N$

In the first line, the number of line segments $N$ ($1 \leq N \leq 200,000$) is given. The following $N$ lines provide information about the line segment to be drawn in the $i$th action. The same line segment will not be given more than once. Each line segment is given in the following format.

$x_1$ $y_1$ $x_2$ $y_2$

The coordinates of the starting point of the line segment $x_1$, $y_1$ ($0 \leq x_1, y_1 \leq 1,000,000,000$) and the coordinates of the end point $x_2$, $y_2$ ($0 \leq x_2, y_2 \leq 1,000,000,000$) are given as integers. However, segments with the same start and end coordinates will not be provided (i.e., $x_1 \ne x_2$ or $y_1 \ne y_2$).

Output

After each action, output the number of one-stroke drawable shapes on one line.

Input/Output Examples
Input example

8
5 0 8 3
5 6 2 3
10 5 10 1
2 3 5 0
5 0 5 6
8 3 5 6
8 3 10 1
10 5 8 3

Output example

1
2
3
2
2
2
0
1

data_split: test