solutions: ["num_integers = int(input())\nstr_in = [int(x) for x in input().strip().split(' ')]\nprint(' '.join([str(x) for x in sorted(str_in)]))\n", "r = int(input())\nf = [int(t) for t in input().split() if t.isdigit()]\nfor i in sorted(f):\n\tprint(i, end=' ')\n", "import sys\narray = [int(x) for x in sys.stdin.readlines()[1].split()]\nfor x in range(1, len(array)):\n\tval = array.pop(x)\n\twhile x > 0 and array[x - 1] > val:\n\t\tx -= 1\n\tarray.insert(x, val)\nprint(' '.join((str(x) for x in array)))\n", "def in_loc(a, n):\n\tV = a[n]\n\tif n == 1:\n\t\ttemp = a[0]\n\t\ta[0] = a[1]\n\t\ta[1] = temp\n\t\treturn a\n\tfor i in range(n - 1, -1, -1):\n\t\tif a[i] > V:\n\t\t\ta[i + 1] = a[i]\n\t\telse:\n\t\t\ta[i + 1] = V\n\t\t\tbreak\n\tif a[0] == a[1]:\n\t\ta[0] = V\n\treturn a\n\ndef insertionSort(a, n):\n\ti = 1\n\tfor i in range(1, n):\n\t\tif a[i] < a[i - 1]:\n\t\t\ta = in_loc(a, i)\n\tprint(*a, sep=' ')\n\ndef main():\n\tn = int(input())\n\ta = [int(x) for x in input().split()]\n\tinsertionSort(a, n)\nmain()\n", "size = int(input())\nv = [int(i) for i in input().strip().split()]\nprint(*sorted(v), sep=' ')\n", "n = int(input())\nl = []\nl = input().split()\nfor i in range(0, n):\n\tl[i] = int(l[i])\nl.sort()\nfor i in l:\n\tprint(i, end=' ')\n", "input()\nnums = list(map(int, input().split()))\nfor count in range(len(nums) - 1):\n\tfor i in range(count, -1, -1):\n\t\tif nums[i] > nums[i + 1]:\n\t\t\t(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])\nprint(' '.join(map(str, nums)))\n", "def main():\n\ts = int(input())\n\tar = list(map(int, input().rstrip().split()))\n\tar = sorted(ar)\n\tstrar = map(str, ar)\n\tprint(' '.join(strar))\n\treturn 0\nmain()\n", "nn = int(input())\nvec = list(map(int, input().split()))\nvec.sort()\nprint(' '.join(map(str, vec)))\n", "size = input()\narr = map(int, input().strip().split(' '))\nprint(' '.join(map(str, sorted(arr))))\n", "def insertion_sort(array):\n\tfor (i, x) in enumerate(array[1:]):\n\t\tfor (j, y) in enumerate(array[:i + 1]):\n\t\t\tif y > x:\n\t\t\t\tarray[j + 1:i + 2] = array[j:i + 1]\n\t\t\t\tarray[j] = x\n\t\t\t\tbreak\n\treturn array\n\ndef main():\n\tarray_size = int(input())\n\tarray = list(map(int, input().split()))\n\tprint(' '.join(('{}'.format(a) for a in insertion_sort(array))))\nmain()\n", "n = int(input())\nL = [int(s) for s in input().split()]\nprint(' '.join([str(i) for i in sorted(L)]))\n", "s = input().split()\nar = list(map(int, input().split()))\nV = ar[len(ar) - 1]\nsort = len(ar) - 1\nfor index in range(1, len(ar)):\n\tvalue = ar[index]\n\ti = index - 1\n\twhile i >= 0:\n\t\tif value < ar[i]:\n\t\t\tar[i + 1] = ar[i]\n\t\t\tar[i] = value\n\t\t\ti = i - 1\n\t\telse:\n\t\t\tbreak\nprint(*ar, sep=' ')\n", "n = int(input())\narray = [int(val) for val in input().split()]\nfor i in range(1, n):\n\titem = array[i]\n\tj = i\n\twhile j > 0 and array[j - 1] > item:\n\t\tarray[j] = array[j - 1]\n\t\tj -= 1\n\tarray[j] = item\n[print(val, end=' ') for val in array]\nprint()\n", "import sys\nN = int(sys.stdin.readline())\nxs = [int(X) for X in sys.stdin.readline().split()]\n[print(X, end=' ') for X in sorted(xs)]\n", "size = int(input())\nar = list(map(int, input().split()))\nfor i in range(0, len(ar)):\n\tj = i\n\twhile j >= 1 and ar[j] < ar[j - 1]:\n\t\t(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])\n\t\tj -= 1\nprint(*ar)\n", "import sys\n\ndef mToString(mArray):\n\tstartStr = ''\n\tfor el in mArray:\n\t\tstartStr = startStr + str(el) + ' '\n\treturn startStr[:-1]\n\ndef insertToArrayWithElement(numArray, myElementIndex):\n\tlastNum = numArray[myElementIndex]\n\tlastNumIndex = myElementIndex\n\twhile lastNumIndex > 0 and lastNum < numArray[lastNumIndex - 1]:\n\t\tnumArray[lastNumIndex] = numArray[lastNumIndex - 1]\n\t\tlastNumIndex = lastNumIndex - 1\n\tnumArray[lastNumIndex] = lastNum\nlines = []\nfor line in sys.stdin:\n\tlines.append(line)\narrayLen = int(lines[0])\nnumArray = list(map(int, lines[1].split()))\nfor i in range(1, arrayLen):\n\tinsertToArrayWithElement(numArray, i)\nprint(mToString(numArray))\n", "x = input()\ny = input().split()\ny = [int(i) for i in y]\ny.sort()\ny = [str(i) for i in y]\nprint(' '.join(y))\n", "def insert_sort(A):\n\tm = len(A)\n\tfor x in range(1, m):\n\t\tk = A[x]\n\t\tj = x\n\t\twhile j > 0 and A[j - 1] > k:\n\t\t\tA[j] = A[j - 1]\n\t\t\tj -= 1\n\t\tA[j] = k\n\treturn A\ni = int(input())\nN = [int(c) for c in input().split()]\nN = insert_sort(N)\nfor a in N:\n\tprint(a, end=' ')\n", "s = int(input())\nassert 1 <= s <= 1000\narray = [int(x) for x in input().split(' ')]\nsortz = array[:1]\nfor i in range(1, len(array)):\n\tsortz.append(array[i])\n\tj = len(sortz) - 1\n\twhile sortz[j] < sortz[j - 1] and j > 0:\n\t\ttemp = sortz[j]\n\t\tsortz[j] = sortz[j - 1]\n\t\tsortz[j - 1] = temp\n\t\tj -= 1\nprint(' '.join((str(x) for x in sortz)))\n", "N = int(input())\narr = [int(x) for x in input().split(' ')]\narr.sort()\nop = ''\nfor x in arr:\n\top += str(x) + ' '\nprint(op)\n", "n = int(input())\nx = [0] * n\nx = sorted(list(map(int, input().split())))\nprint(' '.join((str(i) for i in x)))\n", "import sys\n\ndef insertion_sort(arr, s):\n\tfor v in range(1, len(array)):\n\t\tvalue = arr[v]\n\t\tx = v - 1\n\t\twhile x >= 0 and arr[x] > value:\n\t\t\tarr[x + 1] = arr[x]\n\t\t\tx -= 1\n\t\tarr[x + 1] = value\n\tprint(' '.join([str(i) for i in arr]))\nsize = int(sys.stdin.readline().strip())\narray = sys.stdin.readline().strip().split()\narray = [int(x) for x in array]\ninsertion_sort(array, size)\n", "s = int(input())\narr = list(map(int, input().split()))\n\ndef swap(a, x, y):\n\t(a[x], a[y]) = (a[y], a[x])\nfor i in range(len(arr)):\n\tj = i\n\twhile j > 0 and arr[j] < arr[j - 1]:\n\t\tswap(arr, j - 1, j)\n\t\tj -= 1\nprint(' '.join(map(str, arr)))\n", "T = int(input())\narray = input().split()\nnewarray = []\nfor item in array:\n\tnewarray.append(int(item))\nnewarray.sort()\nprint(' '.join((str(x) for x in newarray)))\n", "s = int(input())\nar = [int(i) for i in str(input()).split()]\nfor i in range(1, s):\n\tx = ar[i]\n\tj = i\n\twhile j > 0 and ar[j - 1] > x:\n\t\tar[j] = ar[j - 1]\n\t\tj -= 1\n\tar[j] = x\nprint(' '.join([str(e) for e in ar]))\n", "input()\nlst = list(map(int, input().split()))\nlst.sort()\nprint(' '.join(map(str, lst)))\n", "n = int(input())\na = []\ns = input()\nnew = s.split()\ns = []\nfor ele in new:\n\ts.append(int(ele))\nnew = sorted(s)\np = ' '.join(map(str, new))\nprint(p)\n", "def get_and_return_list():\n\treturn list(map(lambda x: int(x), input().split(' ')))\n\ndef insert(sort, elem):\n\tmd = False\n\tfor i in range(len(sort)):\n\t\tif sort[i] > elem:\n\t\t\tsort.insert(i, elem)\n\t\t\tmd = True\n\t\t\tbreak\n\tif not md:\n\t\tsort.append(elem)\n\treturn sort\ns = int(input())\nar = get_and_return_list()\nsort = []\nsort.insert(0, ar.pop(0))\nwhile len(ar) > 0:\n\telement = ar.pop(0)\n\tsort = insert(sort, element)\nelems = '{}'\nfor i in sort[:-1]:\n\telems = elems.format('%s {}' % i)\nelems = elems.format(sort[-1])\nprint(elems)\n", "input()\nli = list(map(int, input().split()))\nli.sort()\nprint(*li)\n", "int(input())\nnums = sorted([int(x) for x in str(input()).split()])\nprint(' '.join([str(x) for x in nums]))\n", "import sys\ndata = sys.stdin.readlines()\ntemp = data[1].split(' ')\nunsorted = [int(a) for a in temp]\nfor _ in data[1:]:\n\tunsorted.sort()\n\tresult = ''\n\tfor i in unsorted:\n\t\tresult += str(i) + ' '\n\tresult = result.strip()\n\tprint(result)\n", "N = int(input())\ntoys = [int(x) for x in input().split()]\ntoys.sort()\nprint(' '.join(map(str, toys)))\n", "input()\nnumbers = list(map(lambda x: int(x), input().split(' ')))\nsn = sorted(numbers)\nprint(' '.join(list(map(lambda x: str(x), sn))))\n", "a = input()\nb = input().split(' ')\nb = [int(i) for i in b]\nb.sort()\nprint(*b)\n", "s = int(input())\nar = input().split()\nar = [int(ar[i]) for i in range(s)]\nar.sort()\nfor i in range(s):\n\tprint(ar[i], end=' ')\n", "N = int(input())\narr = [int(x) for x in input().split()]\nfor i in range(1, len(arr)):\n\tfor j in range(1, i + 1):\n\t\tif arr[i - j] > arr[i - j + 1]:\n\t\t\ttemp = arr[i - j]\n\t\t\tarr[i - j] = arr[i - j + 1]\n\t\t\tarr[i - j + 1] = temp\n\t\telse:\n\t\t\tbreak\nprintstr = ''\nfor x in arr:\n\tprintstr += str(x)\n\tprintstr += ' '\nprint(printstr)\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def backSwap(arr, j):\n\tA = arr[j]\n\tB = arr[j - 1]\n\tarr[j] = B\n\tarr[j - 1] = A\n\ndef insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i\n\t\twhile j > 0 and l[j] < l[j - 1]:\n\t\t\tbackSwap(l, j)\n\t\t\tj = j - 1\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j > -1:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(len(l)):\n\t\tj = i\n\t\tkey = l[i]\n\t\twhile l[j - 1] > key and j > 0:\n\t\t\tl[j] = l[j - 1]\n\t\t\tj -= 1\n\t\tl[j] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(L):\n\tfor i in range(1, len(L)):\n\t\tj = i - 1\n\t\tkey = L[i]\n\t\twhile L[j] > key and j >= 0:\n\t\t\tL[j + 1] = L[j]\n\t\t\tj -= 1\n\t\t\tL[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j > 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\nar.sort()\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(u) for u in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(len(l) - 1):\n\t\tj = i\n\t\tkey = l[i + 1]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile j >= 0 and l[j] > key:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(len(l)):\n\t\tj = i\n\t\twhile l[j] < l[j - 1] and j > 0:\n\t\t\t(l[j], l[j - 1]) = (l[j - 1], l[j])\n\t\t\tj -= 1\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i\n\t\tkey = l[i]\n\t\twhile j > 0 and l[j - 1] > key:\n\t\t\tl[j] = l[j - 1]\n\t\t\tj -= 1\n\t\tl[j] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile j >= 0 and l[j] > key:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i\n\t\tkey = l[i]\n\t\twhile (j > 0 and l[j - 1]) > key:\n\t\t\tl[j] = l[j - 1]\n\t\t\tj -= 1\n\t\tl[j] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i\n\t\twhile l[j] < l[j - 1] and j > 0:\n\t\t\t(l[j - 1], l[j]) = (l[j], l[j - 1])\n\t\t\tj -= 1\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile -1 < j and key < l[j]:\n\t\t\tl[j + 1] = l[j]\n\t\t\tl[j] = key\n\t\t\tj -= 1\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "input()\na = map(int, input().split(' '))\nprint(*sorted(a))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile j > -1 and key < l[j]:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\ninput()\nar = list(map(int, input().split()))\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertionSort(theSeq):\n\tn = len(theSeq)\n\tfor i in range(1, n):\n\t\tvalue = theSeq[i]\n\t\tpos = i\n\t\twhile pos > 0 and value < theSeq[pos - 1]:\n\t\t\ttheSeq[pos] = theSeq[pos - 1]\n\t\t\tpos -= 1\n\t\ttheSeq[pos] = value\n\tfor i in theSeq:\n\t\tprint(i, end=' ')\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertionSort(ar)\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input())\nar = [int(i) for i in input().split()]\ninsertion_sort(ar)\nprint(*ar)\n", "m = input().split()\nar = [int(i) for i in input().split()]\nar.sort()\na = [str(i) for i in ar]\nprint(' '.join(a))\n", "def insertion_sort(l):\n\tfor i in range(1, len(l)):\n\t\tj = i - 1\n\t\tkey = l[i]\n\t\twhile l[j] > key and j >= 0:\n\t\t\tl[j + 1] = l[j]\n\t\t\tj -= 1\n\t\tl[j + 1] = key\nm = int(input().strip())\nar = [int(i) for i in input().strip().split()]\ninsertion_sort(ar)\nprint(' '.join(map(str, ar)))\n"]

