A. Accumulation of Dominoes

problem_index: A

time_limit: 1 second

memory_limit: 256 megabytes

note:
The picture below is the grid that Pak Chanek has in the first example.
![image](images/cf_1725_A/1.png)
The picture below is an example of a tight domino in the grid.
![image](images/cf_1725_A/2.png)

solutions: ["(n, m) = map(int, input().split())\nif m == 1:\n\tprint(n - 1)\nelse:\n\tprint((m - 1) * n)\n", "value = input()\nnums = value.split(' ')\nN = int(nums[0])\nM = int(nums[1])\nres = 0\nif M >= 2:\n\tres += (M - 1) * N\nelif M == 1 and N > 1:\n\tres = N - 1\nelse:\n\tres = 0\nprint(res)\n", "(r, c) = map(int, input().split())\nif c == 1:\n\tprint(r - 1)\nelse:\n\tprint((c - 1) * r)\n", "(n, m) = input().split(' ')\nn = int(n)\nm = int(m)\nc = (m - 1) * n\nif m == 1:\n\tc += (n - 1) * m\nif m <= 0 or n <= 0:\n\tc = 0\nprint(c)\n", "temp = input()\ntemp1 = temp.split()\na = int(temp1[0])\nb = int(temp1[1])\nif b == 1:\n\tprint((a - 1) * b)\nelse:\n\tprint((b - 1) * a)\n", "(N, M) = map(int, input().split())\nif M > 1:\n\tprint(N * (M // 2 + (M - 1) // 2))\nelse:\n\tprint(N // 2 + (N - 1) // 2)\n", "(a, b) = [int(i) for i in input().split()]\nif b == 1:\n\tprint(a - 1)\nelse:\n\tprint(a * (b - 1))\n", "(row, column) = input().split()\nrow = int(row)\ncolumn = int(column)\nif column == 1:\n\tprint(row - 1)\nelse:\n\tprint((column - 1) * row)\n", "def solve():\n\t(n, m) = map(int, input().split())\n\tprint(n * (m - 1)) if n != 1 and m != 1 else print(m * n - 1)\nsolve()\n", "(a, b) = map(int, input().split())\nif b == 1:\n\tprint(a - 1)\nelse:\n\tprint(a * (b - 1))\n", "(n, m) = map(int, input().split())\nprint(n * (m - 1) + (n - 1) * (m == 1))\n", "(N, M) = input().split()\nN = int(N)\nM = int(M)\nx = ''\nif M > 1:\n\tx = N * (M - 1)\nelif M == 1:\n\tx = N - 1\nelse:\n\tpass\nprint(x)\n", "(n, m) = map(int, input().split())\nif n == m == 1:\n\tprint(0)\nelif m == 1:\n\tprint(n - 1)\nelif n == 1:\n\tprint(m - 1)\nelse:\n\tprint((m - 1) * n)\n", "(y, x) = map(int, input().split())\nprint(y - 1 if x == 1 else y * (x - 1))\n", "(x, y) = list(map(int, input().split()))\nif x >= y:\n\tif x % 2 == 0 and y % 2 == 0 or (x % 2 == 1 and y % 2 == 0):\n\t\tprint(x * (y - 1))\n\telse:\n\t\tprint((x - 1) * y)\nelif x < y:\n\tprint(x * (y - 1))\nelse:\n\tprint(x * (x - 1))\n", "(n, k) = map(int, input().split())\na = 0\nif n > k and k == 1:\n\ta = (n - 1) * 1\nelif n > k and k != 1:\n\ta = (k - 1) * n\nelif k > n:\n\ta = (k - 1) * n\nif n == k:\n\ta = (k - 1) * n\nprint(a)\n", "(n, m) = (int(i) for i in input().split())\nif m > 1:\n\tprint(n * (m - 1))\nelse:\n\tprint(n - 1)\n", "(n, m) = [int(x) for x in input().split()]\nif m == 1:\n\tprint(n - 1)\nelse:\n\tprint(n * (m - 1))\n", "(n, m) = map(int, input().split())\nif m == 1:\n\tprint(n - 1)\nelif m == 2:\n\tprint(n)\nelse:\n\tprint((m - 1) * n)\n", "(n, m) = map(int, input().split())\nans = 0\nif m == 1:\n\tans = (n - 1) * m\nelse:\n\tans = (m - 1) * n\nprint(ans)\n", "NM = input()\nN = int(NM.split(' ')[0])\nM = int(NM.split(' ')[1])\nif M == 1:\n\tprint(N - 1)\nelse:\n\tprint(N * (M - 1))\n", "a = input('')\nb = a.split()\nc = map(int, b)\nn = int(b[0])\nm = int(b[1])\nif m == 1:\n\tprint(n - 1)\nelse:\n\tprint(n * (m - 1))\n", "(N, M) = map(int, input().split())\nif M != 1:\n\tcount = (M - 1) * N\nelse:\n\tcount = N - 1\nprint(count)\n", "(n, m) = map(int, input().split())\nrowdom = m - 1\ncolumndom = 0\nif m == 1:\n\tcolumndom = n - 1\nres = rowdom * n + m * columndom\nprint(res)\n", "(row, col) = map(int, input().split())\nif col > 1:\n\tprint(row * (col - 1))\nelse:\n\tprint(row - 1)\n", "(n, m) = input().split()\nn = int(n)\nm = int(m)\nif n == 1 and m == 1:\n\tprint(n - 1)\nelif n == 1:\n\tprint(m - 1)\nelif m == 1:\n\tprint(n - 1)\nelse:\n\tprint((m - 1) * n)\n", "def tight_dominos(m, n):\n\tif m == 1 and n == 1:\n\t\treturn 0\n\telif m == 1:\n\t\treturn n - 1\n\telif n == 1:\n\t\treturn m - 1\n\telse:\n\t\treturn (n - 1) * m\n(x, y) = input('').split()\na = int(x)\nb = int(y)\nprint(tight_dominos(a, b))\n", "import sys\n(n, m) = map(int, sys.stdin.readline().split())\nif n == 1:\n\tprint(m - 1)\nelif m == 1:\n\tprint(n - 1)\nelse:\n\tprint((m - 1) * n)\n", "a = list(map(int, input().split()))\nif a[1] == 1:\n\tprint(a[0] - 1)\nelse:\n\tprint(a[0] * (a[1] - 1))\n", "l = list(map(int, input().split()))\nif l[1] > 1:\n\tprint((l[1] - 1) * l[0])\nelse:\n\tprint(l[0] - 1)\n", "data = input()\n(row, col) = data.split(' ')\nrow = int(row)\ncol = int(col)\nif col == 1:\n\tprint(row - 1)\nelse:\n\tprint((col - 1) * row)\n", "from functools import lru_cache\n(n, m) = [int(i) for i in input().split()]\nprint((m - 1) * n if m != 1 else n - 1)\n", "(a, b) = map(int, input().split())\nprint(max((b == 1) * (a - 1), (b - 1) * a))\n", "infor = input().split()\nrows = int(infor[0])\ncolumns = int(infor[1])\nif columns > 2:\n\tnums = columns - 1\n\tfinal = nums * rows\n\tprint(final)\nelif columns == 2:\n\tfinal = rows\n\tprint(final)\nelse:\n\tfinal = rows - 1\n\tprint(final)\n", "import sys\nimport heapq\nfrom collections import defaultdict\nfrom functools import lru_cache\nimport threading\n\ndef Iinput():\n\treturn int(input())\n\ndef Lsinput():\n\treturn list(input().split())\n\ndef Linput():\n\treturn list(map(int, input().split()))\n\ndef insr():\n\ts = input()\n\treturn list(s[:len(s) - 1])\n\ndef two():\n\treturn map(int, input().split())\n(m, n) = two()\nif m == 1 or n == 1:\n\tprint(max(m, n) - 1)\nelse:\n\tprint((n - 1) * m)\n", "import sys\n\ndef input(type=str):\n\treturn type(sys.stdin.readline().strip())\n\ndef input_n(type=str):\n\treturn list(map(type, input().split()))\n(N, M) = input_n(int)\nif M > 1:\n\tprint((M - 1) * N)\nelse:\n\tprint(N - 1)\n", "(r, c) = map(int, input().split())\nans = 0\nans += r * (c - 1)\nif c == 1:\n\tans += r - 1\nprint(ans)\n", "(N, M) = input().split()\nif int(M) != 1:\n\tprint((int(M) - 1) * int(N))\nelse:\n\tprint(int(N) - 1)\n", "(n, m) = map(int, input().split())\nif m == 1:\n\tprint(n - 1)\nelse:\n\trow = m - 1\n\trows = n * row\n\tprint(rows)\n", "s = input()\ns_lst = s.split()\ny = 0\nn = int(s_lst[0])\nm = int(s_lst[-1])\nif n == 1 and m == 2 or (n == 2 and m == 1):\n\ty = 1\nelif m == 1 and n != 2 or (n == 1 and m != 2):\n\ty = max([n, m]) - 1\nelse:\n\ty = n * (m - 1)\nprint(y)\n", "x = input().split(' ')\n(n, m) = (int(x[0]), int(x[1]))\nif m > 1:\n\tprint((m - 1) * n)\nelse:\n\tprint(n - 1)\n", "(N, M) = map(int, input().split(' '))\nif M > 1:\n\tprint((M - 1) * N)\nelif M == 1:\n\tprint(N - 1)\n", "x = list(map(int, input().split()))\nif x[1] == 1:\n\tprint(x[0] - 1)\nelse:\n\tprint((x[1] - 1) * x[0])\n", "(a, q) = map(int, input().split())\nif q == 1:\n\tprint(a - 1)\nelse:\n\tprint((q - 1) * a)\n", "import math\n(n, m) = map(int, input().split())\nif m > 1:\n\tprint((m - 1) * n)\nelse:\n\tprint(n - 1)\n", "grid = input().split()\nif int(grid[1]) == 1:\n\tprint(int(grid[0]) - 1)\nelif int(grid[1]) < 1:\n\tprint(0)\nelse:\n\tprint((int(grid[1]) - 1) * int(grid[0]))\n", "a = list(map(int, input().split()))\n(b, c) = (a[0], a[1])\nif c == 1:\n\tprint(b - 1)\nelse:\n\tprint(b * (c - 1))\n", "(n, m) = [int(x) for x in input().split()]\nif m == 1 and n == 1:\n\tres = 0\nelif m > 1:\n\tres = (m - 1) * n\nelse:\n\tres = (n - 1) * m\nprint(res)\n"]

difficulty: EASY

source: codeforces

raw_problem:
A. Accumulation of Dominoes

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Pak Chanek has a grid that has $$$N$$$ rows and $$$M$$$ columns. Each row is numbered from $$$1$$$ to $$$N$$$ from top to bottom. Each column is numbered from $$$1$$$ to $$$M$$$ from left to right.

Each tile in the grid contains a number. The numbers are arranged as follows:

 Row $$$1$$$ contains integers from $$$1$$$ to $$$M$$$ from left to right.

 Row $$$2$$$ contains integers from $$$M+1$$$ to $$$2 \times M$$$ from left to right.

 Row $$$3$$$ contains integers from $$$2 \times M+1$$$ to $$$3 \times M$$$ from left to right.

 And so on until row $$$N$$$.

A domino is defined as two different tiles in the grid that touch by their sides. A domino is said to be tight if and only if the two numbers in the domino have a difference of exactly $$$1$$$. Count the number of distinct tight dominoes in the grid.

Two dominoes are said to be distinct if and only if there exists at least one tile that is in one domino, but not in the other.

Input

The only line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 10^9$$$) — the number of rows and columns in the grid.

Output

An integer representing the number of distinct tight dominoes in the grid.

Examples

Input

3 4

Output

9

Input

2 1

Output

1

Note

The picture below is the grid that Pak Chanek has in the first example.

The picture below is an example of a tight domino in the grid.

question:
Pak Chanek has a grid that has $$$N$$$ rows and $$$M$$$ columns. Each row is numbered from $$$1$$$ to $$$N$$$ from top to bottom. Each column is numbered from $$$1$$$ to $$$M$$$ from left to right.
Each tile in the grid contains a number. The numbers are arranged as follows:
 -  Row $$$1$$$ contains integers from $$$1$$$ to $$$M$$$ from left to right. -  Row $$$2$$$ contains integers from $$$M+1$$$ to $$$2 \times M$$$ from left to right. -  Row $$$3$$$ contains integers from $$$2 \times M+1$$$ to $$$3 \times M$$$ from left to right. -  And so on until row $$$N$$$. A domino is defined as two different tiles in the grid that touch by their sides. A domino is said to be tight if and only if the two numbers in the domino have a difference of exactly $$$1$$$. Count the number of distinct tight dominoes in the grid.
Two dominoes are said to be distinct if and only if there exists at least one tile that is in one domino, but not in the other.

Input
The only line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 10^9$$$) — the number of rows and columns in the grid.

Output
An integer representing the number of distinct tight dominoes in the grid.

Examples
Input
3 4

Output
9

Input
2 1

Output
1

Note
The picture below is the grid that Pak Chanek has in the first example.
 ![image](1.png) The picture below is an example of a tight domino in the grid.
 ![image](2.png)

image_tags: Others Others

data_split: test


F. Multi-Colored Segments

problem_index: F

time_limit: 3 seconds

memory_limit: 256 megabytes

solutions: ["#############################################################\r\n\r\nimport sys\r\n\r\nipt = sys.stdin.readline\r\n\r\ndef iin():\r\n    return int(ipt())\r\ndef lmin():\r\n    return list(map(int,ipt().split()))\r\n\r\ninf = 1<<30\r\n#############################################################\r\n\r\nfor _ in range(int(input())):\r\n    N = iin()\r\n    A = [lmin()+[i] for i in range(N)]\r\n    R = sorted(A,key=lambda x:x[1])\r\n    opt = []\r\n    ans = [inf]*N\r\n\r\n    for j in range(N):\r\n        l,r,c,i = R[j]\r\n        if not opt:\r\n            opt.append((r,c))\r\n        else:\r\n            nopt = []\r\n            for r2,c2 in opt:\r\n                if c2 != c:\r\n                    ans[i] = min(ans[i],max(0,l-r2))\r\n                    nopt.append((r2,c2))\r\n\r\n            nopt.append((r,c))\r\n            nopt.sort(reverse=True)\r\n            \r\n            if len(nopt) == 3:\r\n                opt = nopt[:2]\r\n            else:\r\n                opt = nopt[:]\r\n    \r\n    R.reverse()\r\n    opt = []\r\n    for j in range(N):\r\n        l,r,c,i = R[j]\r\n        if not opt:\r\n            opt.append((l,c))\r\n        else:\r\n            nopt = []\r\n            for l2,c2 in opt:\r\n                if c2 != c:\r\n                    ans[i] = min(ans[i],max(0,l2-r))\r\n                nopt.append((l2,c2))\r\n\r\n            nopt.append((l,c))\r\n            nopt.sort()\r\n            \r\n            if len(nopt) == 3:\r\n                if nopt[0][1] == nopt[1][1]:\r\n                    opt = [nopt[0]] + [nopt[2]]\r\n                else:\r\n                    opt = nopt[:2]\r\n            else:\r\n                opt = nopt[:]\r\n\r\n    print(*ans)", "import sys\r\nimport os\r\nfrom io import BytesIO, IOBase\r\nBUFSIZE = 8192\r\nclass FastIO(IOBase):\r\n    newlines = 0\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    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    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    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\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\nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\r\n\r\nimport heapq\r\nt = int(input())\r\nfor _ in range(t):\r\n    n = int(input())\r\n    wires = []\r\n    for i in range(n):\r\n        l, r, c = map(int, input().split())\r\n        wires.append((l, r, c, i))\r\n    sorted_by_l = sorted(wires)\r\n    ans = [[float('inf'), float('inf')] for i in range(n)]\r\n    left = [float('inf') for i in range(n + 1)]\r\n    heap = []\r\n    ptr1 = 0\r\n    colors = {}\r\n    zero_set = set()\r\n    backlog_set = set()\r\n    backlog_right = -float('inf')\r\n    backlog_color = -1\r\n    backlog_prev = -1\r\n    for ptr1 in range(n):\r\n        wire = sorted_by_l[ptr1]\r\n        heapq.heappush(heap, (wire[1], wire))\r\n        if wire[2] in colors:\r\n            colors[wire[2]] += 1\r\n        else:\r\n            colors[wire[2]] = 1\r\n            if len(colors.keys()) == 2:\r\n                for ele in heap:\r\n                    ans[ele[1][3]] = [0, 0]\r\n                    zero_set.add(ele[1][3])\r\n        if len(backlog_set) >= 1 and wire[2] != backlog_color:\r\n            for set_ind in backlog_set:\r\n                ans[set_ind][1] = wire[0] - wires[set_ind][1]\r\n            backlog_set.clear()\r\n        if len(colors.keys()) >= 2:\r\n            ans[wire[3]] = [0, 0]\r\n            zero_set.add(wire[3])\r\n        if ptr1 < n-1:\r\n            while heap:\r\n                if heap[0][0] < sorted_by_l[ptr1 + 1][0]:\r\n                    ele = heapq.heappop(heap)\r\n                    colors[ele[1][2]] -= 1\r\n                    if colors[ele[1][2]] == 0:\r\n                        del colors[ele[1][2]]\r\n                    if backlog_color == ele[1][2]:\r\n                        backlog_set.add(ele[1][3])\r\n                        backlog_right = ele[0]\r\n                        if backlog_prev > -1:\r\n                            ans[ele[1][3]][0] = ele[1][0] - backlog_prev\r\n                    else:\r\n                        for set_ind in backlog_set:\r\n                            ans[set_ind][1] = ele[1][0] - wires[set_ind][1]\r\n                        if backlog_right == -float('inf'):\r\n                            backlog_right = ele[0]\r\n                            backlog_set = {ele[1][3]}\r\n                            backlog_color = ele[1][2]\r\n\r\n                        else:\r\n                            ans[ele[1][3]][0] = ele[1][0] - backlog_right\r\n                            backlog_prev = backlog_right\r\n                            backlog_right = ele[0]\r\n                            backlog_set = {ele[1][3]}\r\n                            backlog_color = ele[1][2]\r\n                else:\r\n                    break\r\n        else:\r\n            while heap:\r\n                ele = heapq.heappop(heap)\r\n                colors[ele[1][2]] -= 1\r\n                if colors[ele[1][2]] == 0:\r\n                    del colors[ele[1][2]]\r\n                if backlog_color == ele[1][2]:\r\n                    backlog_set.add(ele[1][3])\r\n                    backlog_right = ele[0]\r\n                    if backlog_prev > -1:\r\n                        ans[ele[1][3]][0] = ele[1][0] - backlog_prev\r\n                else:\r\n                    for set_ind in backlog_set:\r\n                        ans[set_ind][1] = ele[1][0] - wires[set_ind][1]\r\n                    if backlog_right == -float('inf'):\r\n                        backlog_right = ele[0]\r\n                        backlog_set = {ele[1][3]}\r\n                        backlog_color = ele[1][2]\r\n\r\n                    else:\r\n                        ans[ele[1][3]][0] = ele[1][0] - backlog_right\r\n                        backlog_prev = backlog_right\r\n                        backlog_right = ele[0]\r\n                        backlog_set = {ele[1][3]}\r\n                        backlog_color = ele[1][2]\r\n    # print(sorted_by_l)\r\n    # print(ans)\r\n    #print(zero_set)\r\n    for i in range(n):\r\n        if i in zero_set:\r\n            print(0, end = \" \")\r\n        else:\r\n            print(min(abs(ans[i][0]), abs(ans[i][1])), end = \" \")\r\n    print()", "import sys\nfrom bisect import bisect_right, bisect_left\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nfrom math import factorial, floor, inf, ceil, gcd\nfrom collections import defaultdict, deque, Counter\nfrom functools import cmp_to_key\nfrom heapq import heappop, heappush, heapify\n\nBUFSIZE = 8192\n \nclass FastIO(IOBase):\n    newlines = 0\n \n    def __init__(self, file):\n        self._fd = file.fileno()\n        self.buffer = BytesIO()\n        self.writable = \"x\" in file.mode or \"r\" not in file.mode\n        self.write = self.buffer.write if self.writable else None\n \n    def read(self):\n        while True:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            if not b:\n                break\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines = 0\n        return self.buffer.read()\n \n    def readline(self):\n        while self.newlines == 0:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            self.newlines = b.count(b\"\\n\") + (not b)\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines -= 1\n        return self.buffer.readline()\n \n    def flush(self):\n        if self.writable:\n            os.write(self._fd, self.buffer.getvalue())\n            self.buffer.truncate(0), self.buffer.seek(0)\n \n \nclass IOWrapper(IOBase):\n    def __init__(self, file):\n        self.buffer = FastIO(file)\n        self.flush = self.buffer.flush\n        self.writable = self.buffer.writable\n        self.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\n        self.read = lambda: self.buffer.read().decode(\"ascii\")\n        self.readline = lambda: self.buffer.readline().decode(\"ascii\")\n \n \nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\n\n############ ---- Input Functions ---- ############\ndef inp():\n    return(int(input()))\ndef inlt():\n    return(list(map(int,input().split())))\ndef insr():\n    s = input().strip()\n    return(s)\ndef invr():\n    return(map(int,input().split()))\ndef insr2():\n    s = input()\n    return(s.split(\" \"))\n\n###functions\n\n##better sqrt with binary search (since f**k float precision for large nums)\n\ndef sqrt(num):\n    l, r  = 0, 10**18 + 7\n    while r-l != 1:\n        mid = (l+r)//2\n        square = mid*mid\n        if square <= num:\n            l = mid\n        else:\n            r = mid\n    return l\n\n### Calculate C(n, r) mod p, where p is prime (fast with precalculation)\n\ndef build_mod_inverses(n, r, p):\n    fact = [1] * (n + 1)\n    for i in range(1, n + 1):\n        fact[i] = i * fact[i - 1] % p\n    \n    inv = [1] * (n + 1)\n    inv[n] = pow(fact[n], p - 2, p)\n    for i in range(n - 1, -1, -1):\n        inv[i] = (i + 1) * inv[i + 1] % p\n    \n    return fact, inv\n\n# fast C(n, r) mod p calculation using predefined fact and inv\ndef comb(n, r, p, fact, inv):\n    return fact[n] * inv[r] % p * inv[n - r] % p if n >= r >= 0 else 0\n \ndef make_divisors(n):\n    divisors = []\n    for i in range(1, int(n**0.5)+1):\n        if n % i == 0:\n            divisors.append(i)\n            if i != n // i and i != 1:\n                divisors.append(n // i)\n    return divisors\n\ndef dfs(graph, vertex):\n    visited = set()\n    tree = []\n    deq = deque([vertex])\n    while deq:\n        vertex = deq.pop()\n        if vertex not in visited:\n            visited.add(vertex)\n            deq.extend(graph[vertex])\n            tree.append(vertex)\n    return tree\n\ndef find_in_sorted_list(elem, sorted_list):\n    # https://docs.python.org/3/library/bisect.html\n    'Locate the leftmost value exactly equal to x'\n    i = bisect_left(sorted_list, elem)\n    if i != len(sorted_list) and sorted_list[i] == elem:\n        return i\n    return -1\n\n############ SORTED LIST ###############\n\nclass SL:\n    def __init__(self, iterable=[], _load=100):\n        \"\"\"Initialize sorted list instance.\"\"\"\n        values = sorted(iterable)\n        self._len = _len = len(values)\n        self._load = _load\n        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]\n        self._list_lens = [len(_list) for _list in _lists]\n        self._mins = [_list[0] for _list in _lists]\n        self._fen_tree = []\n        self._rebuild = True\n \n    def _fen_build(self):\n        \"\"\"Build a fenwick tree instance.\"\"\"\n        self._fen_tree[:] = self._list_lens\n        _fen_tree = self._fen_tree\n        for i in range(len(_fen_tree)):\n            if i | i + 1 < len(_fen_tree):\n                _fen_tree[i | i + 1] += _fen_tree[i]\n        self._rebuild = False\n \n    def _fen_update(self, index, value):\n        \"\"\"Update `fen_tree[index] += value`.\"\"\"\n        if not self._rebuild:\n            _fen_tree = self._fen_tree\n            while index < len(_fen_tree):\n                _fen_tree[index] += value\n                index |= index + 1\n \n    def _fen_query(self, end):\n        \"\"\"Return `sum(_fen_tree[:end])`.\"\"\"\n        if self._rebuild:\n            self._fen_build()\n \n        _fen_tree = self._fen_tree\n        x = 0\n        while end:\n            x += _fen_tree[end - 1]\n            end &= end - 1\n        return x\n \n    def _fen_findkth(self, k):\n        \"\"\"Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`).\"\"\"\n        _list_lens = self._list_lens\n        if k < _list_lens[0]:\n            return 0, k\n        if k >= self._len - _list_lens[-1]:\n            return len(_list_lens) - 1, k + _list_lens[-1] - self._len\n        if self._rebuild:\n            self._fen_build()\n \n        _fen_tree = self._fen_tree\n        idx = -1\n        for d in reversed(range(len(_fen_tree).bit_length())):\n            right_idx = idx + (1 << d)\n            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:\n                idx = right_idx\n                k -= _fen_tree[idx]\n        return idx + 1, k\n \n    def _delete(self, pos, idx):\n        \"\"\"Delete value at the given `(pos, idx)`.\"\"\"\n        _lists = self._lists\n        _mins = self._mins\n        _list_lens = self._list_lens\n \n        self._len -= 1\n        self._fen_update(pos, -1)\n        del _lists[pos][idx]\n        _list_lens[pos] -= 1\n \n        if _list_lens[pos]:\n            _mins[pos] = _lists[pos][0]\n        else:\n            del _lists[pos]\n            del _list_lens[pos]\n            del _mins[pos]\n            self._rebuild = True\n \n    def _loc_left(self, value):\n        \"\"\"Return an index pair that corresponds to the first position of `value` in the sorted list.\"\"\"\n        if not self._len:\n            return 0, 0\n \n        _lists = self._lists\n        _mins = self._mins\n \n        lo, pos = -1, len(_lists) - 1\n        while lo + 1 < pos:\n            mi = (lo + pos) >> 1\n            if value <= _mins[mi]:\n                pos = mi\n            else:\n                lo = mi\n \n        if pos and value <= _lists[pos - 1][-1]:\n            pos -= 1\n \n        _list = _lists[pos]\n        lo, idx = -1, len(_list)\n        while lo + 1 < idx:\n            mi = (lo + idx) >> 1\n            if value <= _list[mi]:\n                idx = mi\n            else:\n                lo = mi\n \n        return pos, idx\n \n    def _loc_right(self, value):\n        \"\"\"Return an index pair that corresponds to the last position of `value` in the sorted list.\"\"\"\n        if not self._len:\n            return 0, 0\n \n        _lists = self._lists\n        _mins = self._mins\n \n        pos, hi = 0, len(_lists)\n        while pos + 1 < hi:\n            mi = (pos + hi) >> 1\n            if value < _mins[mi]:\n                hi = mi\n            else:\n                pos = mi\n \n        _list = _lists[pos]\n        lo, idx = -1, len(_list)\n        while lo + 1 < idx:\n            mi = (lo + idx) >> 1\n            if value < _list[mi]:\n                idx = mi\n            else:\n                lo = mi\n \n        return pos, idx\n \n    def add(self, value):\n        \"\"\"Add `value` to sorted list.\"\"\"\n        _load = self._load\n        _lists = self._lists\n        _mins = self._mins\n        _list_lens = self._list_lens\n \n        self._len += 1\n        if _lists:\n            pos, idx = self._loc_right(value)\n            self._fen_update(pos, 1)\n            _list = _lists[pos]\n            _list.insert(idx, value)\n            _list_lens[pos] += 1\n            _mins[pos] = _list[0]\n            if _load + _load < len(_list):\n                _lists.insert(pos + 1, _list[_load:])\n                _list_lens.insert(pos + 1, len(_list) - _load)\n                _mins.insert(pos + 1, _list[_load])\n                _list_lens[pos] = _load\n                del _list[_load:]\n                self._rebuild = True\n        else:\n            _lists.append([value])\n            _mins.append(value)\n            _list_lens.append(1)\n            self._rebuild = True\n \n    def discard(self, value):\n        \"\"\"Remove `value` from sorted list if it is a member.\"\"\"\n        _lists = self._lists\n        if _lists:\n            pos, idx = self._loc_right(value)\n            if idx and _lists[pos][idx - 1] == value:\n                self._delete(pos, idx - 1)\n \n    def remove(self, value):\n        \"\"\"Remove `value` from sorted list; `value` must be a member.\"\"\"\n        _len = self._len\n        self.discard(value)\n        if _len == self._len:\n            raise ValueError('{0!r} not in list'.format(value))\n \n    def pop(self, index=-1):\n        \"\"\"Remove and return value at `index` in sorted list.\"\"\"\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        value = self._lists[pos][idx]\n        self._delete(pos, idx)\n        return value\n \n    def bisect_left(self, value):\n        \"\"\"Return the first index to insert `value` in the sorted list.\"\"\"\n        pos, idx = self._loc_left(value)\n        return self._fen_query(pos) + idx\n \n    def bisect_right(self, value):\n        \"\"\"Return the last index to insert `value` in the sorted list.\"\"\"\n        pos, idx = self._loc_right(value)\n        return self._fen_query(pos) + idx\n \n    def count(self, value):\n        \"\"\"Return number of occurrences of `value` in the sorted list.\"\"\"\n        return self.bisect_right(value) - self.bisect_left(value)\n \n    def __len__(self):\n        \"\"\"Return the size of the sorted list.\"\"\"\n        return self._len\n \n    def __getitem__(self, index):\n        \"\"\"Lookup value at `index` in sorted list.\"\"\"\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        return self._lists[pos][idx]\n \n    def __delitem__(self, index):\n        \"\"\"Remove value at `index` from sorted list.\"\"\"\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        self._delete(pos, idx)\n \n    def __contains__(self, value):\n        \"\"\"Return true if `value` is an element of the sorted list.\"\"\"\n        _lists = self._lists\n        if _lists:\n            pos, idx = self._loc_left(value)\n            return idx < len(_lists[pos]) and _lists[pos][idx] == value\n        return False\n \n    def __iter__(self):\n        \"\"\"Return an iterator over the sorted list.\"\"\"\n        return (value for _list in self._lists for value in _list)\n \n    def __reversed__(self):\n        \"\"\"Return a reverse iterator over the sorted list.\"\"\"\n        return (value for _list in reversed(self._lists) for value in reversed(_list))\n \n    def __repr__(self):\n        \"\"\"Return string representation of sorted list.\"\"\"\n        return 'SortedList({0})'.format(list(self))\n\n############ SEGMENT TREE ##############\nclass SegmentTree:\n    def __init__(self, data, default=0, func=lambda a, b: a+b):\n        \"\"\"initialize the segment tree with data\"\"\"\n        self._default = default\n        self._func = func\n        self._len = len(data)\n        self._size = _size = 1 << (self._len - 1).bit_length()\n \n        self.data = [default] * (2 * _size)\n        self.data[_size:_size + self._len] = data\n        for i in reversed(range(_size)):\n            self.data[i] = func(self.data[i + i], self.data[i + i + 1])\n \n    def __delitem__(self, idx):\n        self[idx] = self._default\n \n    def __getitem__(self, idx):\n        return self.data[idx + self._size]\n \n    def __setitem__(self, idx, value):\n        idx += self._size\n        self.data[idx] = value\n        idx >>= 1\n        while idx:\n            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n            idx >>= 1\n \n    def __len__(self):\n        return self._len\n \n    def query(self, start, stop):\n        if start == stop:\n            return self.__getitem__(start)\n        start += self._size\n        stop += self._size\n \n        res = self._default\n        while start < stop:\n            if start & 1:\n                res = self._func(res, self.data[start])\n                start += 1\n            if stop & 1:\n                stop -= 1\n                res = self._func(res, self.data[stop])\n            start >>= 1\n            stop >>= 1\n        return res\n \n    def __repr__(self):\n        return \"SegmentTree({0})\".format(self.data)\n    \n############ DSU ##############\nclass DisjointSetUnion():\n    def __init__(self, n):\n        self.n = n\n        self.parents = [-1] * n\n        self.group = n\n    \n    def find(self, x):\n        if self.parents[x] < 0:\n            return x\n        else:\n            self.parents[x] = self.find(self.parents[x])\n            return self.parents[x]\n    \n    def union(self, x, y):\n        x = self.find(x)\n        y = self.find(y)\n    \n        if x == y:\n            return\n        self.group -= 1\n        if self.parents[x] > self.parents[y]:\n            x, y = y, x\n    \n        self.parents[x] += self.parents[y]\n        self.parents[y] = x\n    \n    def size(self, x):\n        return -self.parents[self.find(x)]\n    \n    def same(self, x, y):\n        return self.find(x) == self.find(y)\n    \n    def members(self, x):\n        root = self.find(x)\n        return [i for i in range(self.n) if self.find(i) == root]\n    \n    def roots(self):\n        return [i for i, x in enumerate(self.parents) if x < 0]\n    \n    def group_count(self):\n        return self.group\n    \n    def all_group_members(self):\n        dic = {r:[] for r in self.roots()}\n        for i in range(self.n):\n            dic[self.find(i)].append(i)\n        return dic\n    \n    def __str__(self):\n        return '\\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())\n\n###code\n\n__ = inp()\nfor _ in range(__):\n    def solve():\n        \n        n = inp()\n        l = []\n        r = []\n        colors = [[] for i in range(n)]\n        for i in range(n):\n            a,b,c = inlt()\n            l.append(a)\n            r.append(b)\n            colors[c-1].append(i)\n            \n        sl_l = SL(l)\n        sl_r = SL(r)\n        ans = [-1]*n\n        \n        for i in range(n):\n            for ind in colors[i]:\n                sl_l.discard(l[ind])\n                sl_r.discard(r[ind])\n                \n            for ind in colors[i]:\n                \n                search_r = sl_r.bisect_right(l[ind])-1\n                search_l = sl_l.bisect_left(r[ind])\n            \n                mn = inf\n                if search_r - search_l + 1 < 0:\n                    mn = 0\n                \n                if search_r > -1:\n                    mn = min(mn, l[ind] - sl_r[search_r])\n                if search_l < len(sl_r):\n                    mn = min(mn, sl_l[search_l] - r[ind])\n                \n                ans[ind] = mn\n            \n            for ind in colors[i]:\n                sl_l.add(l[ind])\n                sl_r.add(r[ind])\n            \n        print(' '.join(map(str, ans)))\n\n\n        return\n    solve()", "import sys\nfrom bisect import bisect_right, bisect_left\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nfrom math import factorial, floor, inf, ceil, gcd\nfrom collections import defaultdict, deque, Counter\nfrom functools import cmp_to_key\nfrom heapq import heappop, heappush, heapify\n\nBUFSIZE = 8192\n \nclass FastIO(IOBase):\n    newlines = 0\n \n    def __init__(self, file):\n        self._fd = file.fileno()\n        self.buffer = BytesIO()\n        self.writable = \"x\" in file.mode or \"r\" not in file.mode\n        self.write = self.buffer.write if self.writable else None\n \n    def read(self):\n        while True:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            if not b:\n                break\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines = 0\n        return self.buffer.read()\n \n    def readline(self):\n        while self.newlines == 0:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            self.newlines = b.count(b\"\\n\") + (not b)\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines -= 1\n        return self.buffer.readline()\n \n    def flush(self):\n        if self.writable:\n            os.write(self._fd, self.buffer.getvalue())\n            self.buffer.truncate(0), self.buffer.seek(0)\n \n \nclass IOWrapper(IOBase):\n    def __init__(self, file):\n        self.buffer = FastIO(file)\n        self.flush = self.buffer.flush\n        self.writable = self.buffer.writable\n        self.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\n        self.read = lambda: self.buffer.read().decode(\"ascii\")\n        self.readline = lambda: self.buffer.readline().decode(\"ascii\")\n \n \nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\n\n############ ---- Input Functions ---- ############\ndef inp():\n    return(int(input()))\ndef inlt():\n    return(list(map(int,input().split())))\ndef insr():\n    s = input().strip()\n    return(s)\ndef invr():\n    return(map(int,input().split()))\ndef insr2():\n    s = input()\n    return(s.split(\" \"))\n\n###functions\n\n##better sqrt with binary search (since f**k float precision for large nums)\n\ndef sqrt(num):\n    l, r  = 0, 10**18 + 7\n    while r-l != 1:\n        mid = (l+r)//2\n        square = mid*mid\n        if square <= num:\n            l = mid\n        else:\n            r = mid\n    return l\n\n### Calculate C(n, r) mod p, where p is prime (fast with precalculation)\n\ndef build_mod_inverses(n, r, p):\n    fact = [1] * (n + 1)\n    for i in range(1, n + 1):\n        fact[i] = i * fact[i - 1] % p\n    \n    inv = [1] * (n + 1)\n    inv[n] = pow(fact[n], p - 2, p)\n    for i in range(n - 1, -1, -1):\n        inv[i] = (i + 1) * inv[i + 1] % p\n    \n    return fact, inv\n\n# fast C(n, r) mod p calculation using predefined fact and inv\ndef comb(n, r, p, fact, inv):\n    return fact[n] * inv[r] % p * inv[n - r] % p if n >= r >= 0 else 0\n \ndef make_divisors(n):\n    divisors = []\n    for i in range(1, int(n**0.5)+1):\n        if n % i == 0:\n            divisors.append(i)\n            if i != n // i and i != 1:\n                divisors.append(n // i)\n    return divisors\n\ndef dfs(graph, vertex):\n    visited = set()\n    tree = []\n    deq = deque([vertex])\n    while deq:\n        vertex = deq.pop()\n        if vertex not in visited:\n            visited.add(vertex)\n            deq.extend(graph[vertex])\n            tree.append(vertex)\n    return tree\n\ndef find_in_sorted_list(elem, sorted_list):\n    # https://docs.python.org/3/library/bisect.html\n    'Locate the leftmost value exactly equal to x'\n    i = bisect_left(sorted_list, elem)\n    if i != len(sorted_list) and sorted_list[i] == elem:\n        return i\n    return -1\n\n############ SORTED LIST ###############\n\nclass SL:\n    def __init__(self, iterable=[], _load=100):\n        \"\"\"Initialize sorted list instance.\"\"\"\n        values = sorted(iterable)\n        self._len = _len = len(values)\n        self._load = _load\n        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]\n        self._list_lens = [len(_list) for _list in _lists]\n        self._mins = [_list[0] for _list in _lists]\n        self._fen_tree = []\n        self._rebuild = True\n \n    def _fen_build(self):\n        \"\"\"Build a fenwick tree instance.\"\"\"\n        self._fen_tree[:] = self._list_lens\n        _fen_tree = self._fen_tree\n        for i in range(len(_fen_tree)):\n            if i | i + 1 < len(_fen_tree):\n                _fen_tree[i | i + 1] += _fen_tree[i]\n        self._rebuild = False\n \n    def _fen_update(self, index, value):\n        \"\"\"Update `fen_tree[index] += value`.\"\"\"\n        if not self._rebuild:\n            _fen_tree = self._fen_tree\n            while index < len(_fen_tree):\n                _fen_tree[index] += value\n                index |= index + 1\n \n    def _fen_query(self, end):\n        \"\"\"Return `sum(_fen_tree[:end])`.\"\"\"\n        if self._rebuild:\n            self._fen_build()\n \n        _fen_tree = self._fen_tree\n        x = 0\n        while end:\n            x += _fen_tree[end - 1]\n            end &= end - 1\n        return x\n \n    def _fen_findkth(self, k):\n        \"\"\"Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`).\"\"\"\n        _list_lens = self._list_lens\n        if k < _list_lens[0]:\n            return 0, k\n        if k >= self._len - _list_lens[-1]:\n            return len(_list_lens) - 1, k + _list_lens[-1] - self._len\n        if self._rebuild:\n            self._fen_build()\n \n        _fen_tree = self._fen_tree\n        idx = -1\n        for d in reversed(range(len(_fen_tree).bit_length())):\n            right_idx = idx + (1 << d)\n            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:\n                idx = right_idx\n                k -= _fen_tree[idx]\n        return idx + 1, k\n \n    def _delete(self, pos, idx):\n        \"\"\"Delete value at the given `(pos, idx)`.\"\"\"\n        _lists = self._lists\n        _mins = self._mins\n        _list_lens = self._list_lens\n \n        self._len -= 1\n        self._fen_update(pos, -1)\n        del _lists[pos][idx]\n        _list_lens[pos] -= 1\n \n        if _list_lens[pos]:\n            _mins[pos] = _lists[pos][0]\n        else:\n            del _lists[pos]\n            del _list_lens[pos]\n            del _mins[pos]\n            self._rebuild = True\n \n    def _loc_left(self, value):\n        \"\"\"Return an index pair that corresponds to the first position of `value` in the sorted list.\"\"\"\n        if not self._len:\n            return 0, 0\n \n        _lists = self._lists\n        _mins = self._mins\n \n        lo, pos = -1, len(_lists) - 1\n        while lo + 1 < pos:\n            mi = (lo + pos) >> 1\n            if value <= _mins[mi]:\n                pos = mi\n            else:\n                lo = mi\n \n        if pos and value <= _lists[pos - 1][-1]:\n            pos -= 1\n \n        _list = _lists[pos]\n        lo, idx = -1, len(_list)\n        while lo + 1 < idx:\n            mi = (lo + idx) >> 1\n            if value <= _list[mi]:\n                idx = mi\n            else:\n                lo = mi\n \n        return pos, idx\n \n    def _loc_right(self, value):\n        \"\"\"Return an index pair that corresponds to the last position of `value` in the sorted list.\"\"\"\n        if not self._len:\n            return 0, 0\n \n        _lists = self._lists\n        _mins = self._mins\n \n        pos, hi = 0, len(_lists)\n        while pos + 1 < hi:\n            mi = (pos + hi) >> 1\n            if value < _mins[mi]:\n                hi = mi\n            else:\n                pos = mi\n \n        _list = _lists[pos]\n        lo, idx = -1, len(_list)\n        while lo + 1 < idx:\n            mi = (lo + idx) >> 1\n            if value < _list[mi]:\n                idx = mi\n            else:\n                lo = mi\n \n        return pos, idx\n \n    def add(self, value):\n        \"\"\"Add `value` to sorted list.\"\"\"\n        _load = self._load\n        _lists = self._lists\n        _mins = self._mins\n        _list_lens = self._list_lens\n \n        self._len += 1\n        if _lists:\n            pos, idx = self._loc_right(value)\n            self._fen_update(pos, 1)\n            _list = _lists[pos]\n            _list.insert(idx, value)\n            _list_lens[pos] += 1\n            _mins[pos] = _list[0]\n            if _load + _load < len(_list):\n                _lists.insert(pos + 1, _list[_load:])\n                _list_lens.insert(pos + 1, len(_list) - _load)\n                _mins.insert(pos + 1, _list[_load])\n                _list_lens[pos] = _load\n                del _list[_load:]\n                self._rebuild = True\n        else:\n            _lists.append([value])\n            _mins.append(value)\n            _list_lens.append(1)\n            self._rebuild = True\n \n    def discard(self, value):\n        \"\"\"Remove `value` from sorted list if it is a member.\"\"\"\n        _lists = self._lists\n        if _lists:\n            pos, idx = self._loc_right(value)\n            if idx and _lists[pos][idx - 1] == value:\n                self._delete(pos, idx - 1)\n \n    def remove(self, value):\n        \"\"\"Remove `value` from sorted list; `value` must be a member.\"\"\"\n        _len = self._len\n        self.discard(value)\n        if _len == self._len:\n            raise ValueError('{0!r} not in list'.format(value))\n \n    def pop(self, index=-1):\n        \"\"\"Remove and return value at `index` in sorted list.\"\"\"\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        value = self._lists[pos][idx]\n        self._delete(pos, idx)\n        return value\n \n    def bisect_left(self, value):\n        \"\"\"Return the first index to insert `value` in the sorted list.\"\"\"\n        pos, idx = self._loc_left(value)\n        return self._fen_query(pos) + idx\n \n    def bisect_right(self, value):\n        \"\"\"Return the last index to insert `value` in the sorted list.\"\"\"\n        pos, idx = self._loc_right(value)\n        return self._fen_query(pos) + idx\n \n    def count(self, value):\n        \"\"\"Return number of occurrences of `value` in the sorted list.\"\"\"\n        return self.bisect_right(value) - self.bisect_left(value)\n \n    def __len__(self):\n        \"\"\"Return the size of the sorted list.\"\"\"\n        return self._len\n \n    def __getitem__(self, index):\n        \"\"\"Lookup value at `index` in sorted list.\"\"\"\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        return self._lists[pos][idx]\n \n    def __delitem__(self, index):\n        \"\"\"Remove value at `index` from sorted list.\"\"\"\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        self._delete(pos, idx)\n \n    def __contains__(self, value):\n        \"\"\"Return true if `value` is an element of the sorted list.\"\"\"\n        _lists = self._lists\n        if _lists:\n            pos, idx = self._loc_left(value)\n            return idx < len(_lists[pos]) and _lists[pos][idx] == value\n        return False\n \n    def __iter__(self):\n        \"\"\"Return an iterator over the sorted list.\"\"\"\n        return (value for _list in self._lists for value in _list)\n \n    def __reversed__(self):\n        \"\"\"Return a reverse iterator over the sorted list.\"\"\"\n        return (value for _list in reversed(self._lists) for value in reversed(_list))\n \n    def __repr__(self):\n        \"\"\"Return string representation of sorted list.\"\"\"\n        return 'SortedList({0})'.format(list(self))\n\n############ SEGMENT TREE ##############\nclass SegmentTree:\n    def __init__(self, data, default=0, func=lambda a, b: a+b):\n        \"\"\"initialize the segment tree with data\"\"\"\n        self._default = default\n        self._func = func\n        self._len = len(data)\n        self._size = _size = 1 << (self._len - 1).bit_length()\n \n        self.data = [default] * (2 * _size)\n        self.data[_size:_size + self._len] = data\n        for i in reversed(range(_size)):\n            self.data[i] = func(self.data[i + i], self.data[i + i + 1])\n \n    def __delitem__(self, idx):\n        self[idx] = self._default\n \n    def __getitem__(self, idx):\n        return self.data[idx + self._size]\n \n    def __setitem__(self, idx, value):\n        idx += self._size\n        self.data[idx] = value\n        idx >>= 1\n        while idx:\n            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n            idx >>= 1\n \n    def __len__(self):\n        return self._len\n \n    def query(self, start, stop):\n        if start == stop:\n            return self.__getitem__(start)\n        start += self._size\n        stop += self._size\n \n        res = self._default\n        while start < stop:\n            if start & 1:\n                res = self._func(res, self.data[start])\n                start += 1\n            if stop & 1:\n                stop -= 1\n                res = self._func(res, self.data[stop])\n            start >>= 1\n            stop >>= 1\n        return res\n \n    def __repr__(self):\n        return \"SegmentTree({0})\".format(self.data)\n    \n############ DSU ##############\nclass DisjointSetUnion():\n    def __init__(self, n):\n        self.n = n\n        self.parents = [-1] * n\n        self.group = n\n    \n    def find(self, x):\n        if self.parents[x] < 0:\n            return x\n        else:\n            self.parents[x] = self.find(self.parents[x])\n            return self.parents[x]\n    \n    def union(self, x, y):\n        x = self.find(x)\n        y = self.find(y)\n    \n        if x == y:\n            return\n        self.group -= 1\n        if self.parents[x] > self.parents[y]:\n            x, y = y, x\n    \n        self.parents[x] += self.parents[y]\n        self.parents[y] = x\n    \n    def size(self, x):\n        return -self.parents[self.find(x)]\n    \n    def same(self, x, y):\n        return self.find(x) == self.find(y)\n    \n    def members(self, x):\n        root = self.find(x)\n        return [i for i in range(self.n) if self.find(i) == root]\n    \n    def roots(self):\n        return [i for i, x in enumerate(self.parents) if x < 0]\n    \n    def group_count(self):\n        return self.group\n    \n    def all_group_members(self):\n        dic = {r:[] for r in self.roots()}\n        for i in range(self.n):\n            dic[self.find(i)].append(i)\n        return dic\n    \n    def __str__(self):\n        return '\\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())\n\n###code\n\n__ = inp()\nfor _ in range(__):\n    def solve():\n        \n        n = inp()\n        ls, rs, color = [], [], [[] for _ in range(n)]\n        for i in range(n):\n            l ,r, c = inlt()\n            ls.append(l)\n            rs.append(r)\n            color[c-1].append(i)\n        sl, sr = SL(ls), SL(rs)\n        ans = [1e99] * n\n        for c in range(n):\n            for i in color[c]:\n                sl.discard(ls[i])\n                sr.discard(rs[i])\n    \n            for i in color[c]:\n                l, r = ls[i], rs[i]\n                ixsl = sl.bisect_left(r)\n                ixsr = sr.bisect_right(l) - 1\n    \n                if ixsr - ixsl + 1 < 0:\n                    ans[i] = 0\n                if ixsl < len(sl):\n                    ans[i] = min(ans[i], sl[ixsl] - r)\n                if ixsr > -1:\n                    ans[i] = min(ans[i], l - sr[ixsr])\n    \n            for i in color[c]:\n                sl.add(ls[i])\n                sr.add(rs[i])\n        print(\" \".join(map(str, ans)))\n        return\n\n    solve()", "class 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\nclass OrderedList(SortedList): #Codeforces, Ordered Multiset\r\n    def __init__(self, arg):\r\n        super().__init__(arg)\r\n    def rangeCountByValue(self, leftVal, rightVal): #returns number of items in range [leftVal,rightVal] inclusive\r\n        leftCummulative = self.bisect_left(leftVal)\r\n        rightCummulative = self.bisect_left(rightVal + 1)\r\n        return rightCummulative - leftCummulative\r\n\r\nfrom collections import defaultdict\r\n\r\ndef solve():\r\n    \r\n    # from random import randint\r\n    # n = 10\r\n    # queries = defaultdict(lambda: []) # {colour: (l, r, query_idx)}\r\n    # temp = []\r\n    # for i in range(n):\r\n    #     l, r, c = randint(1, 6), randint(1, 6), randint(1, 6)\r\n    #     if l > r:\r\n    #         l, r = r, l\r\n    #     temp.append((l, r, c))\r\n    #     queries[c].append((l, r, i))\r\n    # temp = [(3, 3, 2),\r\n    #         (5, 5, 5),\r\n    #         (1, 6, 5),\r\n    #         (1, 3, 5),\r\n    #         (1, 2, 6),\r\n    #         (6, 6, 4),\r\n    #         (4, 5, 4),\r\n    #         (1, 5, 3),\r\n    #         (2, 4, 3),\r\n    #         (3, 4, 3)]\r\n    # for i, (l, r, c) in enumerate(temp):\r\n    #     queries[c].append((l, r, i))\r\n    # inf = int(2e9)\r\n    # naiveans = [inf] * n\r\n    # for i in range(n):\r\n    #     l, r, c = temp[i]\r\n    #     for j in range(n):\r\n    #         ll, rr, cc = temp[j]\r\n    #         if c != cc:\r\n    #             if r < ll:\r\n    #                 dist = ll - r\r\n    #             elif rr < l:\r\n    #                 dist = l - rr\r\n    #             else:\r\n    #                 dist = 0\r\n    #             naiveans[i] = min(naiveans[i], dist)\r\n    \r\n    n = int(input())\r\n    queries = defaultdict(lambda: []) # {colour: (l, r, query_idx)}\r\n    for i in range(n):\r\n        l, r, c = readIntArr()\r\n        queries[c].append((l, r, i))\r\n    \r\n    inf = int(2e9)\r\n    ans = [inf] * n\r\n    prev_segments = SortedList()  # store (l, r)\r\n    colour_query_order = list(queries.keys())\r\n    # start by querying the colours forward\r\n    for c in colour_query_order:\r\n        for l, r, q_i in queries[c]:\r\n            sl_idx = prev_segments.bisect_left((l, r))\r\n            # Lazy to think. check sl_idx - 1 to sl_idx + 1\r\n            for i in range(sl_idx - 1, sl_idx + 2):\r\n                if 0 <= i < len(prev_segments):\r\n                    ll, rr = prev_segments[i]\r\n                    if ll > r:\r\n                        dist = ll - r\r\n                    elif rr < l:\r\n                        dist = l - rr\r\n                    else:\r\n                        dist = 0\r\n                    ans[q_i] = min(ans[q_i], dist)\r\n        # merge in prev_segments\r\n        for l, r, _ in queries[c]:\r\n            sl_idx = prev_segments.bisect_left((l, r))\r\n            while sl_idx - 1 >= 0 and prev_segments[sl_idx - 1][1] + 1 >= l:\r\n                # merge\r\n                l = min(l, prev_segments[sl_idx - 1][0])\r\n                r = max(r, prev_segments[sl_idx - 1][1])\r\n                prev_segments.pop(sl_idx - 1)\r\n                sl_idx -= 1\r\n            while sl_idx < len(prev_segments) and r + 1 >= prev_segments[sl_idx][0]:\r\n                l = min(l, prev_segments[sl_idx][0])\r\n                r = max(r, prev_segments[sl_idx][1])\r\n                prev_segments.pop(sl_idx)\r\n            prev_segments.add((l, r))\r\n        # print('new segments:{}'.format(queries[c]))\r\n        # print(prev_segments)\r\n    \r\n    # query colours backward\r\n    colour_query_order.reverse()\r\n    prev_segments = SortedList()\r\n    for c in colour_query_order:\r\n        for l, r, q_i in queries[c]:\r\n            sl_idx = prev_segments.bisect_left((l, r))\r\n            # Lazy to think. check sl_idx - 1 to sl_idx + 1\r\n            for i in range(sl_idx - 1, sl_idx + 2):\r\n                if 0 <= i < len(prev_segments):\r\n                    ll, rr = prev_segments[i]\r\n                    if ll > r:\r\n                        dist = ll - r\r\n                    elif rr < l:\r\n                        dist = l - rr\r\n                    else:\r\n                        dist = 0\r\n                    ans[q_i] = min(ans[q_i], dist)\r\n        # merge in prev_segments\r\n        for l, r, _ in queries[c]:\r\n            sl_idx = prev_segments.bisect_left((l, r))\r\n            while sl_idx - 1 >= 0 and prev_segments[sl_idx - 1][1] + 1 >= l:\r\n                # merge\r\n                l = min(l, prev_segments[sl_idx - 1][0])\r\n                r = max(r, prev_segments[sl_idx - 1][1])\r\n                prev_segments.pop(sl_idx - 1)\r\n                sl_idx -= 1\r\n            while sl_idx < len(prev_segments) and r + 1 >= prev_segments[sl_idx][0]:\r\n                l = min(l, prev_segments[sl_idx][0])\r\n                r = max(r, prev_segments[sl_idx][1])\r\n                prev_segments.pop(sl_idx)\r\n            prev_segments.add((l, r))\r\n    \r\n    # if ans != naiveans:\r\n    #     print(queries)\r\n    #     print(ans)\r\n    #     print(naiveans)\r\n            \r\n    return ans\r\n            \r\n\r\ndef main():\r\n    \r\n    t = int(input())\r\n    # t = 1\r\n    allans = []\r\n    for _ in range(t):\r\n        ans = solve()\r\n        allans.append(ans)\r\n    multiLineArrayOfArraysPrint(allans)\r\n    \r\n    return\r\n\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):\r\n    print('? {} {}'.format(a, b))\r\n    sys.stdout.flush()\r\n    return int(input())\r\n \r\ndef answerInteractive(ans):\r\n    print('! {}'.format(ans))\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()"]

source: codeforces

raw_problem:
F. Multi-Colored Segments

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Dmitry has $$$n$$$ segments of different colors on the coordinate axis $$$Ox$$$. Each segment is characterized by three integers $$$l_i$$$, $$$r_i$$$ and $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$$$), where $$$l_i$$$ and $$$r_i$$$ are are the coordinates of the ends of the $$$i$$$-th segment, and $$$c_i$$$ is its color.

Dmitry likes to find the minimum distances between segments. However, he considers pairs of segments of the same color uninteresting. Therefore, he wants to know for each segment the distance from this segment to the nearest differently colored segment.

The distance between two segments is the minimum of the distances between a point of the first segment and a point of the second segment. In particular, if the segments intersect, then the distance between them is equal to $$$0$$$.

For example, Dmitry has $$$5$$$ segments:

 The first segment intersects with the second (and these are segments of different colors), so the answers for them are equal to $$$0$$$.

 For the $$$3$$$-rd segment, the nearest segment of a different color is the $$$2$$$-nd segment, the distance to which is equal to $$$2$$$.

 For the $$$4$$$-th segment, the nearest segment of a different color is the $$$5$$$-th segment, the distance to which is equal to $$$1$$$.

 The $$$5$$$-th segment lies inside the $$$2$$$-nd segment (and these are segments of different colors), so the answers for them are equal to $$$0$$$.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The descriptions of the test cases follow.

The first line of description of each test case contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of segments.

The next $$$n$$$ lines contain descriptions of the segments. Each segment is described by three integers $$$l_i$$$, $$$r_i$$$ and $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$$$) — coordinates of the left and right ends of $$$i$$$-th segment, as well as the color of this segment. It is guaranteed that there are at least $$$2$$$ segments of different colors.

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

Output

For each test case, on a separate line print $$$n$$$ integers, where the $$$i$$$-th number is equal to the distance from the $$$i$$$-th segment to the nearest segment of a different color.

Examples

Input

9

3

1 2 1

3 4 1

5 6 2

2

100000000 200000000 1

900000000 1000000000 2

5

1 2 1

2 3 2

3 4 3

4 5 4

5 6 5

5

1 5 1

4 9 2

1 2 1

8 9 2

5 7 3

2

1 100 2

10 90 1

3

1 1 1

10 10 2

1000000000 1000000000 3

3

3 4 1

2 5 1

1 6 2

6

5 6 2

11 12 3

7 8 2

3 4 2

1 2 1

9 10 2

2

1 3 1

2 3 2

Output

3 1 1
700000000 700000000
0 0 0 0 0
0 0 2 1 0
0 0
9 9 999999990
0 0 0
3 1 3 1 1 1
0 0

Input

4

8

11 16 7

12 15 7

2 5 8

17 22 5

1 8 8

19 23 8

16 16 6

6 7 5

9

1 4 3

5 11 1

8 11 3

1 10 1

2 11 1

1 10 4

3 11 1

5 7 1

1 11 1

9

25 25 1

26 26 1

24 24 2

13 14 2

12 16 2

17 18 1

19 19 1

24 27 2

24 27 1

9

15 18 1

20 22 2

13 22 2

13 22 2

3 13 2

6 10 2

3 6 2

19 24 2

22 24 2

Output

0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 3 1 1 3 0 0
0 2 0 0 2 5 9 1 4

Note

In the first test case of the first sample there is only one segment of color $$$2$$$, and all other segments have color $$$1$$$. Therefore, for segments of color $$$1$$$, the answer is equal to the distance to the $$$3$$$rd segment, and for $$$3$$$rd one, the answer is equal to the minimum of the distances to segments of color $$$1$$$.

In the second test case of the first sample there are only $$$2$$$ segments, and for both of them the answer is equal to the distance between them.

In the third test case of the first sample, each segment intersects at least one of its ends with a segment of a different color, so all answers are equal to $$$0$$$.

The fourth test case of the first sample is described in the problem statement.

In the fifth test case of the first sample, one segment lies completely inside the other, and for both of them the answer is $$$0$$$.

In the sixth test case of the first sample, all segments are points of different colors.

question:
Dmitry has $$$n$$$ segments of different colors on the coordinate axis $$$Ox$$$. Each segment is characterized by three integers $$$l_i$$$, $$$r_i$$$ and $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$$$), where $$$l_i$$$ and $$$r_i$$$ are are the coordinates of the ends of the $$$i$$$-th segment, and $$$c_i$$$ is its color.
Dmitry likes to find the minimum distances between segments. However, he considers pairs of segments of the same color uninteresting. Therefore, he wants to know for each segment the distance from this segment to the nearest differently colored segment.
The distance between two segments is the minimum of the distances between a point of the first segment and a point of the second segment. In particular, if the segments intersect, then the distance between them is equal to $$$0$$$.
For example, Dmitry has $$$5$$$ segments:
 ![image](1.png)  -  The first segment intersects with the second (and these are segments of different colors), so the answers for them are equal to $$$0$$$. -  For the $$$3$$$-rd segment, the nearest segment of a different color is the $$$2$$$-nd segment, the distance to which is equal to $$$2$$$. -  For the $$$4$$$-th segment, the nearest segment of a different color is the $$$5$$$-th segment, the distance to which is equal to $$$1$$$. -  The $$$5$$$-th segment lies inside the $$$2$$$-nd segment (and these are segments of different colors), so the answers for them are equal to $$$0$$$.
Input
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.
The descriptions of the test cases follow.
The first line of description of each test case contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of segments.
The next $$$n$$$ lines contain descriptions of the segments. Each segment is described by three integers $$$l_i$$$, $$$r_i$$$ and $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$$$) — coordinates of the left and right ends of $$$i$$$-th segment, as well as the color of this segment. It is guaranteed that there are at least $$$2$$$ segments of different colors.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output
For each test case, on a separate line print $$$n$$$ integers, where the $$$i$$$-th number is equal to the distance from the $$$i$$$-th segment to the nearest segment of a different color.

Examples
Input
9
3
1 2 1
3 4 1
5 6 2
2
100000000 200000000 1
900000000 1000000000 2
5
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
5
1 5 1
4 9 2
1 2 1
8 9 2
5 7 3
2
1 100 2
10 90 1
3
1 1 1
10 10 2
1000000000 1000000000 3
3
3 4 1
2 5 1
1 6 2
6
5 6 2
11 12 3
7 8 2
3 4 2
1 2 1
9 10 2
2
1 3 1
2 3 2

Output
3 1 1
700000000 700000000
0 0 0 0 0
0 0 2 1 0
0 0
9 9 999999990
0 0 0
3 1 3 1 1 1
0 0

Input
4
8
11 16 7
12 15 7
2 5 8
17 22 5
1 8 8
19 23 8
16 16 6
6 7 5
9
1 4 3
5 11 1
8 11 3
1 10 1
2 11 1
1 10 4
3 11 1
5 7 1
1 11 1
9
25 25 1
26 26 1
24 24 2
13 14 2
12 16 2
17 18 1
19 19 1
24 27 2
24 27 1
9
15 18 1
20 22 2
13 22 2
13 22 2
3 13 2
6 10 2
3 6 2
19 24 2
22 24 2

Output
0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 3 1 1 3 0 0
0 2 0 0 2 5 9 1 4

Note
In the first test case of the first sample there is only one segment of color $$$2$$$, and all other segments have color $$$1$$$. Therefore, for segments of color $$$1$$$, the answer is equal to the distance to the $$$3$$$rd segment, and for $$$3$$$rd one, the answer is equal to the minimum of the distances to segments of color $$$1$$$.
In the second test case of the first sample there are only $$$2$$$ segments, and for both of them the answer is equal to the distance between them.
In the third test case of the first sample, each segment intersects at least one of its ends with a segment of a different color, so all answers are equal to $$$0$$$.
The fourth test case of the first sample is described in the problem statement.
In the fifth test case of the first sample, one segment lies completely inside the other, and for both of them the answer is $$$0$$$.
In the sixth test case of the first sample, all segments are points of different colors.

data_split: test


ASCII Expression

source: ACM International Collegiate Programming Contest, Asia Regional 2011, Japan

raw_problem:
Problem H: ASCII Expression

Mathematical expressions appearing in old papers and old technical articles are printed with typewriter in several lines, where a fixed-width or monospaced font is required to print characters (digits, symbols and spaces). Let us consider the following mathematical expression.

It is printed in the following four lines:

        4   2
( 1 - ---- )  * - 5 + 6
        2
       3

where “- 5” indicates unary minus followed by 5. We call such an expression of lines “ASCII expression”.

For helping those who want to evaluate ASCII expressions obtained through optical character recognition (OCR) from old papers, your job is to write a program that recognizes the structure of ASCII expressions and computes their values.

For the sake of simplicity, you may assume that ASCII expressions are constructed by the following rules. Its syntax is shown in Table H.1.

(1)
Terminal symbols are ‘0’,  ‘1’,  ‘2’,  ‘3’,  ‘4’,  ‘5’,  ‘6’,  ‘7’,  ‘8’,  ‘9’,  ‘+’,  ‘-’,  ‘*’,  ‘(’,  ‘)’, and  ‘ ’.

(2)
Nonterminal symbols are expr, term, factor, powexpr, primary, fraction and digit. The start symbol is expr.

(3)
A “cell” is a rectangular region of characters that corresponds to a terminal or nonterminal symbol (Figure H.1). In the cell, there are no redundant rows and columns that consist only of space characters. A cell corresponding to a terminal symbol consists of a single character. A cell corresponding to a nonterminal symbol contains cell(s) corresponding to its descendant(s) but never partially overlaps others.

(4)
Each cell has a base-line, a top-line, and a bottom-line. The base-lines of child cells of the right-hand side of rules I, II, III, and V should be aligned. Their vertical position defines the base-line position of their left-hand side cell.

Table H.1: Rules for constructing ASCII expressions (similar to Backus-Naur Form) The box indicates the cell of the terminal or nonterminal symbol that corresponds to a rectan- gular region of characters. Note that each syntactically-needed space character is explicitly
indicated by the period character denoted by, here.

(5)
powexpr consists of a primary and an optional digit. The digit is placed one line above the base-line of the primary cell. They are horizontally adjacent to each other. The base-line of a powexpr is that of the primary.

(6)
fraction is indicated by three or more consecutive hyphens called “vinculum”. Its dividend expr is placed just above the vinculum, and its divisor expr is placed just beneath it. The number of the hyphens of the vinculum, denoted by wh, is equal to 2 + max(w1, w2), where w1 and w2 indicate the width of the cell of the dividend and that of the divisor, respectively. These cells are centered, where there are ⌈(wh−wk)/2⌉ space characters to the left and ⌊(wh−wk)/2⌋ space characters to the right, (k = 1, 2). The base-line of a fraction is at the position of the vinculum.

(7)
digit consists of one character.

For example, the negative fraction is represented in three lines:

   3
- ---
   4

where the left-most hyphen means a unary minus operator. One space character is required between the unary minus and the vinculum of the fraction.

The fraction  is represented in four lines:

 3 + 4 * - 2
-------------
          2
   - 1 - 2

where the widths of the cells of the dividend and divisor are 11 and 8 respectively. Hence the number of hyphens of the vinculum is 2 + max(11, 8) = 13. The divisor is centered by ⌈(13−8)/2⌉ = 3 space characters (hyphens) to the left and ⌊(13−8)/2⌋ = 2 to the right.

The powexpr (42)3 is represented in two lines:

   2  3
( 4  )

where the cell for 2 is placed one line above the base-line of the cell for 4, and the cell for 3 is placed one line above the base-line of the cell for a primary (42).

Input

The input consists of multiple datasets, followed by a line containing a zero. Each dataset has the following format.

n
str1
str2
.
.
.
strn

n is a positive integer, which indicates the number of the following lines with the same length that represent the cell of an ASCII expression. strk is the k-th line of the cell where each space character is replaced with a period.

You may assume that n ≤ 20 and that the length of the lines is no more than 80.

Output

For each dataset, one line containing a non-negative integer less than 2011 should be output. The integer indicates the value of the ASCII expression in modular arithmetic under modulo 2011. The output should not contain any other characters.

There is no fraction with the divisor that is equal to zero or a multiple of 2011.

Note that powexpr x0 is defined as 1, and xy (y is a positive integer) is defined as the product x×x×...×x where the number of x's is equal to y.

A fractionis computed as the multiplication of x and the inverse of y, i.e., x× inv(y), under y modulo 2011. The inverse of y (1 ≤ y < 2011) is uniquely defined as the integer z (1 ≤ z < 2011) that satisfies z × y ≡ 1 (mod 2011), since 2011 is a prime number.

Sample Input

4
........4...2..........
(.1.-.----.)..*.-.5.+.6
........2..............
.......3...............
3
...3.
-.---
...4.
4
.3.+.4.*.-.2.
-------------
..........2..
...-.1.-.2...
2
...2..3
(.4..).
1
2.+.3.*.5.-.7.+.9
1
(.2.+.3.).*.(.5.-.7.).+.9
3
.2....3.
4..+.---
......5.
3
.2......-.-.3.
4..-.-.-------
..........5...
9
............1............
-------------------------
..............1..........
.1.+.-------------------.
................1........
......1.+.-------------..
..................1......
...........1.+.-------...
................1.+.2....
15
.................2......
................---.....
.......2.........5....3.
.(.---------.+.-----.)..
.....7...........3......
....---.+.1.............
.....4..................
------------------------
.......2................
......---...............
.......5.......2....2...
...(.-----.+.-----.)....
.......3.......3........
..............---.......
...............4........
2
.0....2....
3..+.4..*.5
20
............2............................2......................................
...........3............................3.......................................
..........----.........................----.....................................
............4............................4......................................
.....2.+.------.+.1...............2.+.------.+.1................................
............2............................2......................................
...........2............................2........................2..............
..........----.........................----.....................3...............
............2............................2.....................----.............
...........3............................3........................4..............
(.(.----------------.+.2.+.3.).*.----------------.+.2.).*.2.+.------.+.1.+.2.*.5
............2............................2.......................2..............
...........5............................5.......................2...............
..........----.........................----....................----.............
............6............................6.......................2..............
.........------.......................------....................3...............
............3............................3......................................
..........----.........................----.....................................
............2............................2......................................
...........7............................7.......................................
0

Output for the Sample Input

501
502
1
74
19
2010
821
821
1646
148
81
1933

solutions: ["MOD = 2011\nwhile 1:\n    n = int(input())\n    if n == 0:\n        break\n    S = [input() for i in range(n)]\n    w = len(S[0])\n\n    def parse(bcur, bright, top, bottom):\n        #print(\"parse\", bcur, bright, top, bottom)\n        base = -1\n        for i in range(bcur, bright):\n            for j in range(top, bottom+1):\n                if S[j][i] != '.':\n                    base = j\n                    break\n            if base != -1:\n                break\n        cur = bcur\n        def read():\n            nonlocal cur\n            c = None\n            while 0 <= base < n and cur < bright:\n                #print(\"cur\", base, cur, bright)\n                #print(S[base][cur:])\n                c = S[base][cur]\n                if c != '.':\n                    break\n                cur += 1\n            return c\n        def fraction():\n            nonlocal cur\n            #print(\"fraction\", cur, top, bottom)\n            left = cur\n            while cur < w and S[base][cur] == '-':\n                cur += 1\n            right = cur+1 if cur < w else cur\n            dividend = parse(left, right, top, base-1)\n            divisor = parse(left, right, base+1, bottom)\n            #print(\"deb\", S[base][cur:], dividend, divisor)\n            #print(\"<fraction\", dividend, divisor, (dividend * pow(divisor, MOD-2, MOD)) % MOD)\n            return (dividend * pow(divisor, MOD-2, MOD)) % MOD\n        def primary():\n            nonlocal cur\n            #print(\"primary\", cur, top, bottom)\n            c = read()\n            if c == '(':\n                cur += 1 # '('\n                v = expr()\n                cur += 1 # ')'\n                #print(\"<primary\", v)\n                return v\n            else:\n                cur += 1 # digit\n                #print(\"<primary\", c)\n                return int(c)\n        def powexpr():\n            nonlocal cur\n            #print(\"powexpr\", cur, top, bottom)\n            v = primary()\n            #print(\"<powexpr\", cur, base, v)\n            if 0 < base and cur < bright and S[base-1][cur] in \"0123456789\":\n                #print(\"abc\", v, int(S[base-1][cur]))\n                return pow(v, int(S[base-1][cur]), MOD)\n            return v\n        def factor():\n            nonlocal cur\n            #print(\"factor\", cur, top, bottom)\n            c = read()\n            if c == '-':\n                if S[base][cur+1] == '.':\n                    cur += 1 # '-'\n                    return -factor()\n                else:\n                    return fraction()\n            return powexpr()\n\n        def term():\n            nonlocal cur\n            #print(\"term\", cur, top, bottom)\n            result = 1\n            while 1:\n                v = factor()\n                result *= v\n                result %= MOD\n                c = read()\n                if c != '*':\n                    break\n                cur += 1\n            return result\n\n        def expr():\n            nonlocal cur\n            #print(\"expr\", cur, top, bottom)\n            op = '+'\n            result = 0\n            while 1:\n                v = term()\n                #print(\"<expr\", v)\n                c = read()\n                result += v if op == '+' else MOD-v\n                result %= MOD\n                if not c or c not in '+-':\n                    #print(\"break\", result, v, c, op)\n                    break\n                cur += 1\n                op = c\n            #print(\"<result\", result)\n            return result\n        v = expr()\n        #print(\"<parse\", v)\n        return v\n    print(parse(0, w, 0, n-1))\n"]

question:
Problem H: ASCII Expression

Mathematical expressions appearing in old papers and old technical articles are printed with typewriter in several lines, where a fixed-width or monospaced font is required to print characters (digits, symbols and spaces). Let us consider the following mathematical expression.

![image](1.png)

It is printed in the following four lines:

        4   2
( 1 - ---- )  * - 5 + 6
        2
       3

where “- 5” indicates unary minus followed by 5. We call such an expression of lines “ASCII expression”.

For helping those who want to evaluate ASCII expressions obtained through optical character recognition (OCR) from old papers, your job is to write a program that recognizes the structure of ASCII expressions and computes their values.

For the sake of simplicity, you may assume that ASCII expressions are constructed by the following rules. Its syntax is shown in Table H.1.

(1)
Terminal symbols are ‘0’,  ‘1’,  ‘2’,  ‘3’,  ‘4’,  ‘5’,  ‘6’,  ‘7’,  ‘8’,  ‘9’,  ‘+’,  ‘-’,  ‘*’,  ‘(’,  ‘)’, and  ‘ ’.

(2)
Nonterminal symbols are expr, term, factor, powexpr, primary, fraction and digit. The start symbol is expr.

(3)
A “cell” is a rectangular region of characters that corresponds to a terminal or nonterminal symbol (Figure H.1). In the cell, there are no redundant rows and columns that consist only of space characters. A cell corresponding to a terminal symbol consists of a single character. A cell corresponding to a nonterminal symbol contains cell(s) corresponding to its descendant(s) but never partially overlaps others.

(4)
Each cell has a base-line, a top-line, and a bottom-line. The base-lines of child cells of the right-hand side of rules I, II, III, and V should be aligned. Their vertical position defines the base-line position of their left-hand side cell.
Table H.1: Rules for constructing ASCII expressions (similar to Backus-Naur Form) The box indicates the cell of the terminal or nonterminal symbol that corresponds to a rectan- gular region of characters. Note that each syntactically-needed space character is explicitly
indicated by the period character denoted by, here.

![image](2.png)

(5)
powexpr consists of a primary and an optional digit. The digit is placed one line above the base-line of the primary cell. They are horizontally adjacent to each other. The base-line of a powexpr is that of the primary.

(6)
fraction is indicated by three or more consecutive hyphens called “vinculum”. Its dividend expr is placed just above the vinculum, and its divisor expr is placed just beneath it. The number of the hyphens of the vinculum, denoted by w_{h}, is equal to 2 + max(w_{1}, w_{2}), where w_{1} and w_{2} indicate the width of the cell of the dividend and that of the divisor, respectively. These cells are centered, where there are ⌈(w_{h}−w_{k})/2⌉ space characters to the left and ⌊(w_{h}−w_{k})/2⌋ space characters to the right, (k = 1, 2). The base-line of a fraction is at the position of the vinculum.

(7)
digit consists of one character.

For example, the negative fraction![image](3.png) is represented in three lines:

   3
- ---
   4

where the left-most hyphen means a unary minus operator. One space character is required between the unary minus and the vinculum of the fraction.
The fraction ![image](4.png) is represented in four lines:

 3 + 4 * - 2
-------------
          2
   - 1 - 2

where the widths of the cells of the dividend and divisor are 11 and 8 respectively. Hence the number of hyphens of the vinculum is 2 + max(11, 8) = 13. The divisor is centered by ⌈(13−8)/2⌉ = 3 space characters (hyphens) to the left and ⌊(13−8)/2⌋ = 2 to the right.

The powexpr (4^{2})^{3} is represented in two lines:

   2  3
( 4  )

where the cell for 2 is placed one line above the base-line of the cell for 4, and the cell for 3 is placed one line above the base-line of the cell for a primary (4^{2}).

Input

The input consists of multiple datasets, followed by a line containing a zero. Each dataset has the following format.

n
str
_{1}
str
_{2}
.
.
.
str
_{n}

n is a positive integer, which indicates the number of the following lines with the same length that represent the cell of an ASCII expression. str_{k} is the k-th line of the cell where each space character is replaced with a period.

You may assume that n ≤ 20 and that the length of the lines is no more than 80.

Output

For each dataset, one line containing a non-negative integer less than 2011 should be output. The integer indicates the value of the ASCII expression in modular arithmetic under modulo 2011. The output should not contain any other characters.

There is no fraction with the divisor that is equal to zero or a multiple of 2011.

Note that powexpr x^{0} is defined as 1, and x^{y} (y is a positive integer) is defined as the product x×x×...×x where the number of x's is equal to y.

A fraction![image](5.png)is computed as the multiplication of x and the inverse of y, i.e., x× inv(y), under y modulo 2011. The inverse of y (1 ≤ y < 2011) is uniquely defined as the integer z (1 ≤ z < 2011) that satisfies z × y ≡ 1 (mod 2011), since 2011 is a prime number.

Sample Input

4
........4...2..........
(.1.-.----.)..*.-.5.+.6
........2..............
.......3...............
3
...3.
-.---
...4.
4
.3.+.4.*.-.2.
-------------
..........2..
...-.1.-.2...
2
...2..3
(.4..).
1
2.+.3.*.5.-.7.+.9
1
(.2.+.3.).*.(.5.-.7.).+.9
3
.2....3.
4..+.---
......5.
3
.2......-.-.3.
4..-.-.-------
..........5...
9
............1............
-------------------------
..............1..........
.1.+.-------------------.
................1........
......1.+.-------------..
..................1......
...........1.+.-------...
................1.+.2....
15
.................2......
................---.....
.......2.........5....3.
.(.---------.+.-----.)..
.....7...........3......
....---.+.1.............
.....4..................
------------------------
.......2................
......---...............
.......5.......2....2...
...(.-----.+.-----.)....
.......3.......3........
..............---.......
...............4........
2
.0....2....
3..+.4..*.5
20
............2............................2......................................
...........3............................3.......................................
..........----.........................----.....................................
............4............................4......................................
.....2.+.------.+.1...............2.+.------.+.1................................
............2............................2......................................
...........2............................2........................2..............
..........----.........................----.....................3...............
............2............................2.....................----.............
...........3............................3........................4..............
(.(.----------------.+.2.+.3.).*.----------------.+.2.).*.2.+.------.+.1.+.2.*.5
............2............................2.......................2..............
...........5............................5.......................2...............
..........----.........................----....................----.............
............6............................6.......................2..............
.........------.......................------....................3...............
............3............................3......................................
..........----.........................----.....................................
............2............................2......................................
...........7............................7.......................................
0

Output for the Sample Input

501
502
1
74
19
2010
821
821
1646
148
81
1933

source: aizu

image_tags: Math Others Math Math Math

data_split: test