E. House Planning

problem_index: E

time_limit: 3 seconds

memory_limit: 256 megabytes

note:
In the image below you can see the sample solutions. Planned houses are shown in bright colours: pink and purple. Existing houses are dim.
In test case $$$1$$$, the first planned house is located at point $$$0$$$, the second at point $$$10$$$. The existing house is located at point $$$5$$$ and is at a distance of $$$5$$$ from both planned houses.
![image](images/cf_1735_E/1.png)
It can be shown that there is no answer for test case $$$2$$$.
![image](images/cf_1735_E/2.png)
In test case $$$3$$$, the planned houses are located at points $$$33$$$ and $$$69$$$.
![image](images/cf_1735_E/3.png)
Note that in test case $$$4$$$, both plans are located at point $$$1$$$, where one of the existing houses is located at the same time. It is a correct placement.
![image](images/cf_1735_E/4.png)

solutions: ["# rainboy\r\ndef solve(d, n, d1, d2):\r\n    jj = [-1] * n; ii = [-1] * n; xx = [-1] * n\r\n    i1 = n - 1; i2 = n - 1\r\n    j1 = n - 1; j2 = n - 1\r\n    while 1:\r\n        while i2 >= 0 and jj[i2] != -1: i2 -= 1\r\n        while j2 >= 0 and ii[j2] != -1: j2 -= 1\r\n        if j2 < 0 and j2 < 0:\r\n            break \r\n        if j2 < 0 or d1[i2] > d2[j2]:\r\n            if d1[i2] <= d:\r\n                break \r\n            while j1 >= 0 and (ii[j1] != -1 or d1[i2] - d2[j1] < d):\r\n                j1-=1\r\n            if j1 < 0 or d1[i2] - d2[j1] != d:\r\n                return 0\r\n            jj[i2] = j1; ii[j1] = i2 \r\n        else:\r\n            if d2[j2] <= d:\r\n                break \r\n            while i1 >= 0 and (jj[i1] != -1 or d2[j2] - d1[i1] < d):\r\n                i1 -= 1\r\n            if i1 < 0 or d2[j2] - d1[i1] != d:\r\n                return 0\r\n            jj[i1] = j2; ii[j2] = i1 \r\n    \r\n    a = 0; b = n - 1\r\n    while 1:\r\n        while a < n and jj[a] != -1:\r\n            a += 1\r\n        if a == n:\r\n            break\r\n        while b >= 0 and ii[b] != -1:\r\n            b -= 1 \r\n        if d1[a] + d2[b] != d:\r\n            return 0 \r\n        jj[a] = b; ii[b] = a \r\n    \r\n    x = 0\r\n    for a in range(n):\r\n        # print(f\"d1[{a}]={d1[a]},\", end=\" \")\r\n        # print(f\"jj[{a}] = {jj[a]}, \", end=\"\")\r\n        # print(f\"d2[{jj[a]}] = {d2[jj[a]]} \", end=\"\")\r\n        xx[a] = -d1[a] if d2[jj[a]] - d1[a] == d else d1[a]\r\n        x = min(x,  xx[a])\r\n    print(\"YES\")\r\n    for i in range(n):\r\n        print(f\"{xx[i] - x}\", end=\" \")\r\n    print(\"\")\r\n    print(f\"{0-x} {d - x}\")\r\n    return 1\r\n    \r\n    \r\n\r\nfor _ in range(int(input())):\r\n    n = int(input())\r\n    d1 = sorted(list(map(int, input().split())))\r\n    d2 = sorted(list(map(int, input().split())))\r\n    yes = 0\r\n    for i in range(n):\r\n        if i == 0 or d2[i] != d2[i - 1]:\r\n            if solve(abs(d1[0] - d2[i]), n, d1, d2) or solve(d1[0] + d2[i], n, d1, d2):\r\n                yes = 1\r\n                break \r\n    \r\n    if yes == 0:\r\n        print(\"NO\")", "import random\r\n\r\n\r\nclass TreapMultiSet(object):\r\n    root = 0\r\n    size = 0\r\n\r\n    def __init__(self, data=None):\r\n        if data:\r\n            data = sorted(data)\r\n            self.root = treap_builder(data)\r\n            self.size = len(data)\r\n\r\n    def add(self, key):\r\n        self.root = treap_insert(self.root, key)\r\n        self.size += 1\r\n\r\n    def remove(self, key):\r\n        self.root = treap_erase(self.root, key)\r\n        self.size -= 1\r\n\r\n    def discard(self, key):\r\n        try:\r\n            self.remove(key)\r\n        except KeyError:\r\n            pass\r\n\r\n    def ceiling(self, key):\r\n        x = treap_ceiling(self.root, key)\r\n        return treap_keys[x] if x else None\r\n\r\n    def higher(self, key):\r\n        x = treap_higher(self.root, key)\r\n        return treap_keys[x] if x else None\r\n\r\n    def floor(self, key):\r\n        x = treap_floor(self.root, key)\r\n        return treap_keys[x] if x else None\r\n\r\n    def lower(self, key):\r\n        x = treap_lower(self.root, key)\r\n        return treap_keys[x] if x else None\r\n\r\n    def max(self):\r\n        return treap_keys[treap_max(self.root)]\r\n\r\n    def min(self):\r\n        return treap_keys[treap_min(self.root)]\r\n\r\n    def __len__(self):\r\n        return self.size\r\n\r\n    def __nonzero__(self):\r\n        return bool(self.root)\r\n\r\n    __bool__ = __nonzero__\r\n\r\n    def __contains__(self, key):\r\n        return self.floor(key) == key\r\n\r\n    def __repr__(self):\r\n        return \"TreapMultiSet({})\".format(list(self))\r\n\r\n    def __iter__(self):\r\n        if not self.root:\r\n            return iter([])\r\n        out = []\r\n        stack = [self.root]\r\n        while stack:\r\n            node = stack.pop()\r\n            if node > 0:\r\n                if right_child[node]:\r\n                    stack.append(right_child[node])\r\n                stack.append(~node)\r\n                if left_child[node]:\r\n                    stack.append(left_child[node])\r\n            else:\r\n                out.append(treap_keys[~node])\r\n        return iter(out)\r\n\r\n\r\nclass TreapSet(TreapMultiSet):\r\n    def add(self, key):\r\n        self.root, duplicate = treap_insert_unique(self.root, key)\r\n        if not duplicate:\r\n            self.size += 1\r\n\r\n    def __repr__(self):\r\n        return \"TreapSet({})\".format(list(self))\r\n\r\n\r\nclass TreapHashSet(TreapMultiSet):\r\n    def __init__(self, data=None):\r\n        if data:\r\n            self.keys = set(data)\r\n            super(TreapHashSet, self).__init__(self.keys)\r\n        else:\r\n            self.keys = set()\r\n\r\n    def add(self, key):\r\n        if key not in self.keys:\r\n            self.keys.add(key)\r\n            super(TreapHashSet, self).add(key)\r\n\r\n    def remove(self, key):\r\n        self.keys.remove(key)\r\n        super(TreapHashSet, self).remove(key)\r\n\r\n    def discard(self, key):\r\n        if key in self.keys:\r\n            self.remove(key)\r\n\r\n    def __contains__(self, key):\r\n        return key in self.keys\r\n\r\n    def __repr__(self):\r\n        return \"TreapHashSet({})\".format(list(self))\r\n\r\n\r\nclass TreapHashMap(TreapMultiSet):\r\n    def __init__(self, data=None):\r\n        if data:\r\n            self.map = dict(data)\r\n            super(TreapHashMap, self).__init__(self.map.keys())\r\n        else:\r\n            self.map = {}\r\n\r\n    def __setitem__(self, key, value):\r\n        if key not in self.map:\r\n            super(TreapHashMap, self).add(key)\r\n        self.map[key] = value\r\n\r\n    def __getitem__(self, key):\r\n        return self.map[key]\r\n\r\n    def add(self, key):\r\n        raise TypeError(\"add on TreapHashMap\")\r\n\r\n    def get(self, key, default=None):\r\n        return self.map.get(key, default=default)\r\n\r\n    def remove(self, key):\r\n        self.map.pop(key)\r\n        super(TreapHashMap, self).remove(key)\r\n\r\n    def discard(self, key):\r\n        if key in self.map:\r\n            self.remove(key)\r\n\r\n    def __contains__(self, key):\r\n        return key in self.map\r\n\r\n    def __repr__(self):\r\n        return \"TreapHashMap({})\".format(list(self))\r\n\r\n\r\nleft_child = [0]\r\nright_child = [0]\r\ntreap_keys = [0]\r\ntreap_prior = [0.0]\r\n\r\n\r\ndef treap_builder(sorted_data):\r\n    \"\"\"Build a treap in O(n) time using sorted data\"\"\"\r\n    def build(begin, end):\r\n        if begin == end:\r\n            return 0\r\n        mid = (begin + end) // 2\r\n        root = treap_create_node(sorted_data[mid])\r\n        left_child[root] = build(begin, mid)\r\n        right_child[root] = build(mid + 1, end)\r\n\r\n        # sift down the priorities\r\n        ind = root\r\n        while True:\r\n            lc = left_child[ind]\r\n            rc = right_child[ind]\r\n\r\n            if lc and treap_prior[lc] > treap_prior[ind]:\r\n                if rc and treap_prior[rc] > treap_prior[lc]:\r\n                    treap_prior[ind], treap_prior[rc] = treap_prior[rc], treap_prior[ind]\r\n                    ind = rc\r\n                else:\r\n                    treap_prior[ind], treap_prior[lc] = treap_prior[lc], treap_prior[ind]\r\n                    ind = lc\r\n            elif rc and treap_prior[rc] > treap_prior[ind]:\r\n                treap_prior[ind], treap_prior[rc] = treap_prior[rc], treap_prior[ind]\r\n                ind = rc\r\n            else:\r\n                break\r\n        return root\r\n\r\n    return build(0, len(sorted_data))\r\n\r\n\r\ndef treap_create_node(key):\r\n    treap_keys.append(key)\r\n    treap_prior.append(random.random())\r\n    left_child.append(0)\r\n    right_child.append(0)\r\n    return len(treap_keys) - 1\r\n\r\n\r\ndef treap_split(root, key):\r\n    left_pos = right_pos = 0\r\n    while root:\r\n        if key < treap_keys[root]:\r\n            left_child[right_pos] = right_pos = root\r\n            root = left_child[root]\r\n        else:\r\n            right_child[left_pos] = left_pos = root\r\n            root = right_child[root]\r\n    left, right = right_child[0], left_child[0]\r\n    right_child[left_pos] = left_child[right_pos] = right_child[0] = left_child[0] = 0\r\n    return left, right\r\n\r\n\r\ndef treap_merge(left, right):\r\n    where, pos = left_child, 0\r\n    while left and right:\r\n        if treap_prior[left] > treap_prior[right]:\r\n            where[pos] = pos = left\r\n            where = right_child\r\n            left = right_child[left]\r\n        else:\r\n            where[pos] = pos = right\r\n            where = left_child\r\n            right = left_child[right]\r\n    where[pos] = left or right\r\n    node = left_child[0]\r\n    left_child[0] = 0\r\n    return node\r\n\r\n\r\ndef treap_insert(root, key):\r\n    if not root:\r\n        return treap_create_node(key)\r\n    left, right = treap_split(root, key)\r\n    return treap_merge(treap_merge(left, treap_create_node(key)), right)\r\n\r\n\r\ndef treap_insert_unique(root, key):\r\n    if not root:\r\n        return treap_create_node(key), False\r\n    left, right = treap_split(root, key)\r\n    if left and treap_keys[left] == key:\r\n        return treap_merge(left, right), True\r\n    return treap_merge(treap_merge(left, treap_create_node(key)), right), False\r\n\r\n\r\ndef treap_erase(root, key):\r\n    if not root:\r\n        raise KeyError(key)\r\n    if treap_keys[root] == key:\r\n        return treap_merge(left_child[root], right_child[root])\r\n    node = root\r\n    while root and treap_keys[root] != key:\r\n        parent = root\r\n        root = left_child[root] if key < treap_keys[root] else right_child[root]\r\n    if not root:\r\n        raise KeyError(key)\r\n    if root == left_child[parent]:\r\n        left_child[parent] = treap_merge(left_child[root], right_child[root])\r\n    else:\r\n        right_child[parent] = treap_merge(left_child[root], right_child[root])\r\n\r\n    return node\r\n\r\n\r\ndef treap_ceiling(root, key):\r\n    while root and treap_keys[root] < key:\r\n        root = right_child[root]\r\n    if not root:\r\n        return 0\r\n    min_node = root\r\n    min_key = treap_keys[root]\r\n    while root:\r\n        if treap_keys[root] < key:\r\n            root = right_child[root]\r\n        else:\r\n            if treap_keys[root] < min_key:\r\n                min_key = treap_keys[root]\r\n                min_node = root\r\n            root = left_child[root]\r\n    return min_node\r\n\r\n\r\ndef treap_higher(root, key):\r\n    while root and treap_keys[root] <= key:\r\n        root = right_child[root]\r\n    if not root:\r\n        return 0\r\n    min_node = root\r\n    min_key = treap_keys[root]\r\n    while root:\r\n        if treap_keys[root] <= key:\r\n            root = right_child[root]\r\n        else:\r\n            if treap_keys[root] < min_key:\r\n                min_key = treap_keys[root]\r\n                min_node = root\r\n            root = left_child[root]\r\n    return min_node\r\n\r\n\r\ndef treap_floor(root, key):\r\n    while root and treap_keys[root] > key:\r\n        root = left_child[root]\r\n    if not root:\r\n        return 0\r\n    max_node = root\r\n    max_key = treap_keys[root]\r\n    while root:\r\n        if treap_keys[root] > key:\r\n            root = left_child[root]\r\n        else:\r\n            if treap_keys[root] > max_key:\r\n                max_key = treap_keys[root]\r\n                max_node = root\r\n            root = right_child[root]\r\n    return max_node\r\n\r\n\r\ndef treap_lower(root, key):\r\n    while root and treap_keys[root] >= key:\r\n        root = left_child[root]\r\n    if not root:\r\n        return 0\r\n    max_node = root\r\n    max_key = treap_keys[root]\r\n    while root:\r\n        if treap_keys[root] >= key:\r\n            root = left_child[root]\r\n        else:\r\n            if treap_keys[root] > max_key:\r\n                max_key = treap_keys[root]\r\n                max_node = root\r\n            root = right_child[root]\r\n    return max_node\r\n\r\n\r\ndef treap_min(root):\r\n    if not root:\r\n        raise ValueError(\"min on empty treap\")\r\n    while left_child[root]:\r\n        root = left_child[root]\r\n    return root\r\n\r\n\r\ndef treap_max(root):\r\n    if not root:\r\n        raise ValueError(\"max on empty treap\")\r\n    while right_child[root]:\r\n        root = right_child[root]\r\n    return root\r\n    \r\nimport sys\r\ninput = sys.stdin.readline\r\n\r\nt = int(input())\r\nfor _ in range(t):\r\n    n = int(input())\r\n    \r\n    d1 = list(map(int, input().split()))\r\n    d2 = list(map(int, input().split()))\r\n    \r\n    d1.sort()\r\n    d2.sort()\r\n    \r\n    poss = set()\r\n    v0 = d1[0]\r\n    for v in d2:\r\n        poss.add(v + v0)\r\n        poss.add(abs(v - v0))\r\n        \r\n    index = list(range(~(n - 1), n))\r\n    assert len(index) == 2 * n\r\n    \r\n    def mag(i):\r\n        if i >= 0:\r\n            return d1[i]\r\n        else:\r\n            return d2[~i]\r\n                \r\n    index.sort(key = lambda x: -mag(x))\r\n    #print(d1, d2, index)\r\n    \r\n    pp = list(poss)\r\n    random.shuffle(pp)\r\n    \r\n    for d in pp:\r\n        good = True\r\n        \r\n        out = []\r\n        \r\n        a1 = TreapMultiSet()\r\n        a2 = TreapMultiSet()\r\n        \r\n        for v in d1:\r\n            a1.add(v)\r\n                \r\n        for v in d2:\r\n            a2.add(v)\r\n        \r\n        #print(d)\r\n        for i in index:\r\n            #print(i, a1, a2)\r\n            if i >= 0:\r\n                j = i\r\n                \r\n                if d1[j] <= d:\r\n                    break\r\n                \r\n                if d1[j] in a1:\r\n                    if d1[j] - d in a2:\r\n                        a1.remove(d1[j])\r\n                        a2.remove(d1[j] - d)\r\n                        out.append(d1[j])\r\n                    else:\r\n                        good = False\r\n                        break\r\n            else:\r\n                j = ~i\r\n                \r\n                if d2[j] <= d:\r\n                    break\r\n                \r\n                if d2[j] in a2:\r\n                    if d2[j] - d in a1:\r\n                        a2.remove(d2[j])\r\n                        a1.remove(d2[j] - d)\r\n                        out.append(d - d2[j])\r\n                    else:\r\n                        good = False\r\n                        break\r\n                    \r\n        for v in a1:\r\n            if d - v in a2:\r\n                a2.remove(d - v)\r\n                out.append(v)\r\n            else:\r\n                good = False\r\n        \r\n        if good:\r\n            diff = min(out + [0])\r\n            print('YES')\r\n            print(' '.join(map(lambda x: str(x - diff), out)))\r\n            print(0 - diff, d - diff)\r\n            break\r\n    else:\r\n        print('NO')", "# https://codeforces.com/contest/1735\n\nimport sys\nfrom collections import Counter\n\ninput = lambda: sys.stdin.readline().rstrip()  # faster!\n\n\ndef solve_case():\n    n = int(input())\n    d1 = sorted(map(int, input().split()))\n    d2 = sorted(map(int, input().split()))\n\n    for i in range(n):\n        for f in [1, -1]:\n\n            h = []\n            cnt1 = Counter(d1)\n            cnt2 = Counter(d2)\n\n            p1 = 0\n            cnt1[d1[0]] -= 1\n            p2 = p1 + d1[0] + f * d2[i]\n            cnt2[d2[i]] -= 1\n            h += [p1 + d1[0]]\n            delta = abs(p1 - p2)\n            k = 1\n\n            ok = True\n            j1 = n - 1\n            j2 = n - 1\n            while k < n:\n                while not cnt1[d1[j1]]:\n                    j1 -= 1\n                while not cnt2[d2[j2]]:\n                    j2 -= 1\n\n                if d1[j1] >= d2[j2] and d1[j1] > delta:\n                    req = d1[j1] - delta\n                    if not cnt2[req]:\n                        ok = False\n                        break\n                    if p1 <= p2:\n                        h += [p1 + d1[j1]]\n                    else:\n                        h += [p1 - d1[j1]]\n                    cnt1[d1[j1]] -= 1\n                    cnt2[req] -= 1\n                    k += 1\n\n                elif d2[j2] >= d1[j1] and d2[j2] > delta:\n                    req = d2[j2] - delta\n                    if not cnt1[req]:\n                        ok = False\n                        break\n                    if p1 <= p2:\n                        h += [p2 - d2[j2]]\n                    else:\n                        h += [p2 + d2[j2]]\n                    cnt1[req] -= 1\n                    cnt2[d2[j2]] -= 1\n                    k += 1\n\n                else:\n                    req = delta - d1[j1]\n                    if not cnt2[req]:\n                        ok = False\n                        break\n                    if p1 <= p2:\n                        h += [p1 + d1[j1]]\n                    else:\n                        h += [p1 - d1[j1]]\n                    cnt1[d1[j1]] -= 1\n                    cnt2[req] -= 1\n                    k += 1\n\n            mn = min(p1, p2, min(h))\n            mx = max(p1, p2, max(h))\n            if mx - mn > 2 * 10 ** 9:\n                ok = False\n            else:\n                p1, p2 = p1 - mn, p2 - mn\n                h = [x - mn for x in h]\n\n            if ok:\n                print(\"YES\")\n                print(*h)\n                print(p1, p2)\n                return\n\n    print(\"NO\")\n\n\nfor _ in range(int(input())):\n    solve_case()", "from collections import defaultdict\r\nfrom sys import stdin\r\ninput=lambda :stdin.readline()[:-1]\r\n\r\ndef calc(c,d,n):\r\n  pair=[]\r\n  rem1=defaultdict(int)\r\n  rem2=defaultdict(int)\r\n  for t,x in c:\r\n    if t==1:\r\n      if rem2[x+d]>0:\r\n        pair.append((x,x+d))\r\n        rem2[x+d]-=1\r\n      else:\r\n        rem1[x]+=1\r\n    else:\r\n      if rem1[x+d]>0:\r\n        pair.append((x+d,x))\r\n        rem1[x+d]-=1\r\n      else:\r\n        rem2[x]+=1\r\n  \r\n  for i in rem1:\r\n    if rem1[i]>0:\r\n      if rem1[i]==rem2[d-i]:\r\n        for _ in range(rem1[i]):\r\n          pair.append((i,d-i))\r\n      else:\r\n        return -1\r\n  \r\n  if len(pair)!=n:\r\n    return -1\r\n  else:\r\n    return pair\r\n\r\ndef ANS(d,ans):\r\n  X=[]\r\n  for x,y in ans:\r\n    if x+y==d:\r\n      X.append(x)\r\n    elif x<y:\r\n      X.append(-x)\r\n    else:\r\n      X.append(x)\r\n  mn=min(min(X),0)\r\n  print('YES')\r\n  print(*[i-mn for i in X])\r\n  print(*[0-mn,d-mn])\r\n  return\r\n\r\ndef solve():\r\n  n=int(input())\r\n  a=list(map(int,input().split()))\r\n  b=list(map(int,input().split()))\r\n  c=[]\r\n  for i in range(n):\r\n    c.append((1,a[i]))\r\n    c.append((2,b[i]))\r\n  c.sort(key=lambda x:-x[1])\r\n  for i in range(n):\r\n    d=a[0]+b[i]\r\n    ans=calc(c,d,n)\r\n    if ans!=-1:\r\n      ANS(d,ans)\r\n      return\r\n    d=abs(a[0]-b[i])\r\n    ans=calc(c,d,n)\r\n    if ans!=-1:\r\n      ANS(d,ans)\r\n      return\r\n  print('NO')\r\n\r\nfor _ in range(int(input())):\r\n  solve()", "import os, sys\r\nfrom io import BytesIO, IOBase\r\n\r\nfrom collections import defaultdict, deque, Counter\r\nfrom bisect import bisect_left, bisect_right\r\nfrom heapq import heappush, heappop\r\nfrom functools import lru_cache\r\nfrom itertools import accumulate\r\nimport math\r\n\r\n# Fast IO Region\r\nBUFSIZE = 8192\r\n\r\n\r\nclass FastIO(IOBase):\r\n    newlines = 0\r\n\r\n    def __init__(self, file):\r\n        self._fd = file.fileno()\r\n        self.buffer = BytesIO()\r\n        self.writable = \"x\" in file.mode or \"r\" not in file.mode\r\n        self.write = self.buffer.write if self.writable else None\r\n\r\n    def read(self):\r\n        while True:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n            if not b:\r\n                break\r\n            ptr = self.buffer.tell()\r\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n        self.newlines = 0\r\n        return self.buffer.read()\r\n\r\n    def readline(self):\r\n        while self.newlines == 0:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n            self.newlines = b.count(b\"\\n\") + (not b)\r\n            ptr = self.buffer.tell()\r\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n        self.newlines -= 1\r\n        return self.buffer.readline()\r\n\r\n    def flush(self):\r\n        if self.writable:\r\n            os.write(self._fd, self.buffer.getvalue())\r\n            self.buffer.truncate(0), self.buffer.seek(0)\r\n\r\n\r\nclass IOWrapper(IOBase):\r\n    def __init__(self, file):\r\n        self.buffer = FastIO(file)\r\n        self.flush = self.buffer.flush\r\n        self.writable = self.buffer.writable\r\n        self.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\r\n        self.read = lambda: self.buffer.read().decode(\"ascii\")\r\n        self.readline = lambda: self.buffer.readline().decode(\"ascii\")\r\n\r\n\r\nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\r\n\r\n\r\nclass SortedList:\r\n    def __init__(self, iterable=[], _load=200):\r\n        \"\"\"Initialize sorted list instance.\"\"\"\r\n        values = sorted(iterable)\r\n        self._len = _len = len(values)\r\n        self._load = _load\r\n        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]\r\n        self._list_lens = [len(_list) for _list in _lists]\r\n        self._mins = [_list[0] for _list in _lists]\r\n        self._fen_tree = []\r\n        self._rebuild = True\r\n\r\n    def _fen_build(self):\r\n        \"\"\"Build a fenwick tree instance.\"\"\"\r\n        self._fen_tree[:] = self._list_lens\r\n        _fen_tree = self._fen_tree\r\n        for i in range(len(_fen_tree)):\r\n            if i | i + 1 < len(_fen_tree):\r\n                _fen_tree[i | i + 1] += _fen_tree[i]\r\n        self._rebuild = False\r\n\r\n    def _fen_update(self, index, value):\r\n        \"\"\"Update `fen_tree[index] += value`.\"\"\"\r\n        if not self._rebuild:\r\n            _fen_tree = self._fen_tree\r\n            while index < len(_fen_tree):\r\n                _fen_tree[index] += value\r\n                index |= index + 1\r\n\r\n    def _fen_query(self, end):\r\n        \"\"\"Return `sum(_fen_tree[:end])`.\"\"\"\r\n        if self._rebuild:\r\n            self._fen_build()\r\n\r\n        _fen_tree = self._fen_tree\r\n        x = 0\r\n        while end:\r\n            x += _fen_tree[end - 1]\r\n            end &= end - 1\r\n        return x\r\n\r\n    def _fen_findkth(self, k):\r\n        \"\"\"Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`).\"\"\"\r\n        _list_lens = self._list_lens\r\n        if k < _list_lens[0]:\r\n            return 0, k\r\n        if k >= self._len - _list_lens[-1]:\r\n            return len(_list_lens) - 1, k + _list_lens[-1] - self._len\r\n        if self._rebuild:\r\n            self._fen_build()\r\n\r\n        _fen_tree = self._fen_tree\r\n        idx = -1\r\n        for d in reversed(range(len(_fen_tree).bit_length())):\r\n            right_idx = idx + (1 << d)\r\n            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:\r\n                idx = right_idx\r\n                k -= _fen_tree[idx]\r\n        return idx + 1, k\r\n\r\n    def _delete(self, pos, idx):\r\n        \"\"\"Delete value at the given `(pos, idx)`.\"\"\"\r\n        _lists = self._lists\r\n        _mins = self._mins\r\n        _list_lens = self._list_lens\r\n\r\n        self._len -= 1\r\n        self._fen_update(pos, -1)\r\n        del _lists[pos][idx]\r\n        _list_lens[pos] -= 1\r\n\r\n        if _list_lens[pos]:\r\n            _mins[pos] = _lists[pos][0]\r\n        else:\r\n            del _lists[pos]\r\n            del _list_lens[pos]\r\n            del _mins[pos]\r\n            self._rebuild = True\r\n\r\n    def _loc_left(self, value):\r\n        \"\"\"Return an index pair that corresponds to the first position of `value` in the sorted list.\"\"\"\r\n        if not self._len:\r\n            return 0, 0\r\n\r\n        _lists = self._lists\r\n        _mins = self._mins\r\n\r\n        lo, pos = -1, len(_lists) - 1\r\n        while lo + 1 < pos:\r\n            mi = (lo + pos) >> 1\r\n            if value <= _mins[mi]:\r\n                pos = mi\r\n            else:\r\n                lo = mi\r\n\r\n        if pos and value <= _lists[pos - 1][-1]:\r\n            pos -= 1\r\n\r\n        _list = _lists[pos]\r\n        lo, idx = -1, len(_list)\r\n        while lo + 1 < idx:\r\n            mi = (lo + idx) >> 1\r\n            if value <= _list[mi]:\r\n                idx = mi\r\n            else:\r\n                lo = mi\r\n\r\n        return pos, idx\r\n\r\n    def _loc_right(self, value):\r\n        \"\"\"Return an index pair that corresponds to the last position of `value` in the sorted list.\"\"\"\r\n        if not self._len:\r\n            return 0, 0\r\n\r\n        _lists = self._lists\r\n        _mins = self._mins\r\n\r\n        pos, hi = 0, len(_lists)\r\n        while pos + 1 < hi:\r\n            mi = (pos + hi) >> 1\r\n            if value < _mins[mi]:\r\n                hi = mi\r\n            else:\r\n                pos = mi\r\n\r\n        _list = _lists[pos]\r\n        lo, idx = -1, len(_list)\r\n        while lo + 1 < idx:\r\n            mi = (lo + idx) >> 1\r\n            if value < _list[mi]:\r\n                idx = mi\r\n            else:\r\n                lo = mi\r\n\r\n        return pos, idx\r\n\r\n    def add(self, value):\r\n        \"\"\"Add `value` to sorted list.\"\"\"\r\n        _load = self._load\r\n        _lists = self._lists\r\n        _mins = self._mins\r\n        _list_lens = self._list_lens\r\n\r\n        self._len += 1\r\n        if _lists:\r\n            pos, idx = self._loc_right(value)\r\n            self._fen_update(pos, 1)\r\n            _list = _lists[pos]\r\n            _list.insert(idx, value)\r\n            _list_lens[pos] += 1\r\n            _mins[pos] = _list[0]\r\n            if _load + _load < len(_list):\r\n                _lists.insert(pos + 1, _list[_load:])\r\n                _list_lens.insert(pos + 1, len(_list) - _load)\r\n                _mins.insert(pos + 1, _list[_load])\r\n                _list_lens[pos] = _load\r\n                del _list[_load:]\r\n                self._rebuild = True\r\n        else:\r\n            _lists.append([value])\r\n            _mins.append(value)\r\n            _list_lens.append(1)\r\n            self._rebuild = True\r\n\r\n    def discard(self, value):\r\n        \"\"\"Remove `value` from sorted list if it is a member.\"\"\"\r\n        _lists = self._lists\r\n        if _lists:\r\n            pos, idx = self._loc_right(value)\r\n            if idx and _lists[pos][idx - 1] == value:\r\n                self._delete(pos, idx - 1)\r\n\r\n    def remove(self, value):\r\n        \"\"\"Remove `value` from sorted list; `value` must be a member.\"\"\"\r\n        _len = self._len\r\n        self.discard(value)\r\n        if _len == self._len:\r\n            raise ValueError('{0!r} not in list'.format(value))\r\n\r\n    def pop(self, index=-1):\r\n        \"\"\"Remove and return value at `index` in sorted list.\"\"\"\r\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\r\n        value = self._lists[pos][idx]\r\n        self._delete(pos, idx)\r\n        return value\r\n\r\n    def bisect_left(self, value):\r\n        \"\"\"Return the first index to insert `value` in the sorted list.\"\"\"\r\n        pos, idx = self._loc_left(value)\r\n        return self._fen_query(pos) + idx\r\n\r\n    def bisect_right(self, value):\r\n        \"\"\"Return the last index to insert `value` in the sorted list.\"\"\"\r\n        pos, idx = self._loc_right(value)\r\n        return self._fen_query(pos) + idx\r\n\r\n    def count(self, value):\r\n        \"\"\"Return number of occurrences of `value` in the sorted list.\"\"\"\r\n        return self.bisect_right(value) - self.bisect_left(value)\r\n\r\n    def __len__(self):\r\n        \"\"\"Return the size of the sorted list.\"\"\"\r\n        return self._len\r\n\r\n    def __getitem__(self, index):\r\n        \"\"\"Lookup value at `index` in sorted list.\"\"\"\r\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\r\n        return self._lists[pos][idx]\r\n\r\n    def __delitem__(self, index):\r\n        \"\"\"Remove value at `index` from sorted list.\"\"\"\r\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\r\n        self._delete(pos, idx)\r\n\r\n    def __contains__(self, value):\r\n        \"\"\"Return true if `value` is an element of the sorted list.\"\"\"\r\n        _lists = self._lists\r\n        if _lists:\r\n            pos, idx = self._loc_left(value)\r\n            return idx < len(_lists[pos]) and _lists[pos][idx] == value\r\n        return False\r\n\r\n    def __iter__(self):\r\n        \"\"\"Return an iterator over the sorted list.\"\"\"\r\n        return (value for _list in self._lists for value in _list)\r\n\r\n    def __reversed__(self):\r\n        \"\"\"Return a reverse iterator over the sorted list.\"\"\"\r\n        return (value for _list in reversed(self._lists) for value in reversed(_list))\r\n\r\n    def __repr__(self):\r\n        \"\"\"Return string representation of sorted list.\"\"\"\r\n        return 'SortedList({0})'.format(list(self))\r\n\r\n\r\nii = lambda: int(input())\r\nmii = lambda: map(int, input().split())\r\nlmii = lambda: list(map(int, input().split()))\r\nfrom sys import stdout\r\n\r\nmod = 10 ** 9 + 7\r\nN = 2 * 10 ** 9\r\n\r\n\r\ndef solve():\r\n    n = ii()\r\n    d1 = lmii()\r\n    d2 = lmii()\r\n    dt1 = [(k, 1) for i, k in enumerate(d1)]\r\n    dt2 = [(k, 2) for i, k in enumerate(d2)]\r\n    dt = dt1 + dt2\r\n    dt.sort()\r\n    stl = SortedList(dt)\r\n    s = sum(d1) + sum(d2)\r\n    if s % n == 0:\r\n        d = s // n\r\n        res = []\r\n        while stl:\r\n            k, w = stl.pop()\r\n            k_, w_ = d - k, 3 - w\r\n            if (k_, w_) not in stl:\r\n                break\r\n            stl.discard((k_, w_))\r\n            if w < w_:\r\n                res.append([k, k_])\r\n            else:\r\n                res.append([k_, k])\r\n        else:\r\n            p1, p2 = 0, d\r\n            h = []\r\n            for x, y in res:\r\n                h.append(x)\r\n            print('YES')\r\n            print(*h)\r\n            print(p1, p2)\r\n            return\r\n\r\n    k, w = dt[-1]\r\n    for i in range(len(dt) - 1):\r\n        k, w = dt[-1]\r\n        k_, w_ = dt[i]\r\n        if w_ == w:\r\n            continue\r\n        d = k - k_\r\n        stl = SortedList(dt)\r\n        res = []\r\n        while stl:\r\n            k, w = stl.pop()\r\n            if k >= d:\r\n                k_, w_ = k - d, 3 - w\r\n            else:\r\n                k_, w_ = d - k, 3 - w\r\n            if (k_, w_) not in stl:\r\n                break\r\n            stl.discard((k_, w_))\r\n            if w < w_:\r\n                res.append([k, k_])\r\n            else:\r\n                res.append([k_, k])\r\n        else:\r\n            res.sort(key=lambda x: (x[0] - x[1], -x[0]))\r\n            x, y = res[0]\r\n            if x + d == y:\r\n                p1 = res[0][0]\r\n                p2 = res[0][1]\r\n                h = []\r\n                for x, y in res:\r\n                    if x + d == y:\r\n                        h.append(p1 - x)\r\n                    elif x + y == d:\r\n                        h.append(p1 + x)\r\n                    elif x == y + d:\r\n                        h.append(p1 + x)\r\n                    else:\r\n                        raise Exception('?')\r\n            else:\r\n                res.sort(key=lambda x: (x[1] - x[0], -x[0]))\r\n                x, y = res[0]\r\n                if x != y + d:\r\n                    raise Exception('?')\r\n                p1 = N - x\r\n                p2 = N - y\r\n                h = []\r\n                for x, y in res:\r\n                    if x + d == y:\r\n                        h.append(p1 - x)\r\n                    else:\r\n                        h.append(p1 + x)\r\n            print('YES')\r\n            print(*h)\r\n            print(p1, p2)\r\n            break\r\n    else:\r\n        print('NO')\r\n\r\n\r\nfor _ in range(ii()):\r\n    solve()"]