difficulty: EASY

source: hacker rank

skill_types: ['Sorting']

raw_problem:
<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
In the previous challenge, you wrote code to perform an Insertion Sort on an unsorted array. But how would you prove that the code is correct? I.e. how do you show that for any input your code will provide the right output?

Loop Invariant

In computer science, you could prove it formally with a loop invariant, where you state that a desired property is maintained in your loop. Such a proof is broken down into the following parts:

Initialization: It is true (in a limited sense) before the loop runs.

Maintenance: If it's true before an iteration of a loop, it remains true before the next iteration.

Termination: It will terminate in a useful way once it is finished.

Insertion Sort's Invariant

Say, you have some InsertionSort code, where the outer loop goes through the whole array <svg focusable="false" height="2.176ex" role="img" style="vertical-align: -0.338ex;" viewbox="0 -791.3 750.5 936.9" width="1.743ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M208 74Q208 50 254 46Q272 46 272 35Q272 34 270 22Q267 8 264 4T251 0Q249 0 239 0T205 1T141 2Q70 2 50 0H42Q35 7 35 11Q37 38 48 46H62Q132 49 164 96Q170 102 345 401T523 704Q530 716 547 716H555H572Q578 707 578 706L606 383Q634 60 636 57Q641 46 701 46Q726 46 726 36Q726 34 723 22Q720 7 718 4T704 0Q701 0 690 0T651 1T578 2Q484 2 455 0H443Q437 6 437 9T439 27Q443 40 445 43L449 46H469Q523 49 533 63L521 213H283L249 155Q208 86 208 74ZM516 260Q516 271 504 416T490 562L463 519Q447 492 400 412L310 260L413 259Q516 259 516 260Z" stroke-width="1"></path></g></svg>:

