A. Subrectangle Guess

problem_index: A

time_limit: 1 second

memory_limit: 256 megabytes

solutions: ["import sys\nt = int(sys.stdin.readline())\nfor _ in range(t):\n\t(n, m) = map(int, sys.stdin.readline().split())\n\tL = []\n\tfor i in range(n):\n\t\tL.append(list(map(int, sys.stdin.readline().split())))\n\t(i1, j1) = (0, 0)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif L[i][j] > L[i1][j1]:\n\t\t\t\t(i1, j1) = (i, j)\n\tprint(max(i1 + 1, n - i1) * max(j1 + 1, m - j1))\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\ta = [list(map(int, input().split())) for _ in range(n)]\n\t(mn, argmn) = (-10 ** 10, None)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] > mn:\n\t\t\t\tmn = a[i][j]\n\t\t\t\targmn = (i, j)\n\t(r, c) = argmn\n\tlr = max(c, m - c - 1)\n\ttb = max(r, n - r - 1)\n\tprint((lr + 1) * (tb + 1))\n", "import sys\ninput = sys.stdin.readline\n\ndef solve():\n\t(n, m) = map(int, input().split())\n\tarr = [list(map(int, input().split())) for _ in range(n)]\n\tv = -float('inf')\n\tpoint = [0, 0]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] > v:\n\t\t\t\tv = arr[i][j]\n\t\t\t\tpoint = [i, j]\n\treturn max(point[0] + 1, n - point[0]) * max(point[1] + 1, m - point[1])\nfor _ in range(int(input())):\n\tprint(solve())\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tbo = []\n\tfor i in range(n):\n\t\tbo.append(list(map(int, input().split())))\n\tmaxi = (-99 ** 99, (-1, -1))\n\tfor i in range(n):\n\t\tmaxi = max(maxi, (max(bo[i]), (i, bo[i].index(max(bo[i])))))\n\t(r, c) = maxi[1]\n\tprint(max(r + 1, n - r) * max(c + 1, m - c))\n", "from os import error\nimport sys\ninput = sys.stdin.readline\nDEBUG = False\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 list(s[:len(s) - 1])\n\ndef invr():\n\treturn map(int, input().split())\n\ndef solve():\n\t(n, m) = inlt()\n\t(max_, pi, pj) = (-10 ** 9 - 3, 0, 0)\n\tfor i in range(n):\n\t\trow = inlt()\n\t\tfor j in range(m):\n\t\t\tif max_ < row[j]:\n\t\t\t\t(max_, pi, pj) = (row[j], i, j)\n\tpi += 1\n\tpj += 1\n\tsq1 = pi * pj\n\tsq2 = pi * (m - pj + 1)\n\tsq3 = (n - pi + 1) * pj\n\tsq4 = (n - pi + 1) * (m - pj + 1)\n\treturn max([sq1, sq2, sq3, sq4])\nq = inp()\nfor t in range(q):\n\tans = solve()\n\tprint(ans)\n", "def num():\n\tc = int(input())\n\treturn c\n\ndef stri():\n\tc = str(input())\n\treturn c\n\ndef vector():\n\tc = list(map(int, input().split()))\n\treturn c\n\ndef strvector():\n\tc = list(map(str, input().split()))\n\treturn c\nimport math\n\ndef isprime(num):\n\ta = 2\n\twhile a <= math.sqrt(num):\n\t\tif num % a < 1:\n\t\t\treturn False\n\t\ta = a + 1\n\treturn num > 1\nt = num()\nwhile t > 0:\n\tt -= 1\n\t(n, m) = vector()\n\tarr = []\n\tfor i in range(n):\n\t\tc = vector()\n\t\tarr.append(c)\n\t(x, y) = (0, 0)\n\tmaxi = float('-inf')\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] > maxi:\n\t\t\t\tmaxi = arr[i][j]\n\t\t\t\t(x, y) = (i + 1, j + 1)\n\ta = max(m - y + 1, y)\n\tb = max(n - x + 1, x)\n\tprint(a * b)\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nout = []\nfor _ in range(t):\n\t(n, m) = [int(x) for x in input().split()]\n\tarr = []\n\tmax_ = -float('inf')\n\tcoords = []\n\tfor y in range(n):\n\t\tarr.append([int(x) for x in input().split()])\n\t\tfor x in range(m):\n\t\t\tif arr[y][x] > max_:\n\t\t\t\tmax_ = arr[y][x]\n\t\t\t\tcoords = [y, x]\n\tout.append(str(max(coords[0] + 1, n - coords[0]) * max(coords[1] + 1, m - coords[1])) + '\\n')\nprint(''.join(out))\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor _ in range(n):\n\t\ta.append(list(map(int, input().split())))\n\tma = a[0][0]\n\t(x, y) = (0, 0)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] > ma:\n\t\t\t\tma = a[i][j]\n\t\t\t\t(x, y) = (i, j)\n\tprint(max(x + 1, n - x) * max(y + 1, m - y))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor i in range(n):\n\t\tb = list(map(int, input().split()))\n\t\ta += [b]\n\tc = []\n\tfor i in range(n):\n\t\tc += [max(a[i])]\n\tx = c.index(max(c))\n\ty = a[x].index(max(c))\n\th = max(x + 1, n - x)\n\tw = max(y + 1, m - y)\n\tprint(h * w)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\ta = (0, 0)\n\tmaxc = (-10 ** 10, 0, 0)\n\tfor i in range(n):\n\t\tx = list(map(int, input().split()))\n\t\tfor j in range(m):\n\t\t\tif maxc[0] < x[j]:\n\t\t\t\tmaxc = [x[j], i + 1, j + 1]\n\th = max(maxc[1], n - maxc[1] + 1)\n\tw = max(maxc[2], m - maxc[2] + 1)\n\tprint(h * w)\n", "for i in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tma = -1000000002\n\tfor j in range(n):\n\t\ta.append(list(map(int, input().split())))\n\tfor j in range(n):\n\t\tfor k in range(m):\n\t\t\tif a[j][k] > ma:\n\t\t\t\tma = a[j][k]\n\t\t\t\tr = j\n\t\t\t\tc = k\n\th = max(r + 1, n - r)\n\tw = max(c + 1, m - c)\n\tprint(h * w)\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmm = -1000000001\n\t(x, y) = (0, 0)\n\tfor i in range(n):\n\t\ta = [int(i) for i in input().split()]\n\t\taa = max(enumerate(a), key=lambda x: x[1])\n\t\tif aa[1] > mm:\n\t\t\ty = i + 1\n\t\t\tx = aa[0] + 1\n\t\t\tmm = aa[1]\n\tprint(max(x, m + 1 - x) * max(y, n + 1 - y))\n", "t = int(input())\nfor _ in range(t):\n\tmx = -10 ** 9 - 1\n\tmxi = 0\n\tmxj = 0\n\t(n, m) = map(int, input().split())\n\tfor i in range(n):\n\t\ta = [int(i) for i in input().split()]\n\t\tif max(a) > mx:\n\t\t\tmx = max(a)\n\t\t\tmxi = i\n\t\t\tmxj = a.index(max(a))\n\tl = max(m - 1 - mxj, mxj) + 1\n\ts = max(n - 1 - mxi, mxi) + 1\n\tprint(s * l)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tz = []\n\tfor i in range(n):\n\t\tz.append(list(map(int, input().split())))\n\tmx = float('-inf')\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif z[i][j] > mx:\n\t\t\t\tmx = z[i][j]\n\t\t\t\tix = i\n\t\t\t\tiy = j\n\tx = max(ix + 1, n - ix)\n\tb = max(iy + 1, m - iy)\n\tprint(x * b)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmax_idx = [0, 0]\n\tx = None\n\tfor i in range(n):\n\t\titr = list(map(int, input().split()))\n\t\tfor j in range(m):\n\t\t\tif x == None:\n\t\t\t\tx = itr[j]\n\t\t\tif itr[j] > x:\n\t\t\t\tmax_idx = [i, j]\n\t\t\t\tx = itr[j]\n\tprint(max(max_idx[1] + 1, m - max_idx[1]) * max(max_idx[0] + 1, n - max_idx[0]))\n", "def area(A, n, m):\n\trw = 0\n\tcl = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif A[i][j] >= A[rw][cl]:\n\t\t\t\trw = i\n\t\t\t\tcl = j\n\trw += 1\n\tcl += 1\n\tans = max(rw * cl, rw * (m - cl + 1), (n - rw + 1) * (m - cl + 1), (n - rw + 1) * cl)\n\treturn ans\ntests = int(input())\nfor _ in range(tests):\n\t(n, m) = map(int, input().split())\n\tA = []\n\tfor i in range(n):\n\t\tA.append(list(map(int, input().split())))\n\tprint(area(A, n, m))\n", "t = int(input())\nfor tt in range(t):\n\t(n, m) = map(int, input().split())\n\ta = [list(map(int, input().split())) for mm in range(n)]\n\tm1 = a[0][0]\n\tk = [0, 0]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] > m1:\n\t\t\t\tm1 = a[i][j]\n\t\t\t\tk = [i, j]\n\tprint(max(k[0] + 1, n - k[0]) * max(k[1] + 1, m - k[1]))\n", "for t in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmatrix = []\n\tfor i in range(n):\n\t\tmatrix.append(list(map(int, input().split())))\n\tcurmax = -10 ** 9\n\tindx = (0, 0)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif matrix[i][j] > curmax:\n\t\t\t\tcurmax = matrix[i][j]\n\t\t\t\tindx = (i, j)\n\t(i, j) = (indx[0], indx[1])\n\tprint(max(i + 1, n - i) * max(j + 1, m - j))\n", "MAX = 10 ** 9 + 1\nt = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tmat = []\n\tmx = -MAX\n\tmxIdx = (0, 0)\n\tfor i in range(n):\n\t\tmat.append(list(map(int, input().split())))\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] > mx:\n\t\t\t\tmxIdx = (i + 1, j + 1)\n\t\t\t\tmx = mat[i][j]\n\tif n == m == 1:\n\t\tprint(1)\n\telse:\n\t\tr = max(mxIdx[0], n - mxIdx[0] + 1)\n\t\tc = max(mxIdx[1], m - mxIdx[1] + 1)\n\t\tprint(r * c)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = list(map(int, input().split()))\n\tarr = []\n\tfor i in range(n):\n\t\tarr.append(list(map(int, input().split())))\n\tmaxx = -999999999999\n\tfor i in arr:\n\t\tfor k in i:\n\t\t\tmaxx = max(maxx, k)\n\t(indx, indy) = ([], [])\n\tfor i in range(len(arr)):\n\t\tfor k in range(len(arr[i])):\n\t\t\tif arr[i][k] == maxx:\n\t\t\t\tindx.append(i + 1)\n\t\t\t\tindy.append(k + 1)\n\tans = 99999999999\n\tfor i in range(len(indx)):\n\t\tans = min(ans, max(indx[i], n - indx[i] + 1) * max(m - indy[i] + 1, indy[i]))\n\tprint(ans)\n", "t = int(input())\nanss = []\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tmaxi = 0\n\tmaxi_loc = None\n\tfor i in range(n):\n\t\trow = list(map(int, input().split()))\n\t\tfor j in range(len(row)):\n\t\t\tif maxi_loc is None or row[j] > maxi:\n\t\t\t\tmaxi = row[j]\n\t\t\t\tmaxi_loc = (i, j)\n\tanss.append(max(maxi_loc[0] + 1, n - maxi_loc[0]) * max(maxi_loc[1] + 1, m - maxi_loc[1]))\n[print(ans) for ans in anss]\n", "t = int(input())\nwhile t:\n\t(n, m) = map(int, input().split())\n\tmatrix = []\n\tfor _ in range(n):\n\t\trow = list(map(int, input().split()))\n\t\tmatrix.append(row)\n\tcm = []\n\tM = float('-inf')\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif M < matrix[i][j]:\n\t\t\t\tcm = [i, j]\n\t\t\t\tM = matrix[i][j]\n\tmr = max(cm[0] + 1, n - cm[0])\n\tmc = max(cm[1] + 1, m - cm[1])\n\tans = mr * mc\n\tprint(ans)\n\tt = t - 1\n", "n = int(input())\nfor _ in range(n):\n\t(a, b) = map(int, input().split())\n\tq = [''] * a\n\tc = -100000000000.0\n\t(xx, yy) = (0, 0)\n\tfor i in range(a):\n\t\tw = list(map(int, input().split()))\n\t\tq[i] = w[:]\n\t\tc = max(c, max(w))\n\t\tif c == max(w):\n\t\t\txx = i\n\t\t\tyy = w.index(c)\n\tdx = max(xx, a - 1 - xx) + 1\n\tdy = max(yy, b - 1 - yy) + 1\n\tprint(dx * dy)\n", "for q in range(int(input())):\n\t(n, m) = [int(x) for x in input().split()]\n\tarr = []\n\tmx = -float('inf')\n\tfor i in range(n):\n\t\ttemp = [int(x) for x in input().split()]\n\t\tarr.append(temp)\n\t\tmx = max(mx, max(temp))\n\t(x, y) = (-1, -1)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] == mx:\n\t\t\t\t(x, y) = (i + 1, j + 1)\n\t\t\t\tbreak\n\tx = max(x, n - x + 1)\n\ty = max(y, m - y + 1)\n\tprint(x * y)\n", "for _ in range(int(input())):\n\t(a, b) = map(int, input().split())\n\tl = []\n\tfor i in range(a):\n\t\tl.append(list(map(int, input().split())))\n\tmaxi = -1000000000.0 - 1\n\t(x, y) = (0, 0)\n\tfor i in range(a):\n\t\tfor j in range(b):\n\t\t\tif l[i][j] > maxi:\n\t\t\t\tmaxi = l[i][j]\n\t\t\t\t(x, y) = (i, j)\n\tprint(max(a - x, x + 1) * max(b - y, y + 1))\n", "import math\n\ndef readArr():\n\treturn list(map(int, input().split()))\n\ndef readInt():\n\treturn int(input())\n\ndef solve():\n\t(n, m) = readArr()\n\tmaxi = -10 ** 9\n\t(x, y) = (-1, -1)\n\tfor i in range(n):\n\t\tcur = readArr()\n\t\tfor j in range(m):\n\t\t\tif cur[j] >= maxi:\n\t\t\t\t(x, y) = (i, j)\n\t\t\t\tmaxi = cur[j]\n\tprint(max(x + 1, n - x) * max(y + 1, m - y))\nt = readInt()\nfor i in range(t):\n\tsolve()\n", "t = int(input())\nfor TC in range(t):\n\t(n, m) = map(int, input().split())\n\tboard = []\n\tfor i in range(n):\n\t\tboard.append([int(x) for x in input().split()])\n\tmx = (0, 0)\n\tfor r in range(len(board)):\n\t\tfor c in range(len(board[r])):\n\t\t\tif board[r][c] > board[mx[0]][mx[1]]:\n\t\t\t\tmx = (r, c)\n\tprint(max(m - mx[1], mx[1] + 1) * max(n - mx[0], mx[0] + 1))\n", "import math\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tl = []\n\tmaxi = -math.inf\n\ti1 = 0\n\tj1 = 0\n\tfor i in range(n):\n\t\tl1 = list(map(int, input().split()))\n\t\tfor j in range(m):\n\t\t\tif l1[j] >= maxi:\n\t\t\t\tmaxi = l1[j]\n\t\t\t\ti1 = i\n\t\t\t\tj1 = j\n\ti1 += 1\n\tj1 += 1\n\tnewi = max(i1, n - i1 + 1)\n\tnewj = max(j1, m - j1 + 1)\n\tprint(newi * newj)\n", "def solve():\n\t(n, m) = map(int, input().split())\n\tmat = []\n\tfor i in range(n):\n\t\tmat.append(list(map(int, input().split())))\n\tmaxx = -100000000000\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif maxx < mat[i][j]:\n\t\t\t\tmaxx = mat[i][j]\n\t\t\t\tmaxi = i\n\t\t\t\tmaxj = j\n\th = max(maxi + 1, n - maxi)\n\tw = max(maxj + 1, m - maxj)\n\tprint(h * w)\nt = int(input())\nfor i in range(t):\n\tsolve()\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = [int(x) for x in input().split()]\n\ta = []\n\tfor _ in range(n):\n\t\ta += [int(x) for x in input().split()]\n\tidx = a.index(max(a))\n\t(i, j) = (idx // m, idx % m)\n\tb = max(j + 1, m - j)\n\th = max(i + 1, n - i)\n\tprint(b * h)\n", "import math\nt = int(input())\nwhile t:\n\tt -= 1\n\t(h, i) = input().split()\n\ta = int(h)\n\tb = int(i)\n\ttab = []\n\tfor i in range(0, a):\n\t\tlis = input().split()\n\t\ttab.append([int(x) for x in lis])\n\tma = max(max(tab, key=max))\n\tfor ind in range(0, a):\n\t\tif ma in tab[ind]:\n\t\t\tcol = tab[ind].index(ma) + 1\n\t\t\trow = ind + 1\n\t\t\tbreak\n\tprint(max(row, a - row + 1) * max(col, b - col + 1))\n", "T = int(input())\nq = []\nfor i in range(T):\n\tx = input().split()\n\t(a, b) = (int(x[0]), int(x[1]))\n\tdata = []\n\tfor i in range(a):\n\t\ttemp = [int(i) for i in input().split()]\n\t\tdata.append(temp)\n\tq.append((a, b, data))\n\ndef solve(a, b, data):\n\ti_max = 0\n\tj_max = 0\n\tmaxx = -1000000000.0\n\tfor i in range(a):\n\t\tfor j in range(b):\n\t\t\tif maxx < data[i][j]:\n\t\t\t\tmaxx = data[i][j]\n\t\t\t\ti_max = i\n\t\t\t\tj_max = j\n\ti_max += 1\n\tj_max += 1\n\tif i_max > a / 2:\n\t\th = i_max\n\telse:\n\t\th = a - i_max + 1\n\tif j_max > b / 2:\n\t\tw = j_max\n\telse:\n\t\tw = b - j_max + 1\n\tprint(w * h)\nfor (a, b, data) in q:\n\tsolve(a, b, data)\n", "def solve(mat):\n\tmx = max(map(max, mat))\n\t(x, y) = (-1, -1)\n\tfor i in range(len(mat)):\n\t\tfor j in range(len(mat[0])):\n\t\t\tif mat[i][j] == mx:\n\t\t\t\tx = i\n\t\t\t\ty = j\n\tw = max(x + 1, len(mat) - x)\n\th = max(y + 1, len(mat[0]) - y)\n\treturn w * h\nt = int(input())\nfor i in range(t):\n\t(n, m) = list(map(int, input().split()))\n\tmat = []\n\tfor i in range(n):\n\t\tmat.append(list(map(int, input().split())))\n\tprint(solve(mat))\n", "import math\n\ndef solve(n, m, arr):\n\tif n == 1 and m == 1:\n\t\treturn 1\n\telse:\n\t\tp = getMax(n, m, arr)\n\t\treturn max(p[1] + 1, n - p[1]) * max(p[2] + 1, m - p[2])\n\ndef getMax(n, m, arr):\n\ta = -999999999\n\t(x, y) = (0, 0)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] > a:\n\t\t\t\ta = arr[i][j]\n\t\t\t\t(x, y) = (i, j)\n\treturn (a, x, y)\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tarr = []\n\tfor i in range(n):\n\t\ta = list(map(int, input().split()))\n\t\tarr += [a]\n\tprint(solve(n, m, arr))\n", "t = int(input())\nfor i in range(t):\n\ta = []\n\tb = []\n\t(i1, i2) = (0, 0)\n\tlow = -10 ** 9\n\t(n, m) = [int(x) for x in input().split()]\n\tfor j in range(n):\n\t\tb = list(map(int, input().split()))\n\t\ta.append(b)\n\t\tfor k in range(m):\n\t\t\tif low <= b[k]:\n\t\t\t\tlow = b[k]\n\t\t\t\t(i1, i2) = (j, k)\n\t\tdel b\n\ta1 = max(m - i2, i2 + 1)\n\tb1 = max(n - i1, i1 + 1)\n\tprint(a1 * b1)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tarr = []\n\tfor i in range(n):\n\t\tl = list(map(int, input().split()))\n\t\tarr.append(l)\n\t(mi, mj) = (0, 0)\n\tmele = arr[0][0]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] > mele:\n\t\t\t\tmi = i\n\t\t\t\tmj = j\n\t\t\t\tmele = arr[i][j]\n\tmi += 1\n\tmj += 1\n\trmi = n - mi + 1\n\trmj = m - mj + 1\n\tprint(max(mi * mj, rmi * rmj, mi * rmj, mj * rmi))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tlst = [list(map(int, input().split())) for x in range(n)]\n\t(xi, yi) = (0, 0)\n\tmx = float('-inf')\n\tfor x in range(n):\n\t\tfor y in range(m):\n\t\t\tif mx < lst[x][y]:\n\t\t\t\tmx = lst[x][y]\n\t\t\t\txi = x\n\t\t\t\tyi = y\n\txi += 1\n\tyi += 1\n\tv1 = xi * yi\n\tv2 = xi * m - xi * (yi - 1)\n\tv3 = yi * n - (xi - 1) * yi\n\tv4 = (m - yi + 1) * (n - xi + 1)\n\tprint(max(v1, v2, v3, v4))\n", "for _ in range(int(input())):\n\t(n, m) = list(map(int, input().split()))\n\tarr = []\n\tfor i in range(n):\n\t\ts = list(map(int, input().split()))\n\t\tarr.append(s)\n\tmy_max = arr[0][0]\n\tmy_max_ij = (0, 0)\n\tfor i in range(n):\n\t\tif max(arr[i]) > my_max:\n\t\t\tmy_max = max(arr[i])\n\t\t\tmy_max_ij = (i, arr[i].index(max(arr[i])))\n\tresult = max(n - my_max_ij[0], my_max_ij[0] + 1) * max(m - my_max_ij[1], my_max_ij[1] + 1)\n\tprint(result)\n", "n = int(input())\nfor i in range(n):\n\t(ROWS, COLS) = map(int, input().split())\n\tmatrix = []\n\tfor i in range(ROWS):\n\t\tmatrix.append([int(num) for num in input().split()])\n\tmatrixMax = float('-inf')\n\tmatrixMaxCoord = (0, 0)\n\tfor row in range(ROWS):\n\t\tfor col in range(COLS):\n\t\t\tif matrix[row][col] > matrixMax:\n\t\t\t\tmatrixMax = matrix[row][col]\n\t\t\t\tmatrixMaxCoord = (row, col)\n\t(maxRow, maxCol) = (matrixMaxCoord[0], matrixMaxCoord[1])\n\tmaxDistanceX = max(maxRow + 1, ROWS - maxRow)\n\tmaxDistanceY = max(maxCol + 1, COLS - maxCol)\n\tprint(maxDistanceX * maxDistanceY)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tlst = []\n\tfor i in range(n):\n\t\tlst1 = list(map(int, input().split()))\n\t\tlst.append(lst1)\n\n\tdef myfunc(mylist):\n\t\tx = mylist.index(max(mylist, key=lambda x: max(x)))\n\t\ty = mylist[x].index(max(mylist[x]))\n\t\treturn (x + 1, y + 1)\n\t(x, y) = myfunc(lst)\n\tprint(max(x, n - x + 1) * max(y, m - y + 1))\n", "def solve():\n\t(n, m) = map(int, input().split())\n\tmat = list()\n\tfor i in range(n):\n\t\tmat.append(list(map(int, input().split())))\n\tMax = -2 ** 63\n\t(row, col) = (-1, -1)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] > Max:\n\t\t\t\t(row, col) = (i, j)\n\t\t\t\tMax = mat[i][j]\n\tcol += 1\n\trow += 1\n\trow = max(row, n - row + 1)\n\tcol = max(col, m - col + 1)\n\tprint(row * col)\nfor _ in range(int(input())):\n\tsolve()\n", "tests = int(input())\nfor i in range(tests):\n\t(rows, cols) = list(map(int, input().split()))\n\tvalues = []\n\tfor _ in range(rows):\n\t\tvalues.extend(list(map(int, input().split())))\n\tmax_idx = 0\n\tfor (idx, value) in enumerate(values):\n\t\tif values[idx] > values[max_idx]:\n\t\t\tmax_idx = idx\n\tmax_idx_coords = [max_idx // cols + 1, max_idx % cols + 1]\n\tm_rows = [max_idx_coords[0], rows - max_idx_coords[0] + 1]\n\tm_cols = [max_idx_coords[1], cols - max_idx_coords[1] + 1]\n\tprint(max(m_rows) * max(m_cols))\n", "t = int(input())\nfor _ in range(t):\n\t(m, n) = list(map(int, input().split(' ')))\n\tboard = []\n\tfor _ in range(m):\n\t\trow = list(map(int, input().split(' ')))\n\t\tboard.append(row)\n\tmaxVal = None\n\trowIdx = None\n\tcolIdx = None\n\tfor i in range(len(board)):\n\t\tfor j in range(len(board[i])):\n\t\t\tif maxVal is None or board[i][j] > maxVal:\n\t\t\t\tmaxVal = board[i][j]\n\t\t\t\trowIdx = i\n\t\t\t\tcolIdx = j\n\tprint(max(colIdx + 1, n - colIdx) * max(rowIdx + 1, m - rowIdx))\n", "t = int(input())\nfor i in range(t):\n\tl = [int(i) for i in input().split(' ')]\n\tn = l[0]\n\tm = l[1]\n\ta = []\n\tmax_ = float('-inf')\n\tmaxi = 0\n\tmaxj = 0\n\tfor d in range(n):\n\t\ta.append([int(i) for i in input().split(' ')])\n\t\tif max(a[d]) > max_:\n\t\t\tmax_ = max(a[d])\n\t\t\tmaxi = d + 1\n\t\t\tmaxj = a[d].index(max(a[d])) + 1\n\tans = []\n\tans.append(maxi * maxj)\n\tans.append(maxi * (m - maxj + 1))\n\tans.append((n - maxi + 1) * maxj)\n\tans.append((n - maxi + 1) * (m - maxj + 1))\n\tprint(max(ans))\n", "t = int(input())\nfor i in range(t):\n\t(n, m) = input().split()\n\tmatrix = []\n\tfor row in range(int(n)):\n\t\ttemp = list(map(int, input().split()))\n\t\tmatrix.append(temp)\n\tmax_n = 0\n\tmax_m = 0\n\tfor i in range(len(matrix)):\n\t\tfor j in range(len(matrix[0])):\n\t\t\ttemp = matrix[i][j]\n\t\t\tmax_val = matrix[max_n][max_m]\n\t\t\tmax_n = max_n if max_val > temp else i\n\t\t\tmax_m = max_m if max_val > temp else j\n\tans_n = max(int(n) - max_n, max_n + 1)\n\tans_m = max(int(m) - max_m, max_m + 1)\n\tprint(ans_n * ans_m)\n", "for i in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = [[int(s) for s in input().split()] for i in range(n)]\n\timax = 0\n\tjmax = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] > a[imax][jmax]:\n\t\t\t\timax = i\n\t\t\t\tjmax = j\n\tprint(max(imax + 1, n - imax) * max(jmax + 1, m - jmax))\n", "import sys\ninput = sys.stdin.readline\nprint = sys.stdout.write\nfor _ in range(int(input())):\n\t(h, w) = map(int, sys.stdin.readline().split())\n\tcheck = True\n\tbiggestHeight = 0\n\tbiggestWidth = 0\n\tfor _ in range(h):\n\t\tlst = list(map(int, input().split()))\n\t\tif check == True:\n\t\t\tcheck = False\n\t\t\tbiggest = lst[0]\n\t\tif max(lst) >= biggest:\n\t\t\tbiggest = max(lst)\n\t\t\tbiggestHeight = _ + 1\n\t\t\tbiggestWidth = lst.index(biggest) + 1\n\tif h - biggestHeight + 1 > biggestHeight:\n\t\tbiggestHeight = h - biggestHeight + 1\n\tif w - biggestWidth + 1 > biggestWidth:\n\t\tbiggestWidth = w - biggestWidth + 1\n\tprint(str(biggestHeight * biggestWidth) + '\\n')\n", "p = int(input())\nwhile p:\n\t(n, m) = map(int, input().split())\n\tl = []\n\tfor i in range(n):\n\t\ta = list(map(int, input().split()))\n\t\tl.append(a)\n\t\tif i == 0:\n\t\t\tx = max(a)\n\t\t\ty = i\n\t\t\tz = a.index(x)\n\t\telif x < max(a):\n\t\t\tx = max(a)\n\t\t\ty = i\n\t\t\tz = a.index(x)\n\th = min(y, n - y - 1)\n\tw = min(z, m - z - 1)\n\t(n, m) = (n - h, m - w)\n\tprint(n * m)\n\tp -= 1\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\ttmp = -1000000005\n\tpos = 0\n\tind = 0\n\tfor i in range(1, n + 1):\n\t\tlst = list(map(int, input().split()))\n\t\tif max(lst) > tmp:\n\t\t\tpos = i\n\t\t\ttmp = max(lst)\n\t\t\tind = lst.index(tmp) + 1\n\tprint(max(pos, n - pos + 1) * max(ind, m - ind + 1))\n", "import math\nt = int(input())\nfor _ in range(t):\n\t(n, m) = [int(i) for i in input().split()]\n\tarr = [[0 for i in range(m)] for j in range(n)]\n\tfor i in range(n):\n\t\tarr[i] = list(map(int, input().split()))\n\tidx = [0, 0]\n\tmx = -math.inf\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] > mx:\n\t\t\t\tmx = arr[i][j]\n\t\t\t\tidx = [i, j]\n\t(i, j) = idx\n\ta = max(j + 1, m - j)\n\tb = max(i + 1, n - i)\n\tprint(a * b)\n", "import math\nt = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tmaxi = -math.inf\n\t(a, b) = (0, 0)\n\tfor i in range(n):\n\t\ttemp = list(map(int, input().split()))\n\t\tif maxi < max(temp):\n\t\t\tmaxi = max(temp)\n\t\t\ta = i\n\t\t\tb = temp.index(maxi)\n\tprint(max(a + 1, n - a) * max(b + 1, m - b))\n", "n_tc = input()\nfor i in range(int(n_tc)):\n\t(x, y) = list(map(int, input().split()))\n\ta = []\n\tfor i in range(x):\n\t\talp = list(map(int, input().split()))\n\t\ta.append(alp)\n\tm = float('-inf')\n\tfor i in range(x):\n\t\tfor j in range(y):\n\t\t\tif m < a[i][j]:\n\t\t\t\tm = a[i][j]\n\t\t\t\tx_ind = i\n\t\t\t\ty_ind = j\n\th = max(x_ind + 1, x - x_ind)\n\tm = max(y_ind + 1, y - y_ind)\n\tprint(h * m)\n", "def main():\n\ttee = int(input())\n\tfor _ in range(1, tee + 1):\n\t\t(row, col) = list(map(int, input().split()))\n\t\tlss = []\n\t\tfor __ in range(row):\n\t\t\ttemp = list(map(int, input().split()))\n\t\t\tlss.append(temp)\n\t\tmaxi = float('-inf')\n\t\tmaxa = -1\n\t\tmaxb = -1\n\t\tfor a in range(row):\n\t\t\tfor b in range(col):\n\t\t\t\tif maxi <= lss[a][b]:\n\t\t\t\t\tmaxi = lss[a][b]\n\t\t\t\t\tmaxa = a + 1\n\t\t\t\t\tmaxb = b + 1\n\t\tprint(max(maxa, row - maxa + 1) * max(maxb, col - maxb + 1))\nmain()\n", "t = int(input())\nfor i in range(t):\n\t(n, m) = input().split(' ')\n\t(n, m) = (int(n), int(m))\n\tgrid = []\n\tfor i in range(n):\n\t\tarr = input().split(' ')\n\t\tarr = list(map(int, arr))\n\t\tgrid.append(arr)\n\tmac = -1000000000.0\n\tfor p in grid:\n\t\tif max(p) > mac:\n\t\t\tmac = max(p)\n\t\t\ti = grid.index(p)\n\tj = grid[i].index(max(grid[i]))\n\t(h, w) = (max(i + 1, n - i), max(j + 1, m - j))\n\tprint(h * w)\n", "def find_rmax_cmax(grid):\n\tmx = -10 ** 9 - 1\n\t(r, c) = (0, 0)\n\tfor (i, row) in enumerate(grid):\n\t\tfor (j, x) in enumerate(row):\n\t\t\tif x > mx:\n\t\t\t\t(r, c) = (i, j)\n\t\t\t\tmx = x\n\treturn (r, c)\n\ndef gen_max_sub(n, m, r, c, grid):\n\tfor (nr, nc) in [(r, c), (r, m - 1 - c), (n - 1 - r, c), (n - 1 - r, m - 1 - c)]:\n\t\tif (nr + 1) * 2 > n and (nc + 1) * 2 > m:\n\t\t\treturn (nr + 1, nc + 1)\n\treturn (0, 0)\n\ndef gen_sol(n, m, grid):\n\t(rmax, cmax) = find_rmax_cmax(grid)\n\t(r, c) = gen_max_sub(n, m, rmax, cmax, grid)\n\treturn r * c\nt = int(input())\nfor _ in range(t):\n\t(n, m) = [int(x) for x in input().split()]\n\tgrid = []\n\tfor _ in range(n):\n\t\tline = [int(x) for x in input().split()]\n\t\tgrid.append(line)\n\tprint(gen_sol(n, m, grid))\n", "import sys\n\ndef solve():\n\t(height, width) = list(map(int, input().split(' ')))\n\t(max_row, max_col) = (0, 0)\n\t_max = -sys.maxsize\n\tfor i in range(height):\n\t\trow = list(map(int, input().split(' ')))\n\t\tfor j in range(width):\n\t\t\tif row[j] > _max:\n\t\t\t\t(max_row, max_col) = (i, j)\n\t\t\t\t_max = row[j]\n\tprint(max(height - max_row, max_row + 1) * max(width - max_col, max_col + 1))\nnum_inputs = int(input())\nfor ____ in range(num_inputs):\n\tsolve()\n", "import sys\nT = int(input())\nfor _ in range(T):\n\t(n, m) = map(int, input().split())\n\tlst = []\n\thigh = -1 * 10 ** 9 - 1\n\tloc = [0, 0]\n\tfor i in range(n):\n\t\tinp = input().split()\n\t\ttmp = []\n\t\tfor (j, jj) in enumerate(inp):\n\t\t\tjj = int(jj)\n\t\t\tif jj > high:\n\t\t\t\thigh = jj\n\t\t\t\tloc = [i, j]\n\th = max(loc[0], n - 1 - loc[0]) + 1\n\tw = max(loc[1], m - 1 - loc[1]) + 1\n\tprint(h * w)\n", "for _ in range(int(input())):\n\t(n, m) = [int(a) for a in input().split()]\n\tgrid = []\n\tfor i in range(n):\n\t\tgrid.append([int(b) for b in input().split()])\n\tbest = [grid[0][0], 0, 0]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif grid[i][j] > best[0]:\n\t\t\t\tbest = [grid[i][j], i, j]\n\tprint(max((best[1] + 1) * (best[2] + 1), (best[1] + 1) * (m - best[2]), (n - best[1]) * (best[2] + 1), (n - best[1]) * (m - best[2])))\n", "t = int(input())\nwhile t > 0:\n\tt = t - 1\n\t(n, m) = [int(i) for i in input().split()]\n\tmax_ele = -10 ** 10\n\tfor i in range(n):\n\t\tl = [int(ii) for ii in input().split()]\n\t\tfor j in range(m):\n\t\t\tif l[j] > max_ele:\n\t\t\t\tmax_ele = l[j]\n\t\t\t\tminy = i\n\t\t\t\tminx = j\n\tminy += 1\n\tminx += 1\n\tansx = max([minx, m - minx + 1])\n\tansy = max([miny, n - miny + 1])\n\tprint(ansx * ansy)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmx = -10 ** 9 - 7\n\tli = []\n\tfor _ in range(n):\n\t\tli2 = list(map(int, input().split()))\n\t\tmx = max(mx, max(li2))\n\t\tli.append(li2)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif li[i][j] == mx:\n\t\t\t\tx = max(i + 1, n - i)\n\t\t\t\ty = max(j + 1, m - j)\n\t\t\t\tprint(x * y)\n\t\t\t\tbreak\n", "for _ in range(int(input())):\n\t(n, m) = [int(x) for x in input().split()]\n\tl = []\n\tfor i in range(n):\n\t\tl.append([int(x) for x in input().split()])\n\tmaxi = -10 ** 9\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif maxi <= l[i][j]:\n\t\t\t\ttemp = (i, j)\n\t\t\t\tmaxi = l[i][j]\n\tprint(max(temp[0] + 1, n - temp[0]) * max(temp[1] + 1, m - temp[1]))\n", "from sys import stdin\ninput = stdin.readline\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tli = []\n\tmaxi = -10 ** 10\n\tfor i in range(n):\n\t\tli.append(list(map(int, input().split())))\n\t\tmaxi = max(maxi, max(li[-1]))\n\t(l, r) = (-1, -1)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif li[i][j] == maxi:\n\t\t\t\tl = i\n\t\t\t\tr = j\n\t\t\t\tbreak\n\tprint(max(l + 1, n - l) * max(r + 1, m - r))\n", "for _ in range(int(input())):\n\t(n, q) = map(int, input().split())\n\tl = []\n\tfir = 0\n\tcoin = 0\n\tind = 0\n\tfor j in range(n):\n\t\tlst = list(map(int, input().split()))\n\t\tif j == 0:\n\t\t\tfir = max(lst)\n\t\t\tcoin = 0\n\t\t\tind = lst.index(fir)\n\t\telif max(lst) > fir:\n\t\t\tfir = max(lst)\n\t\t\tcoin = j\n\t\t\tind = lst.index(fir)\n\t\tl.append(lst)\n\trow_dist = max(coin + 1, n - coin)\n\tcol_dist = max(ind + 1, q - ind)\n\tprint(row_dist * col_dist)\n", "for _ in range(int(input())):\n\ta = list(map(int, input().split()))\n\tl = []\n\tfor i in range(a[0]):\n\t\tad = list(map(int, input().split()))\n\t\tl.append(ad)\n\tm = max(l[0])\n\tind = 0\n\tfor i in range(1, a[0]):\n\t\tnum = max(l[i])\n\t\tif num > m:\n\t\t\tm = num\n\t\t\tind = i\n\trow = ind + 1\n\tcolumn = l[ind].index(m) + 1\n\tansrow = 0\n\tanscol = 0\n\tif row > a[0] / 2:\n\t\tansrow = row\n\telse:\n\t\tansrow = a[0] - row + 1\n\tif column > a[1] / 2:\n\t\tanscol = column\n\telse:\n\t\tanscol = a[1] - column + 1\n\tprint(anscol * ansrow)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tx = 0\n\ty = 0\n\tmaxi = -10 ** 10\n\tfor i in range(n):\n\t\tai = list(map(int, input().split()))\n\t\tfor j in range(m):\n\t\t\tif ai[j] >= maxi:\n\t\t\t\ty = i\n\t\t\t\tx = j\n\t\t\t\tmaxi = ai[j]\n\tprint(min(max(x + 1, m - x), m) * min(max(y + 1, n - y), n))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmat = []\n\tmin = -10 ** 9 - 1\n\trow = 0\n\tcol = 0\n\tfor _ in range(n):\n\t\tmat.append(list(map(int, input().split())))\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] > min:\n\t\t\t\tmin = mat[i][j]\n\t\t\t\trow = i\n\t\t\t\tcol = j\n\tprint(max(row + 1, n - row) * max(col + 1, m - col))\n", "import math\nfor i in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmax = -math.inf\n\tcol = 0\n\trow = 0\n\tfor j in range(n):\n\t\ta = list(map(int, input().split()))\n\t\tfor x in range(m):\n\t\t\tif a[x] > max:\n\t\t\t\tmax = a[x]\n\t\t\t\tif m - x - 1 > x:\n\t\t\t\t\tcol = m - x\n\t\t\t\telse:\n\t\t\t\t\tcol = x + 1\n\t\t\t\tif n - j - 1 > j:\n\t\t\t\t\trow = n - j\n\t\t\t\telse:\n\t\t\t\t\trow = j + 1\n\tprint(col * row)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = list(map(int, input().split()))\n\tA = []\n\t(mx, ii, jj) = (-1000000000000.0, -1, -1)\n\tfor i in range(n):\n\t\tB = list(map(int, input().split()))\n\t\tfor j in range(m):\n\t\t\tif mx < B[j]:\n\t\t\t\tmx = B[j]\n\t\t\t\t(ii, jj) = (i, j)\n\tprint(max(ii + 1, n - ii) * max(jj + 1, m - jj))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmx = -float('inf')\n\t(l, r) = (-1, -1)\n\tfor i in range(n):\n\t\ta = list(map(int, input().split()))\n\t\tif max(a) > mx:\n\t\t\tmx = max(a)\n\t\t\tj = a.index(mx)\n\t\t\t(l, r) = (i, j)\n\tprint(max(l + 1, n - l) * max(m - r, r + 1))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tgrid = []\n\tMax = float('-inf')\n\tfor i in range(n):\n\t\tgrid.append(list(map(int, input().split())))\n\t\ta = max(grid[i])\n\t\tif a > Max:\n\t\t\tMax = a\n\t\t\trow = i\n\t\t\tcol = grid[i].index(a)\n\tresult = 1\n\tif row == n - 1 or row == 0:\n\t\tresult *= n\n\telse:\n\t\tresult *= max(n - row, row + 1)\n\tif col == m - 1 or col == 0:\n\t\tresult *= m\n\telse:\n\t\tresult *= max(m - col, col + 1)\n\tprint(result)\n", "for _ in range(int(input())):\n\t(m, n) = map(int, input().split())\n\tans = [float('-inf'), 0, 0]\n\tfor i in range(m):\n\t\ta = [*map(int, input().split())]\n\t\tfor j in range(n):\n\t\t\tif a[j] > ans[0]:\n\t\t\t\t(ans[0], ans[1], ans[2]) = (a[j], i, j)\n\th = max(ans[1] + 1, m - ans[1])\n\tw = max(ans[2] + 1, n - ans[2])\n\tprint(h * w)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tmaxi = -10 ** 9\n\tx_max_index = 0\n\ty_max_index = 0\n\tfor i in range(n):\n\t\ta = list(map(int, input().split()))\n\t\tb = max(a)\n\t\tif b > maxi:\n\t\t\tmaxi = b\n\t\t\tx_max_index = i + 1\n\t\t\ty_max_index = a.index(max(a)) + 1\n\tif x_max_index != 0 and x_max_index > n // 2:\n\t\tx_max_index = n - x_max_index + 1\n\tif y_max_index != 0 and y_max_index > m // 2:\n\t\ty_max_index = m - y_max_index + 1\n\tif n == 1 and m == 1:\n\t\tprint(1)\n\telse:\n\t\tprint((n - x_max_index + 1) * (m - y_max_index + 1))\n", "for t in range(int(input())):\n\t(m, n) = map(int, input().split())\n\tarr = [[int(x) for x in input().split()] for i in range(m)]\n\tmx = -float('inf')\n\t(r, c) = (0, 0)\n\tfor i in range(m):\n\t\tfor j in range(n):\n\t\t\tif arr[i][j] > mx:\n\t\t\t\t(r, c) = (i, j)\n\t\t\t\tmx = arr[i][j]\n\trow = max(r + 1, m - r)\n\tcol = max(c + 1, n - c)\n\tprint(row * col)\n", "t = int(input())\nwhile t:\n\t(n, m) = map(int, input().split())\n\tl = []\n\tM = -100000000000\n\t(p, q, a) = (0, 0, 0)\n\tfor i in range(n):\n\t\tx = list(map(int, input().split()))\n\t\tfor j in x:\n\t\t\ta += 1\n\t\t\tif j > M:\n\t\t\t\tM = j\n\t\t\t\tq = a\n\t\t\t\tp = i\n\t\ta = 0\n\t\tl.append(x)\n\tq -= 1\n\t(a, b) = (0, 0)\n\tp += 1\n\tq += 1\n\tif n <= 2:\n\t\ta = n\n\telif p <= n // 2:\n\t\ta = n - p + 1\n\telse:\n\t\ta = p\n\tif m <= 2:\n\t\tb = m\n\telif q <= m // 2:\n\t\tb = m - q + 1\n\telse:\n\t\tb = q\n\tprint(a * b)\n\tt -= 1\n", "t = int(input())\nfor _ in range(t):\n\t(row, column) = map(int, input().split())\n\tarr = []\n\tfor _ in range(row):\n\t\tnum = list(map(int, input().split()))\n\t\tarr.append(num)\n\tmaximum = arr[0][0]\n\ti = 0\n\tj = 0\n\tinum = 1\n\tjnum = 1\n\tfor p in arr:\n\t\tfor q in p:\n\t\t\tif maximum <= q:\n\t\t\t\tmaximum = q\n\t\t\t\ti = inum\n\t\t\t\tj = jnum\n\t\t\tjnum += 1\n\t\tinum += 1\n\t\tjnum = 1\n\tstandardRow = (row + 1) / 2\n\tstandardCol = (column + 1) / 2\n\th = abs(standardRow - i) + standardRow\n\tw = abs(standardCol - j) + standardCol\n\tprint(int(h * w))\n", "for i in range(int(input())):\n\t(n, m) = list(map(int, input().split()))\n\tp = -10 ** 9 - 2\n\ta = []\n\tfor j in range(n):\n\t\tk = list(map(int, input().split()))\n\t\ta.append(k)\n\tfor f in range(n):\n\t\tfor u in range(m):\n\t\t\tif a[f][u] > p:\n\t\t\t\tp = a[f][u]\n\t\t\t\tx = f + 1\n\t\t\t\ty = u + 1\n\tprint(max(x, n + 1 - x) * max(y, m + 1 - y))\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor i in range(n):\n\t\ta.append(list(map(int, input().split())))\n\t(row, col) = (0, 0)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] > a[row][col]:\n\t\t\t\t(row, col) = (i, j)\n\t(row, col) = (max(row + 1, n - row), max(col + 1, m - col))\n\tprint(row * col)\n", "for _ in [0] * int(input()):\n\t(n, m) = map(int, input().split())\n\ta = [[*map(int, input().split())] for _ in [0] * n]\n\tmaxi = [a[0][0], 0, 0]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif maxi[0] < a[i][j]:\n\t\t\t\t(maxi[0], maxi[1], maxi[2]) = (a[i][j], i, j)\n\tprint(max(maxi[1] + 1, n - maxi[1]) * max(maxi[2] + 1, m - maxi[2]))\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\ta = [[-1 for i in range(m)] for j in range(n)]\n\tmx = -10000000000\n\tfor i in range(n):\n\t\ta[i] = list(map(int, input().split()))\n\t\tmx = max(mx, max(a[i]))\n\t[x, y] = [-1, -1]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == mx:\n\t\t\t\tx = i\n\t\t\t\ty = j\n\tres = max(n - x, x + 1) * max(m - y, y + 1)\n\tprint(res)\n", "x = int(input())\nfor i in range(x):\n\tA = input().split()\n\tn = int(A[0])\n\tm = int(A[1])\n\tC = [0] * m\n\tB = C * n\n\tmaxm = 0\n\tmaxn = 0\n\tp = 0\n\tk = 0\n\tfor j in range(n):\n\t\tB[j] = input().split()\n\tmaxi = int(B[0][0])\n\tfor a in range(m):\n\t\tfor b in range(n):\n\t\t\tif int(B[b][a]) > maxi:\n\t\t\t\tmaxi = int(B[b][a])\n\t\t\t\tmaxm = a\n\t\t\t\tmaxn = b\n\tp = max(maxm + 1, m - maxm)\n\tk = max(maxn + 1, n - maxn)\n\tprint(p * k)\n", "for _ in range(int(input())):\n\t(h, w) = [int(i) for i in input().split()]\n\tm = [int(i) for j in range(h) for i in input().split()]\n\ta = m.index(max(m))\n\t(r, c) = (a // w, a % w)\n\tprint(max((h - r) * (c + 1), (c + 1) * (r + 1), (r + 1) * (w - c), (h - r) * (w - c)))\n", "def solve():\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor _ in range(n):\n\t\ta.append(list(map(int, input().split())))\n\tmx = -2 ** 31\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif mx < a[i][j]:\n\t\t\t\tmx = a[i][j]\n\t\t\t\t(x, y) = (i, j)\n\tprint(max(x + 1, n - x) * max(y + 1, m - y))\nfor _ in range(int(input())):\n\tsolve()\n", "num_of_case = int(input())\nfor _ in range(num_of_case):\n\t(row, col) = [int(x) for x in input().split(' ')]\n\tmax_pos = (-1, -1)\n\tmax_num = float('-inf')\n\tfor row_idx in range(row):\n\t\tr = [int(x) for x in input().split(' ')]\n\t\tfor col_idx in range(col):\n\t\t\tif r[col_idx] > max_num:\n\t\t\t\tmax_num = r[col_idx]\n\t\t\t\tmax_pos = (row_idx, col_idx)\n\tif max_pos[0] >= row // 2:\n\t\tif max_pos[1] >= col // 2:\n\t\t\tprint((max_pos[0] + 1) * (max_pos[1] + 1))\n\t\telse:\n\t\t\tprint((max_pos[0] + 1) * (col - max_pos[1]))\n\telif max_pos[1] >= col // 2:\n\t\tprint((row - max_pos[0]) * (max_pos[1] + 1))\n\telse:\n\t\tprint((row - max_pos[0]) * (col - max_pos[1]))\n", "count = int(input())\nar = [[] for i in range(count)]\nfor i in range(count):\n\t(n, m) = [int(c) for c in input().split()]\n\tfor j in range(n):\n\t\tar[i] += [[int(o) for o in input().split()]]\nfor i in range(count):\n\tm = max([max(j) for j in ar[i]])\n\tfor j in range(len(ar[i])):\n\t\tif m in ar[i][j]:\n\t\t\tindexOfMax = (j, ar[i][j].index(m))\n\tprint(max(len(ar[i]) - indexOfMax[0], indexOfMax[0] + 1) * max(len(ar[i][0]) - indexOfMax[1], indexOfMax[1] + 1))\n", "t = int(input())\nwhile t > 0:\n\tn = [int(i) for i in input().split()]\n\tm = n[1]\n\tn = n[0]\n\tmi = 0\n\tmj = 0\n\tmx = -99999999999\n\tfor i in range(1, n + 1):\n\t\tl = [0] + [int(j) for j in input().split()]\n\t\tfor j in range(1, m + 1):\n\t\t\tif l[j] > mx:\n\t\t\t\tmx = l[j]\n\t\t\t\tmi = i\n\t\t\t\tmj = j\n\tprint(max(m - mj + 1, mj) * max(n - mi + 1, mi))\n\tt -= 1\n", "t = int(input())\nfor i_ in range(t):\n\tsizes = list(map(int, input().split()))\n\thigh = sizes[0]\n\twidth = sizes[1]\n\tmatrix = []\n\ttop_number = -10 ** 9\n\tcoord_top_number = 1\n\tfor j_ in range(high):\n\t\tline = list(map(int, input().split()))\n\t\tmatrix.extend(line)\n\tfor o_ in range(len(matrix)):\n\t\tif top_number < matrix[o_]:\n\t\t\ttop_number = matrix[o_]\n\t\t\tcoord_top_number = o_ + 1\n\tif coord_top_number % width > 0:\n\t\tcoord_high = coord_top_number // width + 1\n\telse:\n\t\tcoord_high = coord_top_number // width\n\tif coord_top_number % width > 0:\n\t\tcoord_width = coord_top_number % width\n\telse:\n\t\tcoord_width = width\n\tif coord_high > high / 2:\n\t\thigh_kef = coord_high\n\telse:\n\t\thigh_kef = high - coord_high + 1\n\tif coord_width > width / 2:\n\t\twidth_kef = coord_width\n\telse:\n\t\twidth_kef = width - coord_width + 1\n\tprint(width_kef * high_kef)\n", "import math\nimport sys\nimport threading\ninput = sys.stdin.readline\nfrom collections import defaultdict as dd\nfrom collections import deque\n\ndef helper(nd):\n\tvis[nd] = 1\n\there = 1\n\tfor ng in gr[nd]:\n\t\tif vis[ng] == 0:\n\t\t\there += helper(ng)\n\ttot[nd] = here\n\treturn here\n\ndef helper1(nd, par):\n\tch = []\n\tfor ng in gr[nd]:\n\t\tif ng != par:\n\t\t\tch.append(ng)\n\tif len(ch) == 0:\n\t\treturn 0\n\tif len(ch) == 1:\n\t\treturn tot[nd] - 2\n\treturn max(tot[ch[1]] - 1 + helper1(ch[0], nd), tot[ch[0]] - 1 + helper1(ch[1], nd))\n\ndef shouvik():\n\tT = int(input())\n\tfor _ in range(T):\n\t\t(n, m) = map(int, input().split())\n\t\tmat = []\n\t\tfor _ in range(n):\n\t\t\tmat.append(list(map(int, input().split())))\n\t\tmx = -sys.maxsize\n\t\t(x, y) = (-1, -1)\n\t\tfor i in range(n):\n\t\t\tfor j in range(m):\n\t\t\t\tif mat[i][j] > mx:\n\t\t\t\t\tmx = mat[i][j]\n\t\t\t\t\t(x, y) = (i, j)\n\t\tw = max(y + 1, m - y)\n\t\th = max(x + 1, n - x)\n\t\tprint(w * h)\nshouvik()\n", "import sys\n\ndef main(a, n, m):\n\tmax_ = float('-inf')\n\tres = None\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif max_ < a[i][j]:\n\t\t\t\tmax_ = a[i][j]\n\t\t\t\tres = (i, j)\n\tnm = [n, m]\n\tres = [max(nm[i] - res[i], res[i] + 1) for i in range(2)]\n\tmul = 1\n\tfor i in res:\n\t\tmul *= i\n\treturn mul\nres = []\nnum = int(sys.stdin.readline())\nfor i in range(num):\n\t(n, m) = [int(i) for i in sys.stdin.readline().split(' ')]\n\ta = []\n\tfor i in range(n):\n\t\ta.append([int(i) for i in sys.stdin.readline().split(' ')])\n\tres.append(main(a, n, m))\nprint(*res, sep='\\n')\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = [int(i) for _ in range(n) for i in input().split()]\n\tmax_a = a.index(max(a))\n\t(i_max, j_max) = (max_a // m, max_a % m)\n\th = max(n - i_max, i_max + 1)\n\tl = max(m - j_max, j_max + 1)\n\tprint(l * h)\n", "t = int(input(''))\nfor z in range(t):\n\t(n, m) = map(int, input().split())\n\tma = -10000000000\n\tfor i in range(n):\n\t\ta = list(map(int, input('').split()))[:m]\n\t\tif max(a) > ma:\n\t\t\tma = max(a)\n\t\t\tp = i + 1\n\t\t\tq = a.index(max(a)) + 1\n\tb = n // 2 + 1\n\tc = m // 2 + 1\n\tif p < b:\n\t\tp = n - p + 1\n\tif q < c:\n\t\tq = m - q + 1\n\tprint(p * q)\n", "T = int(input())\nfor test in range(T):\n\t(n, m) = [int(a) for a in input().split()]\n\tmax_val = float('-inf')\n\tindex_r = 0\n\tindex_c = 0\n\tfor i in range(n):\n\t\ta = list(map(int, input().split()))\n\t\tmax_i = max(a)\n\t\tif max_i > max_val:\n\t\t\tindex_c = a.index(max_i) + 1\n\t\t\tindex_r = i + 1\n\t\t\tmax_val = max_i\n\tprint(max(index_r, n - index_r + 1) * max(index_c, m - index_c + 1))\n", "def main():\n\t(n, m) = map(int, input().split())\n\tma = -10 ** 9 - 1\n\tfor i in range(n):\n\t\ta = list(map(int, input().split()))\n\t\tv = max(a)\n\t\tif v > ma:\n\t\t\tma = v\n\t\t\tmi = i\n\t\t\tmj = a.index(v)\n\tprint(max(mi + 1, n - mi) * max(mj + 1, m - mj))\nfor _ in range(int(input())):\n\tmain()\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tl = []\n\tfor i in range(n):\n\t\tk = list(map(int, input().split()))\n\t\tl.append(k)\n\tmx = -10 ** 9 - 2\n\tx = 0\n\ty = 0\n\tfor r in range(n):\n\t\tfor c in range(m):\n\t\t\tif mx < l[r][c]:\n\t\t\t\tmx = l[r][c]\n\t\t\t\tx = r\n\t\t\t\ty = c\n\tprint(max(n - x, x + 1) * max(m - y, y + 1))\n", "t = int(input())\nwhile t:\n\tt -= 1\n\t(n, m) = [int(x) for x in input().split()]\n\tarr = [[] for _ in range(n)]\n\tfor i in range(n):\n\t\tarr[i] = [int(x) for x in input().split()]\n\ttmp = -float('inf')\n\tindex = (0, 0)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] > tmp:\n\t\t\t\ttmp = arr[i][j]\n\t\t\t\tindex = (i, j)\n\tx = max(index[0] + 1, n - index[0])\n\ty = max(index[1] + 1, m - index[1])\n\tprint(x * y)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tarr = []\n\tfor i in range(n):\n\t\tarr.append(list(map(int, input().split())))\n\tma = float('-inf')\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] > ma:\n\t\t\t\tma = arr[i][j]\n\t\t\t\tmi = i + 1\n\t\t\t\tmj = j + 1\n\tprint(max(mi, n - mi + 1) * max(mj, m - mj + 1))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmass = [list(map(int, input().split())) for r in range(n)]\n\tmx = max([j for i in mass for j in i])\n\tr = [i for i in mass if mx in i][0]\n\t(a, b) = (mass.index(r) + 1, r.index(mx) + 1)\n\tprint(max(a, n - a + 1) * max(b, m - b + 1))\n"]