source: codeforces

raw_problem:
E. House Planning

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

There are $$$n$$$ houses in your city arranged on an axis at points $$$h_1, h_2, \ldots, h_n$$$. You want to build a new house for yourself and consider two options where to place it: points $$$p_1$$$ and $$$p_2$$$.

As you like visiting friends, you have calculated in advance the distances from both options to all existing houses. More formally, you have calculated two arrays $$$d_1$$$, $$$d_2$$$: $$$d_{i, j} = \left|p_i - h_j\right|$$$, where $$$|x|$$$ defines the absolute value of $$$x$$$.

After a long time of inactivity you have forgotten the locations of the houses $$$h$$$ and the options $$$p_1$$$, $$$p_2$$$. But your diary still keeps two arrays — $$$d_1$$$, $$$d_2$$$, whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of $$$d_1$$$ and $$$d_2$$$ may correspond to different houses. Pay attention, that values from one array could not get to another, in other words, all values in the array $$$d_1$$$ correspond the distances from $$$p_1$$$ to the houses, and in the array $$$d_2$$$  — from $$$p_2$$$ to the houses.

Also pay attention, that the locations of the houses $$$h_i$$$ and the considered options $$$p_j$$$ could match. For example, the next locations are correct: $$$h = \{1, 0, 3, 3\}$$$, $$$p = \{1, 1\}$$$, that could correspond to already shuffled $$$d_1 = \{0, 2, 1, 2\}$$$, $$$d_2 = \{2, 2, 1, 0\}$$$.

