E. Lightbulb for Minister

problem_index: E

time_limit: 1 second

memory_limit: 256 megabytes

question:
The Minister for education is coming! Naturally, nobody wants to perform poorly in front of such a honored guest. However, two hours before the arrival it turned out that one of the classes has a malfunctioning lightbulb — for some reason it doesn't get enough energy. The solution was found quickly: all we've got to do is to change the location of the lightbulb so that it got the maximum amount of energy.
Everybody knows that the power of the lightbulb equals ![image](1.png), where C is some constant value and r_{i} is the Euclidean distance from the bulb to the i-th generator. Consequently, our task is to minimize ![image](2.png). Of course, we know the positions of all generators.
The bulb should be on the ceiling of the class. The ceiling of the class is in the form of a strictly convex m-gon (the class itself has the form of a right prism with a strictly convex m-gon at the bottom). Help to find the optimum location for the bulb. Assume that all generators are in the plane of the class ceiling. Consider that the plane of the class ceiling has some Cartesian coordinate system introduced.

Input
The first line contains integer n (2 ≤ n ≤ 10^{5}) — the number of generators. Each of the next n lines contains a pair of integers x_{i}, y_{i}, representing the coordinates of the i-th generator in the plane of the class ceiling. It's guaranteed that no two generators have the same location.
The next line contains integer m (3 ≤ m ≤ 10^{5}) — the number of vertexes in the convex polygon that describes the ceiling of the class. Each of the following m lines contains a pair of integers p_{i}, q_{i}, representing the coordinates of the i-th point of the polygon in the clockwise order. It's guaranteed that the polygon is strictly convex.
The absolute value of all the coordinates don't exceed 10^{6}.

Output
Print a single real number — the minimum value of the sum of squares of distances from the generators to the point of the lightbulb's optimal position. The answer will be considered valid if its absolute or relative error doesn't exceed 10^{ - 4}.

Examples
Input
4
3 2
3 4
5 4
5 2
4
3 3
4 4
5 3
4 2

Output
8.00000000

Note
We'll define a strictly convex polygon as a convex polygon with the following property: no three vertices of the polygon lie on the same line.

source: codeforces

raw_problem:
E. Lightbulb for Minister

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

The Minister for education is coming! Naturally, nobody wants to perform poorly in front of such a honored guest. However, two hours before the arrival it turned out that one of the classes has a malfunctioning lightbulb — for some reason it doesn't get enough energy. The solution was found quickly: all we've got to do is to change the location of the lightbulb so that it got the maximum amount of energy.

Everybody knows that the power of the lightbulb equals , where C is some constant value and ri is the Euclidean distance from the bulb to the i-th generator. Consequently, our task is to minimize . Of course, we know the positions of all generators.

The bulb should be on the ceiling of the class. The ceiling of the class is in the form of a strictly convex m-gon (the class itself has the form of a right prism with a strictly convex m-gon at the bottom). Help to find the optimum location for the bulb. Assume that all generators are in the plane of the class ceiling. Consider that the plane of the class ceiling has some Cartesian coordinate system introduced.

Input

The first line contains integer n (2 ≤ n ≤ 105) — the number of generators. Each of the next n lines contains a pair of integers xi, yi, representing the coordinates of the i-th generator in the plane of the class ceiling. It's guaranteed that no two generators have the same location.

The next line contains integer m (3 ≤ m ≤ 105) — the number of vertexes in the convex polygon that describes the ceiling of the class. Each of the following m lines contains a pair of integers pi, qi, representing the coordinates of the i-th point of the polygon in the clockwise order. It's guaranteed that the polygon is strictly convex.

The absolute value of all the coordinates don't exceed 106.

Output

Print a single real number — the minimum value of the sum of squares of distances from the generators to the point of the lightbulb's optimal position. The answer will be considered valid if its absolute or relative error doesn't exceed 10 - 4.

Examples

Input

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

Output

8.00000000

Note

We'll define a strictly convex polygon as a convex polygon with the following property: no three vertices of the polygon lie on the same line.

image_tags: Math Math

data_split: test


B. A Leapfrog in the Array

problem_index: B

time_limit: 2 seconds

memory_limit: 512 megabytes