difficulty: EASY

source: codeforces

raw_problem:
A. Subrectangle Guess

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Michael and Joe are playing a game. The game is played on a grid with $$$n$$$ rows and $$$m$$$ columns, filled with distinct integers. We denote the square on the $$$i$$$-th ($$$1\le i\le n$$$) row and $$$j$$$-th ($$$1\le j\le m$$$) column by $$$(i, j)$$$ and the number there by $$$a_{ij}$$$.

Michael starts by saying two numbers $$$h$$$ ($$$1\le h \le n$$$) and $$$w$$$ ($$$1\le w \le m$$$). Then Joe picks any $$$h\times w$$$ subrectangle of the board (without Michael seeing).

Formally, an $$$h\times w$$$ subrectangle starts at some square $$$(a,b)$$$ where $$$1 \le a \le n-h+1$$$ and $$$1 \le b \le m-w+1$$$. It contains all squares $$$(i,j)$$$ for $$$a \le i \le a+h-1$$$ and $$$b \le j \le b+w-1$$$.
  Possible move by Joe if Michael says $$$3\times 2$$$ (with maximum of $$$15$$$).
Finally, Michael has to guess the maximum number in the subrectangle. He wins if he gets it right.

Because Michael doesn't like big numbers, he wants the area of the chosen subrectangle (that is, $$$h \cdot w$$$), to be as small as possible, while still ensuring that he wins, not depending on Joe's choice. Help Michael out by finding this minimum possible area.