Check whether there are locations of houses $$$h$$$ and considered points $$$p_1$$$, $$$p_2$$$, for which the founded arrays of distances would be correct. If it is possible, find appropriate locations of houses and considered options.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the length of arrays $$$d_1$$$, $$$d_2$$$.

The next two lines contain $$$n$$$ integers each: arrays $$$d_1$$$ and $$$d_2$$$ ($$$0 \le d_{i, j} \le 10^9$$$) respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^3$$$.

Output

For each test case, output a single line "NO" if there is no answer.

Otherwise output three lines. The first line must contain "YES". In the second line, print $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$. In the third line print two integers $$$p_1$$$, $$$p_2$$$.

It must be satisfied that $$$0 \le h_i, p_1, p_2 \le 2 \cdot 10^9$$$. We can show that if there is an answer, then there is one satisfying these constraints.

If there are several answers, output any of them.

Example

Input

4

1

5

5

2

10 12

5 20

2

10 33

26 69

4

0 2 1 2

2 2 1 0

Output

YES
5
0 10
NO
YES
0 43
33 69
YES
1 0 3 3
1 1

Note

In the image below you can see the sample solutions. Planned houses are shown in bright colours: pink and purple. Existing houses are dim.

In test case $$$1$$$, the first planned house is located at point $$$0$$$, the second at point $$$10$$$. The existing house is located at point $$$5$$$ and is at a distance of $$$5$$$ from both planned houses.

