F. Almost Permutation

problem_index: F

time_limit: 3 seconds

memory_limit: 512 megabytes

solutions: ["import sys\n\ndef is_feasible(cnt, L, R):\n\tn = len(R)\n\tinter = [(L[i], R[i]) for i in range(n)]\n\tright = []\n\tfeasible = True\n\tfor x in range(n):\n\t\tfor p in inter:\n\t\t\tif p[0] == x:\n\t\t\t\tright.append(p[1])\n\t\twhile right and min(right) < x:\n\t\t\tright.remove(min(right))\n\t\tfor quantity in range(cnt[x]):\n\t\t\tif right:\n\t\t\t\tright.remove(min(right))\n\t\t\telse:\n\t\t\t\tfeasible = False\n\treturn feasible\n(n, q) = list(map(int, sys.stdin.readline().split()))\nL = [0 for i in range(n)]\nR = [n - 1 for i in range(n)]\nfor restriction in range(q):\n\t(t, l, r, v) = list(map(int, sys.stdin.readline().split()))\n\tif t == 1:\n\t\tfor k in range(l - 1, r):\n\t\t\tL[k] = max(L[k], v - 1)\n\telse:\n\t\tfor k in range(l - 1, r):\n\t\t\tR[k] = min(R[k], v - 1)\nis_possible = all(map(lambda x, y: x <= y, L, R))\nif not is_possible:\n\tprint(-1)\nelse:\n\tcnt = {x: L.count(x) for x in range(n)}\n\thad_pair = True\n\twhile had_pair:\n\t\thad_pair = False\n\t\tfor x in range(n):\n\t\t\tfor y in range(n):\n\t\t\t\tif cnt[x] > cnt[y] + 1:\n\t\t\t\t\tcnt[x] -= 1\n\t\t\t\t\tcnt[y] += 1\n\t\t\t\t\thas_pair = True\n\t\t\t\t\tif not is_feasible(cnt, L, R):\n\t\t\t\t\t\tcnt[x] += 1\n\t\t\t\t\t\tcnt[y] -= 1\n\t\t\t\t\t\thas_pair = False\n\t\t\t\t\thad_pair = had_pair or has_pair\n\tans = sum([cnt[x] * cnt[x] for x in range(n)])\n\tprint(ans)\n", "import sys\nreadline = sys.stdin.readline\nfrom heapq import heappop as hpp, heappush as hp\n\nclass MinCostFlowwithDijkstra:\n\tINF = 1 << 60\n\n\tdef __init__(self, N):\n\t\tself.N = N\n\t\tself.Edge = [[] for _ in range(N)]\n\n\tdef add_edge(self, st, en, cap, cost):\n\t\tself.Edge[st].append([en, cap, cost, len(self.Edge[en])])\n\t\tself.Edge[en].append([st, 0, -cost, len(self.Edge[st]) - 1])\n\n\tdef get_mf(self, so, si, fl):\n\t\tN = self.N\n\t\tINF = self.INF\n\t\tres = 0\n\t\tPot = [0] * N\n\t\tgeta = N\n\t\tprv = [None] * N\n\t\tprenum = [None] * N\n\t\twhile fl:\n\t\t\tdist = [INF] * N\n\t\t\tdist[so] = 0\n\t\t\tQ = [so]\n\t\t\twhile Q:\n\t\t\t\t(cost, vn) = divmod(hpp(Q), geta)\n\t\t\t\tif dist[vn] < cost:\n\t\t\t\t\tcontinue\n\t\t\t\tfor enum in range(len(self.Edge[vn])):\n\t\t\t\t\t(vf, cap, cost, _) = self.Edge[vn][enum]\n\t\t\t\t\tcc = dist[vn] + cost - Pot[vn] + Pot[vf]\n\t\t\t\t\tif cap > 0 and dist[vf] > cc:\n\t\t\t\t\t\tdist[vf] = cc\n\t\t\t\t\t\tprv[vf] = vn\n\t\t\t\t\t\tprenum[vf] = enum\n\t\t\t\t\t\thp(Q, cc * geta + vf)\n\t\t\tif dist[si] == INF:\n\t\t\t\treturn -1\n\t\t\tfor i in range(N):\n\t\t\t\tPot[i] -= dist[i]\n\t\t\tcfl = fl\n\t\t\tvf = si\n\t\t\twhile vf != so:\n\t\t\t\tcfl = min(cfl, self.Edge[prv[vf]][prenum[vf]][1])\n\t\t\t\tvf = prv[vf]\n\t\t\tfl -= cfl\n\t\t\tres -= cfl * Pot[si]\n\t\t\tvf = si\n\t\t\twhile vf != so:\n\t\t\t\te = self.Edge[prv[vf]][prenum[vf]]\n\t\t\t\te[1] -= cfl\n\t\t\t\tself.Edge[vf][e[3]][1] += cfl\n\t\t\t\tvf = prv[vf]\n\t\treturn res\n(N, Q) = list(map(int, readline().split()))\nT = MinCostFlowwithDijkstra(2 * N + 2)\ngeta = N\ncandi = [set(range(N)) for _ in range(N)]\nfor _ in range(Q):\n\t(t, l, r, v) = list(map(int, readline().split()))\n\tl -= 1\n\tr -= 1\n\tv -= 1\n\tif t == 1:\n\t\tfor vn in range(l, r + 1):\n\t\t\tfor i in range(v - 1, -1, -1):\n\t\t\t\tif i in candi[vn]:\n\t\t\t\t\tcandi[vn].remove(i)\n\telse:\n\t\tfor vn in range(l, r + 1):\n\t\t\tfor i in range(v + 1, N):\n\t\t\t\tif i in candi[vn]:\n\t\t\t\t\tcandi[vn].remove(i)\nif not all(candi):\n\tprint(-1)\nelse:\n\tsource = 2 * N\n\tsink = 2 * N + 1\n\tfor i in range(N):\n\t\tT.add_edge(source, i, 1, 0)\n\t\tfor v in candi[i]:\n\t\t\tT.add_edge(i, geta + v, 1, 0)\n\t\tfor j in range(N):\n\t\t\tT.add_edge(i + geta, sink, 1, 2 * j + 1)\n\tprint(T.get_mf(source, sink, N))\n", "from collections import deque\nfrom heapq import heappop, heappush\n\nclass Edge(object):\n\t__slots__ = ('x', 'y', 'cap', 'cost', 'inv')\n\n\tdef __repr__(self):\n\t\treturn f'{self.x}-->{self.y} ({self.cap} , {self.cost})'\n\nclass MCFP:\n\n\tdef __init__(self):\n\t\tself.G = []\n\n\tdef add(self, x, y, cap, cost):\n\t\tG = self.G\n\t\tG.extend(([] for i in range(max(0, max(x, y) + 1 - len(G)))))\n\t\te = Edge()\n\t\te.x = x\n\t\te.y = y\n\t\te.cap = cap\n\t\te.cost = cost\n\t\tz = Edge()\n\t\tz.x = y\n\t\tz.y = x\n\t\tz.cap = 0\n\t\tz.cost = -cost\n\t\te.inv = z\n\t\tz.inv = e\n\t\tG[x].append(e)\n\t\tG[y].append(z)\n\n\tdef solve(self, src, tgt, inf=float('inf')):\n\t\t(n, G) = (len(self.G), self.G)\n\t\tflowVal = flowCost = 0\n\t\tphi = [0] * n\n\t\tprev = [None] * n\n\t\tinQ = [0] * n\n\t\tcntQ = 1\n\t\tdist = [inf] * n\n\t\twhile 1:\n\t\t\tself.shortest(src, phi, prev, inQ, dist, inf, cntQ)\n\t\t\tif prev[tgt] == None:\n\t\t\t\tbreak\n\t\t\tz = inf\n\t\t\tx = tgt\n\t\t\twhile x != src:\n\t\t\t\te = prev[x]\n\t\t\t\tz = min(z, e.cap)\n\t\t\t\tx = e.x\n\t\t\tx = tgt\n\t\t\twhile x != src:\n\t\t\t\te = prev[x]\n\t\t\t\te.cap -= z\n\t\t\t\te.inv.cap += z\n\t\t\t\tx = e.x\n\t\t\tflowVal += z\n\t\t\tflowCost += z * (dist[tgt] - phi[src] + phi[tgt])\n\t\t\tfor i in range(n):\n\t\t\t\tif prev[i] != None:\n\t\t\t\t\tphi[i] += dist[i]\n\t\t\t\t\tdist[i] = inf\n\t\t\tcntQ += 1\n\t\t\tprev[tgt] = None\n\t\treturn (flowVal, flowCost)\n\n\tdef shortest(self, src, phi, prev, inQ, dist, inf, cntQ):\n\t\t(n, G) = (len(self.G), self.G)\n\t\tQ = [(dist[src], src)]\n\t\tinQ[src] = cntQ\n\t\tdist[src] = 0\n\t\twhile Q:\n\t\t\t(_, x) = heappop(Q)\n\t\t\tinQ[x] = 0\n\t\t\tdx = dist[x] + phi[x]\n\t\t\tfor e in G[x]:\n\t\t\t\ty = e.y\n\t\t\t\tdy = dx + e.cost - phi[y]\n\t\t\t\tif e.cap > 0 and dy < dist[y]:\n\t\t\t\t\tdist[y] = dy\n\t\t\t\t\tprev[y] = e\n\t\t\t\t\tif inQ[y] != cntQ:\n\t\t\t\t\t\tinQ[y] = cntQ\n\t\t\t\t\t\theappush(Q, (dy, y))\n\t\treturn (dist, prev)\n\n\tdef __repr__(self):\n\t\t(n, G) = (len(self.G), self.G)\n\t\ts = []\n\t\tfor i in range(n):\n\t\t\ts.append('    G[{}]:'.format(i))\n\t\t\ts.append('\\n'.join(('        {}'.format(e) for e in G[i])))\n\t\treturn '\\n'.join(s)\nimport sys\nints = (int(x) for x in sys.stdin.read().split())\nsys.setrecursionlimit(3000)\n\ndef main():\n\t(n, q) = (next(ints) for i in range(2))\n\tleq = [n - 1] * n\n\tgeq = [0] * n\n\tfor q in range(q):\n\t\t(t, l, r, v) = (next(ints) for i in range(4))\n\t\tfor i in range(l - 1, r):\n\t\t\tif t == 1:\n\t\t\t\tgeq[i] = max(geq[i], v - 1)\n\t\t\tif t == 2:\n\t\t\t\tleq[i] = min(leq[i], v - 1)\n\timp = any((geq[i] > leq[i] for i in range(n)))\n\tif imp:\n\t\tans = -1\n\telse:\n\t\tsrc = 2 * n + n * n\n\t\ttgt = 2 * n + n * n + 1\n\t\tG = MCFP()\n\t\tfor i in range(n):\n\t\t\tG.add(src, i, 1, 0)\n\t\tfor i in range(n):\n\t\t\tfor j in range(geq[i], leq[i] + 1):\n\t\t\t\tG.add(i, j + n, 1, 0)\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tG.add(i + n, 2 * n + i * n + j, 1, 0)\n\t\t\t\tG.add(2 * n + i * n + j, tgt, 1, 2 * j + 1)\n\t\t(_, ans) = G.solve(src, tgt)\n\tprint(ans)\n\treturn\nmain()\n", "import atexit\nimport io\nimport sys\n_INPUT_LINES = sys.stdin.read().splitlines()\ninput = iter(_INPUT_LINES).__next__\n_OUTPUT_BUFFER = io.StringIO()\nsys.stdout = _OUTPUT_BUFFER\n\n@atexit.register\ndef write():\n\tsys.__stdout__.write(_OUTPUT_BUFFER.getvalue())\n\nclass Arista:\n\n\tdef __init__(self, salida, llegada, capacidad, flujo, costo, indice):\n\t\tself.salida = salida\n\t\tself.llegada = llegada\n\t\tself.capacidad = capacidad\n\t\tself.flujo = flujo\n\t\tself.costo = costo\n\t\tself.indice = indice\n\n\tdef __str__(self):\n\t\ts = ''\n\t\ts = s + 'salida =' + str(self.salida) + '\\n'\n\t\ts = s + 'llegada =' + str(self.llegada) + '\\n'\n\t\ts = s + 'capacidad =' + str(self.capacidad) + '\\n'\n\t\ts = s + 'flujo =' + str(self.flujo) + '\\n'\n\t\ts = s + 'costo =' + str(self.costo) + '\\n'\n\t\ts = s + 'indice =' + str(self.indice) + '\\n'\n\t\ts = s + '------------'\n\t\treturn s\n\nclass Red:\n\n\tdef __init__(self, s, t):\n\t\tself.lista_aristas = []\n\t\tself.lista_adyacencia = {}\n\t\tself.vertices = set()\n\t\tself.fuente = s\n\t\tself.sumidero = t\n\n\tdef agregar_vertice(self, vertice):\n\t\tself.vertices.add(vertice)\n\n\tdef agregar_arista(self, arista):\n\t\tself.vertices.add(arista.salida)\n\t\tself.vertices.add(arista.llegada)\n\t\tself.lista_aristas.append(arista)\n\t\tif arista.salida not in self.lista_adyacencia:\n\t\t\tself.lista_adyacencia[arista.salida] = set()\n\t\tself.lista_adyacencia[arista.salida].add(arista.indice)\n\n\tdef agregar_lista_aristas(self, lista_aristas):\n\t\tfor arista in lista_aristas:\n\t\t\tself.agregar_arista(arista)\n\n\tdef cantidad_de_vertices(self):\n\t\treturn len(self.vertices)\n\n\tdef vecinos(self, vertice):\n\t\tif vertice not in self.lista_adyacencia:\n\t\t\treturn set()\n\t\telse:\n\t\t\treturn self.lista_adyacencia[vertice]\n\n\tdef buscar_valor_critico(self, padre):\n\t\tINFINITO = 1000000000\n\t\tvalor_critico = INFINITO\n\t\tactual = self.sumidero\n\t\twhile actual != self.fuente:\n\t\t\tarista_camino = self.lista_aristas[padre[actual]]\n\t\t\tvalor_critico = min(valor_critico, arista_camino.capacidad - arista_camino.flujo)\n\t\t\tactual = arista_camino.salida\n\t\treturn valor_critico\n\n\tdef actualizar_camino(self, padre, valor_critico):\n\t\tactual = self.sumidero\n\t\tcosto_actual = 0\n\t\twhile actual != self.fuente:\n\t\t\tself.lista_aristas[padre[actual]].flujo += valor_critico\n\t\t\tself.lista_aristas[padre[actual] ^ 1].flujo -= valor_critico\n\t\t\tcosto_actual += valor_critico * self.lista_aristas[padre[actual]].costo\n\t\t\tactual = self.lista_aristas[padre[actual]].salida\n\t\treturn (costo_actual, True)\n\n\tdef camino_de_aumento(self):\n\t\tINFINITO = 1000000000\n\t\tdistancia = {v: INFINITO for v in self.vertices}\n\t\tpadre = {v: -1 for v in self.vertices}\n\t\tdistancia[self.fuente] = 0\n\t\t(capa_actual, capa_nueva) = (set([self.fuente]), set())\n\t\twhile capa_actual:\n\t\t\tfor v in capa_actual:\n\t\t\t\tfor arista_indice in self.vecinos(v):\n\t\t\t\t\tarista = self.lista_aristas[arista_indice]\n\t\t\t\t\tif arista.flujo < arista.capacidad and distancia[arista.salida] + arista.costo < distancia[arista.llegada]:\n\t\t\t\t\t\tdistancia[arista.llegada] = distancia[arista.salida] + arista.costo\n\t\t\t\t\t\tpadre[arista.llegada] = arista.indice\n\t\t\t\t\t\tcapa_nueva.add(arista.llegada)\n\t\t\tcapa_actual = set()\n\t\t\t(capa_actual, capa_nueva) = (capa_nueva, capa_actual)\n\t\tif distancia[self.sumidero] < INFINITO:\n\t\t\tvalor_critico = self.buscar_valor_critico(padre)\n\t\t\t(costo_actual, hay_camino) = self.actualizar_camino(padre, valor_critico)\n\t\t\treturn (valor_critico, costo_actual, hay_camino)\n\t\telse:\n\t\t\treturn (-1, -1, False)\n\n\tdef max_flow_min_cost(self):\n\t\tflujo_total = 0\n\t\tcosto_total = 0\n\t\thay_camino = True\n\t\twhile hay_camino:\n\t\t\t(flujo_actual, costo_actual, hay_camino) = self.camino_de_aumento()\n\t\t\tif hay_camino:\n\t\t\t\tflujo_total += flujo_actual\n\t\t\t\tcosto_total += costo_actual\n\t\treturn (flujo_total, costo_total)\nINFINITO = 10000000000000\n(n, q) = map(int, input().split())\nmaxi = [n for i in range(n)]\nmini = [1 for i in range(n)]\nR = Red(0, 2 * n + 1)\nprohibidos = {i: set() for i in range(n)}\nfor i in range(n):\n\tfor k in range(n + 1):\n\t\tR.agregar_arista(Arista(R.fuente, i + 1, 1, 0, 2 * k + 1, len(R.lista_aristas)))\n\t\tR.agregar_arista(Arista(i + 1, R.fuente, 0, 0, -2 * k - 1, len(R.lista_aristas)))\nfor j in range(n):\n\tR.agregar_arista(Arista(n + j + 1, R.sumidero, 1, 0, 0, len(R.lista_aristas)))\n\tR.agregar_arista(Arista(R.sumidero, n + j + 1, 0, 0, 0, len(R.lista_aristas)))\nfor z in range(q):\n\t(t, l, r, v) = map(int, input().split())\n\tif t == 1:\n\t\tfor i in range(v - 1):\n\t\t\tfor j in range(l, r + 1):\n\t\t\t\tprohibidos[i].add(j)\n\telse:\n\t\tfor i in range(v, n):\n\t\t\tfor j in range(l, r + 1):\n\t\t\t\tprohibidos[i].add(j)\nfor i in range(n):\n\tfor j in range(mini[i], maxi[i] + 1):\n\t\tif j not in prohibidos[i]:\n\t\t\tR.agregar_arista(Arista(i + 1, n + j, 1, 0, 0, len(R.lista_aristas)))\n\t\t\tR.agregar_arista(Arista(n + j, i + 1, 0, 0, 0, len(R.lista_aristas)))\n(flujo_total, costo_total) = R.max_flow_min_cost()\nif flujo_total < n:\n\tprint('-1')\nelse:\n\tprint(costo_total)\n"]