for(int i = 1; i < A.length; i++){
//insertion sort code

You could then state the following loop invariant:

At the start of every iteration of the outer loop (indexed with <svg focusable="false" height="2.176ex" role="img" style="vertical-align: -0.338ex;" viewbox="0 -791.3 345.5 936.9" width="0.802ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z" stroke-width="1"></path></g></svg>), the subarray until <svg focusable="false" height="2.843ex" role="img" style="vertical-align: -0.838ex;" viewbox="0 -863.1 1883.5 1223.9" width="4.375ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z" stroke-width="1"></path><g transform="translate(529,0)"><path d="M21 287Q22 290 23 295T28 317T38 348T53 381T73 411T99 433T132 442Q161 442 183 430T214 408T225 388Q227 382 228 382T236 389Q284 441 347 441H350Q398 441 422 400Q430 381 430 363Q430 333 417 315T391 292T366 288Q346 288 334 299T322 328Q322 376 378 392Q356 405 342 405Q286 405 239 331Q229 315 224 298T190 165Q156 25 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 114 189T154 366Q154 405 128 405Q107 405 92 377T68 316T57 280Q55 278 41 278H27Q21 284 21 287Z" stroke-width="1"></path></g><g transform="translate(981,0)"><path d="M118 -250V750H255V710H158V-210H255V-250H118Z" stroke-width="1"></path></g><g transform="translate(1259,0)"><path d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z" stroke-width="1"></path></g><g transform="translate(1605,0)"><path d="M22 710V750H159V-250H22V-210H119V710H22Z" stroke-width="1"></path></g></g></svg> consists of the original elements that were there, but in sorted order.

To prove Insertion Sort is correct, you will then demonstrate it for the three stages:

Initialization - The subarray starts with the first element of the array, and it is (obviously) sorted to begin with.

Maintenance - Each iteration of the loop expands the subarray, but keeps the sorted property. An element <svg focusable="false" height="2.176ex" role="img" style="vertical-align: -0.338ex;" viewbox="0 -791.3 769.5 936.9" width="1.787ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M52 648Q52 670 65 683H76Q118 680 181 680Q299 680 320 683H330Q336 677 336 674T334 656Q329 641 325 637H304Q282 635 274 635Q245 630 242 620Q242 618 271 369T301 118L374 235Q447 352 520 471T595 594Q599 601 599 609Q599 633 555 637Q537 637 537 648Q537 649 539 661Q542 675 545 679T558 683Q560 683 570 683T604 682T668 681Q737 681 755 683H762Q769 676 769 672Q769 655 760 640Q757 637 743 637Q730 636 719 635T698 630T682 623T670 615T660 608T652 599T645 592L452 282Q272 -9 266 -16Q263 -18 259 -21L241 -22H234Q216 -22 216 -15Q213 -9 177 305Q139 623 138 626Q133 637 76 637H59Q52 642 52 648Z" stroke-width="1"></path></g></svg>  gets inserted into the array only when it is greater than the element to its left. Since the elements to its left have already been sorted, it means <svg focusable="false" height="2.176ex" role="img" style="vertical-align: -0.338ex;" viewbox="0 -791.3 769.5 936.9" width="1.787ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M52 648Q52 670 65 683H76Q118 680 181 680Q299 680 320 683H330Q336 677 336 674T334 656Q329 641 325 637H304Q282 635 274 635Q245 630 242 620Q242 618 271 369T301 118L374 235Q447 352 520 471T595 594Q599 601 599 609Q599 633 555 637Q537 637 537 648Q537 649 539 661Q542 675 545 679T558 683Q560 683 570 683T604 682T668 681Q737 681 755 683H762Q769 676 769 672Q769 655 760 640Q757 637 743 637Q730 636 719 635T698 630T682 623T670 615T660 608T652 599T645 592L452 282Q272 -9 266 -16Q263 -18 259 -21L241 -22H234Q216 -22 216 -15Q213 -9 177 305Q139 623 138 626Q133 637 76 637H59Q52 642 52 648Z" stroke-width="1"></path></g></svg> is greater than all the elements to its left, so the array remains sorted. (In Insertion Sort 2 we saw this by printing the array each time an element was properly inserted.)

Termination - The code will terminate after <svg focusable="false" height="2.176ex" role="img" style="vertical-align: -0.338ex;" viewbox="0 -791.3 345.5 936.9" width="0.802ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z" stroke-width="1"></path></g></svg> has reached the last element in the array, which means the sorted subarray has expanded to encompass the entire array. The array is now fully sorted.

You can often use a similar process to demonstrate the correctness of many algorithms. You can see these notes for more information.

Challenge

In the InsertionSort code below, there is an error. Can you fix it? Print the array only once, when it is fully sorted.

Input Format

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
There will be two lines of input:

<svg focusable="false" height="1.676ex" role="img" style="vertical-align: -0.338ex;" viewbox="0 -576.1 469.5 721.6" width="1.09ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z" stroke-width="1"></path></g></svg> - the size of the array

<svg focusable="false" height="1.676ex" role="img" style="vertical-align: -0.338ex;" viewbox="0 -576.1 1432.5 721.6" width="3.327ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z" stroke-width="1"></path><g transform="translate(529,0)"><path d="M21 287Q22 290 23 295T28 317T38 348T53 381T73 411T99 433T132 442Q161 442 183 430T214 408T225 388Q227 382 228 382T236 389Q284 441 347 441H350Q398 441 422 400Q430 381 430 363Q430 333 417 315T391 292T366 288Q346 288 334 299T322 328Q322 376 378 392Q356 405 342 405Q286 405 239 331Q229 315 224 298T190 165Q156 25 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 114 189T154 366Q154 405 128 405Q107 405 92 377T68 316T57 280Q55 278 41 278H27Q21 284 21 287Z" stroke-width="1"></path></g><g transform="translate(981,0)"><path d="M21 287Q22 290 23 295T28 317T38 348T53 381T73 411T99 433T132 442Q161 442 183 430T214 408T225 388Q227 382 228 382T236 389Q284 441 347 441H350Q398 441 422 400Q430 381 430 363Q430 333 417 315T391 292T366 288Q346 288 334 299T322 328Q322 376 378 392Q356 405 342 405Q286 405 239 331Q229 315 224 298T190 165Q156 25 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 114 189T154 366Q154 405 128 405Q107 405 92 377T68 316T57 280Q55 278 41 278H27Q21 284 21 287Z" stroke-width="1"></path></g></g></svg> - the list of numbers that makes up the array

Constraints

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
<svg focusable="false" height="2.343ex" role="img" style="vertical-align: -0.505ex;" viewbox="0 -791.3 5640.1 1008.6" width="13.1ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z" stroke-width="1"></path><g transform="translate(778,0)"><path d="M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z" stroke-width="1"></path></g><g transform="translate(1834,0)"><path d="M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z" stroke-width="1"></path></g><g transform="translate(2581,0)"><path d="M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z" stroke-width="1"></path></g><g transform="translate(3638,0)"><path d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z" stroke-width="1"></path><path d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z" stroke-width="1" transform="translate(500,0)"></path><path d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z" stroke-width="1" transform="translate(1001,0)"></path><path d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z" stroke-width="1" transform="translate(1501,0)"></path></g></g></svg>

<svg focusable="false" height="2.509ex" role="img" style="vertical-align: -0.671ex;" viewbox="0 -791.3 12090.3 1080.4" width="28.081ex" xmlns:xlink="http://www.w3.org/1999/xlink"><g fill="currentColor" stroke="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><path d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z" stroke-width="1"></path><g transform="translate(778,0)"><path d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z" stroke-width="1"></path><path d="M164 157Q164 133 148 117T109 101H102Q148 22 224 22Q294 22 326 82Q345 115 345 210Q345 313 318 349Q292 382 260 382H254Q176 382 136 314Q132 307 129 306T114 304Q97 304 95 310Q93 314 93 485V614Q93 664 98 664Q100 666 102 666Q103 666 123 658T178 642T253 634Q324 634 389 662Q397 666 402 666Q410 666 410 648V635Q328 538 205 538Q174 538 149 544L139 546V374Q158 388 169 396T205 412T256 420Q337 420 393 355T449 201Q449 109 385 44T229 -22Q148 -22 99 32T50 154Q50 178 61 192T84 210T107 214Q132 214 148 197T164 157Z" stroke-width="1" transform="translate(500,0)"></path><path d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z" stroke-width="1" transform="translate(1001,0)"></path><path d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z" stroke-width="1" transform="translate(1501,0)"></path></g><g transform="translate(3058,0)"><path d="M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z" stroke-width="1"></path></g><g transform="translate(4114,0)"><path d="M52 648Q52 670 65 683H76Q118 680 181 680Q299 680 320 683H330Q336 677 336 674T334 656Q329 641 325 637H304Q282 635 274 635Q245 630 242 620Q242 618 271 369T301 118L374 235Q447 352 520 471T595 594Q599 601 599 609Q599 633 555 637Q537 637 537 648Q537 649 539 661Q542 675 545 679T558 683Q560 683 570 683T604 682T668 681Q737 681 755 683H762Q769 676 769 672Q769 655 760 640Q757 637 743 637Q730 636 719 635T698 630T682 623T670 615T660 608T652 599T645 592L452 282Q272 -9 266 -16Q263 -18 259 -21L241 -22H234Q216 -22 216 -15Q213 -9 177 305Q139 623 138 626Q133 637 76 637H59Q52 642 52 648Z" stroke-width="1"></path></g><g transform="translate(5161,0)"><path d="M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z" stroke-width="1"></path></g><g transform="translate(6218,0)"><path d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z" stroke-width="1"></path><path d="M164 157Q164 133 148 117T109 101H102Q148 22 224 22Q294 22 326 82Q345 115 345 210Q345 313 318 349Q292 382 260 382H254Q176 382 136 314Q132 307 129 306T114 304Q97 304 95 310Q93 314 93 485V614Q93 664 98 664Q100 666 102 666Q103 666 123 658T178 642T253 634Q324 634 389 662Q397 666 402 666Q410 666 410 648V635Q328 538 205 538Q174 538 149 544L139 546V374Q158 388 169 396T205 412T256 420Q337 420 393 355T449 201Q449 109 385 44T229 -22Q148 -22 99 32T50 154Q50 178 61 192T84 210T107 214Q132 214 148 197T164 157Z" stroke-width="1" transform="translate(500,0)"></path><path d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z" stroke-width="1" transform="translate(1001,0)"></path><path d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z" stroke-width="1" transform="translate(1501,0)"></path></g><g transform="translate(8220,0)"><path d="M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z" stroke-width="1"></path></g><g transform="translate(8665,0)"><path d="M52 648Q52 670 65 683H76Q118 680 181 680Q299 680 320 683H330Q336 677 336 674T334 656Q329 641 325 637H304Q282 635 274 635Q245 630 242 620Q242 618 271 369T301 118L374 235Q447 352 520 471T595 594Q599 601 599 609Q599 633 555 637Q537 637 537 648Q537 649 539 661Q542 675 545 679T558 683Q560 683 570 683T604 682T668 681Q737 681 755 683H762Q769 676 769 672Q769 655 760 640Q757 637 743 637Q730 636 719 635T698 630T682 623T670 615T660 608T652 599T645 592L452 282Q272 -9 266 -16Q263 -18 259 -21L241 -22H234Q216 -22 216 -15Q213 -9 177 305Q139 623 138 626Q133 637 76 637H59Q52 642 52 648Z" stroke-width="1"></path></g><g transform="translate(9712,0)"><path d="M84 250Q84 372 166 450T360 539Q361 539 377 539T419 540T469 540H568Q583 532 583 520Q583 511 570 501L466 500Q355 499 329 494Q280 482 242 458T183 409T147 354T129 306T124 272V270H568Q583 262 583 250T568 230H124V228Q124 207 134 177T167 112T231 48T328 7Q355 1 466 0H570Q583 -10 583 -20Q583 -32 568 -40H471Q464 -40 446 -40T417 -41Q262 -41 172 45Q84 127 84 250Z" stroke-width="1"></path></g><g transform="translate(10657,0)"><path d="M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z" stroke-width="1"></path></g><g transform="translate(11187,0)"><path d="M21 287Q22 290 23 295T28 317T38 348T53 381T73 411T99 433T132 442Q161 442 183 430T214 408T225 388Q227 382 228 382T236 389Q284 441 347 441H350Q398 441 422 400Q430 381 430 363Q430 333 417 315T391 292T366 288Q346 288 334 299T322 328Q322 376 378 392Q356 405 342 405Q286 405 239 331Q229 315 224 298T190 165Q156 25 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 114 189T154 366Q154 405 128 405Q107 405 92 377T68 316T57 280Q55 278 41 278H27Q21 284 21 287Z" stroke-width="1"></path></g><g transform="translate(11638,0)"><path d="M21 287Q22 290 23 295T28 317T38 348T53 381T73 411T99 433T132 442Q161 442 183 430T214 408T225 388Q227 382 228 382T236 389Q284 441 347 441H350Q398 441 422 400Q430 381 430 363Q430 333 417 315T391 292T366 288Q346 288 334 299T322 328Q322 376 378 392Q356 405 342 405Q286 405 239 331Q229 315 224 298T190 165Q156 25 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 114 189T154 366Q154 405 128 405Q107 405 92 377T68 316T57 280Q55 278 41 278H27Q21 284 21 287Z" stroke-width="1"></path></g></g></svg>

Output Format

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
Output the numbers in order, space-separated on one line.

Sample Input

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
6
7 4 3 5 6 2

Sample Output

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
2 3 4 5 6 7

Explanation

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
The corrected code returns the sorted array.

question:
In the previous challenge, you wrote code to perform an Insertion Sort on an unsorted array. But how would you prove that the code is correct? I.e. how do you show that for any input your code will provide the right output?

Loop Invariant

In computer science, you could prove it formally with a loop invariant, where you state that a desired property is maintained in your loop. Such a proof is broken down into the following parts:

Initialization: It is true (in a limited sense) before the loop runs.
Maintenance: If it's true before an iteration of a loop, it remains true before the next iteration.
Termination: It will terminate in a useful way once it is finished.

Insertion Sort's Invariant

Say, you have some InsertionSort code, where the outer loop goes through the whole array $\mbox{A}$:

for(int i = 1; i < A.length; i++){
//insertion sort code

You could then state the following loop invariant:

At the start of every iteration of the outer loop (indexed with $\boldsymbol{i}$), the subarray until $ar[i]$ consists of the original elements that were there, but in sorted order.

To prove Insertion Sort is correct, you will then demonstrate it for the three stages:

Initialization - The subarray starts with the first element of the array, and it is (obviously) sorted to begin with.

Maintenance - Each iteration of the loop expands the subarray, but keeps the sorted property. An element $\mbox{V}$  gets inserted into the array only when it is greater than the element to its left. Since the elements to its left have already been sorted, it means $\mbox{V}$ is greater than all the elements to its left, so the array remains sorted. (In Insertion Sort 2 we saw this by printing the array each time an element was properly inserted.)

Termination - The code will terminate after $\boldsymbol{i}$ has reached the last element in the array, which means the sorted subarray has expanded to encompass the entire array. The array is now fully sorted.

![image](1.png)
You can often use a similar process to demonstrate the correctness of many algorithms. You can see these notes for more information.

Challenge

In the InsertionSort code below, there is an error. Can you fix it? Print the array only once, when it is fully sorted.

Input Format

There will be two lines of input:

$\boldsymbol{\mathrm{~S~}}$ - the size of the array
$\textbf{arr}$ - the list of numbers that makes up the array

Constraints

$1\leq s\leq1000$

$-1500\le V\le1500,V\in\textit{arr}$

Output Format

Output the numbers in order, space-separated on one line.

Sample Input
6
7 4 3 5 6 2

Sample Output
2 3 4 5 6 7

Explanation

The corrected code returns the sorted array.

data_split: test


D. Nauuo and Portals

problem_index: D

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
Example 1
The cells with the same letter are a portal. You can set portals in this way:
![image](images/cf_1172_D/1.png)
It satisfies the rule, because:
![image](images/cf_1172_D/2.png)
Example 2
You can set portals in this way:
![image](images/cf_1172_D/3.png)

source: codeforces

raw_problem:
D. Nauuo and Portals

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Nauuo is a girl who loves playing games related to portals.

One day she was playing a game as follows.

In an $$$n\times n$$$ grid, the rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. We denote a cell on the intersection of the $$$r$$$-th row and $$$c$$$-th column as $$$(r,c)$$$.

A portal is a pair of doors. You can travel from one of them to another without changing your direction. More formally, if you walk into a cell with a door, you will teleport to the cell with the other door of the same portal and then walk into the next cell facing the original direction. There can not be more than one doors in a single cell.

The "next cell" is the nearest cell in the direction you are facing. For example, if you are facing bottom, the next cell of $$$(2,5)$$$ is $$$(3,5)$$$.

If you walk into a cell without a door, you must walk into the next cell after that without changing the direction. If the next cell does not exist, you must exit the grid.

You have to set some (possibly zero) portals in the grid, so that if you walk into $$$(i,1)$$$ facing right, you will eventually exit the grid from $$$(r_i,n)$$$, if you walk into $$$(1, i)$$$ facing bottom, you will exit the grid from $$$(n,c_i)$$$.

It is guaranteed that both $$$r_{1..n}$$$ and $$$c_{1..n}$$$ are permutations of $$$n$$$ elements. A permutation of $$$n$$$ elements is a sequence of numbers $$$p_1,p_2,\ldots,p_n$$$ in which every integer from $$$1$$$ to $$$n$$$ appears exactly once.

She got confused while playing the game, can you help her to find a solution?

Input

The first line contains a single integer $$$n$$$ ($$$1\le n\le 1000$$$) — the side length of the grid.

The second line contains $$$n$$$ integers $$$r_1,r_2,\ldots,r_n$$$ ($$$1\le r_i\le n$$$) — if you walk into $$$(i,1)$$$ facing right, you should exit the grid from $$$(r_i,n)$$$. It is guaranteed that $$$r_{1..n}$$$ is a permutation of $$$n$$$ elements.

The third line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1\le c_i\le n$$$) — if you walk into $$$(1,i)$$$ facing bottom, you should exit the grid from $$$(n,c_i)$$$. It is guaranteed that $$$c_{1..n}$$$ is a permutation of $$$n$$$ elements.

Output

If it is impossible to satisfy the rule, print the only number $$$-1$$$.

Otherwise the first line should contain a single integer $$$m$$$ ($$$0\le m\le\frac{n^2}2$$$) — the number of portals you set.

In the following $$$m$$$ lines, each line should contain four integers $$$x_1,y_1,x_2,y_2$$$, represents that you set a portal consisting of two doors in $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$.

If there are multiple answers, print any. You do not have to minimize $$$m$$$.

Examples

Input

3
1 3 2
3 1 2

Output

2
1 1 1 3
2 2 3 1

Input

5
3 1 5 4 2
4 2 1 3 5

Output

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

Note

Example 1

The cells with the same letter are a portal. You can set portals in this way:

It satisfies the rule, because:

Example 2

You can set portals in this way:

question:
Nauuo is a girl who loves playing games related to portals.
One day she was playing a game as follows.
In an $$$n\times n$$$ grid, the rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. We denote a cell on the intersection of the $$$r$$$-th row and $$$c$$$-th column as $$$(r,c)$$$.
A portal is a pair of doors. You can travel from one of them to another without changing your direction. More formally, if you walk into a cell with a door, you will teleport to the cell with the other door of the same portal and then walk into the next cell facing the original direction. There can not be more than one doors in a single cell.
The "next cell" is the nearest cell in the direction you are facing. For example, if you are facing bottom, the next cell of $$$(2,5)$$$ is $$$(3,5)$$$.
If you walk into a cell without a door, you must walk into the next cell after that without changing the direction. If the next cell does not exist, you must exit the grid.
You have to set some (possibly zero) portals in the grid, so that if you walk into $$$(i,1)$$$ facing right, you will eventually exit the grid from $$$(r_i,n)$$$, if you walk into $$$(1, i)$$$ facing bottom, you will exit the grid from $$$(n,c_i)$$$.
It is guaranteed that both $$$r_{1..n}$$$ and $$$c_{1..n}$$$ are permutations of $$$n$$$ elements. A permutation of $$$n$$$ elements is a sequence of numbers $$$p_1,p_2,\ldots,p_n$$$ in which every integer from $$$1$$$ to $$$n$$$ appears exactly once.
She got confused while playing the game, can you help her to find a solution?

Input
The first line contains a single integer $$$n$$$ ($$$1\le n\le 1000$$$) — the side length of the grid.
The second line contains $$$n$$$ integers $$$r_1,r_2,\ldots,r_n$$$ ($$$1\le r_i\le n$$$) — if you walk into $$$(i,1)$$$ facing right, you should exit the grid from $$$(r_i,n)$$$. It is guaranteed that $$$r_{1..n}$$$ is a permutation of $$$n$$$ elements.
The third line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1\le c_i\le n$$$) — if you walk into $$$(1,i)$$$ facing bottom, you should exit the grid from $$$(n,c_i)$$$. It is guaranteed that $$$c_{1..n}$$$ is a permutation of $$$n$$$ elements.