It can be shown that there is no answer for test case $$$2$$$.

In test case $$$3$$$, the planned houses are located at points $$$33$$$ and $$$69$$$.

Note that in test case $$$4$$$, both plans are located at point $$$1$$$, where one of the existing houses is located at the same time. It is a correct placement.

question:
There are $$$n$$$ houses in your city arranged on an axis at points $$$h_1, h_2, \ldots, h_n$$$. You want to build a new house for yourself and consider two options where to place it: points $$$p_1$$$ and $$$p_2$$$.
As you like visiting friends, you have calculated in advance the distances from both options to all existing houses. More formally, you have calculated two arrays $$$d_1$$$, $$$d_2$$$: $$$d_{i, j} = \left|p_i - h_j\right|$$$, where $$$|x|$$$ defines the absolute value of $$$x$$$.
After a long time of inactivity you have forgotten the locations of the houses $$$h$$$ and the options $$$p_1$$$, $$$p_2$$$. But your diary still keeps two arrays — $$$d_1$$$, $$$d_2$$$, whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of $$$d_1$$$ and $$$d_2$$$ may correspond to different houses. Pay attention, that values from one array could not get to another, in other words, all values in the array $$$d_1$$$ correspond the distances from $$$p_1$$$ to the houses, and in the array $$$d_2$$$  — from $$$p_2$$$ to the houses.
Also pay attention, that the locations of the houses $$$h_i$$$ and the considered options $$$p_j$$$ could match. For example, the next locations are correct: $$$h = \{1, 0, 3, 3\}$$$, $$$p = \{1, 1\}$$$, that could correspond to already shuffled $$$d_1 = \{0, 2, 1, 2\}$$$, $$$d_2 = \{2, 2, 1, 0\}$$$.
Check whether there are locations of houses $$$h$$$ and considered points $$$p_1$$$, $$$p_2$$$, for which the founded arrays of distances would be correct. If it is possible, find appropriate locations of houses and considered options.

Input
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. The description of test cases follows.
The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the length of arrays $$$d_1$$$, $$$d_2$$$.
The next two lines contain $$$n$$$ integers each: arrays $$$d_1$$$ and $$$d_2$$$ ($$$0 \le d_{i, j} \le 10^9$$$) respectively.
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^3$$$.

Output
For each test case, output a single line "NO" if there is no answer.
Otherwise output three lines. The first line must contain "YES". In the second line, print $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$. In the third line print two integers $$$p_1$$$, $$$p_2$$$.
It must be satisfied that $$$0 \le h_i, p_1, p_2 \le 2 \cdot 10^9$$$. We can show that if there is an answer, then there is one satisfying these constraints.
If there are several answers, output any of them.

Example
Input
4
1
5
5
2
10 12
5 20
2
10 33
26 69
4
0 2 1 2
2 2 1 0

Output
YES
5
0 10
NO
YES
0 43
33 69
YES
1 0 3 3
1 1

Note
In the image below you can see the sample solutions. Planned houses are shown in bright colours: pink and purple. Existing houses are dim.
In test case $$$1$$$, the first planned house is located at point $$$0$$$, the second at point $$$10$$$. The existing house is located at point $$$5$$$ and is at a distance of $$$5$$$ from both planned houses.
 ![image](1.png) It can be shown that there is no answer for test case $$$2$$$.
 In test case $$$3$$$, the planned houses are located at points $$$33$$$ and $$$69$$$.
 ![image](3.png) Note that in test case $$$4$$$, both plans are located at point $$$1$$$, where one of the existing houses is located at the same time. It is a correct placement.
 ![image](4.png)

image_tags: Graph Graph Graph

data_split: test