question:
Recently Ivan noticed an array a while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might help him to reproduce the bug.
Ivan clearly remembers that there were n elements in the array, and each element was not less than 1 and not greater than n. Also he remembers q facts about the array. There are two types of facts that Ivan remembers:
 -  1 l_{i} r_{i} v_{i} — for each x such that l_{i} ≤ x ≤ r_{i} a_{x} ≥ v_{i}; -  2 l_{i} r_{i} v_{i} — for each x such that l_{i} ≤ x ≤ r_{i} a_{x} ≤ v_{i}. Also Ivan thinks that this array was a permutation, but he is not so sure about it. He wants to restore some array that corresponds to the q facts that he remembers and is very similar to permutation. Formally, Ivan has denoted the cost of array as follows:
![image](1.png), where cnt(i) is the number of occurences of i in the array.
Help Ivan to determine minimum possible cost of the array that corresponds to the facts!

Input
The first line contains two integer numbers n and q (1 ≤ n ≤ 50, 0 ≤ q ≤ 100).
Then q lines follow, each representing a fact about the array. i-th line contains the numbers t_{i}, l_{i}, r_{i} and v_{i} for i-th fact (1 ≤ t_{i} ≤ 2, 1 ≤ l_{i} ≤ r_{i} ≤ n, 1 ≤ v_{i} ≤ n, t_{i} denotes the type of the fact).

Output
If the facts are controversial and there is no array that corresponds to them, print -1. Otherwise, print minimum possible cost of the array.

Examples
Input
3 0

Output
3

Input
3 1
1 1 3 2

Output
5

Input
3 2
1 1 3 2
2 1 3 2

Output
9

Input
3 2
1 1 3 2
2 1 3 1

Output
-1

difficulty: HARD

source: codeforces

raw_problem:
F. Almost Permutation

time limit per test
3 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

Recently Ivan noticed an array a while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might help him to reproduce the bug.

Ivan clearly remembers that there were n elements in the array, and each element was not less than 1 and not greater than n. Also he remembers q facts about the array. There are two types of facts that Ivan remembers:

 1 li ri vi — for each x such that li ≤ x ≤ ri ax ≥ vi;

 2 li ri vi — for each x such that li ≤ x ≤ ri ax ≤ vi.

Also Ivan thinks that this array was a permutation, but he is not so sure about it. He wants to restore some array that corresponds to the q facts that he remembers and is very similar to permutation. Formally, Ivan has denoted the cost of array as follows:

, where cnt(i) is the number of occurences of i in the array.

Help Ivan to determine minimum possible cost of the array that corresponds to the facts!

Input

The first line contains two integer numbers n and q (1 ≤ n ≤ 50, 0 ≤ q ≤ 100).

Then q lines follow, each representing a fact about the array. i-th line contains the numbers ti, li, ri and vi for i-th fact (1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n, 1 ≤ vi ≤ n, ti denotes the type of the fact).

Output

If the facts are controversial and there is no array that corresponds to them, print -1. Otherwise, print minimum possible cost of the array.

Examples

Input

3 0

Output

3

Input

3 1
1 1 3 2

Output

5

Input

3 2
1 1 3 2
2 1 3 2

Output

9

Input

3 2
1 1 3 2
2 1 3 1

Output

-1

data_split: test


B. Omkar and Heavenly Tree

problem_index: B

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
The output of the first sample case corresponds to the following tree:
![image](images/cf_1583_B/2.png)
The output of the second sample case corresponds to the following tree:
![image](images/cf_1583_B/3.png)

solutions: ["R=lambda:map(int,input().split())\r\nt,=R()\r\nwhile t:\r\n t-=1;n,m=R();r={*range(1,n+1)};u=(r-{[*R()][1]for _ in[0]*m}).pop()\r\n for v in r-{u}:print(u,v)", "from multiprocessing.connection import answer_challenge\r\nimport sys\r\n \r\n\r\nfrom bisect import bisect_left, bisect_right\r\ndef is_sorted(l):\r\n    return all(a <= b for a, b in zip(l, l[1:]))\r\ndef lower_bound(a, x):\r\n    i = bisect_left(a, x)\r\n    if i:\r\n        return (i-1)\r\n    else:\r\n        return i\r\ndef upper_bound(a, x):\r\n    i = bisect_right(a, x)\r\n    if i != 0:\r\n        return (i)\r\n    else:\r\n        return -1\r\ndef is_sorted(l):\r\n    return all(a <= b for a, b in zip(l, l[1:]))\r\ndef generate_grid(n,m,default=0):\r\n    dp=[]\r\n    for i in range(n):\r\n        dp.append([default]*m)\r\n    return dp\r\ninput = sys.stdin.readline\r\ndef count_connected(i,ans,vis):\r\n    while ans[i]!=0:\r\n        i=ans[i]\r\n        vis.add(i)\r\n    return i\r\n\r\nfor _ in range(int(input())):\r\n    n,m=(map(int,input().split()))\r\n    ans=[0]*(n+1)\r\n    mainlst=[i for i in range(0,n+1)]\r\n    for i in range(m):\r\n        lst=list(map(int,input().split()))\r\n        a=lst[0]\r\n        b=lst[1]\r\n        c=lst[2]\r\n        mainlst[b]=-1\r\n    i=1\r\n    while mainlst[i]==-1:\r\n        i+=1\r\n    for x in range(1,n+1):\r\n        if i!=x:\r\n            print(i,x)", "def main():\r\n    \r\n    t = int(input())\r\n    allans = []\r\n    for _ in range(t):\r\n        n, m = readIntArr()\r\n        inmiddle = [0] * (n + 1)\r\n        for __ in range(m):\r\n            a, b, c = readIntArr()\r\n            inmiddle[b] = 1\r\n        # use a node not in the middle as a central node\r\n        central = -1\r\n        for u in range(1, n + 1):\r\n            if inmiddle[u] == 0:\r\n                central = u\r\n                break\r\n        assert central != -1\r\n        for v in range(1, n + 1):\r\n            if u == v:\r\n                continue\r\n            allans.append((u, v))\r\n    multiLineArrayOfArraysPrint(allans)\r\n    \r\n    return\r\n\r\nimport sys\r\ninput=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)\r\n# input=lambda: sys.stdin.readline().rstrip(\"\\r\\n\") #FOR READING STRING/TEXT INPUTS.\r\n \r\ndef oneLineArrayPrint(arr):\r\n    print(' '.join([str(x) for x in arr]))\r\ndef multiLineArrayPrint(arr):\r\n    print('\\n'.join([str(x) for x in arr]))\r\ndef multiLineArrayOfArraysPrint(arr):\r\n    print('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\r\n \r\ndef readIntArr():\r\n    return [int(x) for x in input().split()]\r\n# def readFloatArr():\r\n#     return [float(x) for x in input().split()]\r\n \r\ndef makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])\r\n    dv=defaultValFactory;da=dimensionArr\r\n    if len(da)==1:return [dv() for _ in range(da[0])]\r\n    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]\r\n \r\ndef queryInteractive(a, b, c):\r\n    print('? {} {} {}'.format(a, b, c))\r\n    sys.stdout.flush()\r\n    return int(input())\r\n \r\ndef answerInteractive(x1, x2):\r\n    print('! {} {}'.format(x1, x2))\r\n    sys.stdout.flush()\r\n \r\ninf=float('inf')\r\n# MOD=10**9+7\r\n# MOD=998244353\r\n \r\nfrom math import gcd,floor,ceil\r\nimport math\r\n# from math import floor,ceil # for Python2\r\n \r\nfor _abc in range(1):\r\n    main()", "import sys\r\nimport os\r\nfrom collections import Counter, defaultdict, deque\r\nfrom heapq import heapify, heappush, heappop\r\nfrom functools import lru_cache\r\nfrom math import floor, ceil, sqrt, gcd\r\nfrom string import ascii_lowercase\r\nfrom bisect import bisect_left, bisect, bisect_right\r\n\r\n\r\ndef __perform_setup__():\r\n    INPUT_FILE_PATH = \"./code/input.txt\"\r\n    OUTPUT_FILE_PATH = \"./code/output.txt\"\r\n\r\n    sys.stdin = open(INPUT_FILE_PATH, 'r')\r\n    sys.stdout = open(OUTPUT_FILE_PATH, 'w')\r\n\r\n\r\nif \"MY_COMPETITIVE_PROGRAMMING_VARIABLE\" in os.environ:\r\n    __perform_setup__()\r\n\r\n\r\ndef read():\r\n    return input().strip()\r\n\r\n\r\ndef read_int():\r\n    return int(read())\r\n\r\n\r\ndef read_str_list():\r\n    return read().split()\r\n\r\n\r\ndef read_numeric_list():\r\n    return list(map(int, read_str_list()))\r\n\r\n\r\ndef solve(N, M, restrictions):\r\n    restricted = set([r[1] for r in restrictions])\r\n    not_restricted = None\r\n\r\n    for i in range(1, N+1):\r\n        if i not in restricted:\r\n            not_restricted = i\r\n\r\n    ans = []\r\n\r\n    for i in range(1, N+1):\r\n        if i == not_restricted:\r\n            continue\r\n\r\n        ans.append([not_restricted, i])\r\n\r\n    return \"\\n\".join(\" \".join(map(str, edge)) for edge in ans)\r\n\r\n\r\nT = read_int()\r\n\r\nfor t in range(T):\r\n    N, M = read_numeric_list()\r\n    restrictions = []\r\n\r\n    for _ in range(M):\r\n        restrictions.append(read_numeric_list())\r\n\r\n    print(solve(N, M, restrictions))", "import sys\r\ninput = sys.stdin.readline\r\n\r\nfor _ in range(int(input())):\r\n    n, m = map(int, input().split())\r\n    d = [0]*n\r\n    for i in range(m):\r\n        a, b, c = map(int, input().split())\r\n        d[b-1] = 1\r\n    for i in range(n):\r\n        if d[i] == 0:\r\n            for j in range(n):\r\n                if j != i:\r\n                    print(i+1, j+1)\r\n            break"]