Output
If it is impossible to satisfy the rule, print the only number $$$-1$$$.
Otherwise the first line should contain a single integer $$$m$$$ ($$$0\le m\le\frac{n^2}2$$$) — the number of portals you set.
In the following $$$m$$$ lines, each line should contain four integers $$$x_1,y_1,x_2,y_2$$$, represents that you set a portal consisting of two doors in $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$.
If there are multiple answers, print any. You do not have to minimize $$$m$$$.

Examples
Input
3
1 3 2
3 1 2

Output
2
1 1 1 3
2 2 3 1

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

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

Note
Example 1
The cells with the same letter are a portal. You can set portals in this way:
![image](1.png)
It satisfies the rule, because:
![image](2.png)
Example 2
You can set portals in this way:
![image](3.png)

image_tags: Map Map Map

data_split: test


solutions: ["t = int(input())\nn = 1001\nl = [[0 for i in range(n)] for i in range(n)]\nfor i in range(1, n):\n\tl[i][1] = i * (i + 1) // 2\nfor j in range(1, n):\n\tfor k in range(2, n):\n\t\tl[j][k] = l[j][k - 1] + (k - 1) + (j - 1)\nfor z in range(t):\n\t(r1, c1, r2, c2) = list(map(int, input().split()))\n\ts = 0\n\tfor a in range(r1, r2 + 1):\n\t\ts += l[a][c1]\n\tfor b in range(c1 + 1, c2 + 1):\n\t\ts += l[r2][b]\n\tprint(s)\n", "T = int(input())\nN = 1001\ninf = [[0 for _ in range(N)] for _ in range(N)]\nfor i in range(1, N):\n\tinf[i][1] = i * (i + 1) // 2\nfor i in range(1, N):\n\tfor j in range(2, N):\n\t\tinf[i][j] = inf[i][j - 1] + (j - 1) + (i - 1)\nfor _ in range(T):\n\t(r1, c1, r2, c2) = list(map(int, input().split()))\n\tSum = 0\n\tfor i in range(r1, r2 + 1):\n\t\tSum += inf[i][c1]\n\tfor i in range(c1 + 1, c2 + 1):\n\t\tSum += inf[r2][i]\n\tprint(Sum)\n", "from sys import stdin, stdout\ninput = stdin.readline\nt = int(input().strip())\nfor _ in range(t):\n\t(x1, y1, x2, y2) = list(map(int, input().strip().split()))\n\tpoint1 = (1, y1)\n\tpoint2 = (x1, y1)\n\tpoint2 = (x2, y1)\n\tpoint1_value = 1 + (y1 - 1) * y1 // 2\n\tdiff1 = 1 + y1\n\tdiff2 = x1 + y1\n\tdiff3 = x2 + y1 - 1\n\tpoint2_value = point1_value + (x1 - 1) * (2 * diff1 + x1 - 2) // 2\n\tpoint3_value = point1_value + (x2 - 1) * (2 * diff1 + x2 - 2) // 2\n\tans = 0\n\tfor i in range(x2 - x1 + 1):\n\t\tans += point2_value + i * (2 * diff2 + i - 1) // 2\n\tfor i in range(y2 - y1 + 1):\n\t\tans += point3_value + i * (2 * diff3 + i - 1) // 2\n\tans = ans - point3_value\n\tprint(ans)\n", "from itertools import accumulate\n\ndef val_at(x, y, trs):\n\treturn trs[y + x - 2] + x\ntri = list(accumulate(range(2 * 1000 + 1)))\nactri = [0] + list(accumulate(tri))\nT = int(input())\nfor tx in range(T):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tif x2 < x1:\n\t\t(x1, y1, x2, y2) = (x2, y2, x1, y1)\n\tres = tri[x2 - 1] - tri[x1 - 1] + actri[y1 + x2 - 2] - actri[y1 + x1 - 2]\n\tif y2 < y1:\n\t\t(y1, y2) = (y2, y1)\n\tres += x2 * (y2 + 1 - y1) + actri[y2 + 1 + x2 - 2] - actri[y1 + x2 - 2]\n\tprint(res)\n", "matrix = [[0 for i in range(1000)] for i in range(1000)]\nmatrix[0][0] = 1\nfor i in range(1, 1000):\n\tmatrix[i][0] += matrix[i - 1][0] + i + 1\nfor i in range(0, 1000):\n\tfor j in range(1, 1000):\n\t\tmatrix[i][j] = matrix[i][j - 1] + j + i\nt = int(input())\nfor _ in range(t):\n\tx1x2y1y2 = list(map(int, input().split()))\n\tx1 = x1x2y1y2[0]\n\ty1 = x1x2y1y2[1]\n\tx2 = x1x2y1y2[2]\n\ty2 = x1x2y1y2[3]\n\tsum1 = 0\n\tfor i in range(x1 - 1, x2):\n\t\tsum1 += matrix[i][y1 - 1]\n\tfor j in range(y1, y2):\n\t\tsum1 += matrix[x2 - 1][j]\n\tprint(sum1)\n", "from sys import stdin\nfor _ in range(int(stdin.readline())):\n\t(x1, y1, x2, y2) = map(int, stdin.readline().split())\n\td2 = x1 + y1\n\tt2 = y1 + 1\n\td1 = x2 + y1 - 1\n\tq = 0\n\tv = y1 * y1 / 2 - y1 / 2 + 1\n\tfor i in range(1, x1):\n\t\tv += t2\n\t\tt2 += 1\n\tfor i in range(x1, x2):\n\t\tq += v\n\t\tv += d2\n\t\td2 += 1\n\tfor i in range(y1, y2 + 1):\n\t\tq += v\n\t\tv += d1\n\t\td1 += 1\n\tprint(int(q))\n", "def maximum(r1, c1, r2, c2, inf):\n\tSum = 0\n\tfor i in range(r1, r2 + 1):\n\t\tSum += inf[i][c1]\n\tfor j in range(c1 + 1, c2 + 1):\n\t\tSum += inf[r2][j]\n\treturn Sum\ninf = [[0 for i in range(1001)] for i in range(1001)]\nfor i in range(1, 1001):\n\tinf[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tinf[i][j] = inf[i][j - 1] + (i - 1) + (j - 1)\nfor _ in range(int(input())):\n\t(r1, c1, r2, c2) = list(map(int, input().split()))\n\tprint(maximum(r1, c1, r2, c2, inf))\n", "for i in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tlvl = x1 + y1 - 2\n\tans = lvl * (lvl + 1) // 2 + x1\n\twhile x1 < x2:\n\t\tx1 += 1\n\t\tlvl = x1 + y1 - 2\n\t\tans += lvl * (lvl + 1) // 2 + x1\n\twhile y1 < y2:\n\t\ty1 += 1\n\t\tlvl = x1 + y1 - 2\n\t\tans += lvl * (lvl + 1) // 2 + x1\n\tprint(ans)\n", "arr = [[0 for i in range(1001)] for j in range(1001)]\nfor i in range(1, 1001):\n\tarr[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tarr[i][j] = arr[i][j - 1] + (i - 1) + (j - 1)\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tsumup = arr[x1][y1]\n\twhile x1 < x2 and y1 < y2:\n\t\tright = arr[x1][y1 + 1]\n\t\tdown = arr[x1 + 1][y1]\n\t\tif right > down:\n\t\t\ty1 += 1\n\t\t\tsumup += arr[x1][y1]\n\t\tif down >= right:\n\t\t\tx1 += 1\n\t\t\tsumup += arr[x1][y1]\n\tif x1 == x2 and y1 != y2:\n\t\tsumup += sum(arr[x1][y1 + 1:y2 + 1])\n\tif y1 == y2 and x1 != x2:\n\t\tfor k in range(x1 + 1, x2 + 1):\n\t\t\tsumup += arr[k][y1]\n\tprint(sumup)\n", "S = [[0 for i in range(1001)] for j in range(1001)]\nfor i in range(1, 1001):\n\tS[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tS[i][j] = S[i][j - 1] + (i - 1) + (j - 1)\nT = int(input())\nfor i in range(T):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tmax_path = 0\n\tfor i in range(x1, x2 + 1):\n\t\tmax_path += S[i][y1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tmax_path += S[x2][i]\n\tprint(max_path)\n", "a = [[0 for i in range(1000)] for j in range(1000)]\na[0][0] = 1\nfor i in range(1, 1000):\n\ta[i][0] = a[i - 1][0] + i + 1\nfor i in range(1000):\n\tfor j in range(1, 1000):\n\t\ta[i][j] = a[i][j - 1] + i + j\nt = int(input())\nfor i in range(t):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tans = 0\n\tfor j in range(x1 - 1, x2):\n\t\tans += a[j][y1 - 1]\n\tfor j in range(y1, y2):\n\t\tans += a[x2 - 1][j]\n\tprint(ans)\n", "t = int(input())\ninfiniteMat = [[0 for i in range(1001)] for i in range(1001)]\ninfiniteMat[1][1] = 1\nfor i in range(2, 1001):\n\tinfiniteMat[i][1] = infiniteMat[i - 1][1] + i\nfor i in range(1, 1001):\n\tfor j in range(2, 1001):\n\t\tinfiniteMat[i][j] = infiniteMat[i][j - 1] + i + j - 2\nfor _ in range(t):\n\t(x1, y1, x2, y2) = list(map(int, input().split()))\n\tans = 0\n\tfor i in range(x1, x2 + 1):\n\t\tans += infiniteMat[i][y1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tans += infiniteMat[x2][i]\n\tprint(ans)\n", "arr = [[0 for i in range(1000)] for j in range(1000)]\nfor i in range(1000):\n\tarr[i][0] = (i + 1) * (i + 2) // 2\nfor i in range(1000):\n\tfor j in range(1, 1000, 1):\n\t\tarr[i][j] = arr[i][j - 1] + j + i\nfor i in range(int(input())):\n\t(r1, c1, r2, c2) = [int(x) for x in input().split()]\n\tr1 -= 1\n\tc1 -= 1\n\tr2 -= 1\n\tc2 -= 1\n\tsum = arr[r1][c1]\n\tfor j in range(r1 + 1, r2 + 1, 1):\n\t\tsum += arr[j][c1]\n\tfor j in range(c1 + 1, c2 + 1, 1):\n\t\tsum += arr[r2][j]\n\tprint(sum)\n", "for _ in range(int(input())):\n\t(x, y, x1, y1) = map(int, input().split())\n\tn = 0\n\tfor i in range(x):\n\t\tn += i + 1\n\tfor i in range(y - 1):\n\t\tn += x + i\n\tans = n\n\tdiff = x + y\n\tfor i in range(x1 - x):\n\t\tn += diff + i\n\t\tans += n\n\tdiff = x1 + y - 1\n\tfor i in range(y1 - y):\n\t\tn += diff + i\n\t\tans += n\n\tprint(ans)\n", "inf = []\nfor i in range(1000):\n\tfor j in range(1000):\n\t\tif j == 0:\n\t\t\ttemp = []\n\t\t\ttemp.append((i + 1) * (i + 2) // 2)\n\t\t\tinf.append(temp)\n\t\telse:\n\t\t\tinf[i].append(inf[i][j - 1] + i + j)\nt = int(input())\nfor _ in range(t):\n\t(x1, y1, x2, y2) = [int(x) - 1 for x in input().split()]\n\tans = 0\n\tfor i in range(x1, x2 + 1):\n\t\tans += inf[i][y1]\n\tfor j in range(y1 + 1, y2 + 1):\n\t\tans += inf[x2][j]\n\tprint(ans)\n", "m = [[0 for i in range(1001)] for j in range(1001)]\nfor i in range(1, 1001):\n\tm[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tm[i][j] = m[i][j - 1] + (i - 1) + (j - 1)\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tans = 0\n\tfor i in range(x1, x2 + 1):\n\t\tans += m[i][y1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tans += m[x2][i]\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tp = x1 + y1\n\tsum = 0\n\tfor i in range(x1, x2 + 1):\n\t\tsum += p * (p - 1) // 2 - y1 + 1\n\t\tp += 1\n\tp = x2 + y1 + 1\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tsum += p * (p - 1) // 2 - i + 1\n\t\tp += 1\n\tprint(sum)\n", "t = int(input())\nfor case in range(t):\n\t(x1, y1, x2, y2) = map(lambda x: int(x) - 1, input().split())\n\tpathSum = 0\n\tfor row in range(x1, x2 + 1):\n\t\tx = row + y1 + 1\n\t\tcur = x * (x - 1) // 2 + row + 1\n\t\tpathSum += cur\n\tfor col in range(y1 + 1, y2 + 1):\n\t\tx = x2 + col + 1\n\t\tcur = x * (x - 1) // 2 + x2 + 1\n\t\tpathSum += cur\n\tprint(pathSum)\n", "m = []\nfor i in range(1000):\n\tn = []\n\tfor j in range(1000):\n\t\tn.append(0)\n\tm.append(n)\nm[0][0] = 1\nt = 1\nfor i in range(1, 1000):\n\tm[0][i] = m[0][i - 1] + t\n\tt += 1\nt = 2\nfor i in range(1, 1000):\n\tm[i][0] = m[i - 1][0] + t\n\tt += 1\nfor i in range(1, 1000):\n\tt = i + 1\n\tfor j in range(1, 1000):\n\t\tm[i][j] = m[i][j - 1] + t\n\t\tt += 1\ntest = int(input())\nwhile test:\n\t(x1, y1, x2, y2) = input().split()\n\tx1 = int(x1) - 1\n\tx2 = int(x2) - 1\n\ty1 = int(y1) - 1\n\ty2 = int(y2) - 1\n\ts = m[x1][y1]\n\twhile x1 != x2:\n\t\tx1 += 1\n\t\ts += m[x1][y1]\n\twhile y1 != y2:\n\t\ty1 += 1\n\t\ts += m[x1][y1]\n\tprint(s)\n\ttest -= 1\n", "(i1, j1) = (1001, 1001)\ninf = [[0 for x in range(i1)] for y in range(j1)]\nfor i in range(1, 1000 + 1):\n\tinf[i][1] = i * (i + 1) / 2\n\tfor j in range(2, 1000 + 1):\n\t\tinf[i][j] = inf[i][j - 1] + (j - 1) + (i - 1)\nt = int(input())\nfor z in range(t):\n\tsum = 0\n\t(x1, y1, x2, y2) = tuple(map(int, input().split()))\n\ti = x1\n\twhile i <= x2:\n\t\tsum = sum + inf[i][y1]\n\t\ti += 1\n\ti = y1 + 1\n\twhile i <= y2:\n\t\tsum = sum + inf[x2][i]\n\t\ti += 1\n\tprint(int(sum))\n", "mx = 1003\nmat = [[0 for i in range(mx)] for j in range(mx)]\npre_r = [[0 for i in range(mx)] for j in range(mx)]\npre_c = [[0 for i in range(mx)] for j in range(mx)]\ninc_col = 1\ninc_row = 0\ncurr_col = 0\ncurr_row = 1\nfor i in range(1, mx):\n\tinc_row = inc_col\n\tcurr_col += inc_col\n\tcurr_row = curr_col\n\tinc_col += 1\n\tfor j in range(1, mx):\n\t\tmat[i][j] = curr_row\n\t\tpre_r[i][j] = pre_r[i][j - 1] + mat[i][j]\n\t\tpre_c[i][j] = pre_c[i - 1][j] + mat[i][j]\n\t\tcurr_row += inc_row\n\t\tinc_row += 1\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().strip().split())\n\tif x1 == x2 and y1 == y2:\n\t\tprint(0)\n\telse:\n\t\tval1 = pre_c[x2][y1] - pre_c[x1][y1] + mat[x1][y1]\n\t\tval2 = pre_r[x2][y2] - pre_r[x2][y1]\n\t\tval = val2 + val1\n\t\tprint(val)\n", "mat = [[[] for i in range(1005)] for j in range(1005)]\nfor i in range(1, 1001):\n\tmat[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tmat[i][j] = mat[i][j - 1] + (j - 1) + (i - 1)\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\ts = 0\n\tfor i in range(x1, x2 + 1):\n\t\ts += mat[i][y1]\n\tfor j in range(y1 + 1, y2 + 1):\n\t\ts += mat[x2][j]\n\tprint(s)\n", "matrix = [[0 for i in range(2000)] for j in range(2000)]\nfor i in range(1, 2000):\n\tmatrix[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 2000):\n\t\tmatrix[i][j] = matrix[i][j - 1] + (j - 1) + (i - 1)\nfor _ in range(int(input())):\n\ts = 0\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tfor i in range(x1, x2 + 1):\n\t\ts += matrix[i][y1]\n\tfor j in range(y1 + 1, y2 + 1):\n\t\ts += matrix[x2][j]\n\tprint(s)\n", "t = int(input())\nfor k in range(t):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\ta = 0\n\tfor i in range(x1):\n\t\ta += i + 1\n\tfor j in range(y1 - 1):\n\t\ta += x1 + j\n\ta1 = a\n\tb1 = x1 + y1\n\tfor i in range(x2 - x1):\n\t\ta += b1 + i\n\t\ta1 += a\n\tb1 = x2 + y1 - 1\n\tfor i in range(y2 - y1):\n\t\ta += b1 + i\n\t\ta1 += a\n\tprint(a1)\n", "T = int(input())\nlst = [[0 for i in range(1000)] for j in range(1000)]\nlst[0][0] = 1\nm = 2\nfor i in range(1, 1000):\n\tlst[i][0] = lst[i - 1][0] + m\n\tm += 1\nfor i in range(1000):\n\tk = i + 1\n\tfor j in range(1, 1000):\n\t\tlst[i][j] = lst[i][j - 1] + k\n\t\tk += 1\nwhile T > 0:\n\tT = T - 1\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tsum = 0\n\tfor i in range(x1 - 1, x2):\n\t\tsum += lst[i][y1 - 1]\n\tfor i in range(y1, y2):\n\t\tsum += lst[x2 - 1][i]\n\tprint(sum)\n", "matrix = [[0 for _ in range(1001)] for _ in range(1001)]\nfor i in range(1, 1001):\n\tmatrix[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tmatrix[i][j] = matrix[i][j - 1] + (i - 1) + (j - 1)\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tsum_ = 0\n\tfor i in range(x1, x2 + 1):\n\t\tsum_ += matrix[i][y1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tsum_ += matrix[x2][i]\n\tprint(sum_)\n", "l = [[0] * 1000 for i in range(1000)]\nfor i in range(0, 1000):\n\tl[i][0] = (i + 1) * (i + 2) // 2\n\tfor j in range(1, 1000):\n\t\tl[i][j] = l[i][j - 1] + j + i\nfor t in range(int(input())):\n\t(r1, c1, r2, c2) = map(int, input().split())\n\tans = 0\n\tfor i in range(r1 - 1, r2 - 1):\n\t\tans += l[i][c1 - 1]\n\tfor j in range(c1 - 1, c2):\n\t\tans += l[r2 - 1][j]\n\tprint(ans)\n", "matrix = [[None for y in range(1005)] for x in range(1005)]\n\ndef genInfMat():\n\tfor i in range(1, 1001):\n\t\tmatrix[i][1] = i * (i + 1) // 2\n\t\tfor j in range(2, 1001):\n\t\t\tmatrix[i][j] = matrix[i][j - 1] + (j - 1) + (i - 1)\ngenInfMat()\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tscore = 0\n\twhile x1 <= x2:\n\t\tscore += matrix[x1][y1]\n\t\tx1 += 1\n\twhile y1 < y2:\n\t\ty1 += 1\n\t\tscore += matrix[x2][y1]\n\tprint(score)\n", "t = int(input())\narr = []\nmk = 2 * 1000\nfor i in range(mk + 1):\n\tarr.append([0] * (mk + 1))\nn = 1\nfor k in range(2, 2 * mk + 1):\n\ti = 1\n\twhile k - i > mk:\n\t\ti += 1\n\twhile i < k and i < mk + 1:\n\t\tarr[i][k - i] = n\n\t\ti += 1\n\t\tn += 1\nfor l in range(t):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tans = 0\n\tfor i in range(x1, x2 + 1):\n\t\tans += arr[i][y1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tans += arr[x2][i]\n\tprint(ans)\n", "def matCalc():\n\tm = []\n\tr = []\n\tc = []\n\tn = 1\n\ti = 0\n\tj = 0\n\tfor k in range(0, 2000):\n\t\tm.append([])\n\t\twhile j >= 0:\n\t\t\tm[i].append(n)\n\t\t\tj -= 1\n\t\t\ti += 1\n\t\t\tn += 1\n\t\tj = k + 1\n\t\ti = 0\n\treturn m\n\ndef printMaxSum(x1, y1, x2, y2, m):\n\tval = 0\n\tfor i in range(x1 - 1, x2):\n\t\tval += m[i][y1 - 1]\n\tfor j in range(y1, y2):\n\t\tval += m[x2 - 1][j]\n\tprint(val)\nm = matCalc()\nnt = int(input())\nfor i in range(0, nt):\n\tl = list(map(int, input().strip().split(' ')))\n\tx1 = l[0]\n\ty1 = l[1]\n\tx2 = l[2]\n\ty2 = l[3]\n\tprintMaxSum(x1, y1, x2, y2, m)\n", "T = int(input())\ndp = [[1] * 1000 for i in range(1000)]\nfor i in range(1, 1000):\n\tdp[i][0] = dp[i - 1][0] + i + 1\nfor j in range(1, 1000):\n\tdp[0][j] = dp[0][j - 1] + j\nfor i in range(1, 1000):\n\tfor j in range(1, 1000):\n\t\tdp[i][j] = dp[i][j - 1] + i + j\nfor i in range(T):\n\ta = [int(s) for s in input().split()]\n\t(x_1, y_1, x_2, y_2) = (a[0], a[1], a[2], a[3])\n\tans = 0\n\tfor k in range(x_1 - 1, x_2):\n\t\tans += dp[k][y_1 - 1]\n\tfor k in range(y_1, y_2):\n\t\tans += dp[x_2 - 1][k]\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(a, b, c, d) = map(int, input().split())\n\tx = 1\n\tfor i in range(1, b):\n\t\tx = x + i\n\tfor i in range(1, a):\n\t\tx = x + i + b\n\ty = x\n\tfor i in range(a, c):\n\t\tx = x + i + b\n\t\ty += x\n\tfor i in range(b, d):\n\t\tx = x + i + (c - 1)\n\t\ty += x\n\tprint(y)\n", "l = [[0 for i in range(1001)] for j in range(1001)]\nfor i in range(0, 1001):\n\tl[i][0] = (i + 1) * (i + 2) // 2\n\tfor j in range(1, 1001):\n\t\tl[i][j] = l[i][j - 1] + j + i\nt = int(input())\nwhile t:\n\t(a, b, c, d) = map(int, input().split())\n\ts = 0\n\tfor i in range(a - 1, c):\n\t\ts += l[i][b - 1]\n\tfor i in range(b, d):\n\t\ts += l[c - 1][i]\n\tprint(s)\n\tt -= 1\n", "for _ in range(int(input())):\n\t(x1, y1, x2, y2) = list(map(int, input().split()))\n\t(v, i, j) = (0, 1, 1)\n\twhile i != x1 + 1:\n\t\tv = v + i\n\t\ti += 1\n\ti -= 1\n\twhile j != y1:\n\t\tv = v + i\n\t\ti += 1\n\t\tj += 1\n\ts = v\n\twhile x1 != x2:\n\t\tv = v + x1 + y1\n\t\ts = s + v\n\t\tx1 += 1\n\tx1 -= 1\n\twhile y1 != y2:\n\t\tv = v + x1 + y1\n\t\ts = s + v\n\t\ty1 += 1\n\tprint(s)\n", "def num(x, y):\n\tn = (x + y - 2) * (x + y - 1)\n\tn = n / 2\n\tn = n + y\n\treturn int(n)\nt = int(input())\nwhile t > 0:\n\tans = 0\n\tt = t - 1\n\t(p, q, r, s) = input().split()\n\tp = int(p)\n\tq = int(q)\n\tr = int(r)\n\ts = int(s)\n\tfor i in range(p, r):\n\t\tans = ans + num(q, i)\n\tfor j in range(q, s + 1):\n\t\tans = ans + num(j, r)\n\tprint(ans)\n", "import numpy as np\na = np.zeros((1001, 1001))\nfor i in range(1, 1001):\n\ta[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\ta[i][j] = a[i][j - 1] + j - 1 + i - 1\nt = int(input())\nfor k in range(0, t):\n\t(x, y, x_, y_) = map(int, input().split())\n\tans = 0\n\twhile x < x_:\n\t\tans += a[x][y]\n\t\tx += 1\n\twhile y <= y_:\n\t\tans += a[x_][y]\n\t\ty += 1\n\tprint(int(ans))\n", "def array():\n\tarr = [[0 for i in range(1001)] for j in range(1001)]\n\tfor i in range(1, 1001):\n\t\tarr[i][1] = i * (i + 1) // 2\n\t\tfor j in range(2, 1001):\n\t\t\tarr[i][j] = arr[i][j - 1] + (j - 1) + (i - 1)\n\treturn arr\na = array()\nt = int(input())\nfor _ in range(t):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tsum = 0\n\tfor i in range(x1, x2 + 1):\n\t\tsum += a[i][y1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tsum += a[x2][i]\n\tprint(sum)\n", "def val(x, y):\n\tif y > 1:\n\t\treturn x * (x + 1) // 2 + (y - 1) * x + (y - 1) * (y - 2) // 2\n\telse:\n\t\treturn x * (x + 1) // 2\nt = int(input())\nfor k in range(t):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tans = 0\n\tif x1 == x2 and y1 != y2:\n\t\tfor i in range(y1, y2 + 1):\n\t\t\tans += val(x1, i)\n\telif y1 == y2 and x1 != x2:\n\t\tfor i in range(x1, x2 + 1):\n\t\t\tans += val(i, y1)\n\telse:\n\t\tfor i in range(x1, x2 + 1):\n\t\t\tans += val(i, y1)\n\t\tfor i in range(y1 + 1, y2 + 1):\n\t\t\tans += val(x2, i)\n\tprint(ans)\n", "n = 1000\nL = []\n(c, d) = (1, 1)\nfor i in range(n):\n\t(a, b) = (c, d)\n\tL.append([])\n\tfor j in range(n):\n\t\tL[i].append(a)\n\t\ta += b\n\t\tb += 1\n\td += 1\n\tc = c + i + 2\nfor i in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\ts = 0\n\tfor i in range(x1 - 1, x2):\n\t\ts += L[i][y1 - 1]\n\tfor i in range(y1, y2):\n\t\ts += L[x2 - 1][i]\n\tprint(s)\n", "def val(x, y):\n\ts = x + y\n\treturn x + (s - 1) * (s - 2) // 2\nT = int(input())\nfor _ in range(T):\n\t(a, b, p, q) = map(int, input().split())\n\tres = 0\n\tfor x in range(a, p + 1):\n\t\tres += val(x, b)\n\tfor y in range(b + 1, q + 1):\n\t\tres += val(p, y)\n\tprint(res)\n", "try:\n\tli = []\n\tfor i in range(1, 1001):\n\t\tli.append([int(i * (i + 1) / 2)])\n\tfor i in range(1000):\n\t\tprev = li[i][0]\n\t\tfor j in range(2, 1001):\n\t\t\ta = prev + j - 1 + i\n\t\t\tli[i].append(a)\n\t\t\tprev = a\n\tfor _ in range(int(input())):\n\t\t(x1, y1, x2, y2) = map(int, input().split())\n\t\tans = 0\n\t\tfor i in range(x1 - 1, x2):\n\t\t\tans = ans + li[i][y1 - 1]\n\t\tfor i in range(y1, y2):\n\t\t\tans = ans + li[x2 - 1][i]\n\t\tprint(ans)\nexcept:\n\tpass\n", "for _ in range(int(input())):\n\tm = list(map(int, input().split()))\n\tx1 = m[0]\n\ty1 = m[1]\n\tx2 = m[2]\n\ty2 = m[3]\n\ts = 1\n\tfor i in range(1, x1):\n\t\ts = s + i + 1\n\tfor i in range(x1, x1 + y1 - 1):\n\t\ts = s + i\n\tsum = s\n\tfor i in range(x1 + y1, x2 + y1):\n\t\ts = s + i\n\t\tsum = sum + s\n\tfor i in range(x2 + y1 - 1, x2 + y2 - 1):\n\t\ts = s + i\n\t\tsum = sum + s\n\tprint(sum)\n", "from copy import deepcopy\nMAX = 1001\nmat = [[0 for j in range(MAX + 1)] for i in range(MAX + 1)]\npre_r = deepcopy(mat)\npre_c = deepcopy(mat)\n\ndef pre_compute():\n\tfor r in range(1, MAX + 1):\n\t\tmat[r][1] = r * (r + 1) // 2\n\t\tfor c in range(2, MAX + 1):\n\t\t\tmat[r][c] = mat[r][c - 1] + r + c - 2\n\tfor r in range(1, MAX + 1):\n\t\tpre_r[r][1] = mat[r][1]\n\t\tfor c in range(2, MAX + 1):\n\t\t\tpre_r[r][c] = pre_r[r][c - 1] + mat[r][c]\n\tfor c in range(1, MAX + 1):\n\t\tpre_c[1][c] = mat[1][c]\n\t\tfor r in range(2, MAX + 1):\n\t\t\tpre_c[r][c] = pre_c[r - 1][c] + mat[r][c]\n\ndef solve():\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tans = pre_c[x2][y1] - pre_c[x1 - 1][y1] + pre_r[x2][y2] - pre_r[x2][y1]\n\tprint(ans)\npre_compute()\nfor tc in range(int(input())):\n\tsolve()\n", "t = int(input())\nb = []\nfor i in range(0, 1000):\n\ts = (i + 1) * (i + 2) // 2\n\tk = []\n\tk.append(s)\n\tfor j in range(1, 1000):\n\t\ts = k[j - 1] + j + i\n\t\tk.append(s)\n\tb.append(k)\nwhile t > 0:\n\tt = t - 1\n\ta = [int(x) for x in input().split()]\n\ts = 0\n\tfor i in range(a[0] - 1, a[2]):\n\t\ts = s + b[i][a[1] - 1]\n\tfor i in range(a[1], a[3]):\n\t\ts = s + b[a[2] - 1][i]\n\tprint(s)\n", "for _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tv = 1\n\tfor i in range(1, y1):\n\t\tv += i\n\tfor i in range(1, x1):\n\t\tv += i + y1\n\tu = v\n\tfor i in range(x1, x2):\n\t\tv += i + y1\n\t\tu += v\n\tfor i in range(y1 - 1, y2 - 1):\n\t\tv += i + x2\n\t\tu += v\n\tprint(u)\n", "def f(x, y):\n\treturn (x + y) * (x + y - 1) // 2 - y + 1\nn = int(input())\nfor j in range(n):\n\t(y, x, y2, x2) = map(int, input().strip().split())\n\ts = f(y, x)\n\twhile x != x2 or y != y2:\n\t\tif y != y2:\n\t\t\ty += 1\n\t\telse:\n\t\t\tx += 1\n\t\ts += f(y, x)\n\tprint(s)\n\ts = 0\n", "(n, l) = (int(input()), [])\nfor j in range(n):\n\t(y, x, y2, x2) = map(int, input().strip().split())\n\ts = ((x + y) ** 2 - 3 * x - y) / 2 + 1\n\twhile x != x2 or y != y2:\n\t\tif y != y2:\n\t\t\ty += 1\n\t\telse:\n\t\t\tx += 1\n\t\ts += ((x + y) ** 2 - 3 * x - y) / 2 + 1\n\tl.append(s)\n\ts = 0\nfor i in l:\n\tprint(int(i))\n", "from sys import stdin, stdout\ninput = stdin.readline\n\ndef im():\n\treturn map(int, input().split())\n\ndef ii():\n\treturn int(input())\n\ndef il():\n\treturn list(map(int, input().split()))\n\ndef ins():\n\treturn input()[:-1]\nlis = [[0] * 1005 for _ in range(1005)]\nfor i in range(1, 1001):\n\tlis[i][1] = lis[i - 1][1] + i\n\tfor j in range(2, 1001):\n\t\tlis[i][j] = lis[i][j - 1] + (j - 1) + (i - 1)\nfor _ in range(ii()):\n\t(x1, y1, x2, y2) = im()\n\tans = 0\n\twhile x1 < x2:\n\t\tans += lis[x1][y1]\n\t\tx1 += 1\n\twhile y1 < y2:\n\t\tans += lis[x1][y1]\n\t\ty1 += 1\n\tans += lis[x2][y2]\n\tprint(ans)\n", "import math\nrows = 1000\ncols = 1000\narr = [[0 for c in range(cols + 1)] for r in range(rows + 1)]\nfor i in range(1, 1001):\n\tarr[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tarr[i][j] = arr[i][j - 1] + (j - 1) + (i - 1)\nfor _ in range(int(input())):\n\t(r1, c1, r2, c2) = list(map(int, input().split()))\n\tsum = 0\n\tfor i in range(r1, r2 + 1):\n\t\tsum += arr[i][c1]\n\tfor i in range(c1 + 1, c2 + 1):\n\t\tsum += arr[r2][i]\n\tprint(sum)\n", "import math\nrows = 1000\ncols = 1000\narr = [[0 for c in range(cols + 1)] for r in range(rows + 1)]\nfor i in range(1, 1001):\n\tarr[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tarr[i][j] = arr[i][j - 1] + (j - 1) + (i - 1)\ntest_cases = int(input())\nfor test_case in range(test_cases):\n\t(r1, c1, r2, c2) = list(map(int, input().split()))\n\tcol_sum = 0\n\tfor r in range(r1, r2 + 1):\n\t\tcol_sum += arr[r][c1]\n\trow_sum = 0\n\tfor c in range(c1 + 1, c2 + 1):\n\t\trow_sum += arr[r2][c]\n\tprint(col_sum + row_sum)\n", "import math\nrows = 1000\ncols = 1000\narr = [[0 for c in range(cols + 1)] for r in range(rows + 1)]\nnum = 1\nfor r in range(1, rows + 1):\n\tdiff = r - 1\n\tfor c in range(1, cols + 1):\n\t\tif c == 1:\n\t\t\tarr[r][c] = arr[r - 1][c] + r\n\t\telse:\n\t\t\tarr[r][c] = arr[r][c - 1] + diff\n\t\tdiff += 1\ntest_cases = int(input())\nfor test_case in range(test_cases):\n\t(r1, c1, r2, c2) = list(map(int, input().split()))\n\tcol_sum = 0\n\tfor r in range(r1, r2 + 1):\n\t\tcol_sum += arr[r][c1]\n\trow_sum = 0\n\tfor c in range(c1 + 1, c2 + 1):\n\t\trow_sum += arr[r2][c]\n\tprint(col_sum + row_sum)\n", "for _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\ts = 1\n\tfor i in range(1, x1):\n\t\ts = s + i + 1\n\tfor i in range(x1, x1 + y1 - 1):\n\t\ts = s + i\n\tsumm = s\n\tfor i in range(x1 + y1, x2 + y1):\n\t\ts = s + i\n\t\tsumm += s\n\tfor i in range(x2 + y1 - 1, x2 + y2 - 1):\n\t\ts = s + i\n\t\tsumm += s\n\tprint(summ)\n", "for _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().strip().split())\n\ty = [1]\n\tfor i in range(y1 - 1):\n\t\ty.append(y[i] + i + 1)\n\tx = [y[-1]]\n\tfor i in range(1, x2):\n\t\tx.append(x[i - 1] + y1 + i)\n\tbottom = sum(x[x1 - 1:x2])\n\ty_f = [1]\n\tfor i in range(1, x2):\n\t\ty_f.append(y_f[i - 1] + i + 1)\n\tx_f = [y_f[-1]]\n\tfor i in range(1, y2):\n\t\tx_f.append(x_f[i - 1] + x2 - 1 + i)\n\tright = sum(x_f[y1 - 1:y2])\n\tright_f = right - x[-1]\n\tprint(right_f + bottom)\n", "ncases = int(input())\nq = []\nwhile ncases:\n\tq.append(list(map(lambda x: int(x), input().split())))\n\tncases -= 1\nr = 1001\nmatrix = [[None for _ in range(r)] for i in range(r)]\nmatrix[0][0] = 1\ncnt = 1\nfor i in range(1, r):\n\tmatrix[0][i] = matrix[0][i - 1] + cnt\n\tcnt += 1\ncnt = 2\nfor i in range(1, r):\n\tmatrix[i][0] = matrix[i - 1][0] + cnt\n\tcnt += 1\n\tcnt1 = i + 2\n\tfor j in range(1, r):\n\t\tmatrix[i][j] = matrix[i - 1][j] + cnt1\n\t\tcnt1 += 1\n\ndef solver(li):\n\t(x1, y1, x2, y2) = li\n\t(x1, x2, y1, y2) = (x1 - 1, x2 - 1, y1 - 1, y2 - 1)\n\ts = 0\n\tfor i in range(min(y1, y2), max(y1, y2) + 1):\n\t\ts += matrix[max(x1, x2)][i]\n\tfor i in range(min(x1, x2), max(x1, x2)):\n\t\ts += matrix[i][min(y1, y2)]\n\treturn s\nfor li in q:\n\tprint(solver(li))\n", "grid = [1]\nfu = [i for i in range(1, 1001)]\ngrid += fu\nfinal = []\nfinal.append(grid)\nd = [1] * 1000\nfor i in range(2, 1002):\n\tc = [i] + d\n\tfinal.append(c)\nfor i in range(1001):\n\tfor j in range(1, 1001):\n\t\tfinal[i][j] += final[i][j - 1]\nfor i in range(1001):\n\tfor j in range(1, 1001):\n\t\tfinal[j][i] += final[j - 1][i]\nt = int(input())\nfor i in range(t):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tc = 0\n\tfor i in range(x1, x2 + 1):\n\t\tc += final[i - 1][y1 - 1]\n\tfor i in range(y1, y2 + 1):\n\t\tc += final[x2 - 1][i - 1]\n\tc -= final[x2 - 1][y1 - 1]\n\tprint(c)\n", "def f(x, y):\n\treturn (x + y) * (x + y - 1) // 2 - y + 1\nT = int(input())\nfor n1 in range(T):\n\t(x1, y1, x2, y2) = [int(i) for i in input().split(' ')]\n\ts = 0\n\tfor x in range(x1, x2):\n\t\ts += f(x, y1)\n\tfor y in range(y1, y2 + 1):\n\t\ts += f(x2, y)\n\tprint(s)\n", "def value(x, y):\n\treturn x * (x + 1) // 2 + (2 * x + y - 2) * (y - 1) // 2\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tsum = 0\n\tfor x in range(x1, x2 + 1):\n\t\tsum += value(x, y1)\n\tfor y in range(y1 + 1, y2 + 1):\n\t\tsum += value(x2, y)\n\tprint(sum)\n", "arr = []\nc = 1\nfor i in range(1, 1001):\n\tarr.append(c)\n\tc += i\nmatrix = []\nmatrix.append(arr)\nk = 2\nfor i in range(2, 1001):\n\tnewarr = []\n\tc = k\n\tfor j in matrix[-1]:\n\t\tnewarr.append(j + c)\n\t\tc += 1\n\tmatrix.append(newarr)\n\tk += 1\nfor t in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tans = 0\n\tfor i in range(x1, x2 + 1):\n\t\tans += matrix[i - 1][y1 - 1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tans += matrix[x2 - 1][i - 1]\n\tprint(ans)\n", "a = []\ns = 1\ni_s = 1\nr = 2\nc = 1\ni_c = 1\nc_c = 1\nfor i in range(1000):\n\tv = []\n\tfor j in range(1000):\n\t\tv.append(s)\n\t\ts += c\n\t\tc += c_c\n\ta.append(v)\n\ts = i_s + r\n\ti_s = s\n\tr += 1\n\tc = i_c + 1\n\ti_c = c\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tsu = sum(a[x2 - 1][y1 - 1:y2])\n\tfor i in range(x1 - 1, x2 - 1):\n\t\tsu += a[i][y1 - 1]\n\tprint(su)\n", "arr = [[0 for i in range(1000)] for j in range(1000)]\nstart = 0\nfor i in range(len(arr)):\n\tstart += i + 1\n\tinc = i\n\tfor j in range(len(arr)):\n\t\tif j == 0:\n\t\t\tarr[i][j] = start\n\t\telse:\n\t\t\tarr[i][j] = arr[i][j - 1] + inc\n\t\tinc += 1\nfor _ in range(int(input())):\n\tl = input().split()\n\t(x1, y1, x2, y2) = (int(l[0]), int(l[1]), int(l[2]), int(l[3]))\n\tsums = 0\n\tfor i in range(x1, x2 + 1):\n\t\tsums += arr[i - 1][y1 - 1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\tsums += arr[x2 - 1][i - 1]\n\tprint(sums)\n", "def val(r, c):\n\ts = c + r - 2\n\treturn int(s * (s + 1) / 2 + r)\nT = int(input())\nfor i in range(T):\n\t(r1, c1, r2, c2) = map(int, input().split())\n\tpath = 0\n\tfor r in range(r1, r2 + 1):\n\t\tpath += val(r, c1)\n\tfor c in range(c1 + 1, c2 + 1):\n\t\tpath += val(r2, c)\n\tprint(path)\n", "rows = 1000\ncols = 1000\ninf = [[0 for c in range(cols + 1)] for r in range(rows + 1)]\nfor i in range(1, 1001):\n\tinf[i][1] = int(i * (i + 1) / 2)\n\tfor j in range(2, 1001):\n\t\tinf[i][j] = inf[i][j - 1] + j - 1 + i - 1\nfor t in range(int(input())):\n\tsum = 0\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tfor i in range(x1, x2 + 1):\n\t\tsum = sum + inf[i][y1]\n\tfor j in range(y1 + 1, y2 + 1):\n\t\tsum = sum + inf[x2][j]\n\tprint(sum)\n", "t = int(input())\narr = [[0 for _ in range(1001)] for _ in range(1001)]\nfor i in range(1, 1001):\n\tarr[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tarr[i][j] = arr[i][j - 1] + i + j - 2\nfor i in range(t):\n\t(r1, c1, r2, c2) = list(map(int, input().split(' ')))\n\ts = 0\n\tfor i in range(r1, r2 + 1):\n\t\ts = s + arr[i][c1]\n\tfor j in range(c1 + 1, c2 + 1):\n\t\ts = s + arr[r2][j]\n\tprint(s)\n", "t = int(input())\nfor i in range(t):\n\tl = list(map(int, input().split()))\n\tx1 = l[0]\n\ty1 = l[1]\n\tx2 = l[2]\n\ty2 = l[3]\n\ttemp1 = x1\n\ttemp2 = y1\n\ttempval = x1 * (x1 + 1) // 2\n\tnews = (y1 - 1) * (2 * x1 + y1 - 2) // 2\n\tval = tempval + news\n\ts = val\n\twhile temp1 < x2:\n\t\tres = val + temp1 + temp2\n\t\ts = s + res\n\t\ttemp1 = temp1 + 1\n\t\tval = res\n\twhile temp2 < y2:\n\t\tres = val + temp1 + temp2 - 1\n\t\ts = s + res\n\t\ttemp2 += 1\n\t\tval = res\n\tprint(s)\n", "arr = [[0 for x in range(1001)] for y in range(1001)]\nfor i in range(1, 1001):\n\tarr[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1001):\n\t\tarr[i][j] = arr[i][j - 1] + (j - 1) + (i - 1)\nfor T in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\ttotal = 0\n\tfor i in range(x1, x2 + 1):\n\t\ttotal += arr[i][y1]\n\tfor j in range(y1 + 1, y2 + 1):\n\t\ttotal += arr[x2][j]\n\tprint(total)\n", "t = int(input())\nfor k in range(t):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tx1 = int(x1) - 1\n\ty1 = int(y1) - 1\n\tx2 = int(x2) - 1\n\ty2 = int(y2) - 1\n\tpath = 1\n\tx = 0\n\ty = 0\n\twhile x < x1:\n\t\tpath += x + y + 2\n\t\tx += 1\n\twhile y < y1:\n\t\tpath += y + x1 + 1\n\t\ty += 1\n\ttemp = path\n\twhile x1 < x2:\n\t\ttemp += x1 + y1 + 2\n\t\tpath += temp\n\t\tx1 += 1\n\twhile y1 < y2:\n\t\ttemp += y1 + x2 + 1\n\t\tpath += temp\n\t\ty1 += 1\n\tprint(path)\n", "t = int(input())\n\ndef formula(x, y):\n\treturn (y - 1) * (2 * x + (y - 2)) // 2 + x * (x + 1) // 2\nfor i in range(t):\n\t(x1, y1, x2, y2) = [int(i) for i in input().split()]\n\tif x1 > x2 or (x1 == x2 and y1 > y2):\n\t\t(x1, x2) = (x2, x1)\n\t\t(y1, y2) = (y2, y1)\n\ts = 0\n\twhile x1 <= x2:\n\t\ttmp = formula(x1, y1)\n\t\ts += tmp\n\t\tx1 += 1\n\tx1 -= 1\n\ty1 += 1\n\twhile y1 <= y2:\n\t\ttmp = formula(x1, y1)\n\t\ts += tmp\n\t\ty1 += 1\n\tprint(s)\n", "t = int(input())\nfor i in range(t):\n\t(x, y, a, b) = map(int, input().split())\n\te = []\n\ts = 0\n\tw = 0\n\ts = int(x * (x + 1) / 2)\n\tfor j in range(2, y + 1):\n\t\tif j == y:\n\t\t\tw = s\n\t\ts = s + j - 1 + x - 1\n\tif w == 0:\n\t\te.append(s)\n\t\tfor j in range(x, a):\n\t\t\ts = (j + 1) * (j + 2) // 2\n\t\t\te.append(s)\n\telse:\n\t\tw = s - w + 2\n\t\te.append(s)\n\t\tfor j in range(x, a):\n\t\t\ts += w\n\t\t\te.append(s)\n\t\t\tw += 1\n\tfor j in range(y + 1, b + 1):\n\t\ts += j - 1 + a - 1\n\t\te.append(s)\n\tprint(sum(e))\n", "def value_at_xy(x, y):\n\ta = b = V = 1\n\tdiff = 2\n\twhile b != y:\n\t\tV += diff\n\t\tdiff += 1\n\t\tb += 1\n\tdiff -= 1\n\twhile a != x:\n\t\tV += diff\n\t\tdiff += 1\n\t\ta += 1\n\treturn V\n\ndef path_value(x1, y1, x2, y2, V):\n\tret = V\n\tdiff = x1 + y1\n\twhile y1 != y2:\n\t\tV += diff\n\t\tret += V\n\t\tdiff += 1\n\t\ty1 += 1\n\tdiff -= 1\n\twhile x1 != x2:\n\t\tV += diff\n\t\tret += V\n\t\tdiff += 1\n\t\tx1 += 1\n\treturn ret\nT = int(input())\nfor testcases in range(T):\n\t[y1, x1, y2, x2] = [int(x) for x in input().split()]\n\tS = value_at_xy(x1, y1)\n\tprint(path_value(x1, y1, x2, y2, S))\n", "mat = [[0] * 1004 for _ in range(1004)]\nfor i in range(1, 1004):\n\tmat[i][1] = i * (i + 1) // 2\n\tfor j in range(2, 1004):\n\t\tmat[i][j] = mat[i][j - 1] + i + j - 2\n\ndef sol(x1, y1, x2, y2):\n\ts = 0\n\tfor i in range(x1, x2 + 1):\n\t\ts += mat[i][y1]\n\tfor i in range(y1 + 1, y2 + 1):\n\t\ts += mat[x2][i]\n\treturn s\nfor _ in range(int(input())):\n\t(x1, y1, x2, y2) = map(int, input().split())\n\tprint(sol(x1, y1, x2, y2))\n", "t = int(input())\nfor _ in range(t):\n\tarr = list(map(int, input().split()))\n\tx = arr[0]\n\ty = arr[1]\n\tx1 = arr[2]\n\ty1 = arr[3]\n\tn = 0\n\tfor i in range(0, x):\n\t\tn += i + 1\n\tfor i in range(0, y - 1):\n\t\tn += x + i\n\ts = n\n\td = x + y\n\tfor i in range(0, x1 - x):\n\t\tn += d + i\n\t\ts += n\n\td = x1 + y - 1\n\tfor i in range(0, y1 - y):\n\t\tn += d + i\n\t\ts += n\n\tprint(s)\n"]