solutions: ["import sys\n[n, q] = map(int, sys.stdin.readline().strip().split())\nqis = [int(sys.stdin.readline().strip()) for _ in range(q)]\n\ndef query(n, q):\n\td = 2 * n - q\n\twhile d % 2 == 0:\n\t\td //= 2\n\treturn n - d // 2\nfor qi in qis:\n\tprint(query(n, qi))\n", "import math\nfrom decimal import Decimal\n\ndef na():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\treturn (n, b)\n\ndef nab():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\tc = [int(x) for x in input().split()]\n\treturn (n, b, c)\n\ndef dv():\n\t(n, m) = map(int, input().split())\n\treturn (n, m)\n\ndef dva():\n\t(n, m) = map(int, input().split())\n\ta = [int(x) for x in input().split()]\n\tb = [int(x) for x in input().split()]\n\treturn (n, m, b)\n\ndef eratosthenes(n):\n\tsieve = list(range(n + 1))\n\tfor i in sieve:\n\t\tif i > 1:\n\t\t\tfor j in range(i + i, len(sieve), i):\n\t\t\t\tsieve[j] = 0\n\treturn sorted(set(sieve))\n\ndef nm():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\tm = int(input())\n\tc = [int(x) for x in input().split()]\n\treturn (n, b, m, c)\n\ndef dvs():\n\tn = int(input())\n\tm = int(input())\n\treturn (n, m)\n(n, q) = map(int, input().split())\nans = []\nfor i in range(q):\n\tx = int(input())\n\tans.append(x)\nfor i in ans:\n\td = 2 * n - i\n\twhile d % 2 == 0:\n\t\td //= 2\n\tprint(n - d // 2)\n", "import sys\n\ndef query(n, a):\n\twhile not a & 1:\n\t\ta += n - a // 2\n\treturn a + 1 >> 1\n(n, q) = map(int, sys.stdin.readline().split())\narr = [int(sys.stdin.readline()) for _ in range(q)]\nsys.stdout.write('\\n'.join((str(query(n, a)) for a in arr)))\n", "import io\nimport os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(n, q) = map(int, input().split())\nfor _ in range(q):\n\tx = int(input())\n\tfor r in range(100):\n\t\tnum = 2 * n - 2 ** r - x\n\t\tden = 2 ** (r + 1)\n\t\tif num % den == 0 and n - num // den >= 1 and (n - num // den <= n):\n\t\t\tprint(n - num // den)\n\t\t\tbreak\n", "import sys\ninput = sys.stdin.readline\n(n, q) = list(map(int, input().split()))\nx = [int(input()) for i in range(q)]\nfor num in x:\n\tnum = 2 * n - num\n\twhile True:\n\t\tif num % 2 == 0:\n\t\t\tnum = num // 2\n\t\telse:\n\t\t\tbreak\n\tprint(n - num // 2)\n", "import math\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n(n, k) = map(int, input().split())\nfor i in range(k):\n\tr = int(input())\n\tif r % 2 == 1:\n\t\tprint((r + 1) // 2)\n\telse:\n\t\tind = r\n\t\twhile ind % 2 == 0:\n\t\t\tind = ind + (n - ind // 2)\n\t\tprint((ind + 1) // 2)\n", "import sys\ninput = sys.stdin.readline\n(n, q) = list(map(int, input().split()))\nfor i in range(q):\n\ta = int(input())\n\tif a % 2 != 0:\n\t\tprint((a + 1) // 2)\n\telse:\n\t\tb = a // 2\n\t\twhile 1 > 0:\n\t\t\ta = a + (n - b)\n\t\t\tb = a // 2\n\t\t\tif a % 2 != 0:\n\t\t\t\tprint((a + 1) // 2)\n\t\t\t\tbreak\n", "def move(x):\n\ta = x.pop()\n\tif a != None:\n\t\tfor i in range(len(x) - 1, -1, -1):\n\t\t\tif x[i] == None:\n\t\t\t\tx[i] = a\n\t\t\t\treturn x\n\treturn x\n\ndef gen(n):\n\tx = []\n\tfor i in range(1, 2 * n):\n\t\tif i % 2 == 1:\n\t\t\tx.append((i + 1) // 2)\n\t\telse:\n\t\t\tx.append(None)\n\treturn x\n\ndef solve(x, n):\n\tprint(*x)\n\twhile len(x) != n:\n\t\tx = move(x)\n\t\tprint(*x)\n\treturn x\nimport io\nimport os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(n, q) = map(int, input().split())\nfor _ in range(q):\n\tx = int(input())\n\tfor r in range(100):\n\t\tnum = 2 * n - 2 ** r - x\n\t\tden = 2 ** (r + 1)\n\t\tif num % den == 0 and num >= 0 and (den > 0) and (n - num // den >= 1) and (n - num // den <= n):\n\t\t\ti = n - num // den\n\t\t\tprint(i)\n\t\t\tbreak\n", "import sys\n\ndef query(n, a):\n\twhile a % 2 == 0:\n\t\ta += n - a // 2\n\treturn a // 2 + 1\n(n, q) = list(map(int, sys.stdin.readline().split()))\nsys.stdout.write('\\n'.join((str(query(n, int(input()))) for _ in range(q))))\n", "from sys import *\ninput = stdin.readline\n(n, q) = map(int, input().split())\nfor _ in range(q):\n\ti = int(input())\n\twhile i % 2 == 0:\n\t\ti += n - i // 2\n\tprint((i + 1) // 2)\n", "import sys\nimport bisect\ninput = sys.stdin.readline\nt = 1\nmod = 10 ** 9 + 7\nfor _ in range(t):\n\t(n, q) = map(int, input().split())\n\tfor i in range(q):\n\t\tx = int(input())\n\t\tif x % 2 != 0:\n\t\t\tprint((x + 1) // 2)\n\t\telse:\n\t\t\tloop = n - x // 2\n\t\t\twhile 1:\n\t\t\t\tx += loop\n\t\t\t\tif x % 2 != 0:\n\t\t\t\t\tprint((x - 1) // 2 + 1)\n\t\t\t\t\tbreak\n\t\t\t\tloop //= 2\n", "from sys import stdin, stdout\nimport heapq\nimport cProfile, math\nfrom collections import Counter, defaultdict, deque\nfrom bisect import bisect_left, bisect, bisect_right\nimport itertools\nfrom copy import deepcopy\nfrom fractions import Fraction\nimport sys, threading\nimport operator as op\nfrom functools import reduce\nimport sys\nsys.setrecursionlimit(10 ** 6)\nthreading.stack_size(2 ** 27)\nfac_warm_up = False\nprintHeap = str()\nmemory_constrained = False\nP = 10 ** 9 + 7\n\nclass MergeFind:\n\n\tdef __init__(self, n):\n\t\tself.parent = list(range(n))\n\t\tself.size = [1] * n\n\t\tself.num_sets = n\n\t\tself.lista = [[_] for _ in range(n)]\n\n\tdef find(self, a):\n\t\tto_update = []\n\t\twhile a != self.parent[a]:\n\t\t\tto_update.append(a)\n\t\t\ta = self.parent[a]\n\t\tfor b in to_update:\n\t\t\tself.parent[b] = a\n\t\treturn self.parent[a]\n\n\tdef merge(self, a, b):\n\t\ta = self.find(a)\n\t\tb = self.find(b)\n\t\tif a == b:\n\t\t\treturn\n\t\tif self.size[a] < self.size[b]:\n\t\t\t(a, b) = (b, a)\n\t\tself.num_sets -= 1\n\t\tself.parent[b] = a\n\t\tself.size[a] += self.size[b]\n\t\tself.lista[a] += self.lista[b]\n\n\tdef set_size(self, a):\n\t\treturn self.size[self.find(a)]\n\n\tdef __len__(self):\n\t\treturn self.num_sets\n\ndef display(string_to_print):\n\tstdout.write(str(string_to_print) + '\\n')\n\ndef prime_factors(n):\n\tfactors = dict()\n\tfor i in range(2, math.ceil(math.sqrt(n)) + 1):\n\t\twhile n % i == 0:\n\t\t\tif i in factors:\n\t\t\t\tfactors[i] += 1\n\t\t\telse:\n\t\t\t\tfactors[i] = 1\n\t\t\tn = n // i\n\tif n > 2:\n\t\tfactors[n] = 1\n\treturn factors\n\ndef all_factors(n):\n\treturn set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))\n\ndef fibonacci_modP(n, MOD):\n\tif n < 2:\n\t\treturn 1\n\treturn (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD\n\ndef factorial_modP_Wilson(n, p):\n\tif p <= n:\n\t\treturn 0\n\tres = p - 1\n\tfor i in range(n + 1, p):\n\t\tres = res * cached_fn(InverseEuler, i, p) % p\n\treturn res\n\ndef binary(n, digits=20):\n\tb = bin(n)[2:]\n\tb = '0' * (digits - len(b)) + b\n\treturn b\n\ndef is_prime(n):\n\tif n < 4:\n\t\treturn True\n\tif n % 2 == 0:\n\t\treturn False\n\tif n % 3 == 0:\n\t\treturn False\n\ti = 5\n\tw = 2\n\twhile i * i <= n:\n\t\tif n % i == 0:\n\t\t\treturn False\n\t\ti += w\n\t\tw = 6 - w\n\treturn True\n\ndef generate_primes(n):\n\tprime = [True for i in range(n + 1)]\n\tp = 2\n\twhile p * p <= n:\n\t\tif prime[p]:\n\t\t\tfor i in range(p * 2, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 1\n\treturn prime\nfactorial_modP = []\n\ndef warm_up_fac(MOD):\n\tnonlocal factorial_modP, fac_warm_up\n\tif fac_warm_up:\n\t\treturn\n\tfactorial_modP = [1 for _ in range(fac_warm_up_size + 1)]\n\tfor i in range(2, fac_warm_up_size):\n\t\tfactorial_modP[i] = factorial_modP[i - 1] * i % MOD\n\tfac_warm_up = True\n\ndef InverseEuler(n, MOD):\n\treturn pow(n, MOD - 2, MOD)\n\ndef nCr(n, r, MOD):\n\tnonlocal fac_warm_up, factorial_modP\n\tif not fac_warm_up:\n\t\twarm_up_fac(MOD)\n\t\tfac_warm_up = True\n\treturn factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD\n\ndef test_print(*args):\n\tif testingMode:\n\t\tprint(args)\n\ndef display_list(list1, sep=' '):\n\tstdout.write(sep.join(map(str, list1)) + '\\n')\n\ndef display_2D_list(li):\n\tfor i in li:\n\t\tprint(i)\n\ndef prefix_sum(li):\n\tsm = 0\n\tres = []\n\tfor i in li:\n\t\tsm += i\n\t\tres.append(sm)\n\treturn res\n\ndef get_int():\n\treturn int(stdin.readline().strip())\n\ndef get_tuple():\n\treturn list(map(int, stdin.readline().split()))\n\ndef get_list():\n\treturn list(map(int, stdin.readline().split()))\nmemory = dict()\n\ndef clear_cache():\n\tnonlocal memory\n\tmemory = dict()\n\ndef cached_fn(fn, *args):\n\tnonlocal memory\n\tif args in memory:\n\t\treturn memory[args]\n\telse:\n\t\tresult = fn(*args)\n\t\tmemory[args] = result\n\t\treturn result\n\ndef ncr(n, r):\n\treturn math.factorial(n) / (math.factorial(n - r) * math.factorial(r))\n\ndef binary_search(i, li):\n\tfn = lambda x: li[x] - x // i\n\tx = -1\n\tb = len(li)\n\twhile b >= 1:\n\t\twhile b + x < len(li) and fn(b + x) > 0:\n\t\t\tx += b\n\t\tb = b // 2\n\treturn x\nTestCases = False\nfac_warm_up_size = 10 ** 5 + 100\noptimise_for_recursion = True\n\ndef main():\n\t(n, q) = get_tuple()\n\tdiff = (n - 1) * 2 - 1\n\tfor _ in range(q):\n\t\tnum = get_int()\n\t\tif num % 2 != 0:\n\t\t\tprint((num + 1) // 2)\n\t\t\tcontinue\n\t\tnumerator = diff - num + 3\n\t\tn1 = list(bin(numerator))\n\t\tk = 0\n\t\tfor i in n1:\n\t\t\tif i == '1':\n\t\t\t\tk = 0\n\t\t\telse:\n\t\t\t\tk += 1\n\t\tnumerator = diff - num + 3\n\t\tx = (numerator // 2 ** k - 1) // 2\n\t\tprint(n - x)\nif TestCases:\n\tfor i in range(get_int()):\n\t\tmain()\nelse:\n\tmain() if not optimise_for_recursion else threading.Thread(target=main).start()\n", "import sys\ninput = sys.stdin.buffer.readline\nfrom math import ceil\n(n, q) = map(int, input().split())\nfor i in range(q):\n\tindx = int(input())\n\tcount = indx\n\tif indx % 2 == 0:\n\t\tcount = 0\n\t\tpro = n - indx // 2\n\t\twhile pro % 2 == 0:\n\t\t\tcount += pro\n\t\t\tpro //= 2\n\t\tcount += pro\n\t\tcount += indx\n\tprint((count + 1) // 2)\n"]

source: codeforces

raw_problem:
B. A Leapfrog in the Array

time limit per test
2 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored with easy solutions of this problem, and he has come up with the following extravagant algorithm.

Let's consider that initially array contains n numbers from 1 to n and the number i is located in the cell with the index 2i - 1 (Indices are numbered starting from one) and other cells of the array are empty. Each step Dima selects a non-empty array cell with the maximum index and moves the number written in it to the nearest empty cell to the left of the selected one. The process continues until all n numbers will appear in the first n cells of the array. For example if n = 4, the array is changing as follows:

You have to write a program that allows you to determine what number will be in the cell with index x (1 ≤ x ≤ n) after Dima's algorithm finishes.

Input

The first line contains two integers n and q (1 ≤ n ≤ 1018, 1 ≤ q ≤ 200 000), the number of elements in the array and the number of queries for which it is needed to find the answer.

Next q lines contain integers xi (1 ≤ xi ≤ n), the indices of cells for which it is necessary to output their content after Dima's algorithm finishes.

Output

For each of q queries output one integer number, the value that will appear in the corresponding array cell after Dima's algorithm finishes.

Examples

Input

4 3
2
3
4

Output

3
2
4

Input

13 4
10
5
4
8

Output

13
3
8
9

Note

The first example is shown in the picture.

In the second example the final array is [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7].

question:
Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored with easy solutions of this problem, and he has come up with the following extravagant algorithm.
Let's consider that initially array contains n numbers from 1 to n and the number i is located in the cell with the index 2i - 1 (Indices are numbered starting from one) and other cells of the array are empty. Each step Dima selects a non-empty array cell with the maximum index and moves the number written in it to the nearest empty cell to the left of the selected one. The process continues until all n numbers will appear in the first n cells of the array. For example if n = 4, the array is changing as follows:
 ![image](1.png) You have to write a program that allows you to determine what number will be in the cell with index x (1 ≤ x ≤ n) after Dima's algorithm finishes.