It can be shown that Michael can always choose $$$h, w$$$ for which he can ensure that he wins.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 40$$$)  — the size of the grid.

Each of the following $$$n$$$ lines contains $$$m$$$ integers. The $$$j$$$-th integer on the $$$i$$$-th line is $$$a_{ij}$$$ ($$$-10^9 \le a_{ij} \le 10^9$$$)  — the element in the cell $$$(i, j)$$$.

It is guaranteed that all the numbers are distinct (that is, if $$$a_{i_1j_1} = a_{i_2j_2}$$$, then $$$i_1 = i_2, j_1 = j_2$$$).

Output

For each test case print a single positive integer  — the minimum possible area the subrectangle can have while still ensuring that Michael can guarantee the victory.

Example

Input

3
1 1
3
4 4
2 12 6 10
3 15 16 4
1 13 8 11
14 7 9 5
2 3
-7 5 2
0 8 -3

Output

1
9
4

Note

In the first test case, the grid is $$$1\times 1$$$, so the only possible choice for $$$h, w$$$ is $$$h = 1, w = 1$$$, giving an area of $$$h\cdot w = 1$$$.

The grid from the second test case is drawn in the statement. It can be shown that with $$$h = 3, w = 3$$$ Michael can guarantee the victory and that any choice with $$$h\cdot w \le 8$$$ doesn't.