raw_tags: ['Prefix Sum', 'Algorithms', 'Constructive', 'Simple Algos']

source: codechef

tags: ['Range queries', 'Constructive algorithms']

skill_types: ['Range queries']

time_limit: 0.5 seconds

memory_limit: 50000 bytes

raw_problem:
### Read problems statements in [Mandarin Chinese](https://www.codechef.com/download/translated/COOK129/mandarin/TLAPM.pdf), [Russian](https://www.codechef.com/download/translated/COOK129/russian/TLAPM.pdf), [Vietnamese](https://www.codechef.com/download/translated/COOK129/vietnamese/TLAPM.pdf) and [Bengali](https://www.codechef.com/download/translated/COOK129/bengali/TLAPM.pdf) as well.

Deep wants to become a 7-star coder on CodeChef. To achieve this goal, everyday, he has to solve as many problems as he can. But for the first time since he was new to programming, he wasn't able to solve a single problem and lost his confidence. Can you help him solve the problem so that he gets a new boost to go ahead?

In this problem, you are given a matrix that extends infinitely to the right and down, filled with values as shown below.

Let $(x, y)$ denote the cell in the $x$-th row and $y$-th column. The upper-left cell $(1, 1)$ contains an integer $1$. You begin at the cell $(x_1, y_1)$ and must walk to the cell $(x_2, y_2)$ by only moving right and down. Formally, from the cell $(x, y)$, in one step you can move to the cell $(x+1, y)$ or $(x, y+1)$.