Input
The first line contains two integers n and q (1 ≤ n ≤ 10^{18}, 1 ≤ q ≤ 200 000), the number of elements in the array and the number of queries for which it is needed to find the answer.
Next q lines contain integers x_{i} (1 ≤ x_{i} ≤ n), the indices of cells for which it is necessary to output their content after Dima's algorithm finishes.

Output
For each of q queries output one integer number, the value that will appear in the corresponding array cell after Dima's algorithm finishes.

Examples
Input
4 3
2
3
4

Output
3
2
4

Input
13 4
10
5
4
8

Output
13
3
8
9

Note
The first example is shown in the picture.
In the second example the final array is [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7].

data_split: test


D. Powerful array

problem_index: D

time_limit: 5 seconds

memory_limit: 256 megabytes

note:
Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):
![image](images/cf_86_D/1.png)
K1 = 3
K2 = 2
K3 = 1
32·1 + 22·2 + 12·3 = 20

difficulty: HARD

source: codeforces

raw_problem:
D. Powerful array

time limit per test
5 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

An array of positive integers a1, a2, ..., an is given. Let us consider its arbitrary subarray al, al + 1..., ar, where 1 ≤ l ≤ r ≤ n. For every positive integer s denote by Ks the number of occurrences of s into the subarray. We call the power of the subarray the sum of products Ks·Ks·s for every positive integer s. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.

You should calculate the power of t given subarrays.

Input

First line contains two integers n and t (1 ≤ n, t ≤ 200000) — the array length and the number of queries correspondingly.

Second line contains n positive integers ai (1 ≤ ai ≤ 106) — the elements of the array.

Next t lines contain two positive integers l, r (1 ≤ l ≤ r ≤ n) each — the indices of the left and the right ends of the corresponding subarray.

Output

Output t lines, the i-th line of the output should contain single positive integer — the power of the i-th query subarray.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout stream (also you may use %I64d).

Examples

Input

3 2
1 2 1
1 2
1 3

Output

3
6

Input

8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

Output

20
20
20

Note

Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):
 Then K1 = 3, K2 = 2, K3 = 1, so the power is equal to 32·1 + 22·2 + 12·3 = 20.

question:
An array of positive integers a_{1}, a_{2}, ..., a_{n} is given. Let us consider its arbitrary subarray a_{l}, a_{l + 1}..., a_{r}, where 1 ≤ l ≤ r ≤ n. For every positive integer s denote by K_{s} the number of occurrences of s into the subarray. We call the power of the subarray the sum of products K_{s}·K_{s}·s for every positive integer s. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.
You should calculate the power of t given subarrays.

Input
First line contains two integers n and t (1 ≤ n, t ≤ 200000) — the array length and the number of queries correspondingly.
Second line contains n positive integers a_{i} (1 ≤ a_{i} ≤ 10^{6}) — the elements of the array.
Next t lines contain two positive integers l, r (1 ≤ l ≤ r ≤ n) each — the indices of the left and the right ends of the corresponding subarray.

Output
Output t lines, the i-th line of the output should contain single positive integer — the power of the i-th query subarray.
Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout stream (also you may use %I64d).

Examples
Input
3 2
1 2 1
1 2
1 3

Output
3
6

Input
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

Output
20
20
20

Note
Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):
![image](1.png) Then K_{1} = 3, K_{2} = 2, K_{3} = 1, so the power is equal to 3^{2}·1 + 2^{2}·2 + 1^{2}·3 = 20.

tags: ['Mathematics', 'Amortized analysis', 'Data structures', 'Implementation']

skill_types: ['Data structures', 'Amortized analysis']

raw_tags: ['two pointers', 'data structures', 'math', 'implementation']

data_split: test


D. Zigzag

problem_index: D

time_limit: 3 seconds

memory_limit: 256 megabytes

question:
The court wizard Zigzag wants to become a famous mathematician. For that, he needs his own theorem, like the Cauchy theorem, or his sum, like the Minkowski sum. But most of all he wants to have his sequence, like the Fibonacci sequence, and his function, like the Euler's totient function.
The Zigag's sequence with the zigzag factor z is an infinite sequence S_{i}^{z} (i ≥ 1; z ≥ 2), that is determined as follows:
 -  S_{i}^{z} = 2, when ![image](1.png); -  ![image](2.png), when ![image](3.png); -  ![image](4.png), when ![image](5.png). Operation ![image](6.png) means taking the remainder from dividing number x by number y. For example, the beginning of sequence S_{i}^{3} (zigzag factor 3) looks as follows: 1, 2, 3, 2, 1, 2, 3, 2, 1.
Let's assume that we are given an array a, consisting of n integers. Let's define element number i (1 ≤ i ≤ n) of the array as a_{i}. The Zigzag function is function ![image](7.png), where l, r, z satisfy the inequalities 1 ≤ l ≤ r ≤ n, z ≥ 2.
To become better acquainted with the Zigzag sequence and the Zigzag function, the wizard offers you to implement the following operations on the given array a.
 -  The assignment operation. The operation parameters are (p, v). The operation denotes assigning value v to the p-th array element. After the operation is applied, the value of the array element a_{p} equals v. -  The Zigzag operation. The operation parameters are (l, r, z). The operation denotes calculating the Zigzag function Z(l, r, z). Explore the magical powers of zigzags, implement the described operations.

Input
The first line contains integer n (1 ≤ n ≤ 10^{5}) — The number of elements in array a. The second line contains n space-separated integers: a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{9}) — the elements of the array.
The third line contains integer m (1 ≤ m ≤ 10^{5}) — the number of operations. Next m lines contain the operations' descriptions. An operation's description starts with integer t_{i} (1 ≤ t_{i} ≤ 2) — the operation type.
 -  If t_{i} = 1 (assignment operation), then on the line follow two space-separated integers: p_{i}, v_{i} (1 ≤ p_{i} ≤ n; 1 ≤ v_{i} ≤ 10^{9}) — the parameters of the assigning operation. -  If t_{i} = 2 (Zigzag operation), then on the line follow three space-separated integers: l_{i}, r_{i}, z_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n; 2 ≤ z_{i} ≤ 6) — the parameters of the Zigzag operation. You should execute the operations in the order, in which they are given in the input.

Output
For each Zigzag operation print the calculated value of the Zigzag function on a single line. Print the values for Zigzag functions in the order, in which they are given in the input.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

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

Output
5
26
38

Note
Explanation of the sample test:
 -  Result of the first operation is Z(2, 3, 2) = 3·1 + 1·2 = 5. -  Result of the second operation is Z(1, 5, 3) = 2·1 + 3·2 + 1·3 + 5·2 + 5·1 = 26. -  After the third operation array a is equal to 2, 3, 5, 5, 5. -  Result of the forth operation is Z(1, 5, 3) = 2·1 + 3·2 + 5·3 + 5·2 + 5·1 = 38.

difficulty: HARD

source: codeforces

raw_problem:
D. Zigzag

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

The court wizard Zigzag wants to become a famous mathematician. For that, he needs his own theorem, like the Cauchy theorem, or his sum, like the Minkowski sum. But most of all he wants to have his sequence, like the Fibonacci sequence, and his function, like the Euler's totient function.

The Zigag's sequence with the zigzag factor z is an infinite sequence Siz (i ≥ 1; z ≥ 2), that is determined as follows:

 Siz = 2, when ;

 , when ;

 , when .

Operation  means taking the remainder from dividing number x by number y. For example, the beginning of sequence Si3 (zigzag factor 3) looks as follows: 1, 2, 3, 2, 1, 2, 3, 2, 1.

Let's assume that we are given an array a, consisting of n integers. Let's define element number i (1 ≤ i ≤ n) of the array as ai. The Zigzag function is function , where l, r, z satisfy the inequalities 1 ≤ l ≤ r ≤ n, z ≥ 2.

To become better acquainted with the Zigzag sequence and the Zigzag function, the wizard offers you to implement the following operations on the given array a.

 The assignment operation. The operation parameters are (p, v). The operation denotes assigning value v to the p-th array element. After the operation is applied, the value of the array element ap equals v.

 The Zigzag operation. The operation parameters are (l, r, z). The operation denotes calculating the Zigzag function Z(l, r, z).

Explore the magical powers of zigzags, implement the described operations.

Input

The first line contains integer n (1 ≤ n ≤ 105) — The number of elements in array a. The second line contains n space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.

The third line contains integer m (1 ≤ m ≤ 105) — the number of operations. Next m lines contain the operations' descriptions. An operation's description starts with integer ti (1 ≤ ti ≤ 2) — the operation type.

 If ti = 1 (assignment operation), then on the line follow two space-separated integers: pi, vi (1 ≤ pi ≤ n; 1 ≤ vi ≤ 109) — the parameters of the assigning operation.

 If ti = 2 (Zigzag operation), then on the line follow three space-separated integers: li, ri, zi (1 ≤ li ≤ ri ≤ n; 2 ≤ zi ≤ 6) — the parameters of the Zigzag operation.

You should execute the operations in the order, in which they are given in the input.

Output

For each Zigzag operation print the calculated value of the Zigzag function on a single line. Print the values for Zigzag functions in the order, in which they are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Examples

Input

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

Output

5
26
38

Note

Explanation of the sample test:

 Result of the first operation is Z(2, 3, 2) = 3·1 + 1·2 = 5.

 Result of the second operation is Z(1, 5, 3) = 2·1 + 3·2 + 1·3 + 5·2 + 5·1 = 26.

 After the third operation array a is equal to 2, 3, 5, 5, 5.

 Result of the forth operation is Z(1, 5, 3) = 2·1 + 3·2 + 5·3 + 5·2 + 5·1 = 38.