question:
Michael and Joe are playing a game. The game is played on a grid with $$$n$$$ rows and $$$m$$$ columns, filled with distinct integers. We denote the square on the $$$i$$$-th ($$$1\le i\le n$$$) row and $$$j$$$-th ($$$1\le j\le m$$$) column by $$$(i, j)$$$ and the number there by $$$a_{ij}$$$.
Michael starts by saying two numbers $$$h$$$ ($$$1\le h \le n$$$) and $$$w$$$ ($$$1\le w \le m$$$). Then Joe picks any $$$h\times w$$$ subrectangle of the board (without Michael seeing).
Formally, an $$$h\times w$$$ subrectangle starts at some square $$$(a,b)$$$ where $$$1 \le a \le n-h+1$$$ and $$$1 \le b \le m-w+1$$$. It contains all squares $$$(i,j)$$$ for $$$a \le i \le a+h-1$$$ and $$$b \le j \le b+w-1$$$.
 ![image](1.png) Possible move by Joe if Michael says $$$3\times 2$$$ (with maximum of $$$15$$$). Finally, Michael has to guess the maximum number in the subrectangle. He wins if he gets it right.
Because Michael doesn't like big numbers, he wants the area of the chosen subrectangle (that is, $$$h \cdot w$$$), to be as small as possible, while still ensuring that he wins, not depending on Joe's choice. Help Michael out by finding this minimum possible area.
It can be shown that Michael can always choose $$$h, w$$$ for which he can ensure that he wins.