source: codeforces

raw_problem:
B. Omkar and Heavenly Tree

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Lord Omkar would like to have a tree with $$$n$$$ nodes ($$$3 \le n \le 10^5$$$) and has asked his disciples to construct the tree. However, Lord Omkar has created $$$m$$$ ($$$\mathbf{1 \le m < n}$$$) restrictions to ensure that the tree will be as heavenly as possible.

A tree with $$$n$$$ nodes is an connected undirected graph with $$$n$$$ nodes and $$$n-1$$$ edges. Note that for any two nodes, there is exactly one simple path between them, where a simple path is a path between two nodes that does not contain any node more than once.

Here is an example of a tree:

A restriction consists of $$$3$$$ pairwise distinct integers, $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a,b,c \le n$$$). It signifies that node $$$b$$$ cannot lie on the simple path between node $$$a$$$ and node $$$c$$$.

Can you help Lord Omkar and become his most trusted disciple? You will need to find heavenly trees for multiple sets of restrictions. It can be shown that a heavenly tree will always exist for any set of restrictions under the given constraints.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.

The first line of each test case contains two integers, $$$n$$$ and $$$m$$$ ($$$3 \leq n \leq 10^5$$$, $$$\mathbf{1 \leq m < n}$$$), representing the size of the tree and the number of restrictions.

The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \le a_i, b_i, c_i \le n$$$, $$$a$$$, $$$b$$$, $$$c$$$ are distinct), signifying that node $$$b_i$$$ cannot lie on the simple path between nodes $$$a_i$$$ and $$$c_i$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$10^5$$$.

Output

For each test case, output $$$n-1$$$ lines representing the $$$n-1$$$ edges in the tree. On each line, output two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) signifying that there is an edge between nodes $$$u$$$ and $$$v$$$. Given edges have to form a tree that satisfies Omkar's restrictions.

Example

Input

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

Output

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

Note

The output of the first sample case corresponds to the following tree:
   For the first restriction, the simple path between $$$1$$$ and $$$3$$$ is $$$1, 3$$$, which doesn't contain $$$2$$$. The simple path between $$$3$$$ and $$$5$$$ is $$$3, 5$$$, which doesn't contain $$$4$$$. The simple path between $$$5$$$ and $$$7$$$ is $$$5, 3, 1, 2, 7$$$, which doesn't contain $$$6$$$. The simple path between $$$6$$$ and $$$4$$$ is $$$6, 7, 2, 1, 3, 4$$$, which doesn't contain $$$5$$$. Thus, this tree meets all of the restrictions.
The output of the second sample case corresponds to the following tree:

question:
Lord Omkar would like to have a tree with $$$n$$$ nodes ($$$3 \le n \le 10^5$$$) and has asked his disciples to construct the tree. However, Lord Omkar has created $$$m$$$ ($$$\mathbf{1 \le m < n}$$$) restrictions to ensure that the tree will be as heavenly as possible.
A tree with $$$n$$$ nodes is an connected undirected graph with $$$n$$$ nodes and $$$n-1$$$ edges. Note that for any two nodes, there is exactly one simple path between them, where a simple path is a path between two nodes that does not contain any node more than once.
Here is an example of a tree:
 ![image](1.png) A restriction consists of $$$3$$$ pairwise distinct integers, $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a,b,c \le n$$$). It signifies that node $$$b$$$ cannot lie on the simple path between node $$$a$$$ and node $$$c$$$.
Can you help Lord Omkar and become his most trusted disciple? You will need to find heavenly trees for multiple sets of restrictions. It can be shown that a heavenly tree will always exist for any set of restrictions under the given constraints.

Input
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.
The first line of each test case contains two integers, $$$n$$$ and $$$m$$$ ($$$3 \leq n \leq 10^5$$$, $$$\mathbf{1 \leq m < n}$$$), representing the size of the tree and the number of restrictions.
The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \le a_i, b_i, c_i \le n$$$, $$$a$$$, $$$b$$$, $$$c$$$ are distinct), signifying that node $$$b_i$$$ cannot lie on the simple path between nodes $$$a_i$$$ and $$$c_i$$$.
It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$10^5$$$.

Output
For each test case, output $$$n-1$$$ lines representing the $$$n-1$$$ edges in the tree. On each line, output two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) signifying that there is an edge between nodes $$$u$$$ and $$$v$$$. Given edges have to form a tree that satisfies Omkar's restrictions.

Example
Input
2
7 4
1 2 3
3 4 5
5 6 7
6 5 4
5 3
1 2 3
2 3 4
3 4 5

Output
1 2
1 3
3 5
3 4
2 7
7 6
5 1
1 3
3 2
2 4

Note
The output of the first sample case corresponds to the following tree:
 ![image](2.png)  For the first restriction, the simple path between $$$1$$$ and $$$3$$$ is $$$1, 3$$$, which doesn't contain $$$2$$$. The simple path between $$$3$$$ and $$$5$$$ is $$$3, 5$$$, which doesn't contain $$$4$$$. The simple path between $$$5$$$ and $$$7$$$ is $$$5, 3, 1, 2, 7$$$, which doesn't contain $$$6$$$. The simple path between $$$6$$$ and $$$4$$$ is $$$6, 7, 2, 1, 3, 4$$$, which doesn't contain $$$5$$$. Thus, this tree meets all of the restrictions.The output of the second sample case corresponds to the following tree:
 ![image](3.png)

image_tags: Tree Tree Tree

data_split: test


Ant Nest

source: 9th PC Koshien, Final

raw_problem:
アリの巣箱の形状

求悟君は夏休みの自由研究としてアリの巣の観察を行うことにしました。彼のおじいちゃんが孫のために用意してくれた観察用の透明ケースはとてもユニークで、図1のような形をしています。

図１

このケースは、2枚の合同な凸多角形 s1、s2 と何枚かの長方形で構成されています。s1、s2 以外のいずれかの長方形の面を床に接するように置きます。観察を始めた求悟君は、入っている土の量が同じにもかかわらず、底面の選び方によって土の高さが変わることに気付きました（図2）。

図２

求悟君は、ケースの置き方によって、どのくらい高くなるか知りたくなりました。凸多角形 s1 の形、s1 と s2 間の距離 <var>d</var>、土の体積 <var>V</var> を入力とし、土の高さの最大値を出力するプログラムを作成してください。土は、ケースの底面を床に置くとすぐに水平になるものとします。透明ケースの s1 の形は、二次元の座標平面上の <var>n</var> 個の頂点で与えられます。これらの頂点は、反時計回りの順番で入力されます。<var>n</var> は 3 以上 100 以下で、<var>d</var> と <var>V</var> はそれぞれ 1 以上 10,000 以下の整数とします。また、多角形の頂点の座標 <var>(x, y)</var> の <var>x</var>、<var>y</var> はそれぞれ -1,000 以上 1,000 以下の整数とします。<var>V</var>はケースの体積を超えません。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロみっつの行で示されます。各データセットは以下のとおりです。

1 行目 <var>n</var> <var>d</var> <var>V</var>（整数 整数 整数；半角空白区切り）

2 行目 第 1 の頂点の座標 <var>x</var> <var>y</var>（整数 整数；半角空白区切り）

3 行目 第 2 の頂点の座標

:

<var>n+1</var> 行目 第 <var>n</var> の頂点の座標

データセットの数は 20 を超えません。

出力

入力データセットごとに、土の高さの最大値を出力します。答えには 0.00001 を越える誤差があってはいけません。

入力例

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

出力例

1.000000

solutions: ["import sys\nimport math\n\n# READ_FROM_FILE = True\nREAD_FROM_FILE = False\n\nCOUNTER_CLOCKWISE = 1\nCLOCKWISE = -1\nON_SEGMENT = 0\nONLINE_BACK = -2\nONLINE_FRONT = 2\n\nEPS = 1e-10\n\n\ndef inner_product(v0, v1):\n    return v0.real * v1.real + v0.imag + v1.imag\n\n\ndef cross_product(v0, v1):\n    return v0.real * v1.imag - v0.imag * v1.real\n\n\ndef ccw(p0, p1, p2):\n    v01 = p1 - p0\n    v02 = p2 - p0\n\n    cp = cross_product(v01, v02)\n\n    if cp > EPS:\n        return COUNTER_CLOCKWISE\n    if cp < -EPS:\n        return CLOCKWISE\n    if inner_product(v01, v02) < -EPS:\n        return ONLINE_BACK\n    if abs(v01) < abs(v02):\n        return ONLINE_FRONT\n    return ON_SEGMENT\n\n\ndef intersects(p0, p1, p2, p3):\n    return (ccw(p0, p1, p2) * ccw(p0, p1, p3) <= 0) and (ccw(p2, p3, p0) * ccw(p2, p3, p1) <= 0)\n\n\ndef calc_cross_point(p0, p1, p2, p3):\n    v01 = p1 - p0\n    v23 = p3 - p2\n    v20 = p0 - p2\n    v21 = p1 - p2\n\n    d0 = abs(cross_product(v23, v20))\n    d1 = abs(cross_product(v23, v21))\n    d_sum = d0 + d1\n\n    if d_sum == 0.0:\n        return p2\n\n    t = d0 / d_sum\n    return p0 + v01 * t\n\n\ndef calc_area(p_list):\n    n = len(p_list)\n\n    total_area = 0\n    for i in range(n):\n        p0 = p_list[i - 1]\n        p1 = p_list[i]\n        area = cross_product(p0, p1)\n        total_area += area\n    return total_area / 2\n\n\n# Find the area of the left side of the convex polygon (p_list) cut by segment p0p1\n# bl_p: bottom left of all area\n# tr_p: top right of all area\n# p_list: polygon (counterclockwise)\n# p0, p1: segment\ndef convex_cut(bl_p, tr_p, p_list, p0, p1):\n    x0 = p0.real\n    y0 = p0.imag\n    x1 = p1.real\n    y1 = p1.imag\n    n = len(p_list)\n\n    v01 = p1 - p0\n    v01 = v01 / abs(v01)\n\n    s_min = math.inf\n    if v01.real != 0.0:\n        s = (-p0.real + bl_p.real) / v01.real\n        s_min = min(s_min, s)\n    if v01.imag != 0.0:\n        s = (-p0.imag + bl_p.imag) / v01.imag\n        s_min = min(s_min, s)\n\n    s_max = -math.inf\n    if v01.real != 0.0:\n        s = (-p1.real + tr_p.real) / v01.real\n        s_max = max(s_max, s)\n    if v01.imag != 0.0:\n        s = (-p1.imag + tr_p.imag) / v01.imag\n        s_max = max(s_max, s)\n\n    p0 = complex(x0 + s_min * v01.real, y0 + s_min * v01.imag)\n    p1 = complex(x1 + s_max * v01.real, y1 + s_max * v01.imag)\n    cut_p_list = []\n\n    for i in range(n):\n        p2 = p_list[i - 1]\n        p3 = p_list[i]\n        v03 = p3 - p0\n        cp = cross_product(v01, v03)\n\n        if intersects(p0, p1, p2, p3):\n            cross_point = calc_cross_point(p0, p1, p2, p3)\n            cut_p_list.append(cross_point)\n\n        if cp > 0:\n            cut_p_list.append(p3)\n\n    return calc_area(cut_p_list)\n\n\ndef transform(n, p_list):\n    p0 = p_list[0]\n\n    for i in range(n):\n        p_list[i] -= p0\n\n    p01 = p_list[1] - p_list[0]\n\n    theta = -math.atan2(p01.imag, p01.real)\n    z = complex(math.cos(theta), math.sin(theta))\n    for i in range(n):\n        p_list[i] *= z\n    return\n\n\ndef main():\n    if READ_FROM_FILE:\n        f = open('test0.txt', 'r')\n    else:\n        f = sys.stdin\n\n    bl_p = -1001 + -1001j\n    tr_p = 1001 + 1001j\n    while True:\n        n, d, v = map(int, f.readline().split())\n        if n == d == v == 0:\n            break\n\n        s = v / d\n        p_list = []\n        for _ in range(n):\n            x, y = map(int, f.readline().split())\n            p_list.append(complex(x, y))\n\n        max_h = 0\n        for i in range(n):\n            t_p_list = p_list[i:] + p_list[:i]\n            transform(n, t_p_list)\n            left = 0\n            right = 1001\n            while right - left > 1e-6:\n                mid = (left + right) / 2\n                p0 = complex(tr_p.real, mid)\n                p1 = complex(bl_p.real, mid)\n                area = convex_cut(bl_p, tr_p, t_p_list, p0, p1)\n                if area < s:\n                    left = mid\n                else:\n                    right = mid\n\n            max_h = max(max_h, left)\n\n        print(f'{max_h:.5f}')\n\n    if READ_FROM_FILE:\n        f.close()\n    return\n\n\nif __name__ == '__main__':\n    main()\n\n"]