skill_types: ['Data structures']

image_tags: Math Math Math Math Math Math Math

data_split: test


D. Looking for Owls

problem_index: D

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
Here's an owl from the first sample. The owl is sitting and waiting for you to count it.
![image](images/cf_350_D/1.png)

source: codeforces

raw_problem:
D. Looking for Owls

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Emperor Palpatine loves owls very much. The emperor has some blueprints with the new Death Star, the blueprints contain n distinct segments and m distinct circles. We will consider the segments indexed from 1 to n in some way and the circles — indexed from 1 to m in some way.

Palpatine defines an owl as a set of a pair of distinct circles (i, j) (i < j) and one segment k, such that:

 circles i and j are symmetrical relatively to the straight line containing segment k;

 circles i and j don't have any common points;

 circles i and j have the same radius;

 segment k intersects the segment that connects the centers of circles i and j.

Help Palpatine, count the number of distinct owls on the picture.

Input

The first line contains two integers — n and m (1 ≤ n ≤ 3·105, 2 ≤ m ≤ 1500).

The next n lines contain four integers each, x1, y1, x2, y2 — the coordinates of the two endpoints of the segment. It's guaranteed that each segment has positive length.

The next m lines contain three integers each, xi, yi, ri — the coordinates of the center and the radius of the i-th circle. All coordinates are integers of at most 104 in their absolute value. The radius is a positive integer of at most 104.

It is guaranteed that all segments and all circles are dictinct.

Output

Print a single number — the answer to the problem.

Please, do not use the %lld specifier to output 64-bit integers is С++. It is preferred to use the cout stream or the %I64d specifier.

Examples

Input

1 2
3 2 3 -2
0 0 2
6 0 2

Output

1

Input

3 2
0 0 0 1
0 -1 0 1
0 -1 0 0
2 0 1
-2 0 1

Output

3

Input

1 2
-1 0 1 0
-100 0 1
100 0 1

Output

0

Note

Here's an owl from the first sample. The owl is sitting and waiting for you to count it.

question:
Emperor Palpatine loves owls very much. The emperor has some blueprints with the new Death Star, the blueprints contain n distinct segments and m distinct circles. We will consider the segments indexed from 1 to n in some way and the circles — indexed from 1 to m in some way.
Palpatine defines an owl as a set of a pair of distinct circles (i, j) (i < j) and one segment k, such that:
 -  circles i and j are symmetrical relatively to the straight line containing segment k; -  circles i and j don't have any common points; -  circles i and j have the same radius; -  segment k intersects the segment that connects the centers of circles i and j. Help Palpatine, count the number of distinct owls on the picture.

Input
The first line contains two integers — n and m (1 ≤ n ≤ 3·10^{5}, 2 ≤ m ≤ 1500).
The next n lines contain four integers each, x_{1}, y_{1}, x_{2}, y_{2} — the coordinates of the two endpoints of the segment. It's guaranteed that each segment has positive length.
The next m lines contain three integers each, x_{i}, y_{i}, r_{i} — the coordinates of the center and the radius of the i-th circle. All coordinates are integers of at most 10^{4} in their absolute value. The radius is a positive integer of at most 10^{4}.
It is guaranteed that all segments and all circles are dictinct.

Output
Print a single number — the answer to the problem.
Please, do not use the %lld specifier to output 64-bit integers is С++. It is preferred to use the cout stream or the %I64d specifier.

Examples
Input
1 2
3 2 3 -2
0 0 2
6 0 2

Output
1

Input
3 2
0 0 0 1
0 -1 0 1
0 -1 0 0
2 0 1
-2 0 1

Output
3

Input
1 2
-1 0 1 0
-100 0 1
100 0 1

Output
0

Note
Here's an owl from the first sample. The owl is sitting and waiting for you to count it.
 ![image](1.png)

tags: ['Geometry', 'String algorithms', 'Sorting', 'Data structures']

skill_types: ['Sorting', 'Data structures']

raw_tags: ['data structures', 'geometry', 'binary search', 'hashing', 'sortings']

data_split: test


E. Princess and Her Shadow

problem_index: E

time_limit: 1 second

memory_limit: 256 megabytes

note:
Below the pictures for the samples are given (Princess, Shadow and the trees are colored in pink, gray and black correspondingly; the blue dot marks the lattice center).
In the first case the Princess may make two left steps, one step upwards and one right step: ![image](images/cf_317_E/1.png)
In the following case the Princess cannot catch the Shadow: ![image](images/cf_317_E/2.png)
In the last sample the Princess may make two left steps and one down step (in any order): ![image](images/cf_317_E/3.png)

source: codeforces

raw_problem:
E. Princess and Her Shadow

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Princess Vlada enjoys springing in the meadows and walking in the forest. One day — wonderful, sunny day — during her walk Princess found out with astonishment that her shadow was missing! "Blimey!", — she thought and started her search of the shadow in the forest.

Normally the Shadow is too lazy and simply sleeps under the Princess. But at this terrifically hot summer day she got bored of such a dull life, so she decided to play with Vlada.

The forest, where our characters entertain themselves, may be represented as a set of integer cells in the plane, where the Shadow and the Princess can move only up, down, left and right by 1. Some cells (as it happens in decent forests) are occupied by trees. The Shadow and the Princess are not allowed to enter a cell occupied by a tree. Unfortunately, these are the hard times for the forest, so there are very few trees growing here...

At first the Princess was walking within the cell (vx, vy), while the Shadow hid from the Princess in the cell (sx, sy). The Princess, The Shadow and the trees are located in the different cells.

The Shadow is playing with the Princess. As soon as the Princess moves by 1 in some direction, the Shadow simultaneously flies by 1 in the same direction, if it is possible (if the cell to fly to is not occupied by some tree); otherwise, the Shadow doesn't move. The Shadow is very shadowy, so our characters do not interfere with each other.

We say that the Shadow is caught by the Princess if after some move both of them are located in the same cell. Vlada managed to catch her Shadow! Can you?

Input

First line of the input contains the coordinates of the characters vx, vy, sx, sy and the number of trees m (0 ≤ m ≤ 400). The following m lines contain the coordinates of the trees.

All the coordinates are integers between -100 and 100, inclusive. The Princess, The Shadow and the trees are located in the different cells.

Output

If it is impossible for the Princess to catch the Shadow, print "-1" (without quotes).

Otherwise print a sequence of characters "L", "R", "D", "U", corresponding to the Princess's moves, following which she will be able to catch the Shadow at some turn (L — move to the left, R — to the right, U — up, D — down; axis x is directed to the right, y — up).

The number of characters (that is, the number of moves) must not exceed 106. All the Princess's moves should be correct, that is must not lead to the cell where a tree grows. It is allowed for the Princess and the Shadow to occupy the same cell before the last turn.

Examples

Input

0 0 1 0 1
0 1

Output

LLUR

Input

5 0 3 0 8
2 -1
2 0
2 1
3 -1
4 1
4 0
3 1
4 -1

Output

-1

Input

3 2 1 1 3
0 1
1 0
0 0

Output

DLL

Note

Below the pictures for the samples are given (Princess, Shadow and the trees are colored in pink, gray and black correspondingly; the blue dot marks the lattice center).

In the first case the Princess may make two left steps, one step upwards and one right step:

In the following case the Princess cannot catch the Shadow:

In the last sample the Princess may make two left steps and one down step (in any order):

question:
Princess Vlada enjoys springing in the meadows and walking in the forest. One day — wonderful, sunny day — during her walk Princess found out with astonishment that her shadow was missing! "Blimey!", — she thought and started her search of the shadow in the forest.
Normally the Shadow is too lazy and simply sleeps under the Princess. But at this terrifically hot summer day she got bored of such a dull life, so she decided to play with Vlada.
The forest, where our characters entertain themselves, may be represented as a set of integer cells in the plane, where the Shadow and the Princess can move only up, down, left and right by 1. Some cells (as it happens in decent forests) are occupied by trees. The Shadow and the Princess are not allowed to enter a cell occupied by a tree. Unfortunately, these are the hard times for the forest, so there are very few trees growing here...
At first the Princess was walking within the cell (v_{x}, v_{y}), while the Shadow hid from the Princess in the cell (s_{x}, s_{y}). The Princess, The Shadow and the trees are located in the different cells.
The Shadow is playing with the Princess. As soon as the Princess moves by 1 in some direction, the Shadow simultaneously flies by 1 in the same direction, if it is possible (if the cell to fly to is not occupied by some tree); otherwise, the Shadow doesn't move. The Shadow is very shadowy, so our characters do not interfere with each other.
We say that the Shadow is caught by the Princess if after some move both of them are located in the same cell. Vlada managed to catch her Shadow! Can you?

Input
First line of the input contains the coordinates of the characters v_{x}, v_{y}, s_{x}, s_{y} and the number of trees m (0 ≤ m ≤ 400). The following m lines contain the coordinates of the trees.
All the coordinates are integers between -100 and 100, inclusive. The Princess, The Shadow and the trees are located in the different cells.

Output
If it is impossible for the Princess to catch the Shadow, print "-1" (without quotes).
Otherwise print a sequence of characters "L", "R", "D", "U", corresponding to the Princess's moves, following which she will be able to catch the Shadow at some turn (L — move to the left, R — to the right, U — up, D — down; axis x is directed to the right, y — up).
The number of characters (that is, the number of moves) must not exceed 10^{6}. All the Princess's moves should be correct, that is must not lead to the cell where a tree grows. It is allowed for the Princess and the Shadow to occupy the same cell before the last turn.

Examples
Input
0 0 1 0 1
0 1

Output
LLUR