Input
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20$$$). Description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 40$$$)  — the size of the grid.
Each of the following $$$n$$$ lines contains $$$m$$$ integers. The $$$j$$$-th integer on the $$$i$$$-th line is $$$a_{ij}$$$ ($$$-10^9 \le a_{ij} \le 10^9$$$)  — the element in the cell $$$(i, j)$$$.
It is guaranteed that all the numbers are distinct (that is, if $$$a_{i_1j_1} = a_{i_2j_2}$$$, then $$$i_1 = i_2, j_1 = j_2$$$).

Output
For each test case print a single positive integer  — the minimum possible area the subrectangle can have while still ensuring that Michael can guarantee the victory.

Example
Input
3
1 1
3
4 4
2 12 6 10
3 15 16 4
1 13 8 11
14 7 9 5
2 3
-7 5 2
0 8 -3

Output
1
9
4

Note
In the first test case, the grid is $$$1\times 1$$$, so the only possible choice for $$$h, w$$$ is $$$h = 1, w = 1$$$, giving an area of $$$h\cdot w = 1$$$.
The grid from the second test case is drawn in the statement. It can be shown that with $$$h = 3, w = 3$$$ Michael can guarantee the victory and that any choice with $$$h\cdot w \le 8$$$ doesn't.

data_split: test


D. Color the Carpet

problem_index: D

time_limit: 1 second

memory_limit: 256 megabytes

output_spec:
If there is a coloring that satisfies at least ![image](images/cf_297_D/6.png) of the color constraints, print "YES" (without quotes) in the first line. In each of the next h lines, print w integers describing the coloring.
Otherwise, print "NO" (without quotes).