solutions: ["grundy = [[-1] * 15 for _ in range(15)]\ngrundy[0][0] = grundy[0][1] = grundy[1][0] = grundy[1][1] = 0\n\ndef moveCoin(x, y):\n\tif x > 1:\n\t\tif y > 0:\n\t\t\tyield (x - 2, y - 1)\n\t\tif y < 14:\n\t\t\tyield (x - 2, y + 1)\n\tif y > 1:\n\t\tif x > 0:\n\t\t\tyield (x - 1, y - 2)\n\t\tif x < 14:\n\t\t\tyield (x + 1, y - 2)\n\ndef getGrundy(x, y):\n\tif grundy[x][y] != -1:\n\t\treturn grundy[x][y]\n\ts = set()\n\tfor (i, j) in moveCoin(x, y):\n\t\ts.add(getGrundy(i, j))\n\tmex = 0\n\twhile mex in s:\n\t\tmex += 1\n\tgrundy[x][y] = mex\n\treturn mex\nfor _ in range(int(input())):\n\tk = int(input())\n\tcoins = [[0] * 15 for _ in range(15)]\n\tfor _ in range(k):\n\t\t(i, j) = [int(x) - 1 for x in input().split(' ')]\n\t\tcoins[i][j] = 1 - coins[i][j]\n\tres = 0\n\tfor i in range(15):\n\t\tfor j in range(15):\n\t\t\tif coins[i][j]:\n\t\t\t\tres ^= getGrundy(i, j)\n\tprint('First' if res else 'Second')\n", "dic = {}\n\ndef grundy(x, y):\n\tif x < 1 or y < 1 or x > 15 or (y > 15):\n\t\treturn -1\n\tif (x, y) in dic:\n\t\treturn dic[x, y]\n\ts = []\n\ts.append(grundy(x - 1, y - 2))\n\ts.append(grundy(x + 1, y - 2))\n\ts.append(grundy(x - 2, y + 1))\n\ts.append(grundy(x - 2, y - 1))\n\ti = 0\n\twhile True:\n\t\tif i not in s:\n\t\t\tdic[x, y] = i\n\t\t\treturn i\n\t\ti = i + 1\nt = int(input())\nfor _ in range(t):\n\tk = int(input())\n\ta = []\n\tv = 0\n\tfor i in range(k):\n\t\t(x, y) = map(int, input().split())\n\t\tv = v ^ grundy(x, y)\n\tif v:\n\t\tprint('First')\n\telse:\n\t\tprint('Second')\n", "grun = {}\n\ndef grundy(x, y):\n\tif 0 < x < 16 > y > 0:\n\t\tif (x, y) not in grun:\n\t\t\ta = {grundy(x - 2, y - 1), grundy(x - 2, y + 1), grundy(x - 1, y - 2), grundy(x + 1, y - 2)}\n\t\t\tk = 0\n\t\t\twhile k in a:\n\t\t\t\tk += 1\n\t\t\tgrun[x, y] = k\n\t\treturn grun[x, y]\n\treturn -1\nfor _ in range(int(input())):\n\tk = 0\n\tfor _ in range(int(input())):\n\t\tk ^= grundy(*map(int, input().split()))\n\tprint('First' if k else 'Second')\n", "from sys import stdin\n\ndef read_ints():\n\treturn [int(a.strip()) for a in stdin.readline().strip().split(' ')]\nboard = [[-1 for _ in range(15)] for _ in range(15)]\nboard[0][0] = 0\nmoves = [(-1, -2), (-2, -1), (-2, 1), (1, -2)]\n\ndef add(a, b):\n\treturn (a[0] + b[0], a[1] + b[1])\n\ndef is_valid(p):\n\treturn p[0] >= 0 and p[1] >= 0 and (p[0] < 15) and (p[1] < 15)\n\ndef nimber(p):\n\tb = board[p[0]][p[1]]\n\tif b != -1:\n\t\treturn b\n\tfields = [add(p, a) for a in moves]\n\tnimbs = {nimber(a): True for a in fields if is_valid(a)}\n\tb = 0\n\twhile b in nimbs:\n\t\tb += 1\n\tboard[p[0]][p[1]] = b\n\treturn b\nfor _ in range(read_ints()[0]):\n\tr = 0\n\tfor _ in range(read_ints()[0]):\n\t\tfield = add((-1, -1), read_ints())\n\t\tr ^= nimber(field)\n\tprint('First' if r else 'Second')\n", "from functools import reduce\nfrom itertools import chain\nfrom operator import xor\nboard = [[-1] * 19 for _ in range(19)]\nsize = 15\n\ndef mex(*numbers):\n\treturn next((i for i in range(size) if i not in numbers))\nstripes = chain(chain.from_iterable((zip(range(s + 1), reversed(range(s + 1))) for s in range(size))), chain.from_iterable((zip(range(s, size), reversed(range(s, size))) for s in range(1, size))))\nfor (i, j) in stripes:\n\tboard[i + 2][j + 2] = mex(board[i][j + 3], board[i][j + 1], board[i + 1][j], board[i + 3][j])\nfor _ in range(int(input().strip())):\n\tcoins = [[int(x) for x in input().strip().split(' ')] for _ in range(int(input().strip()))]\n\tprint('First' if reduce(xor, (board[x + 1][y + 1] for (x, y) in coins), 0) else 'Second')\n", "def mex(S):\n\ti = 0\n\twhile i in S:\n\t\ti += 1\n\treturn i\n\ndef sg_chess(x, y, max_x=15, max_y=15, cache={}):\n\tkey = (x, y)\n\tS = set()\n\tif key in cache:\n\t\treturn cache[key]\n\tfor (delta_x, delta_y) in [(-2, 1), (-2, -1), (1, -2), (-1, -2)]:\n\t\t(new_x, new_y) = (x + delta_x, y + delta_y)\n\t\tif 1 <= new_x <= max_x and 1 <= new_y <= max_y:\n\t\t\tS.add(sg_chess(new_x, new_y))\n\tcache[key] = mex(S)\n\treturn cache[key]\nfor t in range(int(input())):\n\tk = int(input())\n\tpositions = [tuple(map(int, input().split())) for i in range(k)]\n\tnim_sum = 0\n\tfor (x, y) in positions:\n\t\tnim_sum ^= sg_chess(x, y)\n\tprint(['Second', 'First'][nim_sum > 0])\n", "from functools import reduce\nt = int(input())\nMAX = 15\ngrundy = [[0 for x in range(15)] for y in range(15)]\nmoves = [(-2, -1), (-2, 1), (-1, -2), (1, -2)]\n\ndef mex(s):\n\tm = max(s)\n\tfor i in range(m):\n\t\tif i not in s:\n\t\t\treturn i\n\treturn m + 1\n\ndef in_bound(x, y):\n\treturn x >= 0 and x < MAX and (y >= 0) and (y < MAX)\nfor i in range(2 * MAX - 1):\n\tfor j in range(i + 1):\n\t\tif not in_bound(i - j, j):\n\t\t\tcontinue\n\t\tif i - j <= 1 and j <= 1:\n\t\t\tgrundy[i - j][j] = 0\n\t\telse:\n\t\t\ts = set()\n\t\t\tfor (x, y) in moves:\n\t\t\t\tif in_bound(i - j + x, j + y):\n\t\t\t\t\ts.add(grundy[i - j + x][j + y])\n\t\t\tgrundy[i - j][j] = mex(s)\nfor _ in range(t):\n\tn = int(input())\n\tl = []\n\tfor i in range(n):\n\t\tl.append([int(k) for k in input().split()])\n\tl = [grundy[i - 1][j - 1] for (i, j) in l]\n\ttemp = reduce(lambda x, y: x ^ y, l)\n\tif temp == 0:\n\t\tprint('Second')\n\telse:\n\t\tprint('First')\n", "from functools import reduce\nS = 15\nz = [[0 for _ in range(S)] for _ in range(S)]\n\ndef h(x, y, a, b):\n\tk = x + a\n\tl = y + b\n\treturn z[k][l] if k >= 0 and l >= 0 and (k < S) and (l < S) else 5\nfor xy in range(S * S):\n\tfor x in range(S):\n\t\ty = xy - x\n\t\tif y >= 0 and y < S:\n\t\t\tp = [h(x, y, -2, -1), h(x, y, -2, 1), h(x, y, -1, -2), h(x, y, 1, -2)]\n\t\t\tp.sort()\n\t\t\tt = 0\n\t\t\tfor f in p:\n\t\t\t\tif f == t:\n\t\t\t\t\tt += 1\n\t\t\tz[x][y] = t\nfor _ in range(int(input())):\n\tw = reduce(lambda a, b: a ^ b, (z[g][h] for (g, h) in ((int(x) - 1 for x in input().strip().split()) for _ in range(int(input())))))\n\tprint('First' if w != 0 else 'Second')\n", "import sys\ndic = {}\n\ndef call(x, y):\n\tif x < 1 or y < 1 or x > 15 or (y > 15):\n\t\treturn -1\n\tif (x, y) in dic:\n\t\treturn dic[x, y]\n\ts = []\n\ts.append(call(x - 1, y - 2))\n\ts.append(call(x + 1, y - 2))\n\ts.append(call(x - 2, y + 1))\n\ts.append(call(x - 2, y - 1))\n\ti = 0\n\twhile True:\n\t\tif i not in s:\n\t\t\tdic[x, y] = i\n\t\t\treturn i\n\t\ti = i + 1\nt = int(input())\na = []\nfor _ in range(t):\n\tk = int(input())\n\txorsum = 0\n\tfor _ in range(k):\n\t\t(x, y) = map(int, input().split())\n\t\txorsum = xorsum ^ call(x, y)\n\tif xorsum:\n\t\ta.append('First')\n\telse:\n\t\ta.append('Second')\nfor i in range(len(a)):\n\tprint(a[i])\n", "from functools import reduce\nfrom operator import xor\ngnum = [[-1] * 17 for _ in range(17)]\nfor s in range(2, 31):\n\tfor j in range(max(1, s - 15), min(16, s)):\n\t\ti = s - j\n\t\ttarget = ((i - 1, j - 2), (i + 1, j - 2), (i - 2, j - 1), (i - 2, j + 1))\n\t\tnextval = {gnum[x][y] for (x, y) in target}\n\t\tgnum[i][j] = next((i for i in range(100) if i not in nextval))\nfor _ in range(int(input())):\n\tprint('First' if reduce(xor, (gnum[x][y] for (x, y) in (map(int, input().split()) for _ in range(int(input())))), 0) else 'Second')\n", "memo = dict()\nmoves = [(-2, 1), (-2, -1), (1, -2), (-1, -2)]\n\ndef mex(values):\n\tmax_val = max(values)\n\treturn min(frozenset(range(max_val + 2)).difference(values))\n\ndef grundy(x, y):\n\tif x <= 0 or y <= 0 or x > 15 or (y > 15):\n\t\treturn 10000\n\tkey = (x, y)\n\tif key not in memo:\n\t\tmemo[key] = mex([grundy(x + dx, y + dy) for (dx, dy) in moves])\n\treturn memo[key]\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\ttokens = []\n\tfor _ in range(n):\n\t\ttokens.append(tuple(map(int, input().split())))\n\tresult = 0\n\tfor (x, y) in tokens:\n\t\tresult ^= grundy(x, y)\n\tprint('First' if result > 0 else 'Second')\n", "mp = []\nfor i in range(15):\n\tmp.append([-1] * 15)\ndir = [[-2, 1], [-2, -1], [1, -2], [-1, -2]]\n\ndef dfs(x, y):\n\tif mp[x][y] != -1:\n\t\treturn mp[x][y]\n\tf = [False] * 101\n\tfor i in range(4):\n\t\tex = x + dir[i][0]\n\t\tey = y + dir[i][1]\n\t\tif ex < 0 or ey < 0 or ex >= 15 or (ey >= 15):\n\t\t\tcontinue\n\t\tf[dfs(ex, ey)] = True\n\tfor i in range(101):\n\t\tif not f[i]:\n\t\t\tbreak\n\tmp[x][y] = i\n\treturn i\nfor _ in range(int(input().strip())):\n\ts = 0\n\tfor i in range(int(input().strip())):\n\t\t[x, y] = map(int, input().strip().split())\n\t\ts ^= dfs(x - 1, y - 1)\n\tif s == 0:\n\t\tprint('Second')\n\telse:\n\t\tprint('First')\n", "def setGrundy(matrix, x, y):\n\ts = set()\n\tif inBoard(x - 2, y - 1):\n\t\ts.add(matrix[x - 2][y - 1])\n\tif inBoard(x - 2, y + 1):\n\t\ts.add(matrix[x - 2][y + 1])\n\tif inBoard(x - 1, y - 2):\n\t\ts.add(matrix[x - 1][y - 2])\n\tif inBoard(x + 1, y - 2):\n\t\ts.add(matrix[x + 1][y - 2])\n\tret = 0\n\twhile ret in s:\n\t\tret += 1\n\tmatrix[x][y] = ret\n\ndef inBoard(x, y):\n\treturn x >= 1 and y >= 1 and (x <= 15) and (y <= 15)\n\ndef populate(matrix):\n\tn = len(matrix) - 1\n\tfor i in range(2, n + 2):\n\t\tfor j in range(1, i):\n\t\t\tsetGrundy(matrix, j, i - j)\n\tfor i in range(n + 2, 2 * n + 1):\n\t\tfor j in range(i - n, n + 1):\n\t\t\tsetGrundy(matrix, j, i - j)\ngrundyMatrix = [[0] * 16 for _ in range(16)]\npopulate(grundyMatrix)\nT = int(input())\nfor _ in range(T):\n\tk = int(input())\n\tres = 0\n\tfor i in range(k):\n\t\t(x, y) = map(int, input().split())\n\t\tres ^= grundyMatrix[x][y]\n\tprint('Second' if res == 0 else 'First')\n", "from operator import xor\nfrom functools import lru_cache, reduce\nSIZE = 15\nMOVES = ((1, -2), (-1, -2), (-2, -1), (-2, 1))\n\ndef mex(it):\n\ts = set(it)\n\tfor i in range(len(s) + 1):\n\t\tif i not in s:\n\t\t\treturn i\n\ndef on_board(y, x):\n\treturn 0 <= y < SIZE and 0 <= x < SIZE\n\n@lru_cache(None)\ndef grundy(y, x):\n\ttargets = ((y + dy, x + dx) for (dy, dx) in MOVES)\n\treturn mex((grundy(ty, tx) for (ty, tx) in targets if on_board(ty, tx)))\nfor _ in range(int(input())):\n\tcoords = ((int(x) - 1 for x in input().split()) for _ in range(int(input())))\n\tprint('First' if reduce(xor, (grundy(y, x) for (x, y) in coords)) else 'Second')\n", "def findGrundy(x, y, n, array):\n\tres = 0\n\ttmpArray = []\n\tif x > 1:\n\t\tif y > 0:\n\t\t\ttmpArray.append(array[x - 2][y - 1])\n\t\tif y < n - 1:\n\t\t\ttmpArray.append(array[x - 2][y + 1])\n\tif y > 1:\n\t\tif x > 0:\n\t\t\ttmpArray.append(array[x - 1][y - 2])\n\t\tif x < n - 1:\n\t\t\ttmpArray.append(array[x + 1][y - 2])\n\twhile res in tmpArray:\n\t\tres += 1\n\treturn res\n\ndef buildBoard(n):\n\tarray = []\n\tfor k in range(2 * n - 1):\n\t\tif k < n:\n\t\t\tarray.append([])\n\t\t\tfor i in range(k + 1):\n\t\t\t\ttmp = findGrundy(i, k - i, n, array)\n\t\t\t\tarray[i].append(tmp)\n\t\telse:\n\t\t\tfor i in range(k + 1 - n, n):\n\t\t\t\ttmp = findGrundy(i, k - i, n, array)\n\t\t\t\tarray[i].append(tmp)\n\treturn array\nT = int(input().strip())\nfor i in range(T):\n\tk = int(input().strip())\n\tres = 0\n\tarray = buildBoard(15)\n\tfor j in range(k):\n\t\tpos = [int(x) for x in input().split()]\n\t\tgrundy = array[pos[0] - 1][pos[1] - 1]\n\t\tres ^= grundy\n\tif res == 0:\n\t\tprint('Second')\n\telse:\n\t\tprint('First')\n", "board = {}\nmoves = [(-1, -2), (+1, -2), (-2, -1), (-2, +1)]\n\ndef calc_moves(n, m):\n\tif n < 1 or n > 15 or m < 1 or (m > 15):\n\t\treturn -1\n\telif (n, m) in board:\n\t\treturn board[n, m]\n\tscore = []\n\tfor move in moves:\n\t\tscore.append(calc_moves(n + move[0], m + move[1]))\n\tboard[n, m] = mex(score)\n\treturn board[n, m]\n\ndef mex(s):\n\ti = 0\n\twhile True:\n\t\tif i not in s:\n\t\t\treturn i\n\t\ti += 1\n\ndef print_board(board):\n\tfor j in range(1, 16):\n\t\tfor i in range(1, 16):\n\t\t\tif (i, j) not in board:\n\t\t\t\tcalc_moves(i, j)\n\t\tprint('{0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14}'.format(board[1, j], board[2, j], board[3, j], board[4, j], board[5, j], board[6, j], board[7, j], board[8, j], board[9, j], board[10, j], board[11, j], board[12, j], board[13, j], board[14, j], board[15, j]))\nT = int(input().strip())\nfor i in range(T):\n\tk = int(input().strip())\n\tscore = 0\n\tfor j in range(k):\n\t\t(n, m) = [int(temp) for temp in input().strip().split(' ')]\n\t\tscore ^= calc_moves(n, m)\n\tif score == 0:\n\t\tprint('Second')\n\telse:\n\t\tprint('First')\n", "board = [[-1] * 15 for i in range(15)]\npool = [(i, j) for i in range(15) for j in range(15)]\nfor i in range(2):\n\tfor j in range(2):\n\t\tboard[i][j] = 0\n\t\tpool.remove((i, j))\nwhile pool:\n\tfor (x, y) in list(pool):\n\t\tothers = set()\n\t\tfor (p, q) in [(x - 2, y - 1), (x - 2, y + 1), (x - 1, y - 2), (x + 1, y - 2)]:\n\t\t\tif 0 <= p < 15 and 0 <= q < 15:\n\t\t\t\tothers.add(board[p][q])\n\t\tif -1 not in others:\n\t\t\tfor t in range(max(others) + 2):\n\t\t\t\tif t not in others:\n\t\t\t\t\tboard[x][y] = t\n\t\t\t\t\tpool.remove((x, y))\n\t\t\t\t\tbreak\n\t\t\tbreak\nfor t in range(int(input().strip())):\n\tnim = 0\n\tfor k in range(int(input().strip())):\n\t\t(x, y) = map(lambda t: int(t) - 1, input().strip().split())\n\t\tnim ^= board[x][y]\n\tprint('First' if nim > 0 else 'Second')\n", "def chess(x, y):\n\tif 0 <= x < 15 > y >= 0:\n\t\tif G[x][y] == -1:\n\t\t\ts = {chess(x - 2, y + 1), chess(x - 2, y - 1), chess(x - 1, y - 2), chess(x + 1, y - 2)}\n\t\t\ti = 0\n\t\t\twhile i in s:\n\t\t\t\ti += 1\n\t\t\tG[x][y] = i\n\t\treturn G[x][y]\n\treturn -1\nG = [[-1] * 15 for i in range(15)]\nfor i in range(2):\n\tfor j in range(2):\n\t\tG[i][j] = 0\nfor i in range(15):\n\tfor j in range(15):\n\t\tG[i][j] = chess(i, j)\nfor i in range(int(input())):\n\tans = 0\n\tfor j in range(int(input())):\n\t\t(x, y) = map(int, input().split())\n\t\tans ^= G[x - 1][y - 1]\n\tif ans == 0:\n\t\tprint('Second')\n\telse:\n\t\tprint('First')\n", "from collections import defaultdict\nfrom functools import lru_cache\nfrom functools import reduce\nfrom operator import xor\ndy = [-2, -2, 1, -1]\ndx = [1, -1, -2, -2]\n\ndef inside(y: int, x: int, H: int, W: int) -> bool:\n\treturn 1 <= y <= H and 1 <= x <= W\n\n@lru_cache(10000)\ndef grundy(y, x):\n\tif not inside(y, x, 15, 15):\n\t\treturn -1\n\ts = set((grundy(x + dx[i], y + dy[i]) for i in range(4)))\n\tres = 0\n\twhile res in s:\n\t\tres += 1\n\treturn res\n\ndef main():\n\tT = int(input())\n\tfor i in range(T):\n\t\tk = int(input())\n\t\tgrundy_list = []\n\t\tfor j in range(k):\n\t\t\t(x, y) = map(int, input().split())\n\t\t\tgrundy_list.append(grundy(y, x))\n\t\tprint('First' if reduce(xor, grundy_list) != 0 else 'Second')\nmain()\n", "visited = [[0 for i in range(15)] for i in range(15)]\ngrundy = [[0 for i in range(15)] for i in range(15)]\n\ndef find_grundy(i, j):\n\tif i < 0 or j < 0 or i >= 15 or (j >= 15):\n\t\treturn None\n\tif visited[i][j]:\n\t\treturn grundy[i][j]\n\tvisited[i][j] = 1\n\ts = set()\n\tif find_grundy(i - 2, j + 1) != None:\n\t\ts.add(find_grundy(i - 2, j + 1))\n\tif find_grundy(i - 2, j - 1) != None:\n\t\ts.add(find_grundy(i - 2, j - 1))\n\tif find_grundy(i + 1, j - 2) != None:\n\t\ts.add(find_grundy(i + 1, j - 2))\n\tif find_grundy(i - 1, j - 2) != None:\n\t\ts.add(find_grundy(i - 1, j - 2))\n\tm = 0\n\twhile m in s:\n\t\tm += 1\n\tgrundy[i][j] = m\n\treturn m\nfor t in range(int(input())):\n\tcoins = []\n\tfor k in range(int(input())):\n\t\tcoins.append(map(lambda x: int(x) - 1, input().split()))\n\ttotal = 0\n\tfor c in coins:\n\t\ttotal ^= find_grundy(*c)\n\tprint('First' if total else 'Second')\n", "M = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1], [0, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1], [0, 1, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 1], [0, 1, 1, 2, 1, 4, 3, 2, 3, 3, 3, 2, 3, 3, 3, 1], [0, 0, 0, 3, 4, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1], [0, 0, 0, 2, 3, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 1], [0, 1, 1, 2, 2, 1, 2, 2, 2, 3, 2, 2, 2, 3, 2, 1], [0, 1, 1, 2, 3, 1, 1, 2, 1, 4, 3, 2, 3, 3, 3, 1], [0, 0, 0, 3, 3, 0, 0, 3, 4, 0, 0, 1, 1, 0, 0, 1], [0, 0, 0, 2, 3, 0, 0, 2, 3, 0, 0, 2, 1, 0, 0, 1], [0, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 2, 2, 3, 2, 1], [0, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 4, 3, 1], [0, 0, 0, 3, 3, 0, 0, 3, 3, 0, 0, 3, 4, 0, 0, 1], [0, 0, 0, 2, 3, 0, 0, 2, 3, 0, 0, 2, 3, 0, 0, 2], [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1]]\nn = int(input().strip())\nfor i in range(n):\n\tk = int(input().strip())\n\tx = 0\n\tfor j in range(k):\n\t\t(r, c) = [int(x) for x in input().split()]\n\t\tx ^= M[r][c]\n\tprint('Second' if x == 0 else 'First')\n", "MOVES = [[-2, 1], [-2, -1], [-1, -2], [1, -2]]\n\ndef inrange(x, y):\n\tif x >= 0 and x < 15 and (y >= 0) and (y < 15):\n\t\treturn True\n\treturn False\n\ndef checkPosition(c_b, x, y, MOVES):\n\ts = set()\n\tfor moves in MOVES:\n\t\tcurr_x = x + moves[0]\n\t\tcurr_y = y + moves[1]\n\t\tif inrange(curr_x, curr_y):\n\t\t\ts.add(c_b[curr_x][curr_y])\n\t\t\tif c_b[curr_x][curr_y] == -1:\n\t\t\t\tprint('encountered -1')\n\tres = 0\n\twhile res in s:\n\t\tres += 1\n\treturn res\nCHESS_BOARD = [[-1] * 15 for _ in range(15)]\nMOVES = [[-2, 1], [-2, -1], [-1, -2], [1, -2]]\ny = 0\nwhile y <= 14:\n\ty_temp = y\n\tx = 0\n\twhile y_temp > -1:\n\t\tCHESS_BOARD[x][y_temp] = checkPosition(CHESS_BOARD, x, y_temp, MOVES)\n\t\tx += 1\n\t\ty_temp -= 1\n\ty += 1\nx = 1\nwhile x <= 14:\n\tx_temp = x\n\ty = 14\n\twhile x_temp < 15:\n\t\tCHESS_BOARD[x_temp][y] = checkPosition(CHESS_BOARD, x_temp, y, MOVES)\n\t\tx_temp += 1\n\t\ty -= 1\n\tx += 1\nfor _ in range(int(input().strip())):\n\tres = 0\n\tfor k in range(int(input().strip())):\n\t\t(x, y) = map(int, input().strip().split())\n\t\tx -= 1\n\t\ty -= 1\n\t\tres ^= CHESS_BOARD[x][y]\n\tif res == 0:\n\t\tprint('Second')\n\telse:\n\t\tprint('First')\n", "def parseInput(f):\n\treturn [f(x) for x in input().split()]\nmemo = {}\ndirs = [(-2, 1), (-2, -1), (1, -2), (-1, -2)]\n\ndef check(x, y):\n\treturn 1 <= x <= 15 and 1 <= y <= 15\n\ndef grundy(x, y):\n\tif (x, y) in memo:\n\t\treturn memo[x, y]\n\tmex = set()\n\tfor (dx, dy) in dirs:\n\t\t(nx, ny) = (x + dx, y + dy)\n\t\tif check(nx, ny):\n\t\t\tmex.add(grundy(nx, ny))\n\tanswer = 0\n\twhile answer in mex:\n\t\tanswer += 1\n\tmemo[x, y] = answer\n\treturn answer\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tanswer = 0\n\tfor i in range(n):\n\t\t(x, y) = parseInput(int)\n\t\tanswer ^= grundy(x, y)\n\tprint('First' if answer else 'Second')\n", "cache = [[0] * 16 for x in range(16)]\nmove = [(-2, 1), (-2, -1), (1, -2), (-1, -2)]\nc = 0\nfor z in range(1, 17):\n\tfor x in range(1, z):\n\t\ty = z - x\n\t\tfs = [False] * 17\n\t\tfor m in move:\n\t\t\tif x + m[0] > 0 and x + m[0] < 16 and (y + m[1] > 0) and (y + m[1] < 16):\n\t\t\t\tfs[cache[x + m[0]][y + m[1]]] = True\n\t\tmv = 0\n\t\twhile fs[mv]:\n\t\t\tmv += 1\n\t\tcache[x][y] = mv\nfor z in range(15, 1, -1):\n\tfor i in range(1, z):\n\t\tx = 16 - i\n\t\ty = 16 - z + i\n\t\tfs = [False] * 17\n\t\tfor m in move:\n\t\t\tif x + m[0] > 0 and x + m[0] < 16 and (y + m[1] > 0) and (y + m[1] < 16):\n\t\t\t\tfs[cache[x + m[0]][y + m[1]]] = True\n\t\tmv = 0\n\t\twhile fs[mv]:\n\t\t\tmv += 1\n\t\tcache[x][y] = mv\n\ndef getMex(x, y):\n\treturn cache[x][y]\nimport functools\nfor _ in range(int(input())):\n\txs = 0\n\tfor s in range(int(input())):\n\t\txs ^= getMex(*map(int, input().split(' ')))\n\tprint('First' if xs else 'Second')\n", "import sys\nfrom time import time\ncache = dict()\n\ndef nimber(coord):\n\tif coord in cache:\n\t\treturn cache[coord]\n\tnn = set()\n\tfor (dr, dc) in ((-2, 1), (-2, -1), (1, -2), (-1, -2)):\n\t\t(r, c) = (coord[0] + dr, coord[1] + dc)\n\t\tif not (r < 1 or r > 15 or c < 1 or (c > 15)):\n\t\t\tnn.add(nimber((r, c)))\n\trval = 0\n\twhile rval in nn:\n\t\trval += 1\n\tcache[coord] = rval\n\treturn rval\n\ndef solve(bb):\n\trval = 0\n\tfor coord in bb:\n\t\trval ^= nimber(coord)\n\treturn rval > 0\ntm = time()\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tbb = []\n\tfor _ in range(n):\n\t\t(r, c) = map(int, input().split())\n\t\tbb.append((r, c))\n\tif solve(bb):\n\t\tprint('First')\n\telse:\n\t\tprint('Second')\nprint('time elapsed: %s' % (time() - tm,), file=sys.stderr)\n", "nimber = [[0] * 15 for _ in range(15)]\nfor s in range(29):\n\tfor i in range(max(0, s - 14), min(14, s) + 1):\n\t\tj = s - i\n\t\tex = set(range(5))\n\t\tfor (di, dj) in [(-2, 1), (-2, -1), (1, -2), (-1, -2)]:\n\t\t\tif 0 <= i + di < 15 and 0 <= j + dj < 15:\n\t\t\t\tex.discard(nimber[i + di][j + dj])\n\t\tnimber[i][j] = min(ex)\nfor _ in range(int(input())):\n\tnimsum = 0\n\tfor _ in range(int(input())):\n\t\t(x, y) = map(int, input().split())\n\t\tnimsum ^= nimber[x - 1][y - 1]\n\tprint(['First', 'Second'][nimsum == 0])\n", "N = 15\ng = [[0] * N for i in range(N)]\n\ndef mex(itr):\n\ts = set(list(itr))\n\ti = 0\n\twhile i in s:\n\t\ti += 1\n\treturn i\n\ndef options(i, j):\n\tddi = [1, -1, -2, -2]\n\tddj = [-2, -2, 1, -1]\n\tfor (di, dj) in zip(ddi, ddj):\n\t\tni = i + di\n\t\tnj = j + dj\n\t\tif ni >= 0 and ni < N and (nj >= 0) and (nj < N):\n\t\t\tyield g[ni][nj]\n\ndef work(i, j):\n\tg[i][j] = mex(options(i, j))\n\ndef work_diag(i, j):\n\tif i < 0 or j >= N:\n\t\treturn\n\twork(i, j)\n\twork_diag(i - 1, j + 1)\nfor i in range(N):\n\twork_diag(i, 0)\nfor j in range(1, N):\n\twork_diag(N - 1, j)\nfor _ in range(int(input())):\n\tC = int(input())\n\txor = 0\n\tfor _ in range(C):\n\t\t(x, y) = map(int, input().split())\n\t\tx -= 1\n\t\ty -= 1\n\t\txor ^= g[x][y]\n\tif xor:\n\t\tprint('First')\n\telse:\n\t\tprint('Second')\n", "from functools import lru_cache\n\ndef mex(X):\n\tx = 0\n\twhile x in X:\n\t\tx += 1\n\treturn x\nS = 15\n\n@lru_cache(maxsize=None)\ndef grundy(x, y):\n\tif x == y == 0:\n\t\treturn 0\n\tX = []\n\tfor (vx, vy) in ((x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)):\n\t\tif 0 <= vx < S and 0 <= vy < S:\n\t\t\tX.append(grundy(vx, vy))\n\treturn mex(X)\n\ndef main():\n\tT = int(input())\n\tfor _ in range(T):\n\t\tK = int(input())\n\t\tG = 0\n\t\tfor _ in range(K):\n\t\t\t(x, y) = map(int, input().split())\n\t\t\tG ^= grundy(x - 1, y - 1)\n\t\tprint('First' if G != 0 else 'Second')\nmain()\n", "grun = {}\n\ndef grundy(x, y):\n\tif 0 < x < 16 > y > 0:\n\t\tif (x, y) not in grun:\n\t\t\ta = {grundy(x - 2, y - 1), grundy(x - 2, y + 1), grundy(x - 1, y - 2), grundy(x + 1, y - 2)}\n\t\t\tk = 0\n\t\t\twhile k in a:\n\t\t\t\tk += 1\n\t\t\tgrun[x, y] = k\n\t\treturn grun[x, y]\n\treturn -1\nfor _ in range(int(input())):\n\tk = 0\n\tfor _ in range(int(input())):\n\t\tk ^= grundy(*map(int, input().split()))\n\tprint('First' if k else 'Second')\n", "def setGrundy(matrix, x, y):\n\ts = set()\n\tif inBoard(x - 2, y - 1):\n\t\ts.add(matrix[x - 2][y - 1])\n\tif inBoard(x - 2, y + 1):\n\t\ts.add(matrix[x - 2][y + 1])\n\tif inBoard(x - 1, y - 2):\n\t\ts.add(matrix[x - 1][y - 2])\n\tif inBoard(x + 1, y - 2):\n\t\ts.add(matrix[x + 1][y - 2])\n\tret = 0\n\twhile ret in s:\n\t\tret += 1\n\tmatrix[x][y] = ret\n\ndef inBoard(x, y):\n\treturn x >= 1 and y >= 1 and (x <= 15) and (y <= 15)\n\ndef populate(matrix):\n\tn = len(matrix) - 1\n\tfor i in range(2, n + 2):\n\t\tfor j in range(1, i):\n\t\t\tsetGrundy(matrix, j, i - j)\n\tfor i in range(n + 2, 2 * n + 1):\n\t\tfor j in range(i - n, n + 1):\n\t\t\tsetGrundy(matrix, j, i - j)\ngrundyMatrix = [[0] * 16 for _ in range(16)]\npopulate(grundyMatrix)\nT = int(input())\nfor _ in range(T):\n\tk = int(input())\n\tres = 0\n\tfor i in range(k):\n\t\t(x, y) = map(int, input().split())\n\t\tres ^= grundyMatrix[x][y]\n\tprint('Second' if res == 0 else 'First')\n", "import sys\ndic = {}\n\ndef call(x, y):\n\tif x < 1 or y < 1 or x > 15 or (y > 15):\n\t\treturn -1\n\tif (x, y) in dic:\n\t\treturn dic[x, y]\n\ts = []\n\ts.append(call(x - 1, y - 2))\n\ts.append(call(x + 1, y - 2))\n\ts.append(call(x - 2, y + 1))\n\ts.append(call(x - 2, y - 1))\n\ti = 0\n\twhile True:\n\t\tif i not in s:\n\t\t\tdic[x, y] = i\n\t\t\treturn i\n\t\ti = i + 1\nt = int(input())\na = []\nfor _ in range(t):\n\tk = int(input())\n\txorsum = 0\n\tfor _ in range(k):\n\t\t(x, y) = map(int, input().split())\n\t\txorsum = xorsum ^ call(x, y)\n\tif xorsum:\n\t\ta.append('First')\n\telse:\n\t\ta.append('Second')\nfor i in range(len(a)):\n\tprint(a[i])\n", "value = list()\nfor i in range(17):\n\tvalue.append([None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None])\n\ndef chess(a, b):\n\tif (a == 2 or a == 1) and (b == 1 or b == 2):\n\t\treturn 0\n\tif value[a][b] != None:\n\t\treturn value[a][b]\n\tlis = [[-1, -2], [1, -2], [-2, -1], [-2, 1]]\n\tpoi = list()\n\tfor i in range(4):\n\t\te = a + lis[i][0]\n\t\td = b + lis[i][1]\n\t\tif (e > 0 and e < 16) and (d > 0 and d < 16):\n\t\t\tpoi.append(chess(e, d))\n\tmex = 0\n\twhile True:\n\t\tif poi.count(mex) == 0:\n\t\t\tbreak\n\t\tmex += 1\n\tvalue[a][b] = mex\n\treturn mex\nresult = list()\nfor i in range(int(input())):\n\tg = 0\n\tfor j in range(int(input())):\n\t\tar = list(map(int, input().split()))\n\t\tg ^= chess(ar[0], ar[1])\n\tif g == 0:\n\t\tresult.append('Second')\n\telse:\n\t\tresult.append('First')\nprint('\\n'.join(result))\n", "import math\nimport os\nimport random\nimport re\nimport sys\ndic = {}\n\ndef grundy(x, y):\n\tif x < 1 or y < 1 or x > 15 or (y > 15):\n\t\treturn -1\n\tif (x, y) in dic:\n\t\treturn dic[x, y]\n\ts = []\n\ts.append(grundy(x - 1, y - 2))\n\ts.append(grundy(x + 1, y - 2))\n\ts.append(grundy(x - 2, y + 1))\n\ts.append(grundy(x - 2, y - 1))\n\ti = 0\n\twhile True:\n\t\tif i not in s:\n\t\t\tdic[x, y] = i\n\t\t\treturn i\n\t\ti = i + 1\nt = int(input())\nfor _ in range(t):\n\tk = int(input())\n\ta = []\n\tv = 0\n\tfor i in range(k):\n\t\t(x, y) = map(int, input().split())\n\t\tv = v ^ grundy(x, y)\n\tif v:\n\t\tprint('First')\n\telse:\n\t\tprint('Second')\n", "grundy = [[-1] * 15 for _ in range(15)]\ngrundy[0][0] = grundy[0][1] = grundy[1][0] = grundy[1][1] = 0\n\ndef moveCoin(x, y):\n\tif x > 1:\n\t\tif y > 0:\n\t\t\tyield (x - 2, y - 1)\n\t\tif y < 14:\n\t\t\tyield (x - 2, y + 1)\n\tif y > 1:\n\t\tif x > 0:\n\t\t\tyield (x - 1, y - 2)\n\t\tif x < 14:\n\t\t\tyield (x + 1, y - 2)\n\ndef getGrundy(x, y):\n\tif grundy[x][y] != -1:\n\t\treturn grundy[x][y]\n\ts = set()\n\tfor (i, j) in moveCoin(x, y):\n\t\ts.add(getGrundy(i, j))\n\tmex = 0\n\twhile mex in s:\n\t\tmex += 1\n\tgrundy[x][y] = mex\n\treturn mex\nfor _ in range(int(input())):\n\tk = int(input())\n\tcoins = [[0] * 15 for _ in range(15)]\n\tfor _ in range(k):\n\t\t(i, j) = [int(x) - 1 for x in input().split(' ')]\n\t\tcoins[i][j] = 1 - coins[i][j]\n\tres = 0\n\tfor i in range(15):\n\t\tfor j in range(15):\n\t\t\tif coins[i][j]:\n\t\t\t\tres ^= getGrundy(i, j)\n\tprint('First' if res else 'Second')\n"]