Input
5 0 3 0 8
2 -1
2 0
2 1
3 -1
4 1
4 0
3 1
4 -1

Output
-1

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

Output
DLL

Note
Below the pictures for the samples are given (Princess, Shadow and the trees are colored in pink, gray and black correspondingly; the blue dot marks the lattice center).
In the first case the Princess may make two left steps, one step upwards and one right step: ![image](1.png)
In the following case the Princess cannot catch the Shadow: ![image](2.png)
In the last sample the Princess may make two left steps and one down step (in any order): ![image](3.png)

tags: ['Shortest paths', 'Constructive algorithms']

raw_tags: ['shortest paths', 'constructive algorithms']

image_tags: Map Map Map

data_split: test


E. New Year Domino

problem_index: E

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
Consider the example. The dominoes are set like the picture below.
![image](images/cf_500_E/4.png)
Let's take a look at the 4th plan. To make the 6th domino fall by pushing the 2nd domino, the length of the 3rd domino (whose x-coordinate is 4) should be increased by 1, and the 5th domino (whose x-coordinate is 9) should be increased by 1 (other option is to increase 4th domino instead of 5th also by 1). Then, the dominoes will fall like in the picture below. Each cross denotes a touch between two dominoes.
![image](images/cf_500_E/5.png)
![image](images/cf_500_E/6.png)
![image](images/cf_500_E/7.png)
![image](images/cf_500_E/8.png)
![image](images/cf_500_E/9.png)

solutions: ["import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef RL():\n\treturn map(int, sys.stdin.readline().split())\n\ndef RLL():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef N():\n\treturn int(input())\n\ndef A(n):\n\treturn [0] * n\n\ndef AI(n, x):\n\treturn [x] * n\n\ndef A2(n, m):\n\treturn [[0] * m for i in range(n)]\n\ndef G(n):\n\treturn [[] for i in range(n)]\n\ndef GP(it):\n\treturn [[ch, len(list(g))] for (ch, g) in groupby(it)]\nfrom types import GeneratorType\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\nmod = 10 ** 9 + 7\nfarr = [1]\nifa = []\n\ndef fact(x, mod=0):\n\tif mod:\n\t\twhile x >= len(farr):\n\t\t\tfarr.append(farr[-1] * len(farr) % mod)\n\telse:\n\t\twhile x >= len(farr):\n\t\t\tfarr.append(farr[-1] * len(farr))\n\treturn farr[x]\n\ndef ifact(x, mod):\n\tglobal ifa\n\tfact(x, mod)\n\tifa.append(pow(farr[-1], mod - 2, mod))\n\tfor i in range(x, 0, -1):\n\t\tifa.append(ifa[-1] * i % mod)\n\tifa.reverse()\n\ndef per(i, j, mod=0):\n\tif i < j:\n\t\treturn 0\n\tif not mod:\n\t\treturn fact(i) // fact(i - j)\n\treturn farr[i] * ifa[i - j] % mod\n\ndef com(i, j, mod=0):\n\tif i < j:\n\t\treturn 0\n\tif not mod:\n\t\treturn per(i, j) // fact(j)\n\treturn per(i, j, mod) * ifa[j] % mod\n\ndef catalan(n):\n\treturn com(2 * n, n) // (n + 1)\n\ndef isprime(n):\n\tfor i in range(2, int(n ** 0.5) + 1):\n\t\tif n % i == 0:\n\t\t\treturn False\n\treturn True\n\ndef floorsum(a, b, c, n):\n\tif a == 0:\n\t\treturn b // c * (n + 1)\n\tif a >= c or b >= c:\n\t\treturn floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2\n\tm = (a * n + b) // c\n\treturn n * m - floorsum(c, c - b - 1, a, m - 1)\n\ndef inverse(a, m):\n\ta %= m\n\tif a <= 1:\n\t\treturn a\n\treturn (1 - inverse(m, a) * m) // a % m\n\ndef lowbit(n):\n\treturn n & -n\n\nclass BIT:\n\n\tdef __init__(self, arr):\n\t\tself.arr = arr\n\t\tself.n = len(arr) - 1\n\n\tdef update(self, x, v):\n\t\twhile x <= self.n:\n\t\t\tself.arr[x] += v\n\t\t\tx += x & -x\n\n\tdef query(self, x):\n\t\tans = 0\n\t\twhile x:\n\t\t\tans += self.arr[x]\n\t\t\tx &= x - 1\n\t\treturn ans\n\nclass ST:\n\n\tdef __init__(self, arr):\n\t\tn = len(arr)\n\t\tmx = n.bit_length()\n\t\tself.st = [[0] * mx for i in range(n)]\n\t\tfor i in range(n):\n\t\t\tself.st[i][0] = arr[i]\n\t\tfor j in range(1, mx):\n\t\t\tfor i in range(n - (1 << j) + 1):\n\t\t\t\tself.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])\n\n\tdef query(self, l, r):\n\t\tif l > r:\n\t\t\treturn -inf\n\t\ts = (r + 1 - l).bit_length() - 1\n\t\treturn max(self.st[l][s], self.st[r - (1 << s) + 1][s])\n\nclass DSU:\n\n\tdef __init__(self, n):\n\t\tself.c = [-1] * n\n\n\tdef same(self, x, y):\n\t\treturn self.find(x) == self.find(y)\n\n\tdef find(self, x):\n\t\tif self.c[x] < 0:\n\t\t\treturn x\n\t\tself.c[x] = self.find(self.c[x])\n\t\treturn self.c[x]\n\n\tdef union(self, u, v):\n\t\t(u, v) = (self.find(u), self.find(v))\n\t\tif u == v:\n\t\t\treturn False\n\t\tif self.c[u] > self.c[v]:\n\t\t\t(u, v) = (v, u)\n\t\tself.c[u] += self.c[v]\n\t\tself.c[v] = u\n\t\treturn True\n\n\tdef size(self, x):\n\t\treturn -self.c[self.find(x)]\n\nclass UFS:\n\n\tdef __init__(self, n):\n\t\tself.parent = [i for i in range(n)]\n\t\tself.ranks = [0] * n\n\n\tdef find(self, x):\n\t\tif x != self.parent[x]:\n\t\t\tself.parent[x] = self.find(self.parent[x])\n\t\treturn self.parent[x]\n\n\tdef union(self, u, v):\n\t\t(pu, pv) = (self.find(u), self.find(v))\n\t\tif pu == pv:\n\t\t\treturn False\n\t\tif self.ranks[pu] >= self.ranks[pv]:\n\t\t\tself.parent[pv] = pu\n\t\t\tif self.ranks[pv] == self.ranks[pu]:\n\t\t\t\tself.ranks[pu] += 1\n\t\telse:\n\t\t\tself.parent[pu] = pv\n\ndef Prime(n):\n\tc = 0\n\tprime = []\n\tflag = [0] * (n + 1)\n\tfor i in range(2, n + 1):\n\t\tif not flag[i]:\n\t\t\tprime.append(i)\n\t\t\tc += 1\n\t\tfor j in range(c):\n\t\t\tif i * prime[j] > n:\n\t\t\t\tbreak\n\t\t\tflag[i * prime[j]] = prime[j]\n\t\t\tif i % prime[j] == 0:\n\t\t\t\tbreak\n\treturn flag\n\ndef dij(s, graph):\n\td = {}\n\td[s] = 0\n\theap = [(0, s)]\n\tseen = set()\n\twhile heap:\n\t\t(dis, u) = heappop(heap)\n\t\tif u in seen:\n\t\t\tcontinue\n\t\tseen.add(u)\n\t\tfor (v, w) in graph[u]:\n\t\t\tif v not in d or d[v] > d[u] + w:\n\t\t\t\td[v] = d[u] + w\n\t\t\t\theappush(heap, (d[v], v))\n\treturn d\n\ndef bell(s, g):\n\tdis = AI(n, inf)\n\tdis[s] = 0\n\tfor i in range(n - 1):\n\t\tfor (u, v, w) in edge:\n\t\t\tif dis[v] > dis[u] + w:\n\t\t\t\tdis[v] = dis[u] + w\n\tchange = A(n)\n\tfor i in range(n):\n\t\tfor (u, v, w) in edge:\n\t\t\tif dis[v] > dis[u] + w:\n\t\t\t\tdis[v] = dis[u] + w\n\t\t\t\tchange[v] = 1\n\treturn dis\n\ndef lcm(a, b):\n\treturn a * b // gcd(a, b)\n\ndef lis(nums):\n\tres = []\n\tfor k in nums:\n\t\ti = bisect.bisect_left(res, k)\n\t\tif i == len(res):\n\t\t\tres.append(k)\n\t\telse:\n\t\t\tres[i] = k\n\treturn len(res)\n\ndef RP(nums):\n\tn = len(nums)\n\ts = set(nums)\n\td = {}\n\tfor (i, k) in enumerate(sorted(s), 1):\n\t\td[k] = i\n\tbi = BIT([0] * (len(s) + 1))\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tans += bi.query(d[nums[i]] - 1)\n\t\tbi.update(d[nums[i]], 1)\n\treturn ans\n\nclass DLN:\n\n\tdef __init__(self, val):\n\t\tself.val = val\n\t\tself.pre = None\n\t\tself.next = None\n\ndef nb(i, j, n, m):\n\tfor (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:\n\t\tif 0 <= ni < n and 0 <= nj < m:\n\t\t\tyield (ni, nj)\n\ndef topo(n):\n\tq = deque()\n\tres = []\n\tfor i in range(1, n + 1):\n\t\tif ind[i] == 0:\n\t\t\tq.append(i)\n\t\t\tres.append(i)\n\twhile q:\n\t\tu = q.popleft()\n\t\tfor v in g[u]:\n\t\t\tind[v] -= 1\n\t\t\tif ind[v] == 0:\n\t\t\t\tq.append(v)\n\t\t\t\tres.append(v)\n\treturn res\n\n@bootstrap\ndef gdfs(r, p):\n\tfor ch in g[r]:\n\t\tif ch != p:\n\t\t\tyield gdfs(ch, r)\n\tyield None\n\nclass SMT:\n\n\tdef __init__(self, n, query_fn, I):\n\t\tself.h = 1\n\t\twhile 1 << self.h < n:\n\t\t\tself.h += 1\n\t\tself.n = 1 << self.h\n\t\tself.qf = query_fn\n\t\tself.tree = [I] * (self.n << 1)\n\t\tself.lazy = [0] * self.n\n\n\tdef build(self, v):\n\t\tfor k in range(len(v)):\n\t\t\tself.tree[k + self.n] = v[k]\n\t\tfor k in range(self.n - 1, 0, -1):\n\t\t\tself.tree[k] = self.qf(self.tree[2 * k], self.tree[2 * k + 1])\n\n\tdef apply(self, x, val):\n\t\tself.tree[x] = val\n\t\tif x < self.n:\n\t\t\tself.lazy[x] = 1\n\n\tdef pushup(self, x):\n\t\tself.tree[x] = self.qf(self.tree[2 * x], self.tree[2 * x + 1])\n\n\tdef push(self, x):\n\t\tif self.lazy[x]:\n\t\t\tself.apply(x * 2, 0)\n\t\t\tself.apply(x * 2 + 1, 0)\n\t\t\tself.lazy[x] = 0\n\n\tdef set(self, p, x):\n\t\tp += self.n\n\t\tfor i in range(self.h, 0, -1):\n\t\t\tself.push(p >> i)\n\t\tself.tree[p] = x\n\t\tfor i in range(1, self.h + 1):\n\t\t\tself.pushup(p >> i)\n\n\tdef get(self, p):\n\t\tp += self.n\n\t\tfor i in range(self.h, 0, -1):\n\t\t\tself.push(p >> i)\n\t\treturn self.tree[p]\n\n\tdef update(self, l, r, h):\n\t\tl += self.n\n\t\tr += self.n\n\t\tl0 = l\n\t\tr0 = r\n\t\tfor i in range(self.h, 0, -1):\n\t\t\tif l >> i << i != l:\n\t\t\t\tself.push(l >> i)\n\t\t\tif r + 1 >> i << i != r + 1:\n\t\t\t\tself.push(r >> i)\n\t\twhile l <= r:\n\t\t\tif l & 1:\n\t\t\t\tself.apply(l, h)\n\t\t\t\tl += 1\n\t\t\tif not r & 1:\n\t\t\t\tself.apply(r, h)\n\t\t\t\tr -= 1\n\t\t\tl >>= 1\n\t\t\tr >>= 1\n\t\tfor i in range(1, self.h + 1):\n\t\t\tif l0 >> i << i != l0:\n\t\t\t\tself.pushup(l0 >> i)\n\t\t\tif r0 + 1 >> i << i != r0 + 1:\n\t\t\t\tself.pushup(r0 >> i)\n\n\tdef query(self, l, r):\n\t\tl += self.n\n\t\tr += self.n\n\t\tfor i in range(self.h, 0, -1):\n\t\t\tif l >> i << i != l:\n\t\t\t\tself.push(l >> i)\n\t\t\tif r + 1 >> i << i != r + 1:\n\t\t\t\tself.push(r >> i)\n\t\tans = 0\n\t\twhile l <= r:\n\t\t\tif l & 1:\n\t\t\t\tans = self.qf(ans, self.tree[l])\n\t\t\t\tl += 1\n\t\t\tif not r & 1:\n\t\t\t\tans = self.qf(ans, self.tree[r])\n\t\t\t\tr -= 1\n\t\t\tl >>= 1\n\t\t\tr >>= 1\n\t\treturn ans\n\ndef add(x, y):\n\treturn x + y\nt = 1\nfor i in range(t):\n\tn = N()\n\ts = set()\n\tx = A(n)\n\ty = A(n)\n\tfor i in range(n):\n\t\t(p, l) = RL()\n\t\tx[i] = p\n\t\ty[i] = p + l\n\t\ts.add(p)\n\t\ts.add(y[i])\n\ts = sorted(s)\n\td = {x: i for (i, x) in enumerate(s)}\n\tk = len(s) - 1\n\tarr = [s[i] - s[i - 1] for i in range(1, k + 1)]\n\tsmt = SMT(k, add, 0)\n\tsmt.build(arr)\n\tg = G(n)\n\tq = N()\n\tans = A(q)\n\tfor i in range(q):\n\t\t(a, b) = RL()\n\t\ta -= 1\n\t\tb -= 1\n\t\tg[a].append((i, b))\n\tfor i in range(n - 1, -1, -1):\n\t\tl = d[x[i]]\n\t\tr = d[y[i]]\n\t\tsmt.update(l, r - 1, 0)\n\t\tfor (j, cur) in g[i]:\n\t\t\tcur = d[x[cur]]\n\t\t\tans[j] = smt.query(l, cur - 1)\n\tfor x in ans:\n\t\tprint(x)\n"]