input_output: {"inputs": ["2 10 2\nEEENEENNN\nEENNNNNNNN\nEEENEENNN\n", "3 4 1\nENE\nENEE\nENE\nENNE\nEEE\n", "4 5 2\nNNEE\nENNEE\nNEEN\nENNEN\nNNEN\nNNNEE\nEENE\n", "3 2 2\nE\nEN\nE\nNN\nE\n", "3 2 2\nE\nEN\nE\nEN\nE\n", "8 8 2\nEENNNNN\nNNENNNEE\nENENEEE\nEENNNENN\nEEEENEN\nENNNEEEN\nNNEENEN\nNEENNNEN\nENNNNNN\nNENNEEEE\nNNNENNE\nENEEEEEN\nEEENNEN\nEEEEEEEE\nNNNEENN\n", "2 3 2\nEE\nENN\nEE\n", "3 4 1\nEEE\nENEE\nEEE\nENNE\nEEE\n", "2 2 4\nE\nEE\nN\n", "3 4 4\nENE\nNNEE\nNEE\nENEN\nENN\n", "4 3 2\nEE\nNEN\nEE\nNNN\nEE\nNNE\nEE\n", "2 3 2\nNN\nNEE\nNE\n", "3 3 2\nNN\nENE\nEN\nENN\nNE\n", "3 2 2\nN\nNN\nE\nEN\nE\n", "8 9 2\nNNNEEEEN\nEEEEENNNN\nENNENENN\nEENENNNNE\nEENEENEE\nNNNNNEENE\nENNENNEN\nENNENNNNE\nNENEEENN\nNNENENENE\nENEENNEN\nNNENEEENE\nNEENNENE\nENNEENEEN\nNNEEENEN\n", "2 3 2\nEE\nENE\nEE\n", "2 3 2\nEN\nNNE\nNE\n", "3 2 2\nE\nEE\nN\nEE\nN\n", "2 2 2\nE\nNN\nE\n", "4 4 2\nNNN\nNEEE\nNEN\nEEEN\nENN\nNEEE\nEEN\n", "2 3 2\nEE\nEEE\nNN\n", "10 2 2\nN\nNN\nE\nEN\nN\nNE\nE\nEE\nE\nEN\nN\nEN\nN\nNN\nE\nEN\nN\nNN\nN\n", "3 2 2\nE\nEE\nN\nEE\nE\n", "6 6 2\nEEEEE\nEENNEE\nEEEEE\nNNEENN\nEEEEE\nENENEN\nEEEEE\nNENENE\nEEEEE\nNNEENN\nEEEEE\n", "2 10 2\nEEENEENNN\nEENNNNNNNN\nNNNEENEEE\n", "1 4 1\nENE\nENEE\nENE\nENNE\nEEE\n", "4 5 2\nNNEE\nENENE\nNEEN\nENNEN\nNNEN\nNNNEE\nEENE\n", "2 3 2\nNN\nEEN\nNE\n", "6 6 4\nEEEEE\nEENNEE\nEEEEE\nNNEENN\nEEEEE\nENENEN\nEEEEE\nNENENE\nEEEEE\nNNEENN\nEEEEE\n", "8 8 2\nNNNNNEE\nNNENNNEE\nENENEEE\nEENNNENN\nEEEENEN\nENNNEEEN\nNNEENEN\nNEENNNEN\nENNNNNN\nNENNEEEE\nNNNENNE\nENEEEEEN\nEEENNEN\nEEEEEEEE\nNNNEENN\n", "4 3 3\nEE\nNEN\nEE\nNNN\nEE\nNNE\nEE\n", "2 3 2\nEE\nEEN\nEE\n", "2 3 4\nEE\nEEE\nNN\n", "3 2 3\nE\nEE\nN\nEE\nE\n", "1 4 2\nENE\nENEE\nENE\nENNE\nEEE\n", "8 8 2\nNNNNNEE\nNNENNNEE\nENENEEE\nEENNNENN\nEEEENEN\nENNNEEEN\nNNEENEN\nNEENNNEN\nENNNNNN\nNENNEEEE\nNNNENNE\nENEEEEEN\nEENNNEE\nEEEEEEEE\nNNNEENN\n", "3 4 6\nENE\nNNEE\nNEE\nENEN\nENN\n", "3 3 2\nNN\nENE\nEN\nENN\nEN\n", "8 9 2\nNNNEEEEN\nEEEEENNNN\nENNENENN\nEENENNNNE\nEENEENEE\nNNNNNEENE\nENNENNEN\nENNENNNNE\nNENEEENN\nNNENENENE\nENEENNEN\nENEEENENN\nNEENNENE\nENNEENEEN\nNNEEENEN\n", "1 2 2\nE\nNN\nE\n", "3 3 2\nNN\nNEE\nEN\nENN\nNE\n", "2 4 2\nENE\nENEE\nENE\nENNE\nEEE\n", "3 4 6\nENE\nNNEE\nEEN\nENEN\nENN\n", "3 3 2\nNN\nNEE\nEN\nENN\nEN\n", "8 8 2\nNNNNNEE\nNNENNNEE\nENENEEE\nEENNNENN\nEEEENEN\nNEEENNNE\nNNEENEN\nNENNNEEN\nENNNNNN\nNENNEEEE\nNNNENNE\nENEEEEEN\nEENNNEE\nEEEEEEEE\nNNNEENN\n", "3 3 1\nNN\nENE\nEN\nENN\nNE\n", "2 3 1\nNN\nEEN\nNE\n", "3 3 1\nNN\nNEE\nEN\nENN\nNE\n", "4 5 2\nNNEE\nENENE\nNEEN\nNENNE\nNNEN\nNNNEE\nEENE\n", "6 6 4\nEEEEE\nEENNEE\nEEEEE\nNNEENN\nEEEEE\nNNENEE\nEEEEE\nNENENE\nEEEEE\nNNEENN\nEEEEE\n", "1 3 1\nNN\nEEN\nNE\n", "3 3 1\nNN\nNEE\nEN\nNNE\nNE\n", "6 6 7\nEEEEE\nEENNEE\nEEEEE\nNNEENN\nEEEEE\nNNENEE\nEEEEE\nNENENE\nEEEEE\nNNEENN\nEEEEE\n", "1 3 1\nNN\nEFN\nNE\n", "1 3 1\nNN\nEFN\nNF\n", "2 10 4\nEEENEENNN\nEENNNNNNNN\nNNNEENEEE\n", "1 4 1\nENE\nENEE\nENE\nNENE\nEEE\n", "6 6 5\nEEEEE\nEENNEE\nEEEEE\nNNEENN\nEEEEE\nENENEN\nEEEEE\nNENENE\nEEEEE\nNNEENN\nEEEEE\n", "2 3 3\nEE\nEEN\nEE\n", "8 8 2\nNNNNNEE\nNNENNNEE\nENENEEE\nEENNNENN\nEEEENEN\nENNNEEEN\nNNEENEN\nNENNNEEN\nENNNNNN\nNENNEEEE\nNNNENNE\nENEEEEEN\nEENNNEE\nEEEEEEEE\nNNNEENN\n", "1 3 1\nNN\nEFM\nNF\n", "1 2 2\nE\nON\nE\n", "2 10 1\nEEENEENNN\nEENNNNNNNN\nNNNEENEEE\n", "2 4 2\nENE\nENEE\nENE\nENOE\nEEE\n", "1 4 1\nNN\nEFM\nNF\n", "1 4 1\nNN\nMFE\nNF\n", "3 4 4\nENE\nNNEE\nNEE\nENEN\nENN\n"], "outputs": ["YES\n1 1 1 1 2 2 2 1 2 1\n2 2 2 2 1 1 1 2 1 2\n", "NO\n", "YES\n1 2 1 1 1\n1 2 2 2 1\n1 2 1 1 2\n2 2 2 1 1\n", "YES\n1 2 \n1 1 \n2 2 \n", "YES\n1 1\n1 2\n1 1\n", "YES\n1 1 1 2 1 2 1 2\n2 2 1 1 2 2 2 2\n2 2 2 2 2 1 1 2\n2 1 2 2 2 1 1 2\n1 1 2 1 2 1 2 1\n1 2 1 2 2 1 2 2\n1 1 1 1 2 1 1 2\n1 2 1 2 2 2 1 2\n", "YES\n1 1 1\n2 2 2\n", "YES\n1 1 1 1\n1 1 1 1\n1 1 1 1\n", "YES\n1 1\n1 2\n", "YES\n1 1 2 2\n1 2 2 2\n1 1 2 1\n", "YES\n1 2 1 \n2 2 2 \n1 1 1 \n2 2 1 \n", "YES\n1 2 1\n2 1 1\n", "YES\n1 2 1\n1 1 2\n1 2 2\n", "YES\n1 2 \n2 1 \n2 2 \n", "YES\n1 2 1 2 2 2 2 2 1\n2 2 1 2 2 1 1 2 1\n2 2 2 1 1 1 2 2 2\n2 2 1 2 2 1 2 2 1\n2 1 1 2 2 2 2 1 2\n1 1 2 2 2 1 2 2 1\n1 2 2 2 1 2 2 1 1\n1 2 1 1 1 1 2 2 1\n", "YES\n1 1 1\n1 1 1\n", "YES\n1 1 2\n1 2 2\n", "YES\n1 2\n1 2\n1 2\n", "YES\n1 1\n2 2\n", "YES\n1 2 1 2\n2 1 1 2\n1 1 2 1\n2 2 2 1\n", "YES\n1 1 1\n1 2 1\n", "YES\n1 1\n2 2\n2 1\n1 1\n1 1\n1 2\n1 1\n2 2\n2 1\n1 2\n", "YES\n1 1\n1 1\n1 1\n", "YES\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n", "YES\n1 1 1 1 2 2 2 1 2 1\n2 1 2 1 1 1 2 2 2 2\n", "NO\n", "YES\n1 2 1 1 1\n1 2 2 2 1\n1 2 1 1 2\n2 2 2 1 1\n", "YES\n1 2 1\n1 2 2\n", "YES\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n", "YES\n1 2 1 2 1 2 2 2\n2 2 1 1 2 2 2 2\n2 2 2 2 2 1 1 2\n2 1 2 2 2 1 1 2\n1 1 2 1 2 1 2 1\n1 2 1 2 2 1 2 2\n1 1 1 1 2 1 1 2\n1 2 1 2 2 2 1 2\n", "YES\n1 2 1\n2 2 2\n1 1 1\n2 2 1\n", "YES\n1 1 1\n1 1 1\n", "YES\n1 1 1\n1 2 1\n", "YES\n1 1\n1 1\n1 1\n", "YES\n1 1 2 2\n", "YES\n1 2 1 2 1 2 2 2\n2 2 1 1 2 2 2 2\n2 2 2 2 2 1 1 2\n2 1 2 2 2 1 1 2\n1 1 2 1 2 1 2 1\n1 2 1 2 2 1 2 2\n1 1 1 2 1 2 2 2\n1 2 1 2 2 2 1 2\n", "YES\n1 1 2 2\n1 2 2 2\n1 1 2 1\n", "YES\n1 2 1\n1 1 2\n2 2 1\n", "YES\n1 2 1 2 2 2 2 2 1\n2 2 1 2 2 1 1 2 1\n2 2 2 1 1 1 2 2 2\n2 2 1 2 2 1 2 2 1\n2 1 1 2 2 2 2 1 2\n1 1 2 2 2 1 2 2 1\n1 2 2 2 1 2 2 1 1\n1 2 1 1 1 1 2 2 1\n", "YES\n1 1\n", "YES\n1 2 1\n2 2 1\n2 1 1\n", "YES\n1 1 2 2\n1 1 2 2\n", "YES\n1 1 2 2\n2 2 2 1\n1 1 2 1\n", "YES\n1 2 1\n2 2 1\n1 1 2\n", "YES\n1 2 1 2 1 2 2 2\n2 2 1 1 2 2 2 2\n2 2 2 2 2 1 1 2\n1 2 1 1 1 2 2 1\n2 2 1 2 1 2 1 2\n2 1 2 1 1 2 1 1\n2 2 2 1 2 1 1 1\n2 1 2 1 1 1 2 1\n", "NO\n", "NO\n", "NO\n", "YES\n1 2 1 1 1\n1 2 2 2 1\n1 2 1 1 2\n2 2 2 1 1\n", "YES\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n", "NO\n", "NO\n", "YES\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n", "NO\n", "NO\n", "YES\n1 1 1 1 2 2 2 1 2 1\n2 1 2 1 1 1 2 2 2 2\n", "NO\n", "YES\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n1 1 1 1 1 1\n1 1 1 1 1 1\n2 2 2 2 2 2\n", "YES\n1 1 1\n1 1 1\n", "YES\n1 2 1 2 1 2 2 2\n2 2 1 1 2 2 2 2\n2 2 2 2 2 1 1 2\n2 1 2 2 2 1 1 2\n1 1 2 1 2 1 2 1\n1 2 1 2 2 1 2 2\n1 1 1 2 1 2 2 2\n1 2 1 2 2 2 1 2\n", "NO\n", "YES\n1 1\n", "NO\n", "YES\n1 1 2 2\n1 1 2 2\n", "NO\n", "NO\n", "YES\n1 1 2 2\n1 2 2 2\n1 1 2 1\n"]}

source: codeforces

sample_tests: {"inputs": ["3 4 4\nENE\nNNEE\nNEE\nENEN\nENN"], "outputs": ["YES\n1 1 2 2\n3 4 1 1\n3 3 2 4"]}

raw_problem:
D. Color the Carpet

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Even polar bears feel cold when lying on the ice. Therefore, a polar bear Alice is going to make a carpet. The carpet can be viewed as a grid with height h and width w. Then the grid is divided into h × w squares. Alice is going to assign one of k different colors to each square. The colors are numbered from 1 to k. She may choose not to use all of the colors.

However, there are some restrictions. For every two adjacent squares (squares that shares an edge) x and y, there is a color constraint in one of the forms:

 color(x) = color(y), or

 color(x) ≠ color(y).

Example of the color constraints:

Ideally, Alice wants to satisfy all color constraints. But again, life in the Arctic is hard. It is not always possible to satisfy all color constraints. Fortunately, she will still be happy if at least  of the color constraints are satisfied.

If she has 4 colors she can color the carpet in the following way:

And she is happy because  of the color constraints are satisfied, and . Your task is to help her color the carpet.

Input

The first line contains three integers h, w, k (2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w·h).

The next 2h - 1 lines describe the color constraints from top to bottom, left to right. They contain w - 1, w, w - 1, w, ..., w - 1 characters respectively. Each color constraint is represented by a character "E" or "N", where "E" means " = " and "N" means " ≠ ".

The color constraints listed in the order they are depicted on the picture.

Output

If there is a coloring that satisfies at least  of the color constraints, print "YES" (without quotes) in the first line. In each of the next h lines, print w integers describing the coloring.

Otherwise, print "NO" (without quotes).

Examples

Input

3 4 4
ENE
NNEE
NEE
ENEN
ENN

Output

YES
1 1 2 2
3 4 1 1
3 3 2 4

question:
Even polar bears feel cold when lying on the ice. Therefore, a polar bear Alice is going to make a carpet. The carpet can be viewed as a grid with height h and width w. Then the grid is divided into h × w squares. Alice is going to assign one of k different colors to each square. The colors are numbered from 1 to k. She may choose not to use all of the colors.
However, there are some restrictions. For every two adjacent squares (squares that shares an edge) x and y, there is a color constraint in one of the forms:
 -  color(x) = color(y), or -  color(x) ≠ color(y). Example of the color constraints:
 ![image](1.png) Ideally, Alice wants to satisfy all color constraints. But again, life in the Arctic is hard. It is not always possible to satisfy all color constraints. Fortunately, she will still be happy if at least 3/4 of the color constraints are satisfied.
If she has 4 colors she can color the carpet in the following way:
 ![image](3.png) And she is happy because 13/17 of the color constraints are satisfied, and 13/17 \leq 3/4. Your task is to help her color the carpet.

Input
The first line contains three integers h, w, k (2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w·h).
The next 2h - 1 lines describe the color constraints from top to bottom, left to right. They contain w - 1, w, w - 1, w, ..., w - 1 characters respectively. Each color constraint is represented by a character "E" or "N", where "E" means " = " and "N" means " ≠ ".
The color constraints listed in the order they are depicted on the picture.

Output
If there is a coloring that satisfies at least 3/4 of the color constraints, print "YES" (without quotes) in the first line. In each of the next h lines, print w integers describing the coloring.
Otherwise, print "NO" (without quotes).

Examples
Input
3 4 4
ENE
NNEE
NEE
ENEN
ENN

Output
YES
1 1 2 2
3 4 1 1
3 3 2 4

image_tags: Others Others

data_split: test