difficulty: MEDIUM

source: hacker rank

question:
Two players are playing a game on a $15\times15$ chessboard. The rules of the game are as follows:

The game starts with $\boldsymbol{\mbox{k}}$ coins located at one or more $(x,y)$ coordinates on the board (a single cell may contain more than one coin). The coordinate of the upper left cell is $(1,1)$, and the coordinate of the lower right cell is $(15,15)$.

In each move, a player must move a single coin from some cell $(x,y)$ to one of the following locations:

$(x-2,y+1)$
$(x-2,y-1)$
$(x+1,y-2)$
$(x-1,y-2)$.

Note: The coin must remain inside the confines of the board.

The players move in alternating turns. The first player who is unable to make a move loses the game.

The figure below shows all four possible moves:

![image](1.png)
Note: While the figure shows a $8\times8$ board, this game is played on a $15\times15$ board.

Given the value of $\boldsymbol{\mbox{k}}$ and the initial coordinate(s) of $\boldsymbol{\mbox{k}}$ coins, determine which player will win the game. Assume both players always move optimally.

Input Format

The first line contains an integer, $\mathbf{T}$, denoting the number of test cases.

Each test case is defined as follows over the subsequent lines:

The first line contains an integer, $\boldsymbol{\mbox{k}}$, denoting the number of coins on the board.
Each line $\boldsymbol{i}$ (where $0\leq i<k$) of the $\boldsymbol{\mbox{k}}$ subsequent lines contains $2$ space-separated integers describing the respective values of $x_i$ and $y_i$ of the coordinate where coin $k_i$ is located.