source: aizu

question:
Shape of the Ant Nest Box

Seeko-kun decided to observe an ant nest for his summer vacation research project. His grandfather prepared a unique, transparent observation case for his grandson, which has the shape illustrated in Figure 1.

![image](1.png)
Figure 1

This case consists of two congruent convex polygons s1 and s2, and several rectangles. You place one of the rectangular surfaces other than s1 and s2 so that it touches the floor. Seeko-kun, who started his observation, noticed that despite the amount of soil being the same, the height of the soil changes depending on the choice of the bottom surface (Figure 2).

![image](2.png)
Figure 2

Seeko-kun became curious about how much higher the soil could get, depending on the way the case is positioned. Please create a program that takes the shape of the convex polygon s1, the distance $d$ between s1 and s2, and the volume of soil $V$ as input and outputs the maximum height of the soil. Assume that the soil levels out immediately when the case's bottom surface is placed on the floor. The shape of s1 in the transparent case is provided as $n$ points on the two-dimensional coordinate plane. These points are input in a counterclockwise order. $n$ is an integer between 3 and 100, and both $d$ and $V$ are integers ranging from 1 to 10,000. Additionally, the coordinates $(x, y)$ of the polygon's vertices are integers where $x$ and $y$ range from -1,000 to 1,000. $V$ does not exceed the volume of the case.

Input

A series of datasets is given as input. The end of the input is indicated by a line with three zeros. Each dataset is as follows:

First line $n$ $d$ $V$ (integer integer integer; separated by a single space)
Second line coordinates of the 1st vertex $x$ $y$ (integer integer; separated by a single space)
Third line coordinates of the 2nd vertex
:
Line $n+1$ coordinates of the $n$th vertex

The number of datasets does not exceed 20.

Output

For each input dataset, output the maximum height of the soil. The answer must not have an error exceeding 0.00001.

Input example

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

Output example

1.000000

image_tags:
3D Geometry
3D Geometry

data_split: test


name: Code Festival Team Relay (Parallel) - Nice to Meet You

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>100</var> 点

問題文

りんご海に <var>N</var> 個の島が浮かんでおり、<var>M</var> 社の業者がこれらの島を結ぶ船便を運行しています。便宜上、これらの島を島 <var>1,</var> <var>2,</var> <var>…,</var> <var>N</var> と呼び、これらの業者を業者 <var>1</var>, <var>2</var>, <var>…,</var> <var>M</var> と呼びます。

りんご海の海流は毎日大きく変わります。業者 <var>i</var> <var>(1 ≤ i ≤ M)</var> は、その日の海の状況に応じて、島 <var>a_i</var> から <var>b_i</var> への便または島 <var>b_i</var> から <var>a_i</var> への便のどちらか一方のみを運行します。どちらの方向の便が運行されるかは、それぞれの業者について独立に、等確率で決定されるものとします。

いま、島 <var>1</var> に高橋くんが、島 <var>2</var> に低橋くんがいます。<var>M</var> 社の業者による船便を用いて、高橋くんと低橋くんがその日のうちに同じ島に移動することができる確率を <var>P</var> とします。ただし、船の所要時間などは無視します。このとき、<var>P × 2^M</var> は整数となります。<var>P × 2^M</var> を <var>10^9 + 7</var> で割ったあまりを求めてください。

制約

<var>2 ≤ N ≤ 15</var>

<var>1 ≤ M ≤ N(N-1)/2</var>

<var>1 ≤ a_i < b_i ≤ N</var>

組 <var>(a_i, b_i)</var> はすべて異なる。

入力

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

<var>N</var> <var>M</var>
<var>a_1</var> <var>b_1</var>
<var>:</var>
<var>a_M</var> <var>b_M</var>

出力

値 <var>P × 2^M</var> を <var>10^9 + 7</var> で割ったあまりを出力せよ。

入力例 1

4 3
1 3
2 3
3 4

出力例 1

6

上図に示した <var>2^M = 8</var> 通りの状況が等確率で発生し、そのうち高橋くんと低橋くんが同じ島で出会える状況は <var>6</var> 通りです。したがって、<var>P = 6/2^M,</var> <var>P × 2^M = 6</var> となります。

入力例 2

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

出力例 2

18

入力例 3

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

出力例 3

64

Score : <var>100</var> points

Problem Statement

There are <var>N</var> islands floating in Ringo Sea, and <var>M</var> travel agents operate ships between these islands. For convenience, we will call these islands Island <var>1,</var> <var>2,</var> <var>…,</var> <var>N,</var> and call these agents Agent <var>1,</var> <var>2,</var> <var>…,</var> <var>M</var>.

The sea currents in Ringo Sea change significantly each day. Depending on the state of the sea on the day, Agent <var>i</var> <var>(1 ≤ i ≤ M)</var> operates ships from Island <var>a_i</var> to <var>b_i</var>, or Island <var>b_i</var> to <var>a_i</var>, but not both at the same time. Assume that the direction of the ships of each agent is independently selected with equal probability.

Now, Takahashi is on Island <var>1</var>, and Hikuhashi is on Island <var>2</var>. Let <var>P</var> be the probability that Takahashi and Hikuhashi can travel to the same island in the day by ships operated by the <var>M</var> agents, ignoring the factors such as the travel time for ships. Then, <var>P × 2^M</var> is an integer. Find <var>P × 2^M</var> modulo <var>10^9 + 7</var>.

Constraints

<var>2 ≤ N ≤ 15</var>

<var>1 ≤ M ≤ N(N-1)/2</var>

<var>1 ≤ a_i < b_i ≤ N</var>

All pairs <var>(a_i, b_i)</var> are distinct.

Input

Input is given from Standard Input in the following format:

<var>N</var> <var>M</var>
<var>a_1</var> <var>b_1</var>
<var>:</var>
<var>a_M</var> <var>b_M</var>

Output

Print the value <var>P × 2^M</var> modulo <var>10^9 + 7</var>.

Sample Input 1

4 3
1 3
2 3
3 4

Sample Output 1

6

The <var>2^M = 8</var> scenarios shown above occur with equal probability, and Takahashi and Hikuhashi can meet on the same island in <var>6</var> of them. Thus, <var>P = 6/2^M</var> and <var>P × 2^M = 6</var>.

Sample Input 2

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

Sample Output 2

18

Sample Input 3

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

Sample Output 3

64

question:
There are $N$ islands floating in Ringo Sea, and $M$ travel agents operate ships between these islands. For convenience, we will call these islands Island $1,$ $2,$ $…,$ $N,$ and call these agents Agent $1,$ $2,$ $…,$ $M$.
The sea currents in Ringo Sea change significantly each day. Depending on the state of the sea on the day, Agent $i$ $(1 ≤ i ≤ M)$ operates ships from Island $a_i$ to $b_i$, or Island $b_i$ to $a_i$, but not both at the same time. Assume that the direction of the ships of each agent is independently selected with equal probability.
Now, Takahashi is on Island $1$, and Hikuhashi is on Island $2$. Let $P$ be the probability that Takahashi and Hikuhashi can travel to the same island in the day by ships operated by the $M$ agents, ignoring the factors such as the travel time for ships. Then, $P × 2^M$ is an integer. Find $P × 2^M$ modulo $10^9 + 7$.

Constraints

- $2 ≤ N ≤ 15$
- $1 ≤ M ≤ N(N-1)/2$
- $1 ≤ a_i < b_i ≤ N$
- All pairs $(a_i, b_i)$ are distinct.

Input
Input is given from Standard Input in the following format:
$N$ $M$

$a_1$ $b_1$

$:$

$a_M$ $b_M$

Output
Print the value $P × 2^M$ modulo $10^9 + 7$.

Sample Input 1
4 3
1 3
2 3
3 4

Sample Output 1
6

![image](1.png)

The $2^M = 8$ scenarios shown above occur with equal probability, and Takahashi and Hikuhashi can meet on the same island in $6$ of them. Thus, $P = 6/2^M$ and $P × 2^M = 6$.

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

Sample Output 2
18

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

Sample Output 3
64

data_split: test


B2. Wonderful Coloring - 2

time_limit: 2 seconds

memory_limit: 256 megabytes