difficulty: HARD

source: codeforces

raw_problem:
E. New Year Domino

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Celebrating the new year, many people post videos of falling dominoes; Here's a list of them: https://www.youtube.com/results?search_query=New+Years+Dominos

User ainta, who lives in a 2D world, is going to post a video as well.

There are n dominoes on a 2D Cartesian plane. i-th domino (1 ≤ i ≤ n) can be represented as a line segment which is parallel to the y-axis and whose length is li. The lower point of the domino is on the x-axis. Let's denote the x-coordinate of the i-th domino as pi. Dominoes are placed one after another, so p1 < p2 < ... < pn - 1 < pn holds.

User ainta wants to take a video of falling dominoes. To make dominoes fall, he can push a single domino to the right. Then, the domino will fall down drawing a circle-shaped orbit until the line segment totally overlaps with the x-axis.

Also, if the s-th domino touches the t-th domino while falling down, the t-th domino will also fall down towards the right, following the same procedure above. Domino s touches domino t if and only if the segment representing s and t intersects.

See the picture above. If he pushes the leftmost domino to the right, it falls down, touching dominoes (A), (B) and (C). As a result, dominoes (A), (B), (C) will also fall towards the right. However, domino (D) won't be affected by pushing the leftmost domino, but eventually it will fall because it is touched by domino (C) for the first time.

The picture above is an example of falling dominoes. Each red circle denotes a touch of two dominoes.

User ainta has q plans of posting the video. j-th of them starts with pushing the xj-th domino, and lasts until the yj-th domino falls. But sometimes, it could be impossible to achieve such plan, so he has to lengthen some dominoes. It costs one dollar to increase the length of a single domino by 1. User ainta wants to know, for each plan, the minimum cost needed to achieve it. Plans are processed independently, i. e. if domino's length is increased in some plan, it doesn't affect its length in other plans. Set of dominos that will fall except xj-th domino and yj-th domino doesn't matter, but the initial push should be on domino xj.

Input

The first line contains an integer n (2 ≤ n ≤ 2 × 105)— the number of dominoes.

Next n lines describe the dominoes. The i-th line (1 ≤ i ≤ n) contains two space-separated integers pi, li (1 ≤ pi, li ≤ 109)— the x-coordinate and the length of the i-th domino. It is guaranteed that p1 < p2 < ... < pn - 1 < pn.

The next line contains an integer q (1 ≤ q ≤ 2 × 105) — the number of plans.

Next q lines describe the plans. The j-th line (1 ≤ j ≤ q) contains two space-separated integers xj, yj (1 ≤ xj < yj ≤ n). It means the j-th plan is, to push the xj-th domino, and shoot a video until the yj-th domino falls.

Output

For each plan, print a line containing the minimum cost needed to achieve it. If no cost is needed, print 0.

Examples

Input

6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6

Output

0
1
1
2

Note

Consider the example. The dominoes are set like the picture below.

Let's take a look at the 4th plan. To make the 6th domino fall by pushing the 2nd domino, the length of the 3rd domino (whose x-coordinate is 4) should be increased by 1, and the 5th domino (whose x-coordinate is 9) should be increased by 1 (other option is to increase 4th domino instead of 5th also by 1). Then, the dominoes will fall like in the picture below. Each cross denotes a touch between two dominoes.

question:
Celebrating the new year, many people post videos of falling dominoes; Here's a list of them: https://www.youtube.com/results?search_query=New+Years+Dominos
User ainta, who lives in a 2D world, is going to post a video as well.
There are n dominoes on a 2D Cartesian plane. i-th domino (1 ≤ i ≤ n) can be represented as a line segment which is parallel to the y-axis and whose length is l_{i}. The lower point of the domino is on the x-axis. Let's denote the x-coordinate of the i-th domino as p_{i}. Dominoes are placed one after another, so p_{1} < p_{2} < ... < p_{n - 1} < p_{n} holds.
User ainta wants to take a video of falling dominoes. To make dominoes fall, he can push a single domino to the right. Then, the domino will fall down drawing a circle-shaped orbit until the line segment totally overlaps with the x-axis.
 ![image](1.png) Also, if the s-th domino touches the t-th domino while falling down, the t-th domino will also fall down towards the right, following the same procedure above. Domino s touches domino t if and only if the segment representing s and t intersects.
 ![image](2.png) See the picture above. If he pushes the leftmost domino to the right, it falls down, touching dominoes (A), (B) and (C). As a result, dominoes (A), (B), (C) will also fall towards the right. However, domino (D) won't be affected by pushing the leftmost domino, but eventually it will fall because it is touched by domino (C) for the first time.
 ![image](3.png) The picture above is an example of falling dominoes. Each red circle denotes a touch of two dominoes.