Note: Recall that a cell can have more than one coin (i.e., any cell can have $0$ to $\boldsymbol{\mbox{k}}$ coins in it at any given time).

Constraints

$1\leq T\leq1000$
$1\leq k\leq1000$
$1\leq x_i,y_i\leq15$, where $0\leq i<k$.

Output Format

On a new line for each test case, print $\textbf{First}$ if the first player is the winner; otherwise, print $\textbf{Second}$.

Sample Input
2
3
5 4
5 8
8 2
6
7 1
7 2
7 3
7 4
7 4
7 4

Sample Output
First
Second

data_split: test


I. Say Hello

problem_index: I

time_limit: 2 seconds

memory_limit: 256 megabytes

note: ![image](images/cf_1046_I/1.png) Explanation: Friends should send signals 2 times to each other, first time around point $$$A2$$$ and $$$B2$$$ and second time during A's travel from point $$$A3$$$ to $$$A4$$$ while B stays in point $$$B3=B4$$$.

solutions: ["from sys import stdin\nstdin = iter(stdin)\n\nclass Vector:\n\n\tdef __init__(self, x, y):\n\t\tself.x = x\n\t\tself.y = y\n\n\tdef __sub__(self, other):\n\t\treturn Vector(self.x - other.x, self.y - other.y)\n\n\tdef __add__(self, other):\n\t\treturn Vector(self.x + other.x, self.y + other.y)\n\n\tdef dot(self, vec2):\n\t\treturn self.x * vec2.x + self.y * vec2.y\n\n\tdef cross(self, vec2):\n\t\treturn self.x * vec2.y - self.y * vec2.x\n\n\tdef norm_square(self):\n\t\treturn self.dot(self)\n\n\tdef __str__(self):\n\t\treturn str((self.x, self.y))\n\t__radd__ = __add__\n\t__rsub__ = __sub__\n\ndef min_distnace_less_than_d1(ab1: Vector, ab2: Vector, d1: int):\n\tL = ab2 - ab1\n\tproj1 = ab1.dot(L)\n\tproj2 = ab2.dot(L)\n\tbetween = proj1 * proj2 < 0\n\tif between:\n\t\treturn ab1.cross(L) ** 2 <= d1 ** 2 * L.norm_square()\n\telse:\n\t\tminSquare = min([ab1.norm_square(), ab2.norm_square()])\n\t\treturn minSquare <= d1 ** 2\nN = int(next(stdin))\n(d1, d2) = (int(x) for x in next(stdin).split())\nABs = []\nfor _ in range(N):\n\t(Ax, Ay, Bx, By) = (int(x) for x in next(stdin).split())\n\tABs.append(Vector(Bx, By) - Vector(Ax, Ay))\nresetState = True\ncount = 0\nfor i in range(len(ABs) - 1):\n\t(ab1, ab2) = ABs[i:i + 2]\n\tif resetState and min_distnace_less_than_d1(ab1, ab2, d1):\n\t\tcount += 1\n\t\tresetState = False\n\tresetState = resetState or ab2.norm_square() > d2 ** 2\nprint(count)\n"]