The value of a path is the sum of the values in all visited cells, including $(x_1, y_1)$ and $(x_2, y_2)$. You need to calculate the maximum possible value on the path of a path from $(x_1, y_1)$ to $(x_2, y_2)$.

###Input

- The first line contains an integer $T$, the number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, four integers $x_1$, $y_1$, $x_2$, $y_2$.

###Output
For each test case, output in a single line the maximum possible value of a path from $(x_1, y_1)$ to $(x_2, y_2)$.

###Constraints
- $1 \leq T \leq 1000$
- $1\leq x_1\leq x_2\leq 1000$
- $1\leq y_1\leq y_2\leq 1000$

###Sample Input
	1
	1 1 3 3

###Sample Output
	32

###Explanation
The only way to achieve the maximum possible value is by visiting cells with values $1 \to 3 \to 6 \to 9 \to 13$.

All submissions for this problem are available.

question:
### Read problems statements in [Mandarin Chinese](https://www.codechef.com/download/translated/COOK129/mandarin/TLAPM.pdf), [Russian](https://www.codechef.com/download/translated/COOK129/russian/TLAPM.pdf), [Vietnamese](https://www.codechef.com/download/translated/COOK129/vietnamese/TLAPM.pdf) and [Bengali](https://www.codechef.com/download/translated/COOK129/bengali/TLAPM.pdf) as well.