solutions: ["from collections import *\r\nfrom copy import *\r\nimport sys\r\n\r\ndef in_ipynb():\r\n    try:\r\n        cfg = get_ipython().config \r\n        #print(cfg)\r\n        if cfg['IPKernelApp']['parent_appname']:\r\n            return True\r\n        else:\r\n            return False\r\n    except NameError:\r\n        return False\r\nin_prac=(in_ipynb())\r\nfastio=0\r\nif in_prac:\r\n    handle=open('cfinput.txt','r')\r\ndef input():\r\n    if in_prac:\r\n        return handle.readline().rstrip('\\r').rstrip('\\n')\r\n    else:\r\n        return sys.stdin.readline().rstrip('\\r').rstrip('\\n')\r\ndef pr(output): #rename to print for fastio\r\n    sys.stdout.write(str(output)+'\\n')\r\n    return\r\nif in_prac:\r\n    handle=open('cfinput.txt','r')\r\n#start here\r\nfor _ in range(int(input())):\r\n    n,k=map(int,input().split())\r\n    l=list(map(int,input().split()))\r\n    c=Counter(l)\r\n    setl=set(l)\r\n    D=len([i for i in setl if c[i]>=k])\r\n    c2=Counter([])\r\n    D2={i:[] for i in setl}\r\n    for i,e in enumerate(l):\r\n        c2[e]+=1\r\n        D2[e].append(i)\r\n    \r\n    o=[0 for __ in range(n)]\r\n    for i in D2:\r\n        for P,j in enumerate(D2[i]):\r\n            o[j]=P\r\n    for i,e in enumerate(o):\r\n        if e>k:\r\n            o[i]=-1\r\n    indexes={i:[] for i in setl} #set_l is the unique elements\r\n    for i,e in enumerate(l): #l is the given list\r\n        if len(indexes[e])<k: #discard late occurences\r\n            indexes[e].append(i) #add the index to the list representing the element value\r\n    S=sum(len(i) for i in indexes.values())//k*k\r\n    total=[]\r\n    for i in indexes.values():\r\n        total+=list(i)\r\n    ans={i:0 for i in range(n)}\r\n    for i,e in enumerate(total[:S]):\r\n        ans[e]=i%k+1\r\n        \r\n    ans888=[ans[i] for i in range(n)]\r\n    print(*ans888)", "import sys, math, itertools, functools, collections\r\ninput = sys.stdin.readline\r\n#sys.setrecursionlimit(10**6)\r\n\r\nrs  = lambda: input().strip()\r\nri  = lambda: int(input())\r\nrmi  = lambda: map(int, input().split())\r\nra = lambda: [int(x) for x in input().split()]\r\npa = lambda x: print (\" \".join(map(str, x)))\r\n\r\ntest_case = ri()\r\n\r\n#-------- DIFFERENT WAYS TO UNSTUCK ------------ \r\n# 1. Frequency/Value domain and Pigeon Hole Principle \r\n# 2. Search from end to start instead of start to end\r\n# 3. Prefix Suffix\r\n# 4. Brute force if small input size\r\n\r\ndef solve():\r\n    freq = collections.defaultdict(list)\r\n    #colors = [[] for _ in range(k)]\r\n\r\n    for i, num in enumerate(A):\r\n        freq[num].append(i)\r\n    \r\n    ans = [0] * n\r\n    tmp = []\r\n    #print(freq)\r\n    cnt = 0\r\n    for v in freq.values():\r\n        if len(v) >= k:\r\n            i = 0\r\n            for c in range(1, k+1):\r\n                ans[v[i]] = c\r\n                i += 1\r\n        else:\r\n            cnt += len(v)\r\n            tmp.append(v)\r\n    tmp.sort(key = lambda x:len(x))\r\n    tmp2 = []\r\n    for arr in tmp:\r\n        tmp2 += arr\r\n    #print(tmp, ans)\r\n    i = 0\r\n    q = cnt//k\r\n    #print(tmp, tmp2)\r\n    for i in range(k):\r\n        c = i + 1\r\n        for j in range(q):\r\n            #print(i, i+j*k,tmp2[i+k*j], c)\r\n            ans[tmp2[i+j*k]] = c\r\n    return ans\r\n    \r\n    \r\n\r\nfor _ in range(test_case):\r\n    n, k = rmi()\r\n    A = ra()\r\n    print(*solve())", "R=lambda:map(int,input().split())\r\nt,=R()\r\nwhile t:\r\n t-=1;n,k=R();r=[0]*n;a=[];p=0\r\n for x,i in sorted(zip(R(),range(n))):n*=x==p;a+=[i][:n<k];p=x;n+=1\r\n for i in a[len(a)%k:]:n=n%k+1;r[i]=n\r\n print(*r)", "import sys\r\ninput=sys.stdin.readline\r\nfrom math import floor\r\n# from math import pi\r\nfrom collections import Counter\r\nfrom collections import defaultdict\r\nfor _ in range(int(input())):\r\n    n,k=map(int,input().split())\r\n    nums=list(map(int,input().split()))\r\n    # nums.sort()\r\n    # print(*nums)\r\n    ans=[]\r\n    count=n%k\r\n    hmap={}\r\n    for i,item in enumerate(nums):\r\n        if item not in hmap:\r\n            hmap[item]=[]\r\n        hmap[item].append(i)\r\n    temp=[]\r\n    ans=[0]*n\r\n\r\n    for item in hmap:\r\n        for i in range(min(k,len(hmap[item]))):\r\n            temp.append(hmap[item][i])\r\n            if len(temp)==k:\r\n                for z in range(k):\r\n                    ans[temp[z]]=z+1\r\n                temp.clear()            \r\n    print(*ans)", "import sys\r\ninput = sys.stdin.readline\r\nfrom collections import Counter\r\n\r\nfor _ in range(int(input())):\r\n    n, k = map(int, input().split())\r\n    w = input()[:-1].split()\r\n    d = Counter()\r\n    s = []\r\n    for i, j in enumerate(w):\r\n        if d[j] < k:\r\n            s.append((j, i))\r\n        d[j] += 1\r\n    s.sort()\r\n    x = len(s)\r\n    x -= x%k\r\n    color = [0]*n\r\n    c = 1\r\n    for i, j in s[:x]:\r\n        color[j] = c\r\n        c = c+1\r\n        if c > k:\r\n            c -= k\r\n    print(' '.join(map(str, color)))"]

source: codeforces

raw_problem:
B2. Wonderful Coloring - 2

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

This problem is an extension of the problem "Wonderful Coloring - 1". It has quite many differences, so you should read this statement completely.

Recently, Paul and Mary have found a new favorite sequence of integers $$$a_1, a_2, \dots, a_n$$$. They want to paint it using pieces of chalk of $$$k$$$ colors. The coloring of a sequence is called wonderful if the following conditions are met:

 each element of the sequence is either painted in one of $$$k$$$ colors or isn't painted;

 each two elements which are painted in the same color are different (i. e. there's no two equal values painted in the same color);

 let's calculate for each of $$$k$$$ colors the number of elements painted in the color — all calculated numbers must be equal;

 the total number of painted elements of the sequence is the maximum among all colorings of the sequence which meet the first three conditions.

E. g. consider a sequence $$$a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2]$$$ and $$$k=3$$$. One of the wonderful colorings of the sequence is shown in the figure.
  The example of a wonderful coloring of the sequence $$$a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2]$$$ and $$$k=3$$$. Note that one of the elements isn't painted.
Help Paul and Mary to find a wonderful coloring of a given sequence $$$a$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of two lines. The first one contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$1 \le k \le n$$$) — the length of a given sequence and the number of colors, respectively. The second one contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

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

Output

Output $$$t$$$ lines, each of them must contain a description of a wonderful coloring for the corresponding test case.

Each wonderful coloring must be printed as a sequence of $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le k$$$) separated by spaces where

 $$$c_i=0$$$, if $$$i$$$-th element isn't painted;

 $$$c_i>0$$$, if $$$i$$$-th element is painted in the $$$c_i$$$-th color.

Remember that you need to maximize the total count of painted elements for the wonderful coloring. If there are multiple solutions, print any one.

Example

Input

6
10 3
3 1 1 1 1 10 3 10 10 2
4 4
1 1 1 1
1 1
1
13 1
3 1 4 1 5 9 2 6 5 3 5 8 9
13 2
3 1 4 1 5 9 2 6 5 3 5 8 9
13 3
3 1 4 1 5 9 2 6 5 3 5 8 9

Output

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

Note

In the first test case, the answer is shown in the figure in the statement. The red color has number $$$1$$$, the blue color — $$$2$$$, the green — $$$3$$$.

question:
This problem is an extension of the problem "Wonderful Coloring - 1". It has quite many differences, so you should read this statement completely.
Recently, Paul and Mary have found a new favorite sequence of integers $$$a_1, a_2, \dots, a_n$$$. They want to paint it using pieces of chalk of $$$k$$$ colors. The coloring of a sequence is called wonderful if the following conditions are met:
 -  each element of the sequence is either painted in one of $$$k$$$ colors or isn't painted; -  each two elements which are painted in the same color are different (i. e. there's no two equal values painted in the same color); -  let's calculate for each of $$$k$$$ colors the number of elements painted in the color — all calculated numbers must be equal; -  the total number of painted elements of the sequence is the maximum among all colorings of the sequence which meet the first three conditions. E. g. consider a sequence $$$a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2]$$$ and $$$k=3$$$. One of the wonderful colorings of the sequence is shown in the figure.
 ![image](1.png) The example of a wonderful coloring of the sequence $$$a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2]$$$ and $$$k=3$$$. Note that one of the elements isn't painted. Help Paul and Mary to find a wonderful coloring of a given sequence $$$a$$$.

Input
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10000$$$) — the number of test cases. Then $$$t$$$ test cases follow.
Each test case consists of two lines. The first one contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$1 \le k \le n$$$) — the length of a given sequence and the number of colors, respectively. The second one contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output
Output $$$t$$$ lines, each of them must contain a description of a wonderful coloring for the corresponding test case.
Each wonderful coloring must be printed as a sequence of $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le k$$$) separated by spaces where
 -  $$$c_i=0$$$, if $$$i$$$-th element isn't painted; -  $$$c_i>0$$$, if $$$i$$$-th element is painted in the $$$c_i$$$-th color. Remember that you need to maximize the total count of painted elements for the wonderful coloring. If there are multiple solutions, print any one.

Example
Input
6
10 3
3 1 1 1 1 10 3 10 10 2
4 4
1 1 1 1
1 1
1
13 1
3 1 4 1 5 9 2 6 5 3 5 8 9
13 2
3 1 4 1 5 9 2 6 5 3 5 8 9
13 3
3 1 4 1 5 9 2 6 5 3 5 8 9

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

Note
In the first test case, the answer is shown in the figure in the statement. The red color has number $$$1$$$, the blue color — $$$2$$$, the green — $$$3$$$.

data_split: test


C. Bear and Square Grid

problem_index: C

time_limit: 3 seconds

memory_limit: 256 megabytes

note:
In the first sample, you can choose a square of size 2 × 2. It's optimal to choose a square in the red frame on the left drawing below. Then, you will get a connected component with 10 cells, marked blue in the right drawing.
![image](images/cf_679_C/1.png)

source: codeforces

raw_problem:
C. Bear and Square Grid

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You have a grid with n rows and n columns. Each cell is either empty (denoted by '.') or blocked (denoted by 'X').

Two empty cells are directly connected if they share a side. Two cells (r1, c1) (located in the row r1 and column c1) and (r2, c2) are connected if there exists a sequence of empty cells that starts with (r1, c1), finishes with (r2, c2), and any two consecutive cells in this sequence are directly connected. A connected component is a set of empty cells such that any two cells in the component are connected, and there is no cell in this set that is connected to some cell not in this set.

Your friend Limak is a big grizzly bear. He is able to destroy any obstacles in some range. More precisely, you can choose a square of size k × k in the grid and Limak will transform all blocked cells there to empty ones. However, you can ask Limak to help only once.

The chosen square must be completely inside the grid. It's possible that Limak won't change anything because all cells are empty anyway.

You like big connected components. After Limak helps you, what is the maximum possible size of the biggest connected component in the grid?

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 500) — the size of the grid and Limak's range, respectively.

Each of the next n lines contains a string with n characters, denoting the i-th row of the grid. Each character is '.' or 'X', denoting an empty cell or a blocked one, respectively.

Output

Print the maximum possible size (the number of cells) of the biggest connected component, after using Limak's help.

Examples

Input

5 2
..XXX
XX.XX
X.XXX
X...X
XXXX.

Output

10

Input

5 3
.....
.XXX.
.XXX.
.XXX.
.....

Output

25

Note

In the first sample, you can choose a square of size 2 × 2. It's optimal to choose a square in the red frame on the left drawing below. Then, you will get a connected component with 10 cells, marked blue in the right drawing.

question:
You have a grid with n rows and n columns. Each cell is either empty (denoted by '.') or blocked (denoted by 'X').
Two empty cells are directly connected if they share a side. Two cells (r_{1}, c_{1}) (located in the row r_{1} and column c_{1}) and (r_{2}, c_{2}) are connected if there exists a sequence of empty cells that starts with (r_{1}, c_{1}), finishes with (r_{2}, c_{2}), and any two consecutive cells in this sequence are directly connected. A connected component is a set of empty cells such that any two cells in the component are connected, and there is no cell in this set that is connected to some cell not in this set.
Your friend Limak is a big grizzly bear. He is able to destroy any obstacles in some range. More precisely, you can choose a square of size k × k in the grid and Limak will transform all blocked cells there to empty ones. However, you can ask Limak to help only once.
The chosen square must be completely inside the grid. It's possible that Limak won't change anything because all cells are empty anyway.
You like big connected components. After Limak helps you, what is the maximum possible size of the biggest connected component in the grid?

Input
The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 500) — the size of the grid and Limak's range, respectively.
Each of the next n lines contains a string with n characters, denoting the i-th row of the grid. Each character is '.' or 'X', denoting an empty cell or a blocked one, respectively.

Output
Print the maximum possible size (the number of cells) of the biggest connected component, after using Limak's help.

Examples
Input
5 2
..XXX
XX.XX
X.XXX
X...X
XXXX.

Output
10

Input
5 3
.....
.XXX.
.XXX.
.XXX.
.....

Output
25

Note
In the first sample, you can choose a square of size 2 × 2. It's optimal to choose a square in the red frame on the left drawing below. Then, you will get a connected component with 10 cells, marked blue in the right drawing.
 ![image](1.png)

tags: ['Spanning trees', 'Graph traversal', 'Implementation']

raw_tags: ['dfs and similar', 'implementation', 'dsu']

data_split: test