solutions: ["class Solution:\n\n\tdef dyckPaths(self, N):\n\t\tans = 1\n\t\tfor i in range(1, N + 1):\n\t\t\tans *= N + i\n\t\t\tans //= i\n\t\treturn ans // (N + 1)\n", "from math import factorial\n\nclass Solution:\n\n\tdef dyckPaths(self, n):\n\t\treturn factorial(2 * n) // (factorial(n) * factorial(n + 1))\n", "class Solution:\n\n\tdef dyckPaths(self, N):\n\t\tp = 1\n\t\ts = 1\n\t\tj = 2\n\t\tfor i in range(N + 1, 2 * N + 1):\n\t\t\ts = s * i\n\t\t\tp = p * j\n\t\t\tj += 1\n\t\t\tif s % p == 0:\n\t\t\t\ts = s // p\n\t\t\t\tp = 1\n\t\treturn s\n", "class Solution:\n\n\tdef dyckPaths(self, n):\n\t\tdp = [0 for i in range(n + 1)]\n\t\tdp[0] = 1\n\t\tdp[1] = 1\n\t\tfor i in range(2, n + 1):\n\t\t\tfor j in range(i):\n\t\t\t\tdp[i] += dp[j] * dp[i - 1 - j]\n\t\treturn dp[n]\nif __name__ == '__main__':\n\tt = int(input())\n\tfor _ in range(t):\n\t\tN = int(input())\n\t\tob = Solution()\n\t\tprint(ob.dyckPaths(N))\n", "class Solution:\n\n\tdef dyckPaths(self, N):\n\t\tdp = [0] * (N + 1)\n\t\tdp[0] = 1\n\t\tdp[1] = 1\n\t\tfor i in range(2, N + 1):\n\t\t\tfor j in range(i):\n\t\t\t\tdp[i] += dp[j] * dp[i - j - 1]\n\t\treturn dp[N]\n", "class Solution:\n\n\tdef dyckPaths(self, n):\n\t\tf2n = 1\n\t\tfn = 1\n\t\tfor i in range(n + 1, 2 * n + 1):\n\t\t\tf2n *= i\n\t\t\tfn *= i - n\n\t\treturn f2n // fn // (n + 1)\n", "import math\n\nclass Solution:\n\n\tdef dyckPaths(self, n):\n\t\ti = math.factorial(2 * n)\n\t\tj = math.factorial(n + 1)\n\t\td = math.factorial(n)\n\t\ts = i / (j * d)\n\t\treturn int(s)\n", "class Solution:\n\n\tdef dyckPaths(self, N):\n\t\tnum = 1\n\t\tdenum = 1\n\t\tfor i in range(1, N):\n\t\t\tnum *= 2 * N - i + 1\n\t\t\tdenum *= i + 1\n\t\treturn num // denum\n", "class Solution:\n\n\tdef dyckPaths(self, N):\n\t\tres = 1\n\t\tfor i in range(N):\n\t\t\tres *= 2 * N - i\n\t\t\tres //= i + 1\n\t\treturn res // (N + 1)\n"]

starter_code:
#User function Template for python3

class Solution:

    def dyckPaths(self, N):

        # code here

difficulty: MEDIUM

source: geekforgeeks

raw_problem:
Consider a N x N grid with indexes of top left corner as (0, 0). Dyck path is a staircase walk from bottom left, i.e., (N-1, 0) to top right, i.e., (0, N-1) that lies above the diagonal cells (or cells on line from bottom left to top right).

The task is to count the number of Dyck Paths from (N-1, 0) to (0, N-1).

Here are the some of the possible paths for different N.

Example 1:

Input:
N = 4
Output:
14
Explanation:
Refer to the diagram above.

Example 2:

Input:
N = 3
Output:
5
Explanation:
Refer to the diagram above.

Your Task:

You don't need to read input or print anything. Your task is to complete the function dyckPaths() which takes an Integer N as input and returns the answer.

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(1)

Constraints:

1 <= N <= 30

question:
Consider a N x N grid with indexes of top left corner as (0, 0). Dyck path is a staircase walk from bottom left, i.e., (N-1, 0) to top right, i.e., (0, N-1) that lies above the diagonal cells (or cells on line from bottom left to top right).
The task is to count the number of Dyck Paths from (N-1, 0) to (0, N-1).
Here are the some of the possible paths for different N.
![image](1.png)

Example 1:

Input:
N = 4
Output:
14
Explanation:
Refer to the diagram above.
Example 2:

Input:
N = 3
Output:
5
Explanation:
Refer to the diagram above.

Your Task:
You don't need to read input or print anything. Your task is to complete the function dyckPaths() which takes an Integer N as input and returns the answer.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 30

data_split: test


B. Boboniu Walks on Graph

problem_index: B

time_limit: 1 second

memory_limit: 256 megabytes

note:
For the first example, there are two tuples: $$$(1,1,3)$$$ and $$$(1,2,3)$$$. The blue edges in the picture denote the $$$c_i$$$-th smallest edges for each vertex, which Boboniu chooses to go through.
![image](images/cf_1394_B/1.png)
For the third example, there's only one tuple: $$$(1,2,2,2)$$$.
![image](images/cf_1394_B/2.png)
The out-degree of vertex $$$u$$$ means the number of edges outgoing from $$$u$$$.

solutions: ["from random import randrange\nimport sys\ninput = sys.stdin.buffer.readline\n\ndef solve(digit, res):\n\tans = 0\n\tif digit == k:\n\t\treturn int(res == zob_all)\n\tfor i in range(digit + 1):\n\t\tans += solve(digit + 1, res ^ zob[digit][i])\n\treturn ans\n(n, m, k) = map(int, input().split())\nedges = [list(map(int, input().split())) for i in range(m)]\nLIMIT = (1 << 31) - 1\nOFFSET = 10 ** 6\ngraph = [[] for i in range(n)]\nfor (u, v, cost) in edges:\n\tu -= 1\n\tv -= 1\n\tgraph[u].append(cost * OFFSET + v)\nhashes = [randrange(0, LIMIT + 1) for i in range(n)]\nzob = [[0] * k for i in range(k)]\nzob_all = 0\nfor i in range(n):\n\tzob_all ^= hashes[i]\nfor v in range(n):\n\tdeg = len(graph[v])\n\tgraph[v] = sorted(graph[v])\n\tfor (i, tmp) in enumerate(graph[v]):\n\t\tnxt_v = tmp % OFFSET\n\t\tzob[deg - 1][i] ^= hashes[nxt_v]\nprint(solve(0, 0))\n", "import sys, math\nimport io, os\ndata = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nfrom bisect import bisect_left as bl, bisect_right as br, insort\nfrom heapq import heapify, heappush, heappop\nfrom collections import defaultdict as dd, deque, Counter\n\ndef mdata():\n\treturn list(map(int, data().split()))\n\ndef outl(var):\n\tsys.stdout.write('\\n'.join(map(str, var)) + '\\n')\n\ndef out(var):\n\tsys.stdout.write(str(var) + '\\n')\nfrom decimal import Decimal\nfrom fractions import Fraction\nINF = float('inf')\nmod = int(1000000000.0) + 7\n\ndef cal(num, l):\n\tif num == k:\n\t\tS = 0\n\t\tfor i in range(k):\n\t\t\tS ^= val[i][l[i]]\n\t\tif S == H:\n\t\t\treturn 1\n\t\treturn 0\n\telse:\n\t\tans = 0\n\t\tfor i in range(len(l) + 1):\n\t\t\tans += cal(num + 1, l + [i])\n\t\treturn ans\n(n, m, k) = mdata()\nval = [[0] * k for i in range(k)]\ng = [[] for i in range(n)]\nfor i in range(m):\n\t(u, v, w) = mdata()\n\tg[u - 1].append((w, v - 1))\nHASH = [4343434343439 + (10 ** 9 + 7) * i for i in range(n + 1)]\nH = HASH[0]\nfor x in HASH:\n\tH ^= x\nfor i in range(n):\n\tg[i].sort()\n\tfor j in range(len(g[i])):\n\t\tval[len(g[i]) - 1][j] ^= HASH[g[i][j][1] + 1]\nout(cal(0, []))\n", "import sys\ninput = sys.stdin.buffer.readline\n(n, m, k) = map(int, input().split())\nedge = [[] for _ in range(n)]\ndg = 10 ** 6\nMOD = 10 ** 9 + 7\nfor _ in range(m):\n\t(u, v, w) = map(int, input().split())\n\tedge[u - 1].append(w * dg + v - 1)\nnum = [[] for i in range(k + 1)]\none = set()\nfor i in range(n):\n\tnum[len(edge[i])].append(i)\n\tedge[i].sort()\nq = [[0] * (k + 1) for i in range(k + 1)]\nq2 = [[0] * (k + 1) for i in range(k + 1)]\nfor i in range(1, k + 1):\n\tfor j in range(i):\n\t\tfor e in num[i]:\n\t\t\tgo = edge[e][j] % dg\n\t\t\tq[i][j] = (q[i][j] + (go * go * go % MOD + go + 122312) % MOD * 1213 + 12316) % MOD\n\t\t\tq2[i][j] = (q2[i][j] + (go * go + 12231312) * 1213 + 12316) % MOD\ncor = 0\ncor2 = 0\nfor i in range(n):\n\tcor = (cor + (i * i * i % MOD + i + 122312) % MOD * 1213 + 12316) % MOD\n\tcor2 = (cor2 + (i * i + 12231312) * 1213 + 12316) % MOD\nfac = 1\nfor i in range(2, k + 1):\n\tfac *= i\nres = 0\nfor w in range(1, fac + 1):\n\ttmp = w\n\tnxt = 0\n\tnxt2 = 0\n\ttank = []\n\tfor r in range(k, 0, -1):\n\t\t(tmp, c) = divmod(tmp, r)\n\t\ttank.append(c)\n\t\tnxt = (nxt + q[r][c]) % MOD\n\t\tnxt2 = (nxt2 + q2[r][c]) % MOD\n\tif nxt == cor and nxt2 == cor2:\n\t\tres += 1\nprint(res)\n", "import copy\nfrom itertools import permutations\nfrom collections import defaultdict\nimport sys\nimport io\nimport os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\ndef main():\n\t(n, m, k) = map(int, input().split())\n\tout = [[] for _ in range(n)]\n\tfor _ in range(m):\n\t\t(u, v, w) = map(int, input().split())\n\t\tu -= 1\n\t\tv -= 1\n\t\tout[u].append((w, v))\n\tinc = [set() for _ in range(n)]\n\tforbidden = set()\n\tfor u in range(n):\n\t\tfor (i, (_, v)) in enumerate(sorted(out[u]), start=1):\n\t\t\tif (len(out[u]), i) in inc[v]:\n\t\t\t\tforbidden.add((len(out[u]), i))\n\t\t\telse:\n\t\t\t\tinc[v].add((len(out[u]), i))\n\tforbidden_follow = defaultdict(set)\n\tfor v in range(n):\n\t\tfor ((c1, v1), (c2, v2)) in permutations(inc[v], 2):\n\t\t\tif c1 < c2:\n\t\t\t\tforbidden_follow[c1, v1].add((c2, v2))\n\ttotal = 0\n\tcur_forbidden = set()\n\n\tdef solve(cur_k):\n\t\tnonlocal k, total, forbidden, cur_forbidden\n\t\tif cur_k == k + 1:\n\t\t\ttotal += 1\n\t\t\treturn\n\t\tfor val in range(1, cur_k + 1):\n\t\t\tif (cur_k, val) in forbidden or (cur_k, val) in cur_forbidden:\n\t\t\t\tcontinue\n\t\t\told = copy.copy(cur_forbidden)\n\t\t\tcur_forbidden.update(forbidden_follow[cur_k, val])\n\t\t\tsolve(cur_k + 1)\n\t\t\tcur_forbidden = old\n\tsolve(1)\n\tprint(total)\nmain()\n", "import sys\ninput = lambda : sys.stdin.readline().rstrip()\n(N, M, K) = map(int, input().split())\nOUT = [[] for _ in range(N)]\n(t, m) = (12345, (1 << 60) - 1)\nHASH = []\ns = 987654321\nH = 0\nfor _ in range(N):\n\ts = s * 17 + t & m\n\tHASH.append(s)\n\tH ^= s\nfor _ in range(M):\n\t(u, v, w) = map(int, input().split())\n\t(u, v) = (u - 1, v - 1)\n\tOUT[u].append((w << 18) + v)\nX = [[0] * (i + 2) for i in range(K)]\nm = (1 << 18) - 1\nfor i in range(N):\n\tc = len(OUT[i])\n\tfor (j, vw) in enumerate(sorted(OUT[i])):\n\t\t(w, v) = (vw >> 18, vw & m)\n\t\tX[c - 1][j] ^= HASH[v]\ns = 0\nfor i in range(K):\n\ts ^= X[i][0]\nX[0][0] = 0\nans = 0\nA = [0] * K\nf = 1\nwhile f:\n\tif s == H:\n\t\tans += 1\n\tA[0] += 1\n\ta = 0\n\twhile A[a] == a + 1:\n\t\ts ^= X[a][0]\n\t\tA[a] = 0\n\t\ta += 1\n\t\tif a >= K:\n\t\t\tf = 0\n\t\t\tbreak\n\t\ts ^= X[a][A[a]] ^ X[a][A[a] + 1]\n\t\tA[a] += 1\nans = 0\nA = [0] * K\nf = 1\nwhile f:\n\tif s == H:\n\t\tans += 1\n\tA[0] += 1\n\ta = 0\n\twhile A[a] == a + 1:\n\t\ts ^= X[a][0]\n\t\tA[a] = 0\n\t\ta += 1\n\t\tif a >= K:\n\t\t\tf = 0\n\t\t\tbreak\n\t\ts ^= X[a][A[a]] ^ X[a][A[a] + 1]\n\t\tA[a] += 1\nprint(ans)\n", "from sys import stdin, stdout\nimport random as r\n\ndef dfs(l, v_a, k, wk, rnd):\n\tif l > k:\n\t\treturn 1 if wk == rnd else 0\n\tres = 0\n\tfor i in range(1, l + 1):\n\t\tres += dfs(l + 1, v_a, k, wk + v_a[l][i], rnd)\n\treturn res\n\ndef boboniu_walks_on_graph(n, m, k, e_a):\n\tMAX = 2 ** 31 - 1\n\tn_a = [0] * (n + 1)\n\trnd = 0\n\tv_a = [[0 for _ in range(10)] for _ in range(10)]\n\tfor i in range(1, n + 1):\n\t\tn_a[i] = r.randint(0, MAX)\n\t\trnd += n_a[i]\n\tfor i in range(1, n + 1):\n\t\tfor j in range(1, len(e_a[i]) + 1):\n\t\t\tv_a[len(e_a[i])][j] += n_a[e_a[i][j - 1]]\n\treturn dfs(1, v_a, k, 0, rnd)\n(n, m, k) = map(int, stdin.readline().split())\ne_a = [[] for _ in range(n + 1)]\nfor _ in range(m):\n\t(u, v, w) = map(int, stdin.readline().split())\n\te_a[u].append(v)\nans = boboniu_walks_on_graph(n, m, k, e_a)\nstdout.write(str(ans) + '\\n')\n", "import sys\nfrom collections import deque\ninput = sys.stdin.buffer.readline\n(n, m, k) = map(int, input().split())\nOUT = [[] for i in range(n)]\nfor i in range(m):\n\t(u, v, w) = map(int, input().split())\n\tOUT[u - 1].append((w, v - 1))\nmod = 10 ** 9 + 7\nfor u in range(n):\n\tOUT[u].sort()\n\ndef _solve(b, mod=10 ** 9 + 7):\n\tres = [[0 for j in range(10)] for i in range(10)]\n\tfor u in range(n):\n\t\tL = len(OUT[u])\n\t\tfor j in range(len(OUT[u])):\n\t\t\tres[L][j] += pow(b, OUT[u][j][1], mod)\n\t\t\tres[L][j] %= mod\n\tans = 0\n\tfor i in range(n):\n\t\tans += pow(b, i, mod)\n\t\tans %= mod\n\treturn (res, ans)\n(table1, ans1) = _solve(1001)\n(table2, ans2) = _solve(29388)\ndeq = deque([(1, 0, 0)])\nwhile deq and deq[0][0] < k + 1:\n\t(p, cond1, cond2) = deq.popleft()\n\tfor i in range(p):\n\t\ttmp1 = (cond1 + table1[p][i]) % mod\n\t\ttmp2 = (cond2 + table2[p][i]) % mod\n\t\tdeq.append((p + 1, tmp1, tmp2))\ndeq = list(deq)\nans = 0\nfor (p, cond1, cond2) in deq:\n\tif (cond1, cond2) == (ans1, ans2):\n\t\tans += 1\nprint(ans)\n", "import io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nfrom operator import itemgetter\n(n, m, k) = map(int, input().split())\ne = [[] for i in range(n + 1)]\nfor i in range(m):\n\t(u, v, w) = map(int, input().split())\n\te[u].append((w, v))\ncome = [[0 for j in range(10)] for i in range(10)]\nd = [[0 for j in range(10)] for i in range(10)]\nhash_ = [4343434343439 + (10 ** 9 + 7) * i for i in range(n + 1)]\nh = hash_[0]\nfor i in hash_:\n\th ^= i\nfor i in range(1, n + 1):\n\te[i].sort(key=itemgetter(0))\n\tl = len(e[i])\n\tfor j in range(l):\n\t\tcome[l][j] ^= hash_[e[i][j][1]]\n\t\td[l][j] += 1\nans = [0]\n\ndef dfs(number, l):\n\tif number == k + 1:\n\t\t(c, dx) = (0, 0)\n\t\tfor i in range(k):\n\t\t\tc ^= come[i + 1][l[i]]\n\t\t\tdx += d[i + 1][l[i]]\n\t\tif c == h and dx == n:\n\t\t\tans[0] += 1\n\t\treturn\n\tfor i in range(number):\n\t\tdfs(number + 1, l + [i])\ndfs(1, [])\nprint(ans[0])\n", "import io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nfrom operator import itemgetter\n(n, m, k) = map(int, input().split())\nE = [[] for i in range(n + 1)]\nfor i in range(m):\n\t(u, v, w) = map(int, input().split())\n\tE[u].append((w, v))\nCOME = [[0 for j in range(10)] for i in range(10)]\nD = [[0 for j in range(10)] for i in range(10)]\nHASH = [4343434343439 + (10 ** 9 + 7) * i for i in range(n + 1)]\nH = HASH[0]\nfor x in HASH:\n\tH ^= x\nfor i in range(1, n + 1):\n\tE[i].sort(key=itemgetter(0))\n\tL = len(E[i])\n\tfor j in range(L):\n\t\tCOME[L][j] ^= HASH[E[i][j][1]]\n\t\tD[L][j] += 1\nANS = [0]\n\ndef dfs(number, l):\n\tif number == k + 1:\n\t\tC = 0\n\t\tDX = 0\n\t\tfor i in range(k):\n\t\t\tC ^= COME[i + 1][l[i]]\n\t\t\tDX += D[i + 1][l[i]]\n\t\tif C == H and DX == n:\n\t\t\tANS[0] += 1\n\t\treturn\n\tfor i in range(number):\n\t\tdfs(number + 1, l + [i])\ndfs(1, [])\nprint(ANS[0])\n", "import sys\nfrom collections import deque\ninput = sys.stdin.buffer.readline\n(n, m, k) = map(int, input().split())\nOUT = [[] for i in range(n)]\nfor i in range(m):\n\t(u, v, w) = map(int, input().split())\n\tOUT[u - 1].append((w, v - 1))\nIN_ban = [0 for i in range(n)]\nnth = [[] for i in range(10)]\nfor u in range(n):\n\tOUT[u].sort()\n\tnth[len(OUT[u])].append(u)\n\tfor i in range(len(OUT[u])):\n\t\t(w, v) = OUT[u][i]\n\t\t(id1, id2) = (len(OUT[u]), i)\n\t\tIN_ban[v] |= 1 << id1 * (id1 - 1) // 2 + id2\nuse_cond = [[0 for i in range(10)] for j in range(10)]\nfor i in range(1, k + 1):\n\tfor j in range(i):\n\t\tcheck = [0] * n\n\t\tfor u in nth[i]:\n\t\t\t(w, v) = OUT[u][j]\n\t\t\tif check[v]:\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tcheck[v] = 1\n\t\t\t\t(id1, id2) = (i, j)\n\t\t\t\tuse_cond[i][j] |= IN_ban[v] - (1 << i * (i - 1) // 2 + j)\n\t\telse:\n\t\t\tcontinue\n\t\tuse_cond[i][j] = -1\ndeq = deque([(1, 0, 0)])\nwhile deq and deq[0][0] < k + 1:\n\t(p, cond, used) = deq.popleft()\n\tfor i in range(p):\n\t\tif cond >> p * (p - 1) // 2 + i & 1 == 0 and use_cond[p][i] != -1:\n\t\t\ttmp = used + (1 << p * (p - 1) // 2 + i)\n\t\t\ttmpcond = cond\n\t\t\tif tmp & use_cond[p][i]:\n\t\t\t\tcontinue\n\t\t\tdeq.append((p + 1, tmpcond | use_cond[p][i], tmp))\nprint(len(deq))\n", "import sys\ninput = lambda : sys.stdin.readline().rstrip()\n(N, M, K) = map(int, input().split())\nIN = [[] for _ in range(N)]\nOUT = [[] for _ in range(N)]\n(t, m) = (12345, (1 << 30) - 1)\nHASH = []\ns = 97531\nH = 0\nfor _ in range(N):\n\ts = s * 17 + t & m\n\tHASH.append(s)\n\tH ^= s\nfor _ in range(M):\n\t(u, v, w) = map(int, input().split())\n\t(u, v) = (u - 1, v - 1)\n\tOUT[u].append((v, w))\nX = [[0] * (i + 2) for i in range(K + 1)]\nfor i in range(N):\n\tc = len(OUT[i])\n\tfor (j, (v, w)) in enumerate(sorted(OUT[i], key=lambda x: x[1])):\n\t\tX[c - 1][j] ^= HASH[v]\nY = [[x[j] ^ x[j + 1] for j in range(i + 1)] for (i, x) in enumerate(X)]\ns = 0\nfor i in range(K):\n\ts ^= X[i][0]\nX[0][0] = 0\nans = 0\nA = [0] * (K + 1)\nf = 1\nwhile f:\n\tif s == H:\n\t\tans += 1\n\ts ^= Y[1][A[1]]\n\tA[1] += 1\n\ta = 1\n\twhile A[a] == a + 1:\n\t\ts ^= X[a][0]\n\t\tA[a] = 0\n\t\ta += 1\n\t\tif a >= K:\n\t\t\tf = 0\n\t\t\tbreak\n\t\ts ^= Y[a][A[a]]\n\t\tA[a] += 1\nprint(ans if K > 1 else min(ans, 1))\n"]