difficulty: HARD

source: codeforces

raw_problem:
I. Say Hello

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Two friends are travelling through Bubble galaxy. They say "Hello!" via signals to each other if their distance is smaller or equal than $$$d_1$$$ and

 it's the first time they speak to each other or

 at some point in time after their last talk their distance was greater than $$$d_2$$$.

We need to calculate how many times friends said "Hello!" to each other. For $$$N$$$ moments, you'll have an array of points for each friend representing their positions at that moment. A person can stay in the same position between two moments in time, but if a person made a move we assume this movement as movement with constant speed in constant direction.

Input

The first line contains one integer number $$$N$$$ ($$$2 \leq N \leq 100\,000$$$) representing number of moments in which we captured positions for two friends.

The second line contains two integer numbers $$$d_1$$$ and $$$d_2 \ (0 < d_1 < d_2 < 1000)$$$.

The next $$$N$$$ lines contains four integer numbers $$$A_x,A_y,B_x,B_y$$$ ($$$0 \leq A_x, A_y, B_x, B_y \leq 1000$$$) representing coordinates of friends A and B in each captured moment.

Output

Output contains one integer number that represents how many times friends will say "Hello!" to each other.

Example

Input

4
2 5
0 0 0 10
5 5 5 6
5 0 10 5
14 7 10 5

Output

2

Note

 Explanation: Friends should send signals 2 times to each other, first time around point $$$A2$$$ and $$$B2$$$ and second time during A's travel from point $$$A3$$$ to $$$A4$$$ while B stays in point $$$B3=B4$$$.

question:
Two friends are travelling through Bubble galaxy. They say "Hello!" via signals to each other if their distance is smaller or equal than $$$d_1$$$ and
 -  it's the first time they speak to each other or  -  at some point in time after their last talk their distance was greater than $$$d_2$$$. We need to calculate how many times friends said "Hello!" to each other. For $$$N$$$ moments, you'll have an array of points for each friend representing their positions at that moment. A person can stay in the same position between two moments in time, but if a person made a move we assume this movement as movement with constant speed in constant direction.

Input
The first line contains one integer number $$$N$$$ ($$$2 \leq N \leq 100\,000$$$) representing number of moments in which we captured positions for two friends.
The second line contains two integer numbers $$$d_1$$$ and $$$d_2 \ (0 < d_1 < d_2 < 1000)$$$.
The next $$$N$$$ lines contains four integer numbers $$$A_x,A_y,B_x,B_y$$$ ($$$0 \leq A_x, A_y, B_x, B_y \leq 1000$$$) representing coordinates of friends A and B in each captured moment.

Output
Output contains one integer number that represents how many times friends will say "Hello!" to each other.

Example
Input
4
2 5
0 0 0 10
5 5 5 6
5 0 10 5
14 7 10 5

Output
2

Note
![image](1.png) Explanation: Friends should send signals 2 times to each other, first time around point $$$A2$$$ and $$$B2$$$ and second time during A's travel from point $$$A3$$$ to $$$A4$$$ while B stays in point $$$B3=B4$$$.

data_split: test


E1. A Story of One Country (Easy)

time_limit: 4 seconds

memory_limit: 512 megabytes

note:
The castles in the first and second examples are shown on the pictures below.
![image](images/cf_1181_E1/2.png)   ![image](images/cf_1181_E1/3.png)

source: codeforces

raw_problem:
E1. A Story of One Country (Easy)

time limit per test
4 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

This problem differs from the next problem only in constraints.

Petya decided to visit Byteland during the summer holidays. It turned out that the history of this country is quite unusual.

Initially, there were $$$n$$$ different countries on the land that is now Berland. Each country had its own territory that was represented as a rectangle on the map. The sides of the rectangle were parallel to the axes, and the corners were located at points with integer coordinates. Territories of no two countries intersected, but it was possible that some territories touched each other. As time passed, sometimes two countries merged into one. It only happened if the union of their territories was also a rectangle. In the end only one country remained — Byteland.

Initially, each country had a rectangular castle inside its territory. Its sides were parallel to the axes and its corners had integer coordinates. Some castles might touch the border of the corresponding country and sides or other castles. Miraculously, after all the unions the castles are still intact. Unfortunately, their locations are the only information we have to restore the initial territories of the countries.
  The possible formation of Byteland. The castles are shown in blue.
Petya wonders why no information about the initial countries remained. He suspected that the whole story is a fake. You were recommended to him as a smart person. Please check whether or not there exists a possible set of initial territories that could make the story true.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of countries and castles.

Each of the next $$$n$$$ lines contains four integers $$$a_i, b_i, c_i, d_i$$$ ($$$0 \leq a_i < c_i \leq 10^9$$$, $$$0 \leq b_i < d_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th castle, where $$$(a_i, b_i)$$$ are the coordinates of the lower left corner and $$$(c_i, d_i)$$$ are the coordinates of the upper right corner.

It is guaranteed, that no two castles intersect, however, they may touch.

Output

If there exists a possible set of territories that satisfies the story, print "YES", otherwise print "NO".

You can print each letter in any case (upper or lower).

Examples

Input

4
0 0 1 2
0 2 1 3
1 0 2 1
1 1 2 3

Output

YES

Input

4
0 0 2 1
1 2 3 3
2 0 3 2
0 1 1 3

Output

NO

Note

The castles in the first and second examples are shown on the pictures below.

question:
This problem differs from the next problem only in constraints.
Petya decided to visit Byteland during the summer holidays. It turned out that the history of this country is quite unusual.
Initially, there were $$$n$$$ different countries on the land that is now Berland. Each country had its own territory that was represented as a rectangle on the map. The sides of the rectangle were parallel to the axes, and the corners were located at points with integer coordinates. Territories of no two countries intersected, but it was possible that some territories touched each other. As time passed, sometimes two countries merged into one. It only happened if the union of their territories was also a rectangle. In the end only one country remained — Byteland.
Initially, each country had a rectangular castle inside its territory. Its sides were parallel to the axes and its corners had integer coordinates. Some castles might touch the border of the corresponding country and sides or other castles. Miraculously, after all the unions the castles are still intact. Unfortunately, their locations are the only information we have to restore the initial territories of the countries.
 ![image](1.png) The possible formation of Byteland. The castles are shown in blue. Petya wonders why no information about the initial countries remained. He suspected that the whole story is a fake. You were recommended to him as a smart person. Please check whether or not there exists a possible set of initial territories that could make the story true.

Input
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of countries and castles.
Each of the next $$$n$$$ lines contains four integers $$$a_i, b_i, c_i, d_i$$$ ($$$0 \leq a_i < c_i \leq 10^9$$$, $$$0 \leq b_i < d_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th castle, where $$$(a_i, b_i)$$$ are the coordinates of the lower left corner and $$$(c_i, d_i)$$$ are the coordinates of the upper right corner.
It is guaranteed, that no two castles intersect, however, they may touch.

Output
If there exists a possible set of territories that satisfies the story, print "YES", otherwise print "NO".
You can print each letter in any case (upper or lower).

Examples
Input
4
0 0 1 2
0 2 1 3
1 0 2 1
1 1 2 3

Output
YES

Input
4
0 0 2 1
1 2 3 3
2 0 3 2
0 1 1 3

Output
NO

Note
The castles in the first and second examples are shown on the pictures below.
 ![image](2.png)   ![image](3.png)

image_tags: Map Map Map

data_split: test