solutions: ["for _ in range(int(input())):\n\ts = list(map(str, input().split()))\n\tfront = s[0]\n\tback = s[1]\n\tleft = s[2]\n\tright = s[3]\n\ttop = s[4]\n\tdown = s[5]\n\tif (front == left or front == right) and (front == top or front == down):\n\t\tprint('YES')\n\telif (back == left or back == right) and (back == top or back == down):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for t in range(int(input())):\n\ts = input().split()\n\t(d, loc, p) = ({}, [], 0)\n\tfor x in range(6):\n\t\tif s[x] in d:\n\t\t\td[s[x]].append(x)\n\t\telse:\n\t\t\td[s[x]] = [x]\n\tfor i in d:\n\t\tif len(d[i]) >= 3:\n\t\t\tloc = d[i]\n\t\t\tbreak\n\tfor l in range(0, 5, 2):\n\t\tif l in loc or l + 1 in loc:\n\t\t\tp += 1\n\tif p == 3:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "pairwise = [[0, 2, 4], [0, 3, 4], [1, 3, 4], [1, 2, 4], [0, 2, 5], [0, 3, 5], [1, 3, 5], [1, 2, 5]]\nfor _ in range(int(input())):\n\tc = input().split()\n\tans = 'NO'\n\tfor i in pairwise:\n\t\t(x, y, z) = i\n\t\tif c[x] == c[y] == c[z]:\n\t\t\tans = 'YES'\n\t\t\tbreak\n\tprint(ans)\n", "tests = int(input())\nfor i in range(tests):\n\tarr = list(input().split())\n\tans = 'NO'\n\tif (arr[0] == arr[2] or arr[0] == arr[3]) and (arr[0] == arr[4] or arr[0] == arr[5]):\n\t\tans = 'YES'\n\telif (arr[1] == arr[2] or arr[1] == arr[3]) and (arr[1] == arr[4] or arr[1] == arr[5]):\n\t\tans = 'YES'\n\tprint(ans)\n", "for _ in range(int(input())):\n\ta = input().split()\n\ty = 0\n\tif a[4] == a[0] == a[3]:\n\t\ty = 1\n\telif a[4] == a[0] == a[2]:\n\t\ty = 1\n\telif a[4] == a[1] == a[3]:\n\t\ty = 1\n\telif a[4] == a[1] == a[2]:\n\t\ty = 1\n\telif a[5] == a[0] == a[3]:\n\t\ty = 1\n\telif a[5] == a[0] == a[2]:\n\t\ty = 1\n\telif a[5] == a[1] == a[3]:\n\t\ty = 1\n\telif a[5] == a[1] == a[2]:\n\t\ty = 1\n\tif y == 1:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "import math\nimport sys\n\ndef _int():\n\treturn int(sys.stdin.readline())\n\ndef _ints():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef _intarr():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef _str():\n\treturn sys.stdin.readline()\n\ndef _strarr():\n\treturn sys.stdin.readline().split()\n\ndef adj(a, b, c):\n\tif b != opp[a] and b != opp[c] and (a != opp[c]):\n\t\treturn True\n\treturn False\nt = _int()\nopp = [1, 0, 3, 2, 5, 4]\nfor _ in range(t):\n\tc = _strarr()\n\tcd = dict()\n\tfor i in range(len(opp)):\n\t\tind = cd.get(c[i], [])\n\t\tind.append(i)\n\t\tcd[c[i]] = ind\n\tfound = False\n\tfor k in list(cd.keys()):\n\t\tind = cd.get(k, [])\n\t\tif len(ind) == 3:\n\t\t\tif adj(ind[0], ind[1], ind[2]):\n\t\t\t\tfound = True\n\t\telif len(ind) == 4:\n\t\t\tif adj(ind[0], ind[1], ind[2]):\n\t\t\t\tfound = True\n\t\t\telif adj(ind[0], ind[1], ind[3]):\n\t\t\t\tfound = True\n\t\t\telif adj(ind[0], ind[2], ind[3]):\n\t\t\t\tfound = True\n\t\t\telif adj(ind[1], ind[2], ind[3]):\n\t\t\t\tfound = True\n\t\telif len(ind) >= 5:\n\t\t\tfound = True\n\t\tif found:\n\t\t\tbreak\n\tprint('YES' if found else 'NO')\n", "for t in range(int(input())):\n\ttemp = list(input().split())\n\tfront = temp[0]\n\tback = temp[1]\n\tleft = temp[2]\n\tright = temp[3]\n\ttop = temp[4]\n\tbottom = temp[5]\n\tif left == top and left == front:\n\t\tprint('YES')\n\telif left == top and left == back:\n\t\tprint('YES')\n\telif left == bottom and left == front:\n\t\tprint('YES')\n\telif left == bottom and left == back:\n\t\tprint('YES')\n\telif right == top and right == front:\n\t\tprint('YES')\n\telif right == top and right == back:\n\t\tprint('YES')\n\telif right == bottom and right == front:\n\t\tprint('YES')\n\telif right == bottom and right == back:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nfor j in range(t):\n\t(f, ba, l, r, t, bo) = str(input()).split(' ')\n\tif l == f and f == bo:\n\t\tprint('YES')\n\telif l == f and l == t:\n\t\tprint('YES')\n\telif l == t and t == ba:\n\t\tprint('YES')\n\telif l == ba and ba == bo:\n\t\tprint('YES')\n\telif f == t and t == r:\n\t\tprint('YES')\n\telif t == ba and ba == r:\n\t\tprint('YES')\n\telif bo == r and r == f:\n\t\tprint('YES')\n\telif r == ba and ba == bo:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nfor _ in range(t):\n\ts = input().split()\n\td = {}\n\tfor i in range(6):\n\t\ttry:\n\t\t\td[s[i]].append(i)\n\t\texcept:\n\t\t\td[s[i]] = [i]\n\tflag = False\n\tfor i in list(d.keys()):\n\t\tif len(d[i]) >= 3:\n\t\t\tif 0 in d[i] or 1 in d[i]:\n\t\t\t\tif (3 in d[i] or 2 in d[i]) and (4 in d[i] or 5 in d[i]):\n\t\t\t\t\tflag = True\n\t\t\t\t\tbreak\n\tif flag:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "result = []\nfor _ in range(int(input())):\n\t(front, back, left, right, top, bottom) = input().split()\n\tif len(set([front, left, top])) == 1 or len(set([front, left, bottom])) == 1 or len(set([front, right, top])) == 1 or (len(set([front, right, bottom])) == 1) or (len(set([back, left, top])) == 1) or (len(set([back, left, bottom])) == 1) or (len(set([back, right, top])) == 1) or (len(set([back, right, bottom])) == 1):\n\t\tresult.append('YES')\n\telse:\n\t\tresult.append('NO')\nfor _ in result:\n\tprint(_)\n", "t = int(input())\nwhile t:\n\tt -= 1\n\ts = input()\n\t(front, back, left, right, top, bottom) = s.split()\n\tif front == left and front == bottom and (left == bottom) or (front == right and front == bottom and (right == bottom)) or (front == left and front == top and (left == top)) or (front == right and front == top and (right == top)) or (back == left and back == bottom and (left == bottom)) or (back == right and back == bottom and (right == bottom)) or (back == left and back == top and (left == top)) or (back == right and back == top and (right == top)):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\tl = list(map(str, input().split()))\n\ta = [(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]\n\tc = 0\n\tfor i in a:\n\t\tif len(set([l[i[0] - 1], l[i[1] - 1], l[i[2] - 1]])) == 1:\n\t\t\tc = 1\n\t\t\tbreak\n\tif c == 1:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "def check(color):\n\tfor f1 in [0, 1]:\n\t\tfor f2 in [2, 3]:\n\t\t\tfor f3 in [4, 5]:\n\t\t\t\tif color[f1] == color[f2] == color[f3]:\n\t\t\t\t\treturn 'YES'\n\treturn 'NO'\nt = int(input())\nwhile t > 0:\n\tcolors = input().split()\n\tprint(check(colors))\n\tt -= 1\n", "dic = {'f': 0, 'ba': 0, 'l': 0, 'r': 0, 't': 0, 'bo': 0}\nfor _ in range(int(input())):\n\tx = input().split()\n\tfor (i, j) in zip(dic, x):\n\t\tdic[i] = j[:3]\n\tif dic['t'] == dic['f'] == dic['r']:\n\t\tprint('YES')\n\telif dic['t'] == dic['f'] == dic['l']:\n\t\tprint('YES')\n\telif dic['t'] == dic['ba'] == dic['l']:\n\t\tprint('YES')\n\telif dic['t'] == dic['ba'] == dic['r']:\n\t\tprint('YES')\n\telif dic['bo'] == dic['f'] == dic['r']:\n\t\tprint('YES')\n\telif dic['bo'] == dic['f'] == dic['l']:\n\t\tprint('YES')\n\telif dic['bo'] == dic['ba'] == dic['l']:\n\t\tprint('YES')\n\telif dic['bo'] == dic['ba'] == dic['r']:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nfor i in range(t):\n\tl = list(map(str, input().split()))\n\t(c, count) = (0, 0)\n\tif l[0] in l[2:4]:\n\t\tcount += 1\n\tif l[0] in l[4:]:\n\t\tcount += 1\n\tif l[1] in l[2:4]:\n\t\tc += 1\n\tif l[1] in l[4:]:\n\t\tc += 1\n\tif c == 2 or count == 2:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\t(f, b, l, r, t, d) = input().split()\n\tans = False\n\tif (f == l or f == r) and (f == t or f == d):\n\t\tans = True\n\tif (b == l or b == r) and (b == t or b == d):\n\t\tans = True\n\tif (t == l or t == r) and (t == f or t == b):\n\t\tans = True\n\tif (d == l or d == r) and (d == f or d == b):\n\t\tans = True\n\tif (l == f or l == b) and (l == t or l == d):\n\t\tans = True\n\tif (r == f or r == b) and (r == t or r == d):\n\t\tans = True\n\tprint('YES' if ans else 'NO')\n", "for _ in range(int(input())):\n\tl = list(map(str, input().split()))\n\t(a, b) = (l[0], l[1])\n\t(i, s1, s2) = (2, 0, 0)\n\twhile i < 6:\n\t\tif a in l[i:i + 2]:\n\t\t\ts1 += 1\n\t\tif b in l[i:i + 2]:\n\t\t\ts2 += 1\n\t\ti += 2\n\tif s1 > 1 or s2 > 1:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "str = input()\nT = int(str)\nfor ti in range(T):\n\tcan = False\n\tstr = input()\n\tS = str.split(' ')\n\ts = [[S[0], S[1]], [S[2], S[3]], [S[4], S[5]]]\n\tfor x in (0, 1):\n\t\tfor y in (0, 1):\n\t\t\tfor z in (0, 1):\n\t\t\t\tif s[0][x] == s[1][y] == s[2][z]:\n\t\t\t\t\tcan = True\n\tif can:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\tl = list(input().split())\n\ts1 = []\n\ts2 = []\n\ts3 = []\n\tfor i in range(6):\n\t\tif i <= 1:\n\t\t\ts1.append(l[i])\n\t\telif i <= 3:\n\t\t\ts2.append(l[i])\n\t\telse:\n\t\t\ts3.append(l[i])\n\tcolour = ['black', 'blue', 'red', 'green', 'yellow', 'orange']\n\tfor i in colour:\n\t\tif i in s1 and i in s2 and (i in s3):\n\t\t\tprint('YES')\n\t\t\tbreak\n\telse:\n\t\tprint('NO')\n", "indices = [[0, 2, 4], [0, 3, 4], [0, 2, 5], [0, 3, 5], [1, 2, 4], [1, 3, 4], [1, 2, 5], [1, 3, 5]]\nfor _ in range(int(input())):\n\tcolor = list(map(str, input().split()))\n\tans = 'NO'\n\tfor i in range(8):\n\t\tif color[indices[i][0]] == color[indices[i][1]] == color[indices[i][2]]:\n\t\t\tans = 'YES'\n\t\t\tbreak\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\tl = list(map(str, input().strip().split()))\n\tk = max(set(l), key=l.count)\n\tp = l.count(k)\n\tif (l[0] == k or l[1] == k) and (l[2] == k or l[3] == k) and (l[4] == k or l[5] == k) and (p >= 3):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nfor _ in range(t):\n\ts = input().split(' ')\n\tflag = 0\n\tif s[0] == s[2]:\n\t\tif s[0] == s[4] or s[0] == s[5]:\n\t\t\tflag = 1\n\tif s[0] == s[3]:\n\t\tif s[0] == s[4] or s[0] == s[5]:\n\t\t\tflag = 1\n\tif s[1] == s[2]:\n\t\tif s[1] == s[4] or s[1] == s[5]:\n\t\t\tflag = 1\n\tif s[1] == s[3]:\n\t\tif s[1] == s[4] or s[1] == s[5]:\n\t\t\tflag = 1\n\tif flag == 0:\n\t\tprint('NO')\n\telse:\n\t\tprint('YES')\n", "ujju = int(input())\nfor sai in range(ujju):\n\tu1 = list(map(str, input().split()))\n\th = max(set(u1), key=u1.count)\n\tg = u1.count(h)\n\tif (u1[0] == h or u1[1] == h) and (u1[2] == h or u1[3] == h) and (u1[4] == h or u1[5] == h) and (g >= 3):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "a = int(input(''))\nfor i in range(a):\n\t(F, Ba, L, R, T, B) = map(str, input('').split())\n\tif F == L == B or F == R == B or F == T == L or (F == T == R) or (Ba == L == B) or (Ba == R == B) or (Ba == T == L) or (Ba == T == R):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "def get_answer(cube):\n\tif cube[0] in cube[2:4] and cube[0] in cube[4:len(cube)]:\n\t\treturn 'YES'\n\telif cube[1] in cube[2:4] and cube[1] in cube[4:len(cube)]:\n\t\treturn 'YES'\n\treturn 'NO'\ntest_case = int(input())\nfor i in range(0, test_case):\n\tcube = input().split(' ')\n\tprint(get_answer(cube))\n", "T = int(input())\nwhile T > 0:\n\ta = list(map(str, input().split()))\n\tp = 0\n\tif a[5] == a[0] and a[5] == a[2]:\n\t\tp = 1\n\tif a[5] == a[2] and a[5] == a[1]:\n\t\tp = 1\n\tif a[5] == a[1] and a[5] == a[3]:\n\t\tp = 1\n\tif a[5] == a[0] and a[5] == a[3]:\n\t\tp = 1\n\tif a[4] == a[0] and a[4] == a[2]:\n\t\tp = 1\n\tif a[4] == a[2] and a[4] == a[1]:\n\t\tp = 1\n\tif a[4] == a[1] and a[4] == a[3]:\n\t\tp = 1\n\tif a[4] == a[0] and a[4] == a[3]:\n\t\tp = 1\n\tif p:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n\tT = T - 1\n", "class Cube(object):\n\n\tdef __init__(self, front, back, left, right, top, bottom):\n\t\tself.front = front\n\t\tself.back = back\n\t\tself.left = left\n\t\tself.right = right\n\t\tself.top = top\n\t\tself.bottom = bottom\nT = int(input())\nfor _ in range(T):\n\t(front, back, left, right, top, bottom) = input().split()\n\tcube = Cube(front, back, left, right, top, bottom)\n\tdel front, back, left, right, top, bottom\n\tcubePairs = [{cube.front, cube.back}, {cube.left, cube.right}, {cube.top, cube.bottom}]\n\tif len(cubePairs[0] & cubePairs[1] & cubePairs[2]) > 0:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\t(f, b, l, r, t, bt) = [str(i) for i in input().split()]\n\tif (f == l or f == r) and (f == t or f == bt) or ((b == l or b == r) and (b == t or b == bt)):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "import collections\nfor _ in range(int(input())):\n\t(f, ba, l, r, t, b) = [x for x in input().split()]\n\tif l == f == b or l == f == t or l == ba == b or (l == ba == t) or (r == f == b) or (r == f == t) or (r == ba == b) or (r == ba == t):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nfor i in range(t):\n\ts = list(map(str, input().split()))\n\tif s[0] == s[3] == s[-1] or s[0] == s[3] == s[-2] or s[0] == s[2] == s[-1] or (s[0] == s[2] == s[-2]):\n\t\tprint('YES')\n\telif s[1] == s[3] == s[-1] or s[1] == s[3] == s[-2] or s[1] == s[2] == s[-1] or (s[1] == s[2] == s[-2]):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\t(front, back, left, right, top, bottom) = map(str, input().split())\n\tans = 'NO'\n\tif (front == left or front == right) and (front == top or front == bottom):\n\t\tans = 'YES'\n\telif (back == left or back == right) and (back == top or back == bottom):\n\t\tans = 'YES'\n\tprint(ans)\n", "T = int(input())\nfor t in range(T):\n\tcolor = input().split()\n\ts1 = color[:2]\n\ts2 = color[2:4]\n\ts3 = color[4:6]\n\tbo = False\n\tfor i in range(2):\n\t\tfor j in range(2):\n\t\t\tfor k in range(2):\n\t\t\t\tif s1[i] == s2[j] == s3[k]:\n\t\t\t\t\tbo = True\n\tif bo:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nfor i in range(t):\n\t(a, b, c, d, e, f) = input().split()\n\tif (a == c or a == d) and (a == e or a == f):\n\t\tprint('YES')\n\telif (b == c or b == d) and (b == e or b == f):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "l = [[0, 4, 2], [0, 4, 3], [0, 5, 2], [0, 5, 3], [1, 4, 2], [1, 4, 3], [1, 5, 2], [1, 5, 3]]\n\ndef check():\n\tinp = input().split(' ')\n\tfor [i, j, k] in l:\n\t\tif inp[i] == inp[j] and inp[j] == inp[k]:\n\t\t\treturn 'YES'\n\treturn 'NO'\n\ndef main():\n\tt = int(input())\n\twhile t > 0:\n\t\tprint(check())\n\t\tt -= 1\n\treturn\nmain()\n", "list_triplets = [('front', 'left', 'top'), ('top', 'left', 'back'), ('top', 'right', 'back'), ('front', 'right', 'top'), ('front', 'left', 'bottom'), ('bottom', 'left', 'back'), ('bottom', 'right', 'back'), ('front', 'right', 'bottom')]\ninput_order = ['front', 'back', 'left', 'right', 'top', 'bottom']\nn = input()\nfor _ in range(int(n)):\n\tcolors = input()\n\tcolors = colors.split()\n\tcolor_map = {side: color for (side, color) in zip(input_order, colors)}\n\tflag = False\n\tfor triplet in list_triplets:\n\t\tcurrent_color = None\n\t\ttriplet_flag = True\n\t\tfor side in triplet:\n\t\t\tif current_color is None:\n\t\t\t\tcurrent_color = color_map.get(side)\n\t\t\tif current_color != color_map.get(side):\n\t\t\t\ttriplet_flag = False\n\t\tif triplet_flag is True:\n\t\t\tflag = True\n\tif flag is True:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "n = int(input())\nfor i in range(n):\n\tl = input().split()\n\tc = 0\n\tc1 = 0\n\tif l[0] in l[2:4]:\n\t\tc1 += 1\n\tif l[0] in l[4:]:\n\t\tc1 += 1\n\tif l[1] in l[2:4]:\n\t\tc += 1\n\tif l[1] in l[4:]:\n\t\tc += 1\n\tprint('YES' if c == 2 or c1 == 2 else 'NO')\n", "T = int(input())\nii = 0\nwhile ii < T:\n\tsides = str(input())\n\tsides = sides.split()\n\tdice = {}\n\tcorners = [[0, 4, 3], [0, 3, 5], [0, 5, 2], [0, 2, 4], [1, 4, 3], [1, 3, 5], [1, 5, 2], [1, 2, 4]]\n\tflag = 0\n\ti = 0\n\twhile i < 8:\n\t\ttrip = corners[i]\n\t\tif sides[corners[i][0]] == sides[corners[i][1]] and sides[corners[i][0]] == sides[corners[i][2]]:\n\t\t\tflag = 1\n\t\t\tbreak\n\t\telse:\n\t\t\ti += 1\n\tif flag:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n\tii += 1\n", "for _ in range(int(input())):\n\t(front, back, left, right, top, bottom) = input().split()\n\tif front == left == top or front == left == bottom or front == right == top or (front == right == bottom) or (back == left == top) or (back == left == bottom) or (back == right == top) or (back == right == bottom):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for t in range(int(input())):\n\tc = list(map(str, input().split()))\n\tif c[0] == c[2] == c[5] or c[0] == c[5] == c[3] or c[5] == c[3] == c[1] or (c[5] == c[1] == c[2]) or (c[0] == c[2] == c[4]) or (c[0] == c[4] == c[3]) or (c[4] == c[3] == c[1]) or (c[4] == c[1] == c[2]):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "T = int(input())\nwhile T > 0:\n\ta = list(map(str, input().split()))\n\tp = 0\n\tfor i in range(4, 6):\n\t\tif a[i] == a[0] and a[i] == a[2]:\n\t\t\tp = 1\n\t\telif a[i] == a[2] and a[i] == a[1]:\n\t\t\tp = 1\n\t\telif a[i] == a[1] and a[i] == a[3]:\n\t\t\tp = 1\n\t\telif a[i] == a[0] and a[i] == a[3]:\n\t\t\tp = 1\n\tif p:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n\tT = T - 1\n", "import math\nt = int(input())\nwhile t >= 1:\n\ta = input()\n\ta = a.split()\n\ty = 0\n\tif a[4] == a[0] == a[3]:\n\t\ty = 1\n\telif a[4] == a[0] == a[2]:\n\t\ty = 1\n\telif a[4] == a[1] == a[3]:\n\t\ty = 1\n\telif a[4] == a[1] == a[2]:\n\t\ty = 1\n\telif a[5] == a[0] == a[3]:\n\t\ty = 1\n\telif a[5] == a[0] == a[2]:\n\t\ty = 1\n\telif a[5] == a[1] == a[3]:\n\t\ty = 1\n\telif a[5] == a[1] == a[2]:\n\t\ty = 1\n\tif y == 1:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n\tt = t - 1\n", "base = ((0, 2), (0, 3), (1, 2), (1, 3))\nfor _ in range(int(input())):\n\tc = list(input().split())\n\tans = 'NO'\n\tfor b in base:\n\t\tif c[b[0]] == c[b[1]]:\n\t\t\tif c[b[0]] == c[4] or c[b[0]] == c[5]:\n\t\t\t\tans = 'YES'\n\t\t\t\tbreak\n\tprint(ans)\n", "def buildTriples():\n\ttriples = [[] for _ in range(8)]\n\ttriples[0] = [0, 2, 4]\n\ttriples[1] = [1, 2, 4]\n\ttriples[2] = [1, 3, 4]\n\ttriples[3] = [0, 3, 4]\n\ttriples[4] = [0, 2, 5]\n\ttriples[5] = [1, 2, 5]\n\ttriples[6] = [1, 3, 5]\n\ttriples[7] = [0, 3, 5]\n\treturn triples\n\ndef solve(triples, a):\n\tfor t in triples:\n\t\tif a[t[0]] == a[t[1]] == a[t[2]]:\n\t\t\treturn 'YES'\n\treturn 'NO'\nT = int(input())\ntriples = buildTriples()\nfor _ in range(T):\n\tprint(solve(triples, input().split()))\n", "from collections import Counter\nt = int(input())\nflag = 0\nfor i in range(1, t + 1):\n\tflag = 0\n\ta = input().split()\n\tb = Counter(a)\n\tfor color in ['black', 'blue', 'red', 'green', 'yellow', 'orange']:\n\t\tif b[color] >= 3:\n\t\t\tif (a[0] == color or a[1] == color) and (a[2] == color or a[3] == color) and (a[4] == color or a[5] == color):\n\t\t\t\tprint('YES')\n\t\t\t\tflag = 1\n\t\t\t\tbreak\n\tif flag == 0:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\t(f, ba, l, r, t, bo) = input().split()\n\tif (f == l or f == r) and (f == t or f == bo) or ((ba == l or ba == r) and (ba == t or ba == bo)):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "color_list = ['black', 'blue', 'red', 'green', 'yellow', 'orange']\nfor _ in range(int(input())):\n\tans = 'NO'\n\tpainted = input().split()\n\t(fb, lr, tb) = (painted[:2], painted[2:4], painted[4:6])\n\tfor i in color_list:\n\t\tif i in fb and i in lr and (i in tb):\n\t\t\tans = 'YES'\n\t\t\tbreak\n\tprint(ans)\n", "T = int(input())\nfor i in range(0, T):\n\t(f, b, l, r, t, bo) = map(str, input().split())\n\tif (f == l or f == r) and (f == t or f == bo):\n\t\tprint('YES')\n\telif (b == l or b == r) and (b == t or b == bo):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nwhile t > 0:\n\ts = input().split()\n\ta = 0\n\tif s[0] == s[2] == s[4]:\n\t\ta = 1\n\telif s[0] == s[3] == s[4]:\n\t\ta = 1\n\telif s[0] == s[3] == s[5]:\n\t\ta = 1\n\telif s[0] == s[2] == s[5]:\n\t\ta = 1\n\telif s[1] == s[3] == s[4]:\n\t\ta = 1\n\telif s[1] == s[2] == s[4]:\n\t\ta = 1\n\telif s[1] == s[3] == s[5]:\n\t\ta = 1\n\telif s[1] == s[2] == s[5]:\n\t\ta = 1\n\tif a == 1:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n\tt = t - 1\n", "def check(s1, s2, s3):\n\tif s1 == s2 and s2 == s3 and (s3 == s1):\n\t\treturn True\n\telse:\n\t\treturn False\nfor _ in range(int(input())):\n\t(f, b, l, r, t, bo) = input().split()\n\tif check(f, t, l) or check(f, t, r) or check(f, bo, l) or check(f, bo, r) or check(b, t, l) or check(b, t, r) or check(b, bo, l) or check(b, bo, r):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\tList = [str(x) for x in input().split()]\n\tif List[0] == List[3] == List[4] or List[0] == List[3] == List[5] or List[0] == List[2] == List[4] or (List[0] == List[2] == List[5]) or (List[1] == List[3] == List[4]) or (List[1] == List[3] == List[5]) or (List[1] == List[2] == List[4]) or (List[1] == List[2] == List[5]):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\tarr = list(map(str, input().split()))\n\t(front, back, left, right, top, bottom) = arr\n\tif front == right == bottom or front == right == top or front == left == bottom or (front == left == top):\n\t\tprint('YES')\n\telif back == left == top or front == left == top or top == front == right or (right == back == top):\n\t\tprint('YES')\n\telif right == back == top or right == front == top or bottom == front == right or (right == back == bottom):\n\t\tprint('YES')\n\telif bottom == front == right or bottom == left == front or bottom == back == left or (bottom == back == right):\n\t\tprint('YES')\n\telif left == back == top or bottom == left == back or bottom == front == left or (left == front == top):\n\t\tprint('YES')\n\telif back == top == right or back == left == top or bottom == back == left or (bottom == back == right):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nfor ni in range(t):\n\ts = input().split()\n\t(f, b) = (s[0], s[1])\n\tl1 = [s[2], s[3]]\n\tl2 = [s[4], s[5]]\n\tif f in l1 and f in l2:\n\t\tprint('YES')\n\telif b in l1 and b in l2:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = int(input())\nfor k in range(t):\n\t(f, b, l, r, t, d) = map(str, input().split())\n\tif t == f and t == l or (t == f and t == r):\n\t\tprint('YES')\n\telif f == d and d == l or (f == d and d == r):\n\t\tprint('YES')\n\telif b == d and d == l or (b == d and d == r):\n\t\tprint('YES')\n\telif b == t and t == r or (b == t and t == l):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "T = int(input())\nfor _ in range(T):\n\tl = list(map(str, input().split()))\n\tL = [[0, 2, 4], [0, 3, 4], [0, 2, 5], [0, 3, 5], [1, 2, 4], [1, 3, 4], [1, 2, 5], [1, 3, 5]]\n\tf = 1\n\tfor i in range(8):\n\t\tl1 = L[i]\n\t\tif l[l1[0]] == l[l1[1]] and l[l1[0]] == l[l1[2]]:\n\t\t\tprint('YES')\n\t\t\tf = 0\n\t\t\tbreak\n\tif f == 1:\n\t\tprint('NO')\n", "for _ in range(int(input())):\n\tl = list(map(str, input().split()))\n\tif l[0] == l[2] and l[2] == l[5] or (l[0] == l[2] and l[2] == l[4]) or (l[0] == l[3] and l[3] == l[5]) or (l[0] == l[3] and l[3] == l[4]) or (l[1] == l[2] and l[2] == l[5]) or (l[1] == l[2] and l[2] == l[4]) or (l[1] == l[3] and l[3] == l[5]) or (l[1] == l[3] and l[3] == l[4]):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "t = input()\nfor c in range(0, int(t)):\n\tarr = list(input().split())\n\tans = 'NO'\n\tif (arr[0] == arr[2] or arr[0] == arr[3]) and (arr[0] == arr[4] or arr[0] == arr[5]):\n\t\tans = 'YES'\n\telif (arr[1] == arr[2] or arr[1] == arr[3]) and (arr[1] == arr[4] or arr[1] == arr[5]):\n\t\tans = 'YES'\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\t(col1, col2, col3, col4, col5, col6) = input().split()\n\tif set([col1, col2]) & set([col3, col4]) & set([col5, col6]):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "T = int(input())\nfor i in range(T):\n\tC = input().split()\n\tif C[0] == C[2] == C[4] or C[0] == C[2] == C[5] or C[0] == C[3] == C[4] or (C[0] == C[3] == C[5]) or (C[1] == C[2] == C[4]) or (C[1] == C[2] == C[5]) or (C[1] == C[3] == C[4]) or (C[1] == C[3] == C[5]):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "for tc in range(int(input())):\n\t(front, back, left, right, top, bottom) = input().split()\n\tpossible = {'black', 'blue', 'red', 'green', 'yellow', 'orange'}\n\tans = 'NO'\n\t(f1, f2, b1, b2) = (False, False, False, False)\n\tif front in (left, right):\n\t\tf1 = True\n\tif front in (top, bottom):\n\t\tf2 = True\n\tif back in (left, right):\n\t\tb1 = True\n\tif back in (top, bottom):\n\t\tb2 = True\n\tif f1 and f2:\n\t\tans = 'YES'\n\tif b1 and b2:\n\t\tans = 'YES'\n\tprint(ans)\n", "from collections import *\nfor u in range(int(input())):\n\tl = input().split()\n\tC = l\n\tif C[0] == C[2] == C[4] or C[0] == C[2] == C[5] or C[0] == C[3] == C[4] or (C[0] == C[3] == C[5]) or (C[1] == C[2] == C[4]) or (C[1] == C[2] == C[5]) or (C[1] == C[3] == C[4]) or (C[1] == C[3] == C[5]):\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "listk = []\nfor _ in range(int(input())):\n\tcc = input().split()\n\tcc1 = set(cc[0:2])\n\tcc2 = set(cc[2:4])\n\tcc3 = set(cc[4:])\n\tif cc1.intersection(cc2.intersection(cc3)) != set():\n\t\tlistk.append('YES')\n\telse:\n\t\tlistk.append('NO')\nfor ele in listk:\n\tprint(ele)\n"]

input_output: {"inputs": [["2", "blue yellow green orange black green", "green yellow green orange black green"], "2\nblue yellow green orange black green\ngreen yellow green orange black green"], "outputs": [["NO", "YES"], "NO\nYES\n"]}

difficulty: EASY

raw_tags: ['Case work', 'Special', 'Implementation', 'Algorithms']

source: codechef

time_limit: 1 seconds

memory_limit: 50000 bytes

raw_problem:
Read problems statements in Mandarin Chinese  and Russian.

One day, Chef found a cube which has each of its sides painted in some color out of black, blue, red, green, yellow and orange.

Now he asks you to check if he can choose three sides such that they are pairwise adjacent and painted in the same color.

Input

The first line of the input contains an integer T denoting the number of test cases.

A single line of each test case contains six words denoting the colors of painted sides in the order: front, back, left, right, top and bottom, respectively.

Output

For each test case, output a single line containing the word "YES" or "NO" (without quotes) corresponding to the answer of the problem.

Constraints

1 ≤ T ≤  50000

Each color will be from the list {"black", "blue", "red", "green", "yellow", "orange"}

Subtasks

Subtask 1: (25 points)

1 ≤ T ≤  12000

For each test case there will be at most three different colors

Subtask 2: (75 points)

Original constraints

Example

Input:
2
blue yellow green orange black green
green yellow green orange black green

Output:
NO
YES

Explanation

Example case 1.

There are no three sides with the same color.

Example case 2.

In this test case, the front, bottom and left sides are green (see picture).

All submissions for this problem are available.

question:
Read problems statements in Mandarin Chinese  and Russian.
One day, Chef found a cube which has each of its sides painted in some color out of black, blue, red, green, yellow and orange.
Now he asks you to check if he can choose three sides such that they are pairwise adjacent and painted in the same color.
Input

- The first line of the input contains an integer T denoting the number of test cases.
- A single line of each test case contains six words denoting the colors of painted sides in the order: front, back, left, right, top and bottom, respectively.

Output
For each test case, output a single line containing the word "YES" or "NO" (without quotes) corresponding to the answer of the problem.
Constraints

- 1 ≤ T ≤  50000
- Each color will be from the list {"black", "blue", "red", "green", "yellow", "orange"}

Subtasks
Subtask 1: (25 points)

- 1 ≤ T ≤  12000
- For each test case there will be at most three different colors

Subtask 2: (75 points)

- Original constraints

Example
Input:
2
blue yellow green orange black green
green yellow green orange black green

Output:
NO
YES

Explanation

Example case 1.
There are no three sides with the same color.
![image](1.png)
Example case 2.
In this test case, the front, bottom and left sides are green (see picture).
![image](2.png)
All submissions for this problem are available.

image_tags:
3D Geometry
3D Geometry

data_split: test


I. Imagination Castle

problem_raw:
I. Imagination Castle

time limit per test
2 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

Given a chessboard of size $$$N \times M$$$ ($$$N$$$ rows and $$$M$$$ columns). Each row is numbered from $$$1$$$ to $$$N$$$ from top to bottom and each column is numbered from $$$1$$$ to $$$M$$$ from left to right. The tile in row $$$r$$$ and column $$$c$$$ is denoted as $$$(r,c)$$$. There exists $$$K$$$ distinct special tiles on the chessboard with the $$$i$$$-th special tile being tile $$$(X_i,Y_i)$$$. It is guaranteed that tile $$$(1,1)$$$ is not a special tile.

A new chess piece has been invented, which is the castle. The castle moves similarly to a rook in regular chess, but slightly differently. In one move, a castle that is on some tile can only move to another tile in the same row or in the same column, but only in the right direction or the down direction. Formally, in one move, the castle on tile $$$(r,c)$$$ can only move to tile $$$(r',c')$$$ if and only if one of the following two conditions is satisfied:

 $$$r'=r$$$ and $$$c'>c$$$.

 $$$c'=c$$$ and $$$r'>r$$$.

Chaneka and Bhinneka will play a game. In the beginning of the game, there is a castle in tile $$$(1,1)$$$. The two players will play alternatingly with Chaneka going first. In one turn, the player on that turn must move the castle following the movement rules of the castle.

If a player moves the castle to a special tile on her turn, then that player wins the game and the game ends. If on a turn, the castle cannot be moved, the player on that turn loses and the game ends.

Given the size of the board and the locations of each special tile. Determine the winner of this game if Chaneka and Bhinneka plays optimally.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$1 \leq N,M \leq 2 \cdot 10^5$$$; $$$0 \leq K \leq \min(N \times M - 1, 2\cdot10^5)$$$) — the size of the chessboard and the number of special tiles.

The $$$i$$$-th of the next $$$K$$$ lines contains two integers $$$X_i$$$ and $$$Y_i$$$ ($$$1\leq X_i\leq N$$$; $$$1\leq Y_i\leq M$$$; $$$(X_i, Y_i) \neq (1,1)$$$) — the location of each special tile. The special tiles are pairwise distinct.

Output

Output Chaneka if Chaneka is the winner, output Bhinneka if Bhinneka is the winner.

Examples

Input

4 5 3
1 3
4 4
1 5

Output

Chaneka

Input

2 2 0

Output

Bhinneka

Note

In the first example, the following is an illustration of the chessboard in the beginning of the game.

Chaneka can move the castle to special tile $$$(1,3)$$$ or $$$(1,5)$$$ directly on her first turn. Therefore, Chaneka is the winner.

In the second example, the following is an illustration of the chessboard in the beginning of the game.

Chaneka can only move the castle to tile $$$(1, 2)$$$ or $$$(2, 1)$$$ on her first turn. Whatever Chaneka does, Bhinneka will be able to directly move the castle to tile $$$(2, 2)$$$. After that, on Chaneka's turn, she cannot move the castle, so Chaneka loses. Therefore, Bhinneka is the winner.

problem_index: I

time_limit: 2 seconds

memory_limit: 512 megabytes

input:
4 5 3
1 3
4 4
1 5

output: Chaneka

input: 2 2 0

output: Bhinneka

question:
Given a chessboard of size $$$N \times M$$$ ($$$N$$$ rows and $$$M$$$ columns). Each row is numbered from $$$1$$$ to $$$N$$$ from top to bottom and each column is numbered from $$$1$$$ to $$$M$$$ from left to right. The tile in row $$$r$$$ and column $$$c$$$ is denoted as $$$(r,c)$$$. There exists $$$K$$$ distinct special tiles on the chessboard with the $$$i$$$-th special tile being tile $$$(X_i,Y_i)$$$. It is guaranteed that tile $$$(1,1)$$$ is not a special tile.
A new chess piece has been invented, which is the castle. The castle moves similarly to a rook in regular chess, but slightly differently. In one move, a castle that is on some tile can only move to another tile in the same row or in the same column, but only in the right direction or the down direction. Formally, in one move, the castle on tile $$$(r,c)$$$ can only move to tile $$$(r',c')$$$ if and only if one of the following two conditions is satisfied:
 -  $$$r'=r$$$ and $$$c'>c$$$. -  $$$c'=c$$$ and $$$r'>r$$$. Chaneka and Bhinneka will play a game. In the beginning of the game, there is a castle in tile $$$(1,1)$$$. The two players will play alternatingly with Chaneka going first. In one turn, the player on that turn must move the castle following the movement rules of the castle.
If a player moves the castle to a special tile on her turn, then that player wins the game and the game ends. If on a turn, the castle cannot be moved, the player on that turn loses and the game ends.
Given the size of the board and the locations of each special tile. Determine the winner of this game if Chaneka and Bhinneka plays optimally.

Input
The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$1 \leq N,M \leq 2 \cdot 10^5$$$; $$$0 \leq K \leq \min(N \times M - 1, 2\cdot10^5)$$$) — the size of the chessboard and the number of special tiles.
The $$$i$$$-th of the next $$$K$$$ lines contains two integers $$$X_i$$$ and $$$Y_i$$$ ($$$1\leq X_i\leq N$$$; $$$1\leq Y_i\leq M$$$; $$$(X_i, Y_i) \neq (1,1)$$$) — the location of each special tile. The special tiles are pairwise distinct.

Output
Output Chaneka if Chaneka is the winner, output Bhinneka if Bhinneka is the winner.

Examples
Input

4 5 3
1 3
4 4
1 5

Output

Chaneka

Input

2 2 0

Output

Bhinneka

Note
In the first example, the following is an illustration of the chessboard in the beginning of the game.
 ![image](1.png)
Chaneka can move the castle to special tile $$$(1,3)$$$ or $$$(1,5)$$$ directly on her first turn. Therefore, Chaneka is the winner.
In the second example, the following is an illustration of the chessboard in the beginning of the game.
 ![image](2.png)
Chaneka can only move the castle to tile $$$(1, 2)$$$ or $$$(2, 1)$$$ on her first turn. Whatever Chaneka does, Bhinneka will be able to directly move the castle to tile $$$(2, 2)$$$. After that, on Chaneka's turn, she cannot move the castle, so Chaneka loses. Therefore, Bhinneka is the winner.

source: codeforces

image_tags: Chessboard Chessboard

data_split: test