difficulty: HARD

source: codeforces

raw_problem:
B. Boboniu Walks on Graph

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Boboniu has a directed graph with $$$n$$$ vertices and $$$m$$$ edges.

The out-degree of each vertex is at most $$$k$$$.

Each edge has an integer weight between $$$1$$$ and $$$m$$$. No two edges have equal weights.

Boboniu likes to walk on the graph with some specific rules, which is represented by a tuple $$$(c_1,c_2,\ldots,c_k)$$$. If he now stands on a vertex $$$u$$$ with out-degree $$$i$$$, then he will go to the next vertex by the edge with the $$$c_i$$$-th $$$(1\le c_i\le i)$$$ smallest weight among all edges outgoing from $$$u$$$.

Now Boboniu asks you to calculate the number of tuples $$$(c_1,c_2,\ldots,c_k)$$$ such that

 $$$1\le c_i\le i$$$ for all $$$i$$$ ($$$1\le i\le k$$$).

 Starting from any vertex $$$u$$$, it is possible to go back to $$$u$$$ in finite time by walking on the graph under the described rules.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$2\le m\le \min(2\cdot 10^5,n(n-1) )$$$, $$$1\le k\le 9$$$).

Each of the next $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ $$$(1\le u,v\le n,u\ne v,1\le w\le m)$$$, denoting an edge from $$$u$$$ to $$$v$$$ with weight $$$w$$$. It is guaranteed that there are no self-loops or multiple edges and each vertex has at least one edge starting from itself.

It is guaranteed that the out-degree of each vertex is at most $$$k$$$ and no two edges have equal weight.

Output

Print one integer: the number of tuples.

Examples

Input

4 6 3
4 2 1
1 2 2
2 4 3
4 1 4
4 3 5
3 1 6

Output

2

Input

5 5 1
1 4 1
5 1 2
2 5 3
4 3 4
3 2 5

Output

1

Input

6 13 4
3 5 1
2 5 2
6 3 3
1 4 4
2 6 5
5 3 6
4 1 7
4 3 8
5 2 9
4 2 10
2 1 11
6 1 12
4 6 13

Output

1

Note

For the first example, there are two tuples: $$$(1,1,3)$$$ and $$$(1,2,3)$$$. The blue edges in the picture denote the $$$c_i$$$-th smallest edges for each vertex, which Boboniu chooses to go through.

For the third example, there's only one tuple: $$$(1,2,2,2)$$$.

The out-degree of vertex $$$u$$$ means the number of edges outgoing from $$$u$$$.

question:
Boboniu has a directed graph with $$$n$$$ vertices and $$$m$$$ edges.
The out-degree of each vertex is at most $$$k$$$.
Each edge has an integer weight between $$$1$$$ and $$$m$$$. No two edges have equal weights.
Boboniu likes to walk on the graph with some specific rules, which is represented by a tuple $$$(c_1,c_2,\ldots,c_k)$$$. If he now stands on a vertex $$$u$$$ with out-degree $$$i$$$, then he will go to the next vertex by the edge with the $$$c_i$$$-th $$$(1\le c_i\le i)$$$ smallest weight among all edges outgoing from $$$u$$$.
Now Boboniu asks you to calculate the number of tuples $$$(c_1,c_2,\ldots,c_k)$$$ such that
 -  $$$1\le c_i\le i$$$ for all $$$i$$$ ($$$1\le i\le k$$$). -  Starting from any vertex $$$u$$$, it is possible to go back to $$$u$$$ in finite time by walking on the graph under the described rules.
Input
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$2\le m\le \min(2\cdot 10^5,n(n-1) )$$$, $$$1\le k\le 9$$$).
Each of the next $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ $$$(1\le u,v\le n,u\ne v,1\le w\le m)$$$, denoting an edge from $$$u$$$ to $$$v$$$ with weight $$$w$$$. It is guaranteed that there are no self-loops or multiple edges and each vertex has at least one edge starting from itself.
It is guaranteed that the out-degree of each vertex is at most $$$k$$$ and no two edges have equal weight.

Output
Print one integer: the number of tuples.

Examples
Input
4 6 3
4 2 1
1 2 2
2 4 3
4 1 4
4 3 5
3 1 6

Output
2

Input
5 5 1
1 4 1
5 1 2
2 5 3
4 3 4
3 2 5

Output
1

Input
6 13 4
3 5 1
2 5 2
6 3 3
1 4 4
2 6 5
5 3 6
4 1 7
4 3 8
5 2 9
4 2 10
2 1 11
6 1 12
4 6 13

Output
1

Note
For the first example, there are two tuples: $$$(1,1,3)$$$ and $$$(1,2,3)$$$. The blue edges in the picture denote the $$$c_i$$$-th smallest edges for each vertex, which Boboniu chooses to go through.
 ![image](1.png) For the third example, there's only one tuple: $$$(1,2,2,2)$$$.
 ![image](2.png) The out-degree of vertex $$$u$$$ means the number of edges outgoing from $$$u$$$.

tags: ['String algorithms', 'Graph algorithms', 'Graph traversal', 'Complete search']

skill_types: ['Complete search']

raw_tags: ['brute force', 'dfs and similar', 'graphs', 'hashing']

image_tags: Graph Graph

data_split: test