Deep wants to become a 7-star coder on CodeChef. To achieve this goal, everyday, he has to solve as many problems as he can. But for the first time since he was new to programming, he wasn't able to solve a single problem and lost his confidence. Can you help him solve the problem so that he gets a new boost to go ahead?

In this problem, you are given a matrix that extends infinitely to the right and down, filled with values as shown below.

![image](1.png)

Let $(x, y)$ denote the cell in the $x$-th row and $y$-th column. The upper-left cell $(1, 1)$ contains an integer $1$. You begin at the cell $(x_1, y_1)$ and must walk to the cell $(x_2, y_2)$ by only moving right and down. Formally, from the cell $(x, y)$, in one step you can move to the cell $(x+1, y)$ or $(x, y+1)$.

The value of a path is the sum of the values in all visited cells, including $(x_1, y_1)$ and $(x_2, y_2)$. You need to calculate the maximum possible value on the path of a path from $(x_1, y_1)$ to $(x_2, y_2)$.

###Input

- The first line contains an integer $T$, the number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, four integers $x_1$, $y_1$, $x_2$, $y_2$.

###Output
For each test case, output in a single line the maximum possible value of a path from $(x_1, y_1)$ to $(x_2, y_2)$.

###Constraints
- $1 \leq T \leq 1000$
- $1\leq x_1\leq x_2\leq 1000$
- $1\leq y_1\leq y_2\leq 1000$

###Sample Input
	1
	1 1 3 3

###Sample Output
	32

###Explanation
The only way to achieve the maximum possible value is by visiting cells with values $1 \to 3 \to 6 \to 9 \to 13$.
All submissions for this problem are available.

data_split: test