User ainta has q plans of posting the video. j-th of them starts with pushing the x_{j}-th domino, and lasts until the y_{j}-th domino falls. But sometimes, it could be impossible to achieve such plan, so he has to lengthen some dominoes. It costs one dollar to increase the length of a single domino by 1. User ainta wants to know, for each plan, the minimum cost needed to achieve it. Plans are processed independently, i. e. if domino's length is increased in some plan, it doesn't affect its length in other plans. Set of dominos that will fall except x_{j}-th domino and y_{j}-th domino doesn't matter, but the initial push should be on domino x_{j}.

Input
The first line contains an integer n (2 ≤ n ≤ 2 × 10^{5})— the number of dominoes.
Next n lines describe the dominoes. The i-th line (1 ≤ i ≤ n) contains two space-separated integers p_{i}, l_{i} (1 ≤ p_{i}, l_{i} ≤ 10^{9})— the x-coordinate and the length of the i-th domino. It is guaranteed that p_{1} < p_{2} < ... < p_{n - 1} < p_{n}.
The next line contains an integer q (1 ≤ q ≤ 2 × 10^{5}) — the number of plans.
Next q lines describe the plans. The j-th line (1 ≤ j ≤ q) contains two space-separated integers x_{j}, y_{j} (1 ≤ x_{j} < y_{j} ≤ n). It means the j-th plan is, to push the x_{j}-th domino, and shoot a video until the y_{j}-th domino falls.

Output
For each plan, print a line containing the minimum cost needed to achieve it. If no cost is needed, print 0.

Examples
Input
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6

Output
0
1
1
2

Note
Consider the example. The dominoes are set like the picture below.
 ![image](4.png) Let's take a look at the 4th plan. To make the 6th domino fall by pushing the 2nd domino, the length of the 3rd domino (whose x-coordinate is 4) should be increased by 1, and the 5th domino (whose x-coordinate is 9) should be increased by 1 (other option is to increase 4th domino instead of 5th also by 1). Then, the dominoes will fall like in the picture below. Each cross denotes a touch between two dominoes.
 ![image](5.png)  ![image](6.png)  ![image](7.png)  ![image](8.png)  ![image](9.png)

tags: ['Spanning trees', 'Dynamic programming', 'Data structures']

skill_types: ['Dynamic programming', 'Data structures']

image_tags:
2D Geometry
2D Geometry
2D Geometry
2D Geometry
2D Geometry
2D Geometry
2D Geometry
2D Geometry
2D Geometry

data_split: test


E. Middle Duplication

problem_index: E

time_limit: 1 second

memory_limit: 256 megabytes

note:
The images below present the tree for the examples. The number in each node is the node number, while the subscripted letter is its label. To the right is the string representation of the tree, with each letter having the same color as the corresponding node.
Here is the tree for the first example. Here we duplicated the labels of nodes $$$1$$$ and $$$3$$$. We should not duplicate the label of node $$$2$$$ because it would give us the string "bbaaab", which is lexicographically greater than "baaaab".
![image](images/cf_1623_E/1.png)
In the second example, we can duplicate the labels of nodes $$$1$$$ and $$$2$$$. Note that only duplicating the label of the root will produce a worse result than the initial string.
![image](images/cf_1623_E/2.png)
In the third example, we should not duplicate any character at all. Even though we would want to duplicate the label of the node $$$3$$$, by duplicating it we must also duplicate the label of the node $$$2$$$, which produces a worse result.
![image](images/cf_1623_E/3.png)
There is no way to produce string "darkkcyan" from a tree with the initial string representation "darkcyan" :(.

solutions: ["import sys\nI = lambda : [*map(int, sys.stdin.readline().split())]\nleft = []\nright = []\n(n, k) = I()\nparents = [-1] * n\ns = input()\nfor i in range(n):\n\t(l, r) = I()\n\tl -= 1\n\tr -= 1\n\tleft.append(l)\n\tright.append(r)\n\tif l >= 0:\n\t\tparents[l] = i\n\tif r >= 0:\n\t\tparents[r] = i\ncovered = [0] * n\ncovered.append(1)\norder = []\ncurr = 0\nwhile len(order) < n:\n\tif covered[left[curr]]:\n\t\tif covered[curr]:\n\t\t\tif covered[right[curr]]:\n\t\t\t\tcurr = parents[curr]\n\t\t\telse:\n\t\t\t\tcurr = right[curr]\n\t\telse:\n\t\t\tcovered[curr] = 1\n\t\t\torder.append(curr)\n\telse:\n\t\tcurr = left[curr]\nafter = 'a'\nwant = [0] * n\ncurr = s[order[-1]]\nfor i in range(n - 2, -1, -1):\n\tnew = s[order[i]]\n\tif new != curr:\n\t\tafter = curr\n\t\tcurr = new\n\tif curr < after:\n\t\twant[order[i]] = 1\ndist = [float('inf')] * n\nfor v in order:\n\tif want[v]:\n\t\tdist[v] = 0\n\telif left[v] >= 0:\n\t\tdist[v] = dist[left[v]] + 1\ndupe = [0] * n\nchecked = [0] * n\ncurr = 0\nlef = k\nwhile lef > 0 and curr != -1:\n\tif dupe[curr]:\n\t\tif left[curr] >= 0 and dupe[left[curr]] == 0 and (checked[left[curr]] == 0):\n\t\t\tcurr = left[curr]\n\t\telif right[curr] >= 0 and dupe[right[curr]] == 0 and (checked[right[curr]] == 0):\n\t\t\tcurr = right[curr]\n\t\telse:\n\t\t\tcurr = parents[curr]\n\telif dist[curr] < lef:\n\t\tlef -= dist[curr] + 1\n\t\tdupe[curr] = 1\n\t\tfor i in range(dist[curr]):\n\t\t\tcurr = left[curr]\n\t\t\tdupe[curr] = 1\n\telse:\n\t\tchecked[curr] = 1\n\t\tcurr = parents[curr]\nout = []\nfor guy in order:\n\tif dupe[guy]:\n\t\tout.append(2 * s[guy])\n\telse:\n\t\tout.append(s[guy])\nprint(''.join(out))\n", "import io, os, sys\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\noutput = sys.stdout.write\nDEBUG = os.environ.get('debug') is not None\nif DEBUG:\n\tfrom inspect import currentframe, getframeinfo\n\tfrom re import search\n\ndef debug(*args):\n\tif not DEBUG:\n\t\treturn\n\tframe = currentframe().f_back\n\ts = getframeinfo(frame).code_context[0]\n\tr = search('\\\\((.*)\\\\)', s).group(1)\n\tvnames = r.split(', ')\n\tvar_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]\n\tprefix = f'{currentframe().f_back.f_lineno:02d}: '\n\tprint(f\"{prefix}{', '.join(var_and_vals)}\")\nINF = float('inf')\nfrom types import GeneratorType\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\tto = f(*args, **kwargs)\n\t\twhile True:\n\t\t\tif type(to) is GeneratorType:\n\t\t\t\tstack.append(to)\n\t\t\t\tto = next(to)\n\t\t\telse:\n\t\t\t\tstack.pop()\n\t\t\t\tif not stack:\n\t\t\t\t\tbreak\n\t\t\t\tto = stack[-1].send(to)\n\t\treturn to\n\treturn wrappedfunc\n\ndef main():\n\t(N, K) = list(map(int, input().split()))\n\tS = input().decode().strip()\n\t(L, R) = ([-1] * N, [-1] * N)\n\tfor p in range(N):\n\t\t(l, r) = map(int, input().split())\n\t\t(L[p], R[p]) = (l - 1, r - 1)\n\tinorder = []\n\n\t@bootstrap\n\tdef dfs1(u):\n\t\tif L[u] > -1:\n\t\t\tyield dfs1(L[u])\n\t\tinorder.append(u)\n\t\tif R[u] > -1:\n\t\t\tyield dfs1(R[u])\n\t\tyield None\n\tdfs1(0)\n\tgood = [False] * N\n\tlast = ''\n\tfor i in range(N - 2, -1, -1):\n\t\t(u, v) = (inorder[i], inorder[i + 1])\n\t\tif S[u] != S[v]:\n\t\t\tlast = S[v]\n\t\tif S[u] < last:\n\t\t\tgood[u] = True\n\tdup = [False] * N\n\n\t@bootstrap\n\tdef dfs2(u, cost=1):\n\t\tnonlocal K\n\t\tif cost > K:\n\t\t\tyield\n\t\tif L[u] > -1:\n\t\t\tyield dfs2(L[u], cost + 1)\n\t\tif L[u] > -1 and dup[L[u]]:\n\t\t\tdup[u] = True\n\t\telif good[u]:\n\t\t\tdup[u] = True\n\t\t\tK -= cost\n\t\tif R[u] > -1 and dup[u]:\n\t\t\tyield dfs2(R[u], 1)\n\t\tyield None\n\tdfs2(0)\n\tprint(''.join((S[u] * 2 if dup[u] else S[u] for u in inorder)))\nmain()\n"]

source: codeforces

raw_problem:
E. Middle Duplication

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

A binary tree of $$$n$$$ nodes is given. Nodes of the tree are numbered from $$$1$$$ to $$$n$$$ and the root is the node $$$1$$$. Each node can have no child, only one left child, only one right child, or both children. For convenience, let's denote $$$l_u$$$ and $$$r_u$$$ as the left and the right child of the node $$$u$$$ respectively, $$$l_u = 0$$$ if $$$u$$$ does not have the left child, and $$$r_u = 0$$$ if the node $$$u$$$ does not have the right child.

Each node has a string label, initially is a single character $$$c_u$$$. Let's define the string representation of the binary tree as the concatenation of the labels of the nodes in the in-order. Formally, let $$$f(u)$$$ be the string representation of the tree rooted at the node $$$u$$$. $$$f(u)$$$ is defined as follows: $$$$$$ f(u) = \begin{cases} \texttt{<empty string>}, & \text{if }u = 0; \\ f(l_u) + c_u + f(r_u) & \text{otherwise}, \end{cases} $$$$$$ where $$$+$$$ denotes the string concatenation operation.

This way, the string representation of the tree is $$$f(1)$$$.

For each node, we can duplicate its label at most once, that is, assign $$$c_u$$$ with $$$c_u + c_u$$$, but only if $$$u$$$ is the root of the tree, or if its parent also has its label duplicated.

You are given the tree and an integer $$$k$$$. What is the lexicographically smallest string representation of the tree, if we can duplicate labels of at most $$$k$$$ nodes?

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

 $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;

 in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

The second line contains a string $$$c$$$ of $$$n$$$ lower-case English letters, where $$$c_i$$$ is the initial label of the node $$$i$$$ for $$$1 \le i \le n$$$. Note that the given string $$$c$$$ is not the initial string representation of the tree.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i, r_i \le n$$$). If the node $$$i$$$ does not have the left child, $$$l_i = 0$$$, and if the node $$$i$$$ does not have the right child, $$$r_i = 0$$$.

It is guaranteed that the given input forms a binary tree, rooted at $$$1$$$.

Output

Print a single line, containing the lexicographically smallest string representation of the tree if at most $$$k$$$ nodes have their labels duplicated.

Examples

Input

4 3
abab
2 3
0 0
0 4
0 0

Output

baaaab

Input

8 2
kadracyn
2 5
3 4
0 0
0 0
6 8
0 7
0 0
0 0

Output

daarkkcyan

Input

8 3
kdaracyn
2 5
0 3
0 4
0 0
6 8
0 7
0 0
0 0

Output

darkcyan

Note

The images below present the tree for the examples. The number in each node is the node number, while the subscripted letter is its label. To the right is the string representation of the tree, with each letter having the same color as the corresponding node.

Here is the tree for the first example. Here we duplicated the labels of nodes $$$1$$$ and $$$3$$$. We should not duplicate the label of node $$$2$$$ because it would give us the string "bbaaab", which is lexicographically greater than "baaaab".

In the second example, we can duplicate the labels of nodes $$$1$$$ and $$$2$$$. Note that only duplicating the label of the root will produce a worse result than the initial string.

In the third example, we should not duplicate any character at all. Even though we would want to duplicate the label of the node $$$3$$$, by duplicating it we must also duplicate the label of the node $$$2$$$, which produces a worse result.

There is no way to produce string "darkkcyan" from a tree with the initial string representation "darkcyan" :(.

question:
A binary tree of $$$n$$$ nodes is given. Nodes of the tree are numbered from $$$1$$$ to $$$n$$$ and the root is the node $$$1$$$. Each node can have no child, only one left child, only one right child, or both children. For convenience, let's denote $$$l_u$$$ and $$$r_u$$$ as the left and the right child of the node $$$u$$$ respectively, $$$l_u = 0$$$ if $$$u$$$ does not have the left child, and $$$r_u = 0$$$ if the node $$$u$$$ does not have the right child.
Each node has a string label, initially is a single character $$$c_u$$$. Let's define the string representation of the binary tree as the concatenation of the labels of the nodes in the in-order. Formally, let $$$f(u)$$$ be the string representation of the tree rooted at the node $$$u$$$. $$$f(u)$$$ is defined as follows: $$$$$$ f(u) = \begin{cases} \texttt{<empty string>}, & \text{if }u = 0; \\ f(l_u) + c_u + f(r_u) & \text{otherwise}, \end{cases} $$$$$$ where $$$+$$$ denotes the string concatenation operation.
This way, the string representation of the tree is $$$f(1)$$$.
For each node, we can duplicate its label at most once, that is, assign $$$c_u$$$ with $$$c_u + c_u$$$, but only if $$$u$$$ is the root of the tree, or if its parent also has its label duplicated.
You are given the tree and an integer $$$k$$$. What is the lexicographically smallest string representation of the tree, if we can duplicate labels of at most $$$k$$$ nodes?
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
 -  $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$; -  in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.
Input
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).
The second line contains a string $$$c$$$ of $$$n$$$ lower-case English letters, where $$$c_i$$$ is the initial label of the node $$$i$$$ for $$$1 \le i \le n$$$. Note that the given string $$$c$$$ is not the initial string representation of the tree.
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i, r_i \le n$$$). If the node $$$i$$$ does not have the left child, $$$l_i = 0$$$, and if the node $$$i$$$ does not have the right child, $$$r_i = 0$$$.
It is guaranteed that the given input forms a binary tree, rooted at $$$1$$$.

Output
Print a single line, containing the lexicographically smallest string representation of the tree if at most $$$k$$$ nodes have their labels duplicated.

Examples
Input
4 3
abab
2 3
0 0
0 4
0 0

Output
baaaab

Input
8 2
kadracyn
2 5
3 4
0 0
0 0
6 8
0 7
0 0
0 0

Output
daarkkcyan

Input
8 3
kdaracyn
2 5
0 3
0 4
0 0
6 8
0 7
0 0
0 0

Output
darkcyan

Note
The images below present the tree for the examples. The number in each node is the node number, while the subscripted letter is its label. To the right is the string representation of the tree, with each letter having the same color as the corresponding node.
Here is the tree for the first example. Here we duplicated the labels of nodes $$$1$$$ and $$$3$$$. We should not duplicate the label of node $$$2$$$ because it would give us the string "bbaaab", which is lexicographically greater than "baaaab".
 ![image](1.png) In the second example, we can duplicate the labels of nodes $$$1$$$ and $$$2$$$. Note that only duplicating the label of the root will produce a worse result than the initial string.
 ![image](2.png) In the third example, we should not duplicate any character at all. Even though we would want to duplicate the label of the node $$$3$$$, by duplicating it we must also duplicate the label of the node $$$2$$$, which produces a worse result.
 ![image](3.png) There is no way to produce string "darkkcyan" from a tree with the initial string representation "darkcyan" :(.

tags: ['Graph traversal', 'String algorithms', 'Greedy algorithms', 'Tree algorithms', 'Data structures']

skill_types: ['Data structures', 'Greedy algorithms']

raw_tags: ['data structures', 'greedy', 'dfs and similar', 'strings', 'trees']

image_tags: Tree Tree Tree

data_split: test


H. Black and White

problem_index: H

time_limit: 2 seconds

memory_limit: 256 megabytes

output_spec:
Print 2n lines containing 2m characters each — the tiling scheme. Every tile is represented by a square 2 × 2 in the following manner (the order corresponds to the order of the picture above):
![image](images/cf_48_H/2.png)

source: codeforces

raw_problem:
H. Black and White

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

According to the legends the king of Berland Berl I was noted for his love of beauty and order. One day he ordered to tile the palace hall's floor where balls and receptions used to take place with black and white tiles according to a regular geometrical pattern invented by him. However, as is after the case, due to low financing there were only a black and b white tiles delivered to the palace. The other c tiles were black and white (see the picture).

The initial plan failed! Having learned of that, the king gave a new command: tile the floor with the available tiles so that no black side of a tile touched a white one. The tiles are squares of one size 1 × 1, every black and white tile can be rotated in one of the four ways.

The court programmer was given the task to work out the plan of tiling and he coped with the task and didn't suffer the consequences of disobedience. And can you cope with it?

Input

The first line contains given integers n and m (1 ≤ n, m ≤ 100) which represent the sizes of the rectangle that needs to be tiled. The next line contains non-negative numbers a, b and c, a + b + c = nm, c ≥ m.

Output

Print 2n lines containing 2m characters each — the tiling scheme. Every tile is represented by a square 2 × 2 in the following manner (the order corresponds to the order of the picture above):
   If multiple solutions exist, output any.

Examples

Input

2 2
0 0 4

Output

\../
#\/#
\##/
.\/.

Input

2 3
1 2 3

Output

###/\#
##/..\
#/....
/.....

question:
According to the legends the king of Berland Berl I was noted for his love of beauty and order. One day he ordered to tile the palace hall's floor where balls and receptions used to take place with black and white tiles according to a regular geometrical pattern invented by him. However, as is after the case, due to low financing there were only a black and b white tiles delivered to the palace. The other c tiles were black and white (see the picture).
 ![image](1.png) The initial plan failed! Having learned of that, the king gave a new command: tile the floor with the available tiles so that no black side of a tile touched a white one. The tiles are squares of one size 1 × 1, every black and white tile can be rotated in one of the four ways.
The court programmer was given the task to work out the plan of tiling and he coped with the task and didn't suffer the consequences of disobedience. And can you cope with it?

Input
The first line contains given integers n and m (1 ≤ n, m ≤ 100) which represent the sizes of the rectangle that needs to be tiled. The next line contains non-negative numbers a, b and c, a + b + c = nm, c ≥ m.

Output
Print 2n lines containing 2m characters each — the tiling scheme. Every tile is represented by a square 2 × 2 in the following manner (the order corresponds to the order of the picture above):
 ![image](2.png)  If multiple solutions exist, output any.
Examples
Input
2 2
0 0 4

Output
\../
#\/#
\##/
.\/.

Input
2 3
1 2 3

Output
###/\#
##/..\
#/....
/.....

image_tags: Patterns Table

data_split: test