D. New Year and Fireworks

problem_index: D

time_limit: 2.5 seconds

memory_limit: 256 megabytes

note:
For the first sample, the drawings below show the situation after each level of recursion. Limak launched the firework from the bottom-most red cell. It covered t1 = 4 cells (marked red), exploded and divided into two parts (their further movement is marked green). All explosions are marked with an 'X' character. On the last drawing, there are 4 red, 4 green, 8 orange and 23 pink cells. So, the total number of visited cells is 4 + 4 + 8 + 23 = 39.
![image](images/cf_750_D/1.png)
For the second sample, the drawings below show the situation after levels 4, 5 and 6. The middle drawing shows directions of all parts that will move in the next level.
![image](images/cf_750_D/2.png)

solutions: ["from collections import defaultdict\ndx = [0, -1, -1, -1, 0, 1, 1, 1]\ndy = [1, 1, 0, -1, -1, -1, 0, 1]\nvisited = defaultdict(lambda : False)\ngrid = [[False for _ in range(320)] for _ in range(320)]\n\ndef dfs(x, y, d, n, N, inp):\n\tif n >= N or visited[x, y, d, n]:\n\t\treturn\n\tvisited[x, y, d, n] = True\n\tdist = inp[n]\n\tfor i in range(1, dist + 1):\n\t\tgrid[x + dx[d] * i][y + i * dy[d]] = True\n\tif n < N:\n\t\tdfs(x + dx[d] * dist, y + dy[d] * dist, (d + 1) % 8, n + 1, N, inp)\n\t\tdfs(x + dx[d] * dist, y + dy[d] * dist, (d + 7) % 8, n + 1, N, inp)\nN = int(input())\ninp = list(map(int, input().strip().split()))\ndfs(160, 160, 0, 0, N, inp)\nresult = sum(map(sum, grid))\nprint(result)\n", "dr = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]\nn = int(input())\nt = [int(i) for i in input().split()]\nvisited = set()\nN = 150 * 2 + 10\ncovers = [[0] * N for i in range(N)]\n\ndef dfs(d, pos, path):\n\tmem = (d, pos, path)\n\tif mem in visited:\n\t\treturn set()\n\telse:\n\t\tvisited.add(mem)\n\tif d == n + 1:\n\t\treturn\n\tfor _ in range(t[d - 1]):\n\t\tpos = (pos[0] + dr[path][0], pos[1] + dr[path][1])\n\t\tcovers[pos[0]][pos[1]] = 1\n\tdfs(d + 1, pos, (path + 1) % 8)\n\tdfs(d + 1, pos, (path - 1) % 8)\ndfs(1, (int(N / 2), int(N / 2)), 0)\nprint(sum([sum(i) for i in covers]))\n", "from sys import stdin, stdout\n\ndef ri():\n\treturn map(int, input().split())\nw = 15\nadding = [(0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1)]\n\ndef fill(x, y, dir, depth):\n\tfor i in range(t[depth]):\n\t\tx += adding[dir][0]\n\t\ty += adding[dir][1]\n\t\tv[x][y] = 1\n\ndef dfs(x, y, dir, depth):\n\tif depth == n:\n\t\treturn\n\tif (dir, depth) in T[x][y]:\n\t\treturn\n\tfill(x, y, dir, depth)\n\tndepth = depth + 1\n\tnx = x + adding[dir][0] * t[depth]\n\tny = y + adding[dir][1] * t[depth]\n\tndir = (dir + 1) % 8\n\tdfs(nx, ny, ndir, ndepth)\n\tndir = (8 + dir - 1) % 8\n\tdfs(nx, ny, ndir, ndepth)\n\tT[x][y].add(tuple((dir, depth)))\nn = int(input())\nt = list(ri())\nv = [[0 for i in range(n * w)] for j in range(n * w)]\nT = [[set() for i in range(n * w)] for j in range(n * w)]\ndfs(n * w // 2, n * w // 2, 0, 0)\nans = 0\nfor i in range(n * w):\n\tfor j in range(n * w):\n\t\tif v[i][j]:\n\t\t\tans += 1\nprint(ans)\n", "import sys\nplane = set()\ncrackers = {((0, -1), (0, 1))}\nn = int(input())\na = [int(x) for x in input().split()]\ncrack_dict = {(1, 0): ((1, -1), (1, 1)), (1, 1): ((1, 0), (0, 1)), (0, 1): ((1, 1), (-1, 1)), (-1, 1): ((0, 1), (-1, 0)), (-1, 0): ((-1, 1), (-1, -1)), (-1, -1): ((-1, 0), (0, -1)), (0, -1): ((-1, -1), (1, -1)), (1, -1): ((0, -1), (1, 0))}\n\ndef move(cracker):\n\t(point, direc) = cracker\n\tpoint2 = (point[0] + direc[0], point[1] + direc[1])\n\treturn (point2, direc)\n\ndef crack(cracker):\n\t(point, direc) = cracker\n\t(direc1, direc2) = crack_dict[direc]\n\treturn ((point, direc1), (point, direc2))\nfor x in a:\n\tfor i in range(x):\n\t\tcrackers = set((move(cracker) for cracker in crackers))\n\t\tplane.update((cracker[0] for cracker in crackers))\n\tnew_crackers = set()\n\tfor cracker in crackers:\n\t\tnew_crackers.update(crack(cracker))\n\tcrackers = new_crackers\nprint(len(plane))\n", "from math import sin\n\ndef mp():\n\treturn map(int, input().split())\n\ndef lt():\n\treturn list(map(int, input().split()))\n\ndef pt(x):\n\tprint(x)\n\ndef ip():\n\treturn input()\n\ndef it():\n\treturn int(input())\n\ndef sl(x):\n\treturn [t for t in x]\n\ndef spl(x):\n\treturn x.split()\n\ndef aj(liste, item):\n\tliste.append(item)\n\ndef bin(x):\n\treturn '{0:b}'.format(x)\n\ndef listring(l):\n\treturn ' '.join([str(x) for x in l])\n\ndef ptlist(l):\n\tprint(' '.join([str(x) for x in l]))\nn = it()\nstep = lt()\ndict = {}\n\ndef explosion(start, s, d):\n\t(i, j) = start\n\tt = s + 1\n\tif d == 0:\n\t\tfor k in range(j + 1, j + t):\n\t\t\tdict[i, k] = True\n\t\treturn (((i, j + t - 1), (d + 7) % 8), ((i, j + t - 1), (d + 1) % 8))\n\tif d == 1:\n\t\tfor k in range(1, t):\n\t\t\tdict[i + k, j + k] = True\n\t\treturn (((i + t - 1, j + t - 1), (d + 7) % 8), ((i + t - 1, j + t - 1), (d + 1) % 8))\n\tif d == 2:\n\t\tfor k in range(1, t):\n\t\t\tdict[i + k, j] = True\n\t\treturn (((i + t - 1, j), (d + 7) % 8), ((i + t - 1, j), (d + 1) % 8))\n\tif d == 3:\n\t\tfor k in range(1, t):\n\t\t\tdict[i + k, j - k] = True\n\t\treturn (((i + t - 1, j - t + 1), (d + 7) % 8), ((i + t - 1, j - t + 1), (d + 1) % 8))\n\tif d == 4:\n\t\tfor k in range(1, t):\n\t\t\tdict[i, j - k] = True\n\t\treturn (((i, j - t + 1), (d + 7) % 8), ((i, j - t + 1), (d + 1) % 8))\n\tif d == 5:\n\t\tfor k in range(1, t):\n\t\t\tdict[i - k, j - k] = True\n\t\treturn (((i - t + 1, j - t + 1), (d + 7) % 8), ((i - t + 1, j - t + 1), (d + 1) % 8))\n\tif d == 6:\n\t\tfor k in range(1, t):\n\t\t\tdict[i - k, j] = True\n\t\treturn (((i - t + 1, j), (d + 7) % 8), ((i - t + 1, j), (d + 1) % 8))\n\tif d == 7:\n\t\tfor k in range(1, t):\n\t\t\tdict[i - k, j + k] = True\n\t\treturn (((i - t + 1, j + t - 1), (d + 7) % 8), ((i - t + 1, j + t - 1), (d + 1) % 8))\nstart = [((0, 0), 0)]\nfor i in range(n):\n\tl = []\n\tfor (p, q) in start:\n\t\t(a, b) = explosion(p, step[i], q)\n\t\tl.append(a)\n\t\tl.append(b)\n\tstart = set(l)\npt(len(dict))\n", "import time\ncoord = set()\nflows = int(input())\nstart = time.time()\nt = list(map(int, input().split()))\ndirections = {0: (0, 1), 1: (1, 1), 2: (1, 0), 3: (1, -1), 4: (0, -1), 5: (-1, -1), 6: (-1, 0), 7: (-1, 1)}\nwas = [[[[0 for j in range(300)] for i in range(300)] for x in range(31)] for y in range(8)]\n\ndef flight(n, x=0, y=0, direction=0):\n\tif was[direction][n][x][y]:\n\t\treturn\n\twas[direction][n][x][y] = 1\n\tif n:\n\t\tfor _ in range(t[flows - n]):\n\t\t\tx += directions[direction][0]\n\t\t\ty += directions[direction][1]\n\t\t\tcoord.add((x, y))\n\t\tflight(n - 1, x, y, (direction + 1) % 8)\n\t\tflight(n - 1, x, y, (direction - 1) % 8)\nflight(flows)\nprint(len(coord))\n", "from sys import *\nT = int(stdin.readline())\nt = [int(s) for s in stdin.readline().split(' ')]\na = []\nfor i in range(T - 1, -1, -1):\n\tif i % 2 == 0:\n\t\ta += [(e[0], -e[1]) for e in a]\n\t\ta = [(e[0] - t[i], e[1]) for e in a]\n\t\ta += [(-x - 1, 0) for x in range(t[i])]\n\t\ta = list(set(a))\n\tif i % 2 == 1:\n\t\ta += [(e[1], -e[0]) for e in a]\n\t\ta = [(e[0] - t[i], e[1] + t[i]) for e in a]\n\t\ta += [(-x - 1, x + 1) for x in range(t[i])]\n\t\ta = list(set(a))\nprint(len(a))\n", "k = int(input()) & 1\np = []\ns = range(1, 6)\nfor q in map(int, input().split()[::-1]):\n\tif k:\n\t\tp += [(x, -y) for (x, y) in p]\n\t\tp = [(x - q, y) for (x, y) in p]\n\t\tp += [(-x, 0) for x in s[:q]]\n\telse:\n\t\tp += [(y, -x) for (x, y) in p]\n\t\tp = [(x - q, y + q) for (x, y) in p]\n\t\tp += [(-x, x) for x in s[:q]]\n\tp = list(set(p))\n\tk = 1 - k\nprint(len(p))\n"]

difficulty: HARD

source: codeforces

raw_problem:
D. New Year and Fireworks

time limit per test
2.5 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

One tradition of welcoming the New Year is launching fireworks into the sky. Usually a launched firework flies vertically upward for some period of time, then explodes, splitting into several parts flying in different directions. Sometimes those parts also explode after some period of time, splitting into even more parts, and so on.

Limak, who lives in an infinite grid, has a single firework. The behaviour of the firework is described with a recursion depth n and a duration for each level of recursion t1, t2, ..., tn. Once Limak launches the firework in some cell, the firework starts moving upward. After covering t1 cells (including the starting cell), it explodes and splits into two parts, each moving in the direction changed by 45 degrees (see the pictures below for clarification). So, one part moves in the top-left direction, while the other one moves in the top-right direction. Each part explodes again after covering t2 cells, splitting into two parts moving in directions again changed by 45 degrees. The process continues till the n-th level of recursion, when all 2n - 1 existing parts explode and disappear without creating new parts. After a few levels of recursion, it's possible that some parts will be at the same place and at the same time — it is allowed and such parts do not crash.

Before launching the firework, Limak must make sure that nobody stands in cells which will be visited at least once by the firework. Can you count the number of those cells?

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 30) — the total depth of the recursion.

The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 5). On the i-th level each of 2i - 1 parts will cover ti cells before exploding.

Output

Print one integer, denoting the number of cells which will be visited at least once by any part of the firework.

Examples

Input

4
4 2 2 3

Output

39

Input

6
1 1 1 1 1 3

Output

85

Input

1
3

Output

3

Note

For the first sample, the drawings below show the situation after each level of recursion. Limak launched the firework from the bottom-most red cell. It covered t1 = 4 cells (marked red), exploded and divided into two parts (their further movement is marked green). All explosions are marked with an 'X' character. On the last drawing, there are 4 red, 4 green, 8 orange and 23 pink cells. So, the total number of visited cells is 4 + 4 + 8 + 23 = 39.

For the second sample, the drawings below show the situation after levels 4, 5 and 6. The middle drawing shows directions of all parts that will move in the next level.

question:
One tradition of welcoming the New Year is launching fireworks into the sky. Usually a launched firework flies vertically upward for some period of time, then explodes, splitting into several parts flying in different directions. Sometimes those parts also explode after some period of time, splitting into even more parts, and so on.
Limak, who lives in an infinite grid, has a single firework. The behaviour of the firework is described with a recursion depth n and a duration for each level of recursion t_{1}, t_{2}, ..., t_{n}. Once Limak launches the firework in some cell, the firework starts moving upward. After covering t_{1} cells (including the starting cell), it explodes and splits into two parts, each moving in the direction changed by 45 degrees (see the pictures below for clarification). So, one part moves in the top-left direction, while the other one moves in the top-right direction. Each part explodes again after covering t_{2} cells, splitting into two parts moving in directions again changed by 45 degrees. The process continues till the n-th level of recursion, when all 2^{n - 1} existing parts explode and disappear without creating new parts. After a few levels of recursion, it's possible that some parts will be at the same place and at the same time — it is allowed and such parts do not crash.
Before launching the firework, Limak must make sure that nobody stands in cells which will be visited at least once by the firework. Can you count the number of those cells?

Input
The first line of the input contains a single integer n (1 ≤ n ≤ 30) — the total depth of the recursion.
The second line contains n integers t_{1}, t_{2}, ..., t_{n} (1 ≤ t_{i} ≤ 5). On the i-th level each of 2^{i - 1} parts will cover t_{i} cells before exploding.

Output
Print one integer, denoting the number of cells which will be visited at least once by any part of the firework.

Examples
Input
4
4 2 2 3

Output
39

Input
6
1 1 1 1 1 3

Output
85

Input
1
3

Output
3

Note
For the first sample, the drawings below show the situation after each level of recursion. Limak launched the firework from the bottom-most red cell. It covered t_{1} = 4 cells (marked red), exploded and divided into two parts (their further movement is marked green). All explosions are marked with an 'X' character. On the last drawing, there are 4 red, 4 green, 8 orange and 23 pink cells. So, the total number of visited cells is 4 + 4 + 8 + 23 = 39.
 ![image](1.png) For the second sample, the drawings below show the situation after levels 4, 5 and 6. The middle drawing shows directions of all parts that will move in the next level.
 ![image](2.png)

tags: ['Graph traversal', 'Implementation', 'Complete search', 'Dynamic programming', 'Data structures']

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

raw_tags: ['data structures', 'implementation', 'dfs and similar', 'dp', 'brute force']

image_tags: Map Map

data_split: test


E. Robot Arm

problem_index: E

time_limit: 8 seconds

memory_limit: 256 megabytes

output_spec:
Print m lines. The i-th line should contain two real values, denoting the coordinates of the blue endpoint of the last segment after applying operations 1, ..., i. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.
Namely, let's assume that your answer for a particular value of a coordinate is a and the answer of the jury is b. The checker program will consider your answer correct if ![image](images/cf_618_E/5.png) for all coordinates.

note:
The following pictures shows the state of the arm after each operation. The coordinates of point F are printed after applying each operation. For simplicity, we only show the blue endpoints of a segment (with the exception for the red endpoint of the first segment). For instance, the point labeled B is the blue endpoint for segment 1 and also the red endpoint for segment 2.
Initial state:
![image](images/cf_618_E/6.png)
1
3
![image](images/cf_618_E/7.png)
3
90
![image](images/cf_618_E/8.png)
5
48
![image](images/cf_618_E/9.png)
4
1
![image](images/cf_618_E/10.png)

solutions: ["from cmath import rect\nimport sys\nimport math\nfrom functools import reduce\n\nclass SegmentTree:\n\n\tdef __init__(self, L, function=lambda x, y: x + y):\n\t\tself.function = function\n\t\tN = self.size = len(L)\n\t\tM = 1 << N.bit_length()\n\t\tself.margin = 2 * M - N\n\t\tself.L = [None for i in range(self.margin)] + L\n\t\tfor i in range(M - 1, 0, -1):\n\t\t\t(x, y) = (self.L[i << 1], self.L[i << 1 | 1])\n\t\t\tself.L[i] = None if x is None or y is None else function(x, y)\n\n\tdef modify(self, pos, value):\n\t\tp = pos + self.margin\n\t\tself.L[p] = value\n\t\twhile p > 1:\n\t\t\t(x, y) = (self.L[p], self.L[p ^ 1])\n\t\t\tif p & 1:\n\t\t\t\t(x, y) = (y, x)\n\t\t\tself.L[p >> 1] = None if x is None or y is None else self.function(x, y)\n\t\t\tp >>= 1\n\n\tdef query(self, left, right):\n\t\t(l, r) = (left + self.margin, right + self.margin)\n\t\tstack = []\n\t\tvoid = True\n\t\twhile l < r:\n\t\t\tif l & 1:\n\t\t\t\tif void:\n\t\t\t\t\tresult = self.L[l]\n\t\t\t\t\tvoid = False\n\t\t\t\telse:\n\t\t\t\t\tresult = self.function(result, self.L[l])\n\t\t\t\tl += 1\n\t\t\tif r & 1:\n\t\t\t\tr -= 1\n\t\t\t\tstack.append(self.L[r])\n\t\t\tl >>= 1\n\t\t\tr >>= 1\n\t\tinit = stack.pop() if void else result\n\t\treturn reduce(self.function, reversed(stack), init)\n\ndef degrect(r, phi):\n\treturn rect(r, math.radians(phi))\n\ndef vsum(u, v):\n\treturn (u[0] + v[0] * degrect(1, u[1]), (u[1] + v[1]) % 360)\n\ndef solve(f):\n\t(n, m) = [int(x) for x in f.readline().split()]\n\tsegments = [[1, 0] for i in range(n)]\n\tarm = SegmentTree([(1, 0) for i in range(n)], vsum)\n\tfor line in f:\n\t\t(q, i, a) = [int(x) for x in line.split()]\n\t\tif q == 1:\n\t\t\tsegments[i - 1][0] += a\n\t\telse:\n\t\t\tsegments[i - 1][1] -= a\n\t\tarm.modify(i - 1, (degrect(segments[i - 1][0], segments[i - 1][1]), segments[i - 1][1]))\n\t\tquery = arm.query(0, n)[0]\n\t\tprint(query.real, query.imag)\nsolve(sys.stdin)\n"]

source: codeforces

raw_problem:
E. Robot Arm

time limit per test
8 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Roger is a robot. He has an arm that is a series of n segments connected to each other. The endpoints of the i-th segment are initially located at points (i - 1, 0) and (i, 0). The endpoint at (i - 1, 0) is colored red and the endpoint at (i, 0) is colored blue for all segments. Thus, the blue endpoint of the i-th segment is touching the red endpoint of the (i + 1)-th segment for all valid i.

Roger can move his arm in two different ways:

 He can choose some segment and some value. This is denoted as choosing the segment number i and picking some positive l. This change happens as follows: the red endpoint of segment number i and segments from 1 to i - 1 are all fixed in place. Imagine a ray from the red endpoint to the blue endpoint. The blue endpoint and segments i + 1 through n are translated l units in the direction of this ray.
In this picture, the red point labeled A and segments before A stay in place, while the blue point labeled B and segments after B gets translated.

 He can choose a segment and rotate it. This is denoted as choosing the segment number i, and an angle a. The red endpoint of the i-th segment will stay fixed in place. The blue endpoint of that segment and segments i + 1 to n will rotate clockwise by an angle of a degrees around the red endpoint.
In this picture, the red point labeled A and segments before A stay in place, while the blue point labeled B and segments after B get rotated around point A.

Roger will move his arm m times. These transformations are a bit complicated, and Roger easily loses track of where the blue endpoint of the last segment is. Help him compute the coordinates of the blue endpoint of the last segment after applying each operation. Note that these operations are cumulative, and Roger's arm may intersect itself arbitrarily during the moves.

Input

The first line of the input will contain two integers n and m (1 ≤ n, m ≤ 300 000) — the number of segments and the number of operations to perform.

Each of the next m lines contains three integers xi, yi and zi describing a move. If xi = 1, this line describes a move of type 1, where yi denotes the segment number and zi denotes the increase in the length. If xi = 2, this describes a move of type 2, where yi denotes the segment number, and zi denotes the angle in degrees. (1 ≤ xi ≤ 2, 1 ≤ yi ≤ n, 1 ≤ zi ≤ 359)

Output

Print m lines. The i-th line should contain two real values, denoting the coordinates of the blue endpoint of the last segment after applying operations 1, ..., i. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

Namely, let's assume that your answer for a particular value of a coordinate is a and the answer of the jury is b. The checker program will consider your answer correct if  for all coordinates.

Examples

Input

5 4
1 1 3
2 3 90
2 5 48
1 4 1

Output

8.0000000000 0.0000000000
5.0000000000 -3.0000000000
4.2568551745 -2.6691306064
4.2568551745 -3.6691306064

Note

The following pictures shows the state of the arm after each operation. The coordinates of point F are printed after applying each operation. For simplicity, we only show the blue endpoints of a segment (with the exception for the red endpoint of the first segment). For instance, the point labeled B is the blue endpoint for segment 1 and also the red endpoint for segment 2.

Initial state:
   Extend segment 1 by 3.    Rotate segment 3 by 90 degrees clockwise.    Rotate segment 5 by 48 degrees clockwise.    Extend segment 4 by 1.

question:
Roger is a robot. He has an arm that is a series of n segments connected to each other. The endpoints of the i-th segment are initially located at points (i - 1, 0) and (i, 0). The endpoint at (i - 1, 0) is colored red and the endpoint at (i, 0) is colored blue for all segments. Thus, the blue endpoint of the i-th segment is touching the red endpoint of the (i + 1)-th segment for all valid i.
Roger can move his arm in two different ways:
 -  He can choose some segment and some value. This is denoted as choosing the segment number i and picking some positive l. This change happens as follows: the red endpoint of segment number i and segments from 1 to i - 1 are all fixed in place. Imagine a ray from the red endpoint to the blue endpoint. The blue endpoint and segments i + 1 through n are translated l units in the direction of this ray. ![image](1.png) ![image](2.png) In this picture, the red point labeled A and segments before A stay in place, while the blue point labeled B and segments after B gets translated.-  He can choose a segment and rotate it. This is denoted as choosing the segment number i, and an angle a. The red endpoint of the i-th segment will stay fixed in place. The blue endpoint of that segment and segments i + 1 to n will rotate clockwise by an angle of a degrees around the red endpoint. ![image](3.png) ![image](4.png) In this picture, the red point labeled A and segments before A stay in place, while the blue point labeled B and segments after B get rotated around point A. Roger will move his arm m times. These transformations are a bit complicated, and Roger easily loses track of where the blue endpoint of the last segment is. Help him compute the coordinates of the blue endpoint of the last segment after applying each operation. Note that these operations are cumulative, and Roger's arm may intersect itself arbitrarily during the moves.

Input
The first line of the input will contain two integers n and m (1 ≤ n, m ≤ 300 000) — the number of segments and the number of operations to perform.
Each of the next m lines contains three integers x_{i}, y_{i} and z_{i} describing a move. If x_{i} = 1, this line describes a move of type 1, where y_{i} denotes the segment number and z_{i} denotes the increase in the length. If x_{i} = 2, this describes a move of type 2, where y_{i} denotes the segment number, and z_{i} denotes the angle in degrees. (1 ≤ x_{i} ≤ 2, 1 ≤ y_{i} ≤ n, 1 ≤ z_{i} ≤ 359)

Output
Print m lines. The i-th line should contain two real values, denoting the coordinates of the blue endpoint of the last segment after applying operations 1, ..., i. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 4}.
Namely, let's assume that your answer for a particular value of a coordinate is a and the answer of the jury is b. The checker program will consider your answer correct if ![image](5.png) for all coordinates.

Examples
Input
5 4
1 1 3
2 3 90
2 5 48
1 4 1

Output
8.0000000000 0.0000000000
5.0000000000 -3.0000000000
4.2568551745 -2.6691306064
4.2568551745 -3.6691306064

Note
The following pictures shows the state of the arm after each operation. The coordinates of point F are printed after applying each operation. For simplicity, we only show the blue endpoints of a segment (with the exception for the red endpoint of the first segment). For instance, the point labeled B is the blue endpoint for segment 1 and also the red endpoint for segment 2.
Initial state:
 ![image](6.png)  Extend segment 1 by 3.  ![image](7.png)  Rotate segment 3 by 90 degrees clockwise.  ![image](8.png)  Rotate segment 5 by 48 degrees clockwise.  ![image](9.png)  Extend segment 4 by 1.  ![image](10.png)

skill_types: ['Data structures']

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

data_split: test


G. Pisces

problem_index: G

time_limit: 5 seconds

memory_limit: 512 megabytes

note:
In the first example, there could be one fish swimming through lakes $$$2$$$, $$$1$$$, and $$$4$$$, and the second fish swimming through lakes $$$3$$$, $$$1$$$, and $$$2$$$.
In the second example a single fish can not possibly be part of all observations simultaneously, but two fish swimming $$$2 \to 1 \to 4$$$ and $$$3 \to 1 \to 5$$$ can.
In the third example one fish can move from lake $$$1$$$ to lake $$$5$$$, others staying in their lakes during all time: two fish in lake $$$4$$$, six fish in lake $$$5$$$, one fish in lake $$$3$$$. The system of lakes is shown on the picture.
![image](images/cf_1023_G/1.png)

source: codeforces

raw_problem:
G. Pisces

time limit per test
5 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

A group of researchers are studying fish population in a natural system of lakes and rivers. The system contains $$$n$$$ lakes connected by $$$n - 1$$$ rivers. Each river has integer length (in kilometers) and can be traversed in both directions. It is possible to travel between any pair of lakes by traversing the rivers (that is, the network of lakes and rivers form a tree).

There is an unknown number of indistinguishable fish living in the lakes. On day $$$1$$$, fish can be at arbitrary lakes. Fish can travel between lakes by swimming the rivers. Each fish can swim a river $$$l$$$ kilometers long in any direction in $$$l$$$ days. Further, each fish can stay any number of days in any particular lake it visits. No fish ever appear or disappear from the lake system. Each lake can accomodate any number of fish at any time.

The researchers made several observations. The $$$j$$$-th of these observations is "on day $$$d_j$$$ there were at least $$$f_j$$$ distinct fish in the lake $$$p_j$$$". Help the researchers in determining the smallest possible total number of fish living in the lake system that doesn't contradict the observations.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of lakes in the system.

The next $$$n - 1$$$ lines describe the rivers. The $$$i$$$-th of these lines contains three integers $$$u_i$$$, $$$v_i$$$, $$$l_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq l_i \leq 10^3$$$) — $$$1$$$-based indices of lakes connected by the $$$i$$$-th river, and the length of this river.

The next line contains a single integer $$$k$$$ ($$$1 \leq k \leq 10^5$$$) — the number of observations.

The next $$$k$$$ lines describe the observations. The $$$j$$$-th of these lines contains three integers $$$d_j$$$, $$$f_j$$$, $$$p_j$$$ ($$$1 \leq d_j \leq 10^8$$$, $$$1 \leq f_j \leq 10^4$$$, $$$1 \leq p_j \leq n$$$) — the day, the number of fish, and the lake index of the $$$j$$$-th observation. No two observations happen on the same day at the same lake simultaneously.

Output

Print one integer — the smallest total number of fish not contradicting the observations.

Examples

Input

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

Output

2

Input

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

Output

2

Input

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

Output

10

Note

In the first example, there could be one fish swimming through lakes $$$2$$$, $$$1$$$, and $$$4$$$, and the second fish swimming through lakes $$$3$$$, $$$1$$$, and $$$2$$$.

In the second example a single fish can not possibly be part of all observations simultaneously, but two fish swimming $$$2 \to 1 \to 4$$$ and $$$3 \to 1 \to 5$$$ can.

In the third example one fish can move from lake $$$1$$$ to lake $$$5$$$, others staying in their lakes during all time: two fish in lake $$$4$$$, six fish in lake $$$5$$$, one fish in lake $$$3$$$. The system of lakes is shown on the picture.

question:
A group of researchers are studying fish population in a natural system of lakes and rivers. The system contains $$$n$$$ lakes connected by $$$n - 1$$$ rivers. Each river has integer length (in kilometers) and can be traversed in both directions. It is possible to travel between any pair of lakes by traversing the rivers (that is, the network of lakes and rivers form a tree).
There is an unknown number of indistinguishable fish living in the lakes. On day $$$1$$$, fish can be at arbitrary lakes. Fish can travel between lakes by swimming the rivers. Each fish can swim a river $$$l$$$ kilometers long in any direction in $$$l$$$ days. Further, each fish can stay any number of days in any particular lake it visits. No fish ever appear or disappear from the lake system. Each lake can accomodate any number of fish at any time.
The researchers made several observations. The $$$j$$$-th of these observations is "on day $$$d_j$$$ there were at least $$$f_j$$$ distinct fish in the lake $$$p_j$$$". Help the researchers in determining the smallest possible total number of fish living in the lake system that doesn't contradict the observations.

Input
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of lakes in the system.
The next $$$n - 1$$$ lines describe the rivers. The $$$i$$$-th of these lines contains three integers $$$u_i$$$, $$$v_i$$$, $$$l_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq l_i \leq 10^3$$$) — $$$1$$$-based indices of lakes connected by the $$$i$$$-th river, and the length of this river.
The next line contains a single integer $$$k$$$ ($$$1 \leq k \leq 10^5$$$) — the number of observations.
The next $$$k$$$ lines describe the observations. The $$$j$$$-th of these lines contains three integers $$$d_j$$$, $$$f_j$$$, $$$p_j$$$ ($$$1 \leq d_j \leq 10^8$$$, $$$1 \leq f_j \leq 10^4$$$, $$$1 \leq p_j \leq n$$$) — the day, the number of fish, and the lake index of the $$$j$$$-th observation. No two observations happen on the same day at the same lake simultaneously.

Output
Print one integer — the smallest total number of fish not contradicting the observations.

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

Output
2

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

Output
2

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

Output
10

Note
In the first example, there could be one fish swimming through lakes $$$2$$$, $$$1$$$, and $$$4$$$, and the second fish swimming through lakes $$$3$$$, $$$1$$$, and $$$2$$$.
In the second example a single fish can not possibly be part of all observations simultaneously, but two fish swimming $$$2 \to 1 \to 4$$$ and $$$3 \to 1 \to 5$$$ can.
In the third example one fish can move from lake $$$1$$$ to lake $$$5$$$, others staying in their lakes during all time: two fish in lake $$$4$$$, six fish in lake $$$5$$$, one fish in lake $$$3$$$. The system of lakes is shown on the picture.
 ![image](1.png)

tags: ['Tree algorithms', 'Data structures', 'Flows and cuts']

skill_types: ['Data structures']

data_split: test


Digital Racing Circuil

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

raw_problem:
Problem H: Digital Racing Circuit

You have an ideally small racing car on an x-y plane (0 ≤ x, y ≤ 255, where bigger y denotes upper coordinate). The racing circuit course is figured by two solid walls. Each wall is a closed loop of connected line segments. End point coordinates of every line segment are both integers (See Figure 1). Thus, a wall is represented by a list of end point integer coordinates (x1, y1), (x2, y2), ...,(xn, yn). The start line and the goal line are identical.

Figure 1. A Simple Course

For the qualification run, you start the car at any integer coordinate position on the start line, say (sx, sy).

At any clock t (≥ 0), according to the acceleration parameter at t, (ax,t, ay,t), the velocity changes instantly to (vx,t-1 + ax,t, vy,t-1 + ay,t), if the velocity at t - 1 is (vx,t-1, vy,t-1). The velocity will be kept constant until the next clock. It is assumed that the velocity at clock -1, (vx,-1, vy,-1) is (0, 0). Each of the acceleration components must be either -1, 0, or 1, because your car does not have so fantastic engine and brake. In other words, any successive pair of velocities should not differ more than 1 for either x-component or y-component. Note that your trajectory will be piecewise linear as the walls are.

Your car should not touch nor run over the circuit wall, or your car will be crashed, even at the start line. The referee watches your car's trajectory very carefully, checking whether or not the trajectory touches the wall or attempts to cross the wall.

The objective of the qualification run is to finish your run within as few clock units as possible, without suffering from any interference by other racing cars. That is, you run alone the circuit around clockwise and reach, namely touch or go across the goal line without having been crashed. Don't be crashed even in the last trajectory segment after you reach the goal line. But we don't care whatever happens after that clock

Your final lap time is the clock t when you reach the goal line for the first time after you have once left the start line. But it needs a little adjustment at the goal instant. When you cross the goal line, only the necessary fraction of your car's last trajectory segment is counted. For example, if the length of your final trajectory segment is 3 and only its 1/3 fraction is needed to reach the goal line, you have to add only 0.333 instead of 1 clock unit.

Drivers are requested to control their cars as cleverly as possible to run fast but avoiding crash. ALAS! The racing committee decided that it is too DANGEROUS to allow novices to run the circuit. In the last year, it was reported that some novices wrenched their fingers by typing too enthusiastically their programs. So, this year, you are invited as a referee assistant in order to accumulate the experience on this dangerous car race.

A number of experienced drivers are now running the circuit for the qualification for semi-finals. They submit their driving records to the referee. The referee has to check the records one by one whether it is not a fake.

Now, you are requested to make a program to check the validity of driving records for any given course configuration. Is the start point right on the start line without touching the walls? Is every value in the acceleration parameter list either one of -1, 0, and 1? Does the length of acceleration parameter list match the reported lap time? That is, aren't there any excess acceleration parameters after the goal, or are these enough to reach the goal? Doesn't it involve any crash? Does it mean a clockwise running all around? (Note that it is not inhibited to run backward temporarily unless crossing the start line again.) Is the lap time calculation correct? You should allow a rounding error up to 0.01 clock unit in the lap time.

Input

The input consists of a course configuration followed by a number of driving records on that course.

A course configuration is given by two lists representing the inner wall and the outer wall, respectively. Each line shows the end point coordinates of the line segments that comprise the wall. A course configuration looks as follows:

ix,1 iy,1 ..... ix,N iy,N 99999
ox,1 oy,1 ..... ox,M oy,M 99999

where data are alternating x-coordinates and y-coordinates that are all non-negative integers (≤ 255) terminated by 99999. The start/goal line is a line segment connecting the coordinates (ix,1, iy,1) and (ox,1, oy,1). For simplicity, iy,1 is assumed to be equal to oy,1; that is, the start/goal line is horizontal on the x-y plane. Note that N and M may vary among course configurations, but do not exceed 100, because too many curves involve much danger even for experienced drivers. You need not check the validity of the course configuration.

A driving record consists of three parts, which is terminated by 99999: two integers sx, sy for the start position (sx, sy), the lap time with three digits after the decimal point, and the sequential list of acceleration parameters at all clocks until the goal. It is assumed that the length of the acceleration parameter list does not exceed 500. A driving record looks like the following:

sx sy
lap-time
ax,0 ay,0 ax,1 ay,1 ... ax,L ay,L 99999

Input is terminated by a null driving record; that is, it is terminated by a 99999 that immediately follows 99999 of the last driving record.

Output

The test result should be reported by simply printing OK or NG for each driving record, each result in each line. No other letter is allowed in the result.

Sample Input

6 28 6 32 25 32 26 27 26 24 6 24 99999
2 28 2 35 30 35 30 20 2 20 99999

3 28
22.667
0 1 1 1 1 0 0 -1 0 -1 1 0 0 0 1 0 -1 0 0 -1 -1 -1 -1 0 -1 0 -1 -1 -1 1 -1 1
-1 1 -1 0 1 0 1 1 1 1 1 0 1 1 99999

5 28
22.667
0 1 -1 1 1 0 1 -1 1 -1 1 0 1 0 1 0 -1 -1 -1 0 -1 -1 -1 0 -1 1 -1 -1 -1 1
-1 0 -1 1 -1 0 1 0 1 0 1 1 1 1 1 1 99999

4 28
6.333
0 1 0 1 1 -1 -1 -1 0 -1 0 -1 0 -1 99999

3 28
20.000
0 -1 1 -1 1 0 1 1 1 1 1 0 -1 0 -1 0 -1 1 -1 1
-1 1 -1 0 -1 -1 -1 -1 -1 -1 -1 0 1 0 1 -1 1 -1 1 -1 99999

99999

Output for the Sample Input

OK
NG
NG
NG

source: aizu

question:
Problem H: Digital Racing Circuit

You have an ideally small racing car on an x-y plane (0 ≤ x, y ≤ 255, where bigger y denotes upper coordinate). The racing circuit course is figured by two solid walls. Each wall is a closed loop of connected line segments. End point coordinates of every line segment are both integers (See Figure 1). Thus, a wall is represented by a list of end point integer coordinates (x_{1}, y_{1}), (x_{2}, y_{2}), ...,(x_{n}, y_{n}). The start line and the goal line are identical.

![image](1.png)
Figure 1. A Simple Course

For the qualification run, you start the car at any integer coordinate position on the start line, say (s_{x}, s_{y}).

At any clock t (≥ 0), according to the acceleration parameter at t, (a_{x,t}, a_{y,t}), the velocity changes instantly to (v_{x,t-1} + a_{x,t}, v_{y,t-1} + a_{y,t}), if the velocity at t - 1 is (v_{x,t-1}, v_{y,t-1}). The velocity will be kept constant until the next clock. It is assumed that the velocity at clock -1, (v_{x,-1}, v_{y,-1}) is (0, 0). Each of the acceleration components must be either -1, 0, or 1, because your car does not have so fantastic engine and brake. In other words, any successive pair of velocities should not differ more than 1 for either x-component or y-component. Note that your trajectory will be piecewise linear as the walls are.

Your car should not touch nor run over the circuit wall, or your car will be crashed, even at the start line. The referee watches your car's trajectory very carefully, checking whether or not the trajectory touches the wall or attempts to cross the wall.

The objective of the qualification run is to finish your run within as few clock units as possible, without suffering from any interference by other racing cars. That is, you run alone the circuit around clockwise and reach, namely touch or go across the goal line without having been crashed. Don't be crashed even in the last trajectory segment after you reach the goal line. But we don't care whatever happens after that clock

Your final lap time is the clock t when you reach the goal line for the first time after you have once left the start line. But it needs a little adjustment at the goal instant. When you cross the goal line, only the necessary fraction of your car's last trajectory segment is counted. For example, if the length of your final trajectory segment is 3 and only its 1/3 fraction is needed to reach the goal line, you have to add only 0.333 instead of 1 clock unit.

Drivers are requested to control their cars as cleverly as possible to run fast but avoiding crash. ALAS! The racing committee decided that it is too DANGEROUS to allow novices to run the circuit. In the last year, it was reported that some novices wrenched their fingers by typing too enthusiastically their programs. So, this year, you are invited as a referee assistant in order to accumulate the experience on this dangerous car race.

A number of experienced drivers are now running the circuit for the qualification for semi-finals. They submit their driving records to the referee. The referee has to check the records one by one whether it is not a fake.

Now, you are requested to make a program to check the validity of driving records for any given course configuration. Is the start point right on the start line without touching the walls? Is every value in the acceleration parameter list either one of -1, 0, and 1? Does the length of acceleration parameter list match the reported lap time? That is, aren't there any excess acceleration parameters after the goal, or are these enough to reach the goal? Doesn't it involve any crash? Does it mean a clockwise running all around? (Note that it is not inhibited to run backward temporarily unless crossing the start line again.) Is the lap time calculation correct? You should allow a rounding error up to 0.01 clock unit in the lap time.

Input

The input consists of a course configuration followed by a number of driving records on that course.

A course configuration is given by two lists representing the inner wall and the outer wall, respectively. Each line shows the end point coordinates of the line segments that comprise the wall. A course configuration looks as follows:

_{x,1} _{y,1} ..... _{x,N} _{y,N} 99999

_{x,1} _{y,1} ..... _{x,M} _{y,M} 99999

where data are alternating x-coordinates and y-coordinates that are all non-negative integers (≤ 255) terminated by 99999. The start/goal line is a line segment connecting the coordinates (i_{x,1}, i_{y,1}) and (o_{x,1}, o_{y,1}). For simplicity, i_{y,1} is assumed to be equal to o_{y,1}; that is, the start/goal line is horizontal on the x-y plane. Note that N and M may vary among course configurations, but do not exceed 100, because too many curves involve much danger even for experienced drivers. You need not check the validity of the course configuration.

A driving record consists of three parts, which is terminated by 99999: two integers s_{x}, s_{y} for the start position (s_{x}, s_{y}), the lap time with three digits after the decimal point, and the sequential list of acceleration parameters at all clocks until the goal. It is assumed that the length of the acceleration parameter list does not exceed 500. A driving record looks like the following:

_{x,0} _{y,0} _{x,1} _{y,1} ... _{x,L} _{y,L} 99999

Input is terminated by a null driving record; that is, it is terminated by a 99999 that immediately follows 99999 of the last driving record.

Output

The test result should be reported by simply printing OK or NG for each driving record, each result in each line. No other letter is allowed in the result.

Sample Input

6 28 6 32 25 32 26 27 26 24 6 24 99999
2 28 2 35 30 35 30 20 2 20 99999

3 28
22.667
0 1 1 1 1 0 0 -1 0 -1 1 0 0 0 1 0 -1 0 0 -1 -1 -1 -1 0 -1 0 -1 -1 -1 1 -1 1
-1 1 -1 0 1 0 1 1 1 1 1 0 1 1 99999

5 28
22.667
0 1 -1 1 1 0 1 -1 1 -1 1 0 1 0 1 0 -1 -1 -1 0 -1 -1 -1 0 -1 1 -1 -1 -1 1
-1 0 -1 1 -1 0 1 0 1 0 1 1 1 1 1 1 99999

4 28
6.333
0 1 0 1 1 -1 -1 -1 0 -1 0 -1 0 -1 99999

3 28
20.000
0 -1 1 -1 1 0 1 1 1 1 1 0 -1 0 -1 0 -1 1 -1 1
-1 1 -1 0 -1 -1 -1 -1 -1 -1 -1 0 1 0 1 -1 1 -1 1 -1 99999

99999

Output for the Sample Input

OK
NG
NG
NG

data_split: test


Painting Tree

source: Kyoto University Programming Contest 2020 Spring

raw_problem:
L: 木の彩色

問題文

モデューロさんは木の絵を描くのがとてもうまいです。

モデューロさんは長い年月をかけて頂点が $N$ 個である木の絵を書きました。
この木の頂点には $1$ から $N$ までの番号がついており、頂点 $a_i$ と $b_i$ $(1 \leq i \leq N-1)$ は直接辺でつながれています。
すべての頂点には色がまだ塗られていません。

モデューロさんが書いたこの木の絵はたくさんの人を感動させ、有名な美術館に飾られることが決まりました。

この美術館には順に $N$ 人の人が来場します。モデューロさんは来場者特典として、それぞれの人に $1$ 枚ずつ木の絵のコピーを配布することにしました。

さらに、来場者に満足してもらうため、配布する木の絵の頂点すべてに色を塗ることにしました。
$k$ 番目 $(1 \leq k \leq N)$ に来場する人は、以下の 2 条件を共に満たす絵が配布されたときにのみ満足します。

最短距離が $k$ の倍数である任意の 2 頂点は、同じ色で塗られている。

最短距離が $k$ の倍数でない任意の 2 頂点は、異なる色で塗られている。

モデューロさんが持っている色の数は無限にあります。また、それぞれのコピーで色の塗り方が違っても構いません。

それぞれの来場者に対し、その来場者を満足させるように頂点を塗ることができるかどうか判定してください。

制約

$1 \leq N \leq 10^5$

$1 \leq a_i, b_i \leq N$

入力はすべて整数である

入力によって与えられるグラフが木であることは保証される。

入力

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

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

$1$ 行目には、木の頂点数を表す整数 $N$ が与えられる。

$2$ 行目から $N$ 行目には、木の辺の情報が与えられる。このうち $i+1(1 \leq i \leq N-1)$ 行目には、頂点 $a_i$ と $b_i$ が辺でつながっていることを示す 2 つの整数 $a_i,b_i$ が与えられる。

出力

以下を満たす 0 または 1 からなる文字列 $S = s_1 s_2 \ldots s_N$ を出力せよ。

$s_k = 1$ : $k$ 番目の来場者が満足できるよう与えられた木の絵の頂点に彩色できる

$s_k = 0$ : $k$ 番目の来場者が満足できるよう与えられた木の絵の頂点に彩色できない

入力例 1

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

出力例 1

1100111

入力例1の木は以下の図のようになります。

例えば、$k=2$ の時、以下のように塗れば条件を満たします。

また、$k=5$ の時、以下のように塗れば条件を満たします。

入力例 2

6
1 2
2 3
3 4
4 5
5 6

出力例 2

111111

入力例 3

1

出力例 3

1

solutions: ["import sys\nfrom collections import deque\nreadline = sys.stdin.readline\n\ndef parorder(Edge, p):\n    N = len(Edge)\n    par = [0]*N\n    par[p] = -1\n    stack = [p]\n    order = []\n    visited = set([p])\n    ast = stack.append\n    apo = order.append\n    while stack:\n        vn = stack.pop()\n        apo(vn)\n        for vf in Edge[vn]:\n            if vf in visited:\n                continue\n            visited.add(vf)\n            par[vf] = vn\n            ast(vf)\n    return par, order\n\ndef getcld(p):\n    res = [[] for _ in range(len(p))]\n    for i, v in enumerate(p[1:], 1):\n        res[v].append(i)\n    return res\n\ndef bfs(s):\n    Q = deque(s)\n    used = set(s)\n    dist = [0]*N\n    while Q:\n        vn = Q.pop()\n        for vf in Edge[vn]:\n            if vf not in used:\n                used.add(vf)\n                dist[vf] = 1 + dist[vn]\n                Q.appendleft(vf)\n    return dist\n\nN = int(readline())\nEdge = [[] for _ in range(N)]\nfor _ in range(N-1):\n    a, b = map(int, readline().split())\n    a -= 1\n    b -= 1\n    Edge[a].append(b)\n    Edge[b].append(a)\n\ndist0 = bfs([0])\nst = dist0.index(max(dist0))\ndists = bfs([st])\nen = dists.index(max(dists))\ndiste = bfs([en])\nD = dists[en]\npath = [i for i in range(N) if dists[i] + diste[i] == D]\ndistp = bfs(path)\n\ntable = [1]*(N+5)\nmini = 0\nfor i in range(N):\n    if distp[i] == 0:\n        continue\n    fi = dists[i]\n    if 2*distp[i] == fi:\n        mini = max(mini, fi-1)\n    else:\n        mini = max(mini, fi)\n    fi = diste[i]\n    if 2*distp[i] == fi:\n        mini = max(mini, fi-1)\n    else:\n        mini = max(mini, fi)\n\nfor i in range(mini+1):\n    table[i] = 0\ntable[1] = 1\ntable[2] = 1\nfor i in range(D+1, N+1):\n    table[i] = 1\n\nprint(''.join(map(str, table[1:N+1])))\n            \n    \n\n"]

source: aizu

question:
Title: Coloring of Trees

Problem Statement
Modulo-san is very good at drawing pictures of trees. Modulo-san has spent many years drawing a picture of a tree with $N$ vertices. The vertices of this tree are numbered from $1$ to $N$, and vertices $a_i$ and $b_i$ $(1 \leq i \leq N-1)$ are connected directly by an edge. No colors have been painted on any of the vertices yet. Modulo-san's drawing of this tree moved many people and it was decided to be displayed in a famous art museum. $N$ visitors will come to this art museum in sequence. As a special privilege for the visitors, Modulo-san decided to distribute a copy of the tree drawing to each person, one sheet per visitor. Furthermore, to satisfy the visitors, it has been decided to paint all the vertices of the tree drawing to be distributed. The $k$th visitor $(1 \leq k \leq N)$ will be satisfied only when they are given a painting that satisfies both of the following two conditions:

- Any two vertices with a shortest distance that is a multiple of $k$ are painted with the same color.
- Any two vertices with a shortest distance that is not a multiple of $k$ are painted with different colors.

Modulo-san has an infinite number of colors available. The way of painting may be different for each copy. Determine whether it is possible to paint the vertices in a way that will satisfy each visitor, respectively.

Constraints

- $1 \leq N \leq 10^5$
- $1 \leq a_i, b_i \leq N$
- All input values are integers.
- It is guaranteed that the graph given by the input is a tree.

Input
Input is given from standard input in the following format.

\[
\begin{align*}
N \\
a_1\ b_1 \\
a_2\ b_2 \\
\vdots \\
a_{N-1}\ b_{N-1} \\
\end{align*}
\]

- The first line contains the integer $N$, which represents the number of vertices in the tree.
- From the second line to the $N$th line, information about the edges of the tree is given. On the $i+1(1 \leq i \leq N-1)$ line, two integers $a_i,b_i$, which indicate that vertices $a_i$ and $b_i$ are connected by an edge, are given.

Output
Output a string $S = s_1 s_2 \ldots s_N$ consisting of 0s and 1s such that:

- $s_k = 1$: It is possible to color the vertices of the given tree drawing in a way that will satisfy the $k$th visitor.
- $s_k = 0$: It is not possible to color the vertices of the given tree drawing in a way that will satisfy the $k$th visitor.

Example Input 1
\[
\begin{align*}
7 \\
1\ 3 \\
2\ 3 \\
3\ 4 \\
4\ 5 \\
4\ 6 \\
6\ 7 \\
\end{align*}
\]

Example Output 1
\[
1100111
\]

The tree of Example Input 1 looks like the following figure.
![image](1.png)
For example, when $k=2$, you can paint as follows to meet the conditions.
![image](2.png)
Also, when $k=5$, you can paint as follows to meet the conditions.
![image](3.png)

Example Input 2
\[
\begin{align*}
6 \\
1\ 2 \\
2\ 3 \\
3\ 4 \\
4\ 5 \\
5\ 6 \\
\end{align*}
\]

Example Output 2
\[
111111
\]

Example Input 3
\[
1
\]

Example Output 3
\[
1
\]

image_tags: Tree Tree Tree

data_split: test


B. Mushroom Scientists

problem_index: B

time_limit: 2 seconds

memory_limit: 256 megabytes

solutions: ["a = int(input())\nb = list(map(int, input().split()))\nif sum(b) == 0:\n\tprint(' '.join([str(a / 3)] * 3))\nelse:\n\tprint(' '.join(map(str, map(lambda x: a * x / sum(b), b))))\n", "n = int(input())\n(a, b, c) = map(int, input().split())\ns = a + b + c\nif s == 0:\n\tprint(0, 0, 0)\nelse:\n\tprint(n * a / s, n * b / s, n * c / s)\n", "S = int(input())\nv = [int(x) for x in input().strip().split()]\nzeroes = v.count(0)\ntotal = sum(v)\nans = []\nif zeroes == 0:\n\tans = [S * v[i] / total for i in range(3)]\nelif zeroes == 1:\n\tfor i in range(3):\n\t\tif v[i] == 0:\n\t\t\ttotal -= v[i]\n\tfor i in range(3):\n\t\tif v[i] != 0:\n\t\t\tans.append(S * v[i] / total)\n\t\telse:\n\t\t\tans.append(0)\nelse:\n\tfor i in range(3):\n\t\tif v[i] == 0:\n\t\t\tans.append(0)\n\t\telse:\n\t\t\tans.append(S)\nprint(*ans)\n", "def count(x1, y1, z1, x2, y2, z2):\n\tif x2 == 0 and a != 0 or (y2 == 0 and b != 0) or (z2 == 0 and c != 0):\n\t\treturn False\n\tif x2 == 0:\n\t\tx2 = 1\n\tif y2 == 0:\n\t\ty2 = 1\n\tif z2 == 0:\n\t\tz2 = 1\n\treturn (x1 / x2) ** a * (y1 / y2) ** b * (z1 / z2) ** c < 1\nn = int(input())\n(a, b, c) = map(int, input().split())\n(l1, r1) = (0, n)\nfor i in range(200):\n\tx1 = l1 + (r1 - l1) / 3\n\t(l2, r2) = (0, n - x1)\n\tfor j in range(200):\n\t\ty1 = l2 + (r2 - l2) / 3\n\t\ty2 = r2 - (r2 - l2) / 3\n\t\tif count(x1, y1, n - x1 - y1, x1, y2, n - x1 - y2):\n\t\t\tl2 = y1\n\t\telse:\n\t\t\tr2 = y2\n\ty11 = l2\n\tx2 = r1 - (r1 - l1) / 3\n\t(l2, r2) = (0, n - x2)\n\tfor j in range(200):\n\t\ty1 = l2 + (r2 - l2) / 3\n\t\ty2 = r2 - (r2 - l2) / 3\n\t\tif count(x2, y1, n - x2 - y1, x2, y2, n - x2 - y2):\n\t\t\tl2 = y1\n\t\telse:\n\t\t\tr2 = y2\n\ty22 = l2\n\tif count(x1, y11, n - x1 - y11, x2, y22, n - x2 - y22):\n\t\tl1 = x1\n\t\tp = y11\n\telse:\n\t\tr1 = x2\n\t\tp = y22\nprint(l1, p, n - l1 - p)\n", "s = float(input())\n(a, b, c) = map(float, input().split())\nif a == b and b == c and (c == 0):\n\tprint('0 0 ')\n\tprint(s)\nelse:\n\tprint(a * s / (a + b + c), end=' ')\n\tprint(b * s / (a + b + c), end=' ')\n\tprint(c * s / (a + b + c), end=' ')\n", "def gribnye(s, a, b, c):\n\tif a == b == c == s == 0:\n\t\treturn [0.0]\n\telif a == b == c == 0 and s != 0:\n\t\treturn (0, 0, 0)\n\ta1 = a * s / (a + b + c)\n\tb1 = b * s / (a + b + c)\n\tc1 = c * s / (a + b + c)\n\treturn (a1, b1, c1)\nS = int(input())\n(A, B, C) = [int(i) for i in input().split()]\nprint(*gribnye(S, A, B, C))\n", "sa = int(input())\n(a, b, c) = map(int, input().split(' '))\nif a == 0 and b == 0 and (c == 0):\n\tprint(0, 0, 0)\nelse:\n\tx = a * sa / (a + b + c)\n\ty = b * sa / (a + b + c)\n\tz = c * sa / (a + b + c)\n\tprint(x, y, z)\n", "S = int(input())\nv = [int(x) for x in input().strip().split()]\nprint(*([S * v[i] / sum(v) for i in range(3)] if sum(v) != 0 else '000'))\n", "from sys import stdin, stdout\ns = int(stdin.readline())\n(a, b, c) = map(int, stdin.readline().split())\nE = 10 ** (-7)\n(x, y, z) = (s / 3, s / 3, s / 3)\nans = 1\n\ndef power(v, n):\n\tcnt = 1\n\twhile n:\n\t\tif n % 2:\n\t\t\tcnt *= v\n\t\tn >>= 1\n\t\tv *= v\n\treturn cnt\n\ndef count(f, s, t):\n\treturn power(f / x, int(a)) * power(s / y, int(b)) * power(t / z, int(c))\n\ndef third(S, f, s):\n\tglobal x, y, z\n\t(l, r) = (0, S)\n\t(lb, rb) = (l + (r - l) / 3, r - (r - l) / 3)\n\twhile r - l > E:\n\t\tif count(f, s, lb) > count(f, s, rb):\n\t\t\tr = rb\n\t\telse:\n\t\t\tl = lb\n\t\t(lb, rb) = (l + (r - l) / 3, r - (r - l) / 3)\n\tif count(f, s, (lb + rb) / 2) > ans:\n\t\t(x, y, z) = (f, s, (lb + rb) / 2)\n\treturn count(f, s, (lb + rb) / 2)\n\ndef second(S, f):\n\t(l, r) = (0, S)\n\t(lb, rb) = (l + (r - l) / 3, r - (r - l) / 3)\n\twhile r - l > E:\n\t\tif third(S - lb, f, lb) > third(S - rb, f, rb):\n\t\t\tr = rb\n\t\telse:\n\t\t\tl = lb\n\t\t(lb, rb) = (l + (r - l) / 3, r - (r - l) / 3)\n\treturn third(S - (lb + rb) / 2, f, (lb + rb) / 2)\n\ndef first(S):\n\t(l, r) = (0, s)\n\t(lb, rb) = (l + (r - l) / 3, r - (r - l) / 3)\n\twhile r - l > E:\n\t\tif second(S - lb, lb) > second(S - rb, rb):\n\t\t\tr = rb\n\t\telse:\n\t\t\tl = lb\n\t\t(lb, rb) = (l + (r - l) / 3, r - (r - l) / 3)\n\treturn (S - (rb + lb) / 2, (rb + lb) / 2)\nfirst(s)\nstdout.write(str(x) + ' ' + str(y) + ' ' + str(z))\n"]

question:
As you very well know, the whole Universe traditionally uses three-dimensional Cartesian system of coordinates. In this system each point corresponds to three real coordinates (x, y, z). In this coordinate system, the distance between the center of the Universe and the point is calculated by the following formula: ![image](1.png). Mushroom scientists that work for the Great Mushroom King think that the Universe isn't exactly right and the distance from the center of the Universe to a point equals x^{a}·y^{b}·z^{c}.
To test the metric of mushroom scientists, the usual scientists offered them a task: find such x, y, z (0 ≤ x, y, z; x + y + z ≤ S), that the distance between the center of the Universe and the point (x, y, z) is maximum possible in the metric of mushroom scientists. The mushroom scientists aren't good at maths, so they commissioned you to do the task.
Note that in this problem, it is considered that 0^{0} = 1.

Input
The first line contains a single integer S (1 ≤ S ≤ 10^{3}) — the maximum sum of coordinates of the sought point.
The second line contains three space-separated integers a, b, c (0 ≤ a, b, c ≤ 10^{3}) — the numbers that describe the metric of mushroom scientists.

Output
Print three real numbers — the coordinates of the point that reaches maximum value in the metrics of mushroom scientists. If there are multiple answers, print any of them that meets the limitations.
A natural logarithm of distance from the center of the Universe to the given point in the metric of mushroom scientists shouldn't differ from the natural logarithm of the maximum distance by more than 10^{ - 6}. We think that ln(0) =  - ∞.

Examples
Input
3
1 1 1

Output
1.0 1.0 1.0

Input
3
2 0 0

Output
3.0 0.0 0.0

source: codeforces

raw_problem:
B. Mushroom Scientists

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

As you very well know, the whole Universe traditionally uses three-dimensional Cartesian system of coordinates. In this system each point corresponds to three real coordinates (x, y, z). In this coordinate system, the distance between the center of the Universe and the point is calculated by the following formula: . Mushroom scientists that work for the Great Mushroom King think that the Universe isn't exactly right and the distance from the center of the Universe to a point equals xa·yb·zc.

To test the metric of mushroom scientists, the usual scientists offered them a task: find such x, y, z (0 ≤ x, y, z; x + y + z ≤ S), that the distance between the center of the Universe and the point (x, y, z) is maximum possible in the metric of mushroom scientists. The mushroom scientists aren't good at maths, so they commissioned you to do the task.

Note that in this problem, it is considered that 00 = 1.

Input

The first line contains a single integer S (1 ≤ S ≤ 103) — the maximum sum of coordinates of the sought point.

The second line contains three space-separated integers a, b, c (0 ≤ a, b, c ≤ 103) — the numbers that describe the metric of mushroom scientists.

Output

Print three real numbers — the coordinates of the point that reaches maximum value in the metrics of mushroom scientists. If there are multiple answers, print any of them that meets the limitations.

A natural logarithm of distance from the center of the Universe to the given point in the metric of mushroom scientists shouldn't differ from the natural logarithm of the maximum distance by more than 10 - 6. We think that ln(0) =  - ∞.

Examples

Input

3
1 1 1

Output

1.0 1.0 1.0

Input

3
2 0 0

Output

3.0 0.0 0.0

skill_types: ['Sorting']

data_split: test


A. Tokitsukaze and Discard Items

problem_index: A

time_limit: 1 second

memory_limit: 256 megabytes

solutions: ["(n, m, k) = map(int, input().split())\narr = map(int, input().split())\nanswer = 0\ncur_page = -1\nremoved = 0\nfor (i, el) in enumerate(arr):\n\tif (el - removed - 1) // k != cur_page:\n\t\tanswer += 1\n\t\tremoved = i\n\t\tcur_page = (el - removed - 1) // k\nprint(answer)\n", "from collections import deque\n(n, m, k) = list(map(int, input().split()))\np = deque((int(x) - 1 for x in input().split()))\nnumRemoved = 0\nops = 0\nwhile len(p) > 0:\n\tcurrRemoved = 1\n\tfront = p.popleft()\n\tcurrPage = (front - numRemoved) // k\n\twhile len(p) > 0 and (p[0] - numRemoved) // k == currPage:\n\t\tcurrRemoved += 1\n\t\tp.popleft()\n\tops += 1\n\tnumRemoved += currRemoved\nprint(ops)\n", "(n, m, k) = list(map(int, input().split(' ')))\np = tuple(map(int, input().split(' ')))\nd = 0\npart = (p[0] - 1) // k\nmoves = 0\nskip = 0\nfor pi in p:\n\tif (pi - 1 - d) // k == part:\n\t\tskip += 1\n\t\tcontinue\n\td += skip\n\tpart = (pi - 1 - d) // k\n\tskip = 1\n\tmoves += 1\nprint(moves + 1)\n", "(n, m, k) = map(int, input().split())\nl = list(map(int, input().split()))\ni = 0\noperations = 0\nwhile i < m:\n\tj = i\n\tcu = (l[i] - 1 - j) // k\n\twhile i < m and (l[i] - 1 - j) // k == cu:\n\t\ti += 1\n\toperations += 1\nprint(operations)\n", "(n, m, k) = map(int, input().split())\np = [int(x) for x in input().split()]\nt = 0\ni = 0\nop = 0\nwhile i < m:\n\tcmp = ((p[i] - t - 1) // k + 1) * k\n\ti += 1\n\ttemp = t\n\tt += 1\n\top += 1\n\twhile i < m:\n\t\tif p[i] - temp <= cmp:\n\t\t\ti += 1\n\t\t\tt += 1\n\t\telse:\n\t\t\tbreak\nprint(op)\n", "import sys\nimport math\nimport bisect\nimport heapq\nfrom bisect import bisect_right\nfrom sys import stdin, stdout\n\ndef get_ints_in_variables():\n\treturn map(int, sys.stdin.readline().strip().split())\n\ndef get_int():\n\treturn int(sys.stdin.readline())\n\ndef get_ints_in_list():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\n\ndef get_list_of_list(n):\n\treturn [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]\n\ndef get_string():\n\treturn sys.stdin.readline().strip()\n\ndef myceil(x, y):\n\treturn (x + y - 1) // y\n\ndef bst(mxp, k, cnt, el):\n\tl = 1\n\tr = mxp\n\tans = 1\n\twhile l <= r:\n\t\tmid = (l + r) // 2\n\t\tif mid * k >= el - cnt:\n\t\t\tans = mid\n\t\t\tr = mid - 1\n\t\telse:\n\t\t\tl = mid + 1\n\treturn ans\n\ndef Solution(arr, n, m, k):\n\tans = 0\n\tcnt = 0\n\ti = 0\n\twhile i < m:\n\t\tpos = ((arr[i] - cnt - 1) // k + 1) * k + cnt\n\t\twhile i < m and pos >= arr[i]:\n\t\t\ti += 1\n\t\t\tcnt += 1\n\t\tans += 1\n\tprint(ans)\n\ndef main():\n\t(n, m, k) = get_ints_in_variables()\n\tarr = get_ints_in_list()\n\tSolution(arr, n, m, k)\nmain()\n", "import math\n(n, m, k) = list(map(int, input().split()))\np = list(map(int, input().split()))\np.sort()\nok = k\nip = 0\ns = 0\nif ok == 1:\n\tprint(len(p))\nelse:\n\twhile ip < n and p:\n\t\tm = False\n\t\tcnt = 0\n\t\to = 0\n\t\twhile o < len(p):\n\t\t\tif ip < p[o] and p[o] <= k:\n\t\t\t\tm = True\n\t\t\t\tcnt += 1\n\t\t\t\tp.pop(o)\n\t\t\t\to -= 1\n\t\t\telse:\n\t\t\t\tbreak\n\t\t\to += 1\n\t\tif m:\n\t\t\ts += 1\n\t\t\tk += cnt\n\t\telse:\n\t\t\tl = math.ceil((p[o] - k) / ok)\n\t\t\tip = k + ok * (l - 1)\n\t\t\tk += ok * l\n\tprint(s)\n", "(n, m, k) = map(int, input().split())\np = list(map(int, input().split()))\np = [p[i] - 1 for i in range(m)]\npage = [(p[i] - i) // k for i in range(m)]\nsame = 0\npos = [0] * m\nfor i in range(m):\n\tif i > 0:\n\t\tif page[i] == page[i - 1]:\n\t\t\tsame += 1\n\t\telse:\n\t\t\tsame = 0\n\tpos[i] = (p[i] - i) % k + same\ncurr = page[0]\npages = [[]]\nfor i in range(m):\n\tif page[i] == curr:\n\t\tpages[-1].append(pos[i])\n\telse:\n\t\tcurr = page[i]\n\t\tpages.append([pos[i]])\ntot = 0\nfor page in pages:\n\ta = len(page)\n\tind = 0\n\tend = k\n\tsteps = 1\n\twhile ind < a:\n\t\tif page[ind] >= end:\n\t\t\tend = k + ind\n\t\t\tsteps += 1\n\t\tind += 1\n\ttot += steps\nprint(tot)\n", "import sys\ninput = sys.stdin.readline\n(n, m, k) = list(map(int, input().split()))\nA = list(map(int, input().split()))\nA.append(n + 1)\nCOMP = []\nNOW = 0\nfor a in A:\n\tif a - NOW - 1 != 0:\n\t\tif a - NOW - 1 > 2 * k:\n\t\t\tCOMP.append([(a - NOW - 1) % k + k, 0])\n\t\telse:\n\t\t\tCOMP.append([a - NOW - 1, 0])\n\tCOMP.append([1, 1])\n\tNOW = a\nCOMP.pop()\nANS = 0\nNOW_PAGE = 0\nNOW_SCORE = 0\npa = 0\nLEN = len(COMP)\nwhile pa < LEN:\n\t(i, j) = COMP[pa]\n\tif NOW_PAGE + i <= k:\n\t\tNOW_PAGE += i\n\t\tNOW_SCORE += j\n\t\tpa += 1\n\telif NOW_SCORE > 0:\n\t\tCOMP[pa][0] -= k - NOW_PAGE\n\t\tNOW_PAGE = k - NOW_SCORE\n\t\tANS += 1\n\t\tNOW_SCORE = 0\n\telif NOW_PAGE == k:\n\t\tNOW_PAGE = 0\n\telse:\n\t\tCOMP[pa][0] -= k - NOW_PAGE\n\t\tNOW_PAGE = k - NOW_SCORE\nif NOW_SCORE > 0:\n\tANS += 1\nprint(ANS)\n", "(n, m, k) = list(map(int, input().split()))\nls = list(map(int, input().split()))\nans = 0\ni = 0\nst = 1\nwhile i < len(ls):\n\tthrow = 0\n\tnex = ls[i]\n\tadd = (nex - st) // k\n\tst = st + add * k\n\twhile i < len(ls) and st <= ls[i] <= st + k - 1:\n\t\tthrow += 1\n\t\ti += 1\n\tst += throw\n\tans += 1\nprint(ans)\n", "(n, m, k) = map(int, input().split())\na = sorted(map(int, input().split()))\nd = 0\ni = 0\nt = 0\nwhile i < len(a):\n\tp = (a[i] - d - 1) // k\n\tj = i\n\twhile j < len(a) and (a[j] - d - 1) // k == p:\n\t\tj = j + 1\n\td = d + j - i\n\tt = t + 1\n\ti = j\nprint(t)\n", "(n, m, k) = map(int, input().split())\na = list(map(int, input().split()))\n(d, i, t) = (0, 0, 0)\nwhile i < m:\n\tpg = (a[i] - d - 1) // k\n\tj = i\n\twhile j < m and (a[j] - d - 1) // k == pg:\n\t\tj += 1\n\td += j - i\n\tt += 1\n\ti = j\nprint(t)\n", "from collections import defaultdict\nimport sys\ninput = sys.stdin.readline\ninf = 100000000000000000\nmod = 998244353\n(n, m, k) = map(int, input().split())\nA = [0] + list(map(int, input().split()))\nsum = 0\nans = 0\nnow = 1\nwhile now <= m:\n\tr = sum\n\tr += (A[now] - sum - 1) // k * k\n\tr += k\n\twhile now <= m and r >= A[now]:\n\t\tsum += 1\n\t\tnow += 1\n\tans += 1\nprint(ans)\n", "(n, m, k) = map(int, input().split())\nps = list(map(int, input().split()))\nshift = 0\nres = 0\nind = 0\nwhile len(ps) > ind:\n\tres += 1\n\tfirst = (ps[ind] - shift - 1) // k * k + 1\n\tds = 0\n\twhile len(ps) > ind and ps[ind] - shift - first < k:\n\t\tds += 1\n\t\tind += 1\n\tshift += ds\nprint(res)\n", "(n, m, k) = list(map(int, input().split()))\ndiscard = list(map(int, input().split()))\nstartK = (int(discard[0] / k) + (discard[0] % k != 0)) * k\nstep = 0\nid = 0\nwhile True:\n\tdisnum = 0\n\twhile id < m and startK >= discard[id]:\n\t\tdisnum += 1\n\t\tid += 1\n\tstartK += disnum\n\tif disnum == 0:\n\t\tif id == m:\n\t\t\tbreak\n\t\tstartK += int((discard[id] - startK) / k + ((discard[id] - startK) % k != 0)) * k\n\telse:\n\t\tstep += 1\nprint(step)\n", "(n, m, k) = map(int, input().split())\nl = list(map(int, input().split()))\nbeg = 1\ncnt = 0\ni = 0\nj = 0\nele = 0\nwhile i < m:\n\tend = ((l[i] - ele - 1) // k + 1) * k + ele\n\twhile i < m and l[i] <= end:\n\t\ti += 1\n\t\tele += 1\n\tcnt += 1\nprint(cnt)\n", "import math\nimport collections\n\ndef func(a, k):\n\tif a % k != 0:\n\t\tmod = 1\n\telse:\n\t\tmod = 0\n\treturn math.floor(a / k) * k + mod * k\n(n, m, k) = input().split()\nlist = input().split()\nk = int(k)\ntemp = k\nsize = 0\nanswer = 0\nc = 0\nc2 = 0\ncheck = 'false'\nused = 0\ntemp = func(int(list[0]), k)\nfor i in range(len(list)):\n\tlist[i] = int(list[i])\n\tused = 0\n\tif list[i] <= temp:\n\t\tc += 1\n\t\tcheck = 'true'\n\t\tused = 1\n\tif list[i] >= temp:\n\t\tif check is 'true':\n\t\t\tanswer += 1\n\t\t\tcheck = 'false'\n\t\t\ttemp += c\n\t\t\tc = 0\n\t\t\tif list[i] - c <= temp and used == 0:\n\t\t\t\tc += 1\n\t\t\t\tcheck = 'true'\n\t\t\t\tused = 1\n\t\t\telse:\n\t\t\t\ttemp = temp + func(int(list[i]) - temp, k)\n\t\t\t\tif list[i] - c <= temp and used == 0:\n\t\t\t\t\tc += 1\n\t\t\t\t\tcheck = 'true'\n\t\t\t\t\tused = 1\n\t\telif check is 'false':\n\t\t\ttemp = temp + func(int(list[i]) - temp, k)\n\t\t\tif list[i] - c <= temp and used == 0:\n\t\t\t\tc += 1\n\t\t\t\tcheck = 'true'\n\t\t\t\tused = 1\nprint(answer if check is 'false' else answer + 1)\n", "from decimal import Decimal\n\ndef ceil(n, k):\n\tif n % k != 0:\n\t\treturn n // k + 1\n\treturn n // k\n(n, m, k) = map(int, input().split())\na = list(map(int, input().split()))\ni = 0\ndif = 0\nans = 0\nwhile i < m:\n\tgp = ceil(a[i] - dif, k)\n\twhile i < m:\n\t\tif ceil(a[i] - dif, k) == gp:\n\t\t\ti += 1\n\t\telse:\n\t\t\tdif = i\n\t\t\tbreak\n\tans += 1\nprint(ans)\n", "(n, m, k) = map(int, input().split())\np = list(map(int, input().split()))\np = list(map(lambda x: x - 1, p))\ndis = 0\nans = 0\ncnt = 1\nfor i in range(m - 1):\n\tif (p[i] - dis) // k != (p[i + 1] - dis) // k:\n\t\tdis += cnt\n\t\tans += 1\n\t\tcnt = 1\n\telse:\n\t\tcnt += 1\nans += 1\nprint(ans)\n", "(n, m, k) = map(int, input().split())\np = list(map(int, input().split()))\nrev = 1\nnew_rev = 1\npage = None\ncount = 0\nfor i in range(m):\n\tif (p[i] - rev) // k != page:\n\t\tcount += 1\n\t\trev = new_rev\n\t\tpage = (p[i] - rev) // k\n\tnew_rev += 1\nprint(count)\n", "R = lambda : list(map(int, input().split()))\n(n, m, k) = R()\nl = R()\nq = 0\nt = 1\nnb = 0\nfor i in range(m - 1):\n\tif (l[i + 1] - 1 - q) // k == (l[i] - 1 - q) // k:\n\t\tt += 1\n\t\tpass\n\telse:\n\t\tnb += 1\n\t\tq += t\n\t\tt = 1\nprint(nb + 1)\n", "(n, m, k) = list(map(int, input().split()))\nP = [int(x) for x in input().split()]\nP.reverse()\nops = 0\ni = 1\nwhile P:\n\tnxt = P[-1]\n\ttogo = nxt - i\n\tskip = togo // k * k\n\ti += skip\n\tspace = k\n\twhile space:\n\t\tspecial = 0\n\t\twhile P and P[-1] < i + space:\n\t\t\tspecial += 1\n\t\t\tP.pop()\n\t\ti += space\n\t\tif not special:\n\t\t\tbreak\n\t\tops += 1\n\t\tspace = special\nprint(ops)\n", "(n, m, k) = [int(i) for i in input().split()]\nlst = [int(j) for j in input().split()]\n(result, new_result) = (1, 1)\n(page, count) = (None, 0)\nfor i in range(m):\n\tif (lst[i] - result) // k != page:\n\t\tcount += 1\n\t\tresult = new_result\n\t\tpage = (lst[i] - result) // k\n\tnew_result += 1\nprint(count)\n", "import sys\nimport math\nimport collections\nimport heapq\nimport decimal\ninput = sys.stdin.readline\n(n, m, k) = (int(i) for i in input().split())\nl = [int(i) for i in input().split()]\ni = 0\nc = 0\nc1 = 0\nwhile i < m:\n\tc2 = 0\n\tp = ((l[i] - c1 - 1) // k + 1) * k + c1\n\tfor j in range(i, m):\n\t\tif l[j] <= p:\n\t\t\tc2 += 1\n\t\telse:\n\t\t\tbreak\n\ti += c2\n\tc1 += c2\n\tc += 1\nprint(c)\n", "(n, m, k) = list(map(int, input().split()))\np = list(map(int, input().split()))\n(deleted, right) = (0, 0)\nc = 0\nmoves = 0\nwhile c < m:\n\tright = (1 + (p[c] - deleted - 1) // k) * k + deleted\n\twhile c < len(p) and p[c] <= right:\n\t\tc += 1\n\t\tdeleted += 1\n\tmoves += 1\nprint(moves)\n", "(n, m, k) = list(map(int, input().split()))\narr = list(map(int, input().split()))\n(res, i) = (1, 0)\nf = (arr[0] - 1) // k * k + 1\ne = f + k - 1\nwhile e < arr[-1]:\n\td = 0\n\twhile i + d < m and arr[i + d] <= e:\n\t\td += 1\n\ti += d\n\tif d > 0:\n\t\te += d\n\t\tres += 1\n\telse:\n\t\tf = e + 1\n\t\tf += (arr[i] - f) // k * k\n\t\te = f + k - 1\nprint(res)\n", "(n, m, k) = map(int, input().split())\np = list(map(int, input().split()))\nc = 0\ntmp = 0\nops = 0\ncurr_page = (p[0] - 1) // k\nfor pp in p:\n\tif curr_page != (pp - 1 - c) // k:\n\t\tc += tmp\n\t\ttmp = 1\n\t\tops += 1\n\t\tcurr_page = (pp - 1 - c) // k\n\telse:\n\t\ttmp += 1\nprint(ops + 1)\n", "import math\n(n, m, k) = map(int, input().strip().split(' '))\nlst = list(map(int, input().strip().split(' ')))\nc = 0\nc1 = 0\npg = 0\nans = 0\nfor i in range(m):\n\tif i == 0:\n\t\tif lst[i] % k != 0:\n\t\t\tpg = lst[i] // k + 1\n\t\telse:\n\t\t\tpg = lst[i] // k\n\t\tc += 1\n\t\tans += 1\n\telse:\n\t\tif (lst[i] - c1) % k != 0:\n\t\t\tp = (lst[i] - c1) // k + 1\n\t\telse:\n\t\t\tp = (lst[i] - c1) // k\n\t\tif p == pg:\n\t\t\tc += 1\n\t\telse:\n\t\t\tans += 1\n\t\t\tc1 = c\n\t\t\tif (lst[i] - c1) % k != 0:\n\t\t\t\tpg = (lst[i] - c1) // k + 1\n\t\t\telse:\n\t\t\t\tpg = (lst[i] - c1) // k\n\t\t\tc += 1\nprint(ans)\n", "(n, m, k) = list(map(int, input().split()))\nl = list(map(int, input().split()))\no = 0\nd = 0\nwhile m > d:\n\tg = l[d]\n\tpage = (g - d - 1) // k\n\tadd = 1\n\twhile d + add < m and page * k < l[d + add] - d <= (page + 1) * k:\n\t\tadd += 1\n\td += add\n\to += 1\nprint(o)\n", "(n, m, k) = map(int, input().split())\nlis = list(map(int, input().split()))\nx = 0\ni = 0\nwhile i < m:\n\ty = i\n\tcur = (lis[i] - 1 - y) // k\n\twhile i < m and (lis[i] - 1 - y) // k == cur:\n\t\ti += 1\n\tx += 1\nprint(x)\n", "(n, m, k) = list(map(int, input().split()))\nmi = list(map(int, input().split()))\nans = 0\nitems_to_del = 0\nshift = 1\nc_page = None\nfor el in mi:\n\tif c_page is None:\n\t\tc_page = (el - shift) // k\n\t\titems_to_del = 1\n\telse:\n\t\tpage = (el - shift) // k\n\t\tif page != c_page:\n\t\t\tshift += items_to_del\n\t\t\tans += 1\n\t\t\tc_page = (el - shift) // k\n\t\t\titems_to_del = 1\n\t\telse:\n\t\t\titems_to_del += 1\nif items_to_del != 0:\n\tans += 1\nprint(ans)\n", "(n, m, k) = map(int, input().split())\np = list(map(int, input().split()))\npage = k * ((p[0] - 1) // k + 1)\nj = 0\nk_op = 0\ncfnt = 0\nwhile j < m:\n\tif p[j] - cfnt > page:\n\t\tcfnt = j\n\t\tpage = k * ((p[j] - cfnt - 1) // k + 1)\n\t\tk_op += 1\n\t\tj -= 1\n\tj += 1\nprint(k_op + 1)\n", "from sys import stdin\nfrom math import gcd, sqrt\nfrom collections import deque\ninput = stdin.readline\nR = lambda : map(int, input().split())\nI = lambda : int(input())\nS = lambda : input().rstrip('\\n')\nhg = lambda x, y: (y + x - 1) // x * x\n(n, m, k) = R()\nans = d = p = pg = 0\nfor i in R():\n\tif i - d <= pg:\n\t\tp += 1\n\t\tcontinue\n\telse:\n\t\td += p\n\t\tp = 0\n\t\tans += 1\n\t\tpg = hg(k, i - d)\n\t\tp += 1\nprint(ans)\n", "import math\n\ndef solve():\n\t(n, m, k) = list(map(int, input().split()))\n\tarr = list(map(int, input().split()))\n\tcurrent = k\n\tindex = 0\n\titeration = 0\n\twhile index < m:\n\t\tif current < arr[index]:\n\t\t\tcurrent += math.ceil((arr[index] - current) / k) * k\n\t\t\tcontinue\n\t\tval = 0\n\t\twhile index < m and current >= arr[index]:\n\t\t\tval += 1\n\t\t\tindex += 1\n\t\titeration += 1\n\t\tif index == m:\n\t\t\tbreak\n\t\tif val == 0:\n\t\t\tcurrent += math.ceil((arr[index] - current) / k) * k\n\t\telse:\n\t\t\tcurrent += val\n\tprint(iteration)\nsolve()\n", "(n, m, k) = list(map(int, input().split()))\nl = list(map(int, input().split()))\nout = 0\nd = 0\nwhile m > d:\n\tnex = l[d]\n\tpage = (nex - d - 1) // k\n\tadd = 1\n\twhile d + add < m and page * k < l[d + add] - d <= (page + 1) * k:\n\t\tadd += 1\n\td += add\n\tout += 1\nprint(out)\n", "(n, m, k) = map(int, input().split())\na = list(map(int, input().split()))\n(ans, result) = (0, 0)\n(page, new_result) = (None, 1)\nfor i in range(m):\n\tif (a[i] - result) // k != page:\n\t\tans += 1\n\t\tresult = new_result\n\t\tpage = (a[i] - result) // k\n\tnew_result += 1\nprint(ans)\n", "(n, m, k) = [int(p) for p in input().split()]\narr = [int(p) for p in input().split()]\nfor i in range(len(arr)):\n\tarr[i] -= 1\ncnt = 0\nsteps = 0\ni = 0\ngcnt = 0\nwhile i < m:\n\tpg = (arr[i] - gcnt) // k\n\tj = i\n\tloop = True\n\twhile j < m:\n\t\tif (arr[j] - gcnt) // k == pg:\n\t\t\tcnt += 1\n\t\t\tj += 1\n\t\telse:\n\t\t\tbreak\n\t\tif loop:\n\t\t\tsteps += 1\n\t\t\tloop = False\n\ti = j\n\tgcnt = cnt\nprint(steps)\n", "(n, m, k) = map(int, input().split())\np = list(map(int, input().split()))\ncount = 0\ndelete = 0\nnow = 0\nwhile now < m:\n\tup = ((p[now] - delete - 1) // k + 1) * k + delete\n\twhile now < m and p[now] <= up:\n\t\tnow += 1\n\t\tdelete += 1\n\tcount += 1\nprint(count)\n", "def naiveSolve():\n\treturn\n\ndef main():\n\t(n, m, k) = readIntArr()\n\tp = readIntArr()\n\tfor i in range(m):\n\t\tp[i] -= 1\n\tdiscarded = 0\n\tnOperations = 1\n\tleftI = -1\n\tfor (i, x) in enumerate(p):\n\t\tif i == 0:\n\t\t\tleftI = i\n\t\t\tcontinue\n\t\tif (p[leftI] - discarded) // k != (x - discarded) // k:\n\t\t\tnOperations += 1\n\t\t\tdiscarded += i - leftI\n\t\t\tleftI = i\n\tprint(nOperations)\n\treturn\nimport sys\ninput = sys.stdin.buffer.readline\n\ndef oneLineArrayPrint(arr):\n\tprint(' '.join([str(x) for x in arr]))\n\ndef multiLineArrayPrint(arr):\n\tprint('\\n'.join([str(x) for x in arr]))\n\ndef multiLineArrayOfArraysPrint(arr):\n\tprint('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\n\ndef readIntArr():\n\treturn [int(x) for x in input().split()]\n\ndef makeArr(defaultValFactory, dimensionArr):\n\tdv = defaultValFactory\n\tda = dimensionArr\n\tif len(da) == 1:\n\t\treturn [dv() for _ in range(da[0])]\n\telse:\n\t\treturn [makeArr(dv, da[1:]) for _ in range(da[0])]\n\ndef queryInteractive(l, r):\n\tprint('? {} {}'.format(l, r))\n\tsys.stdout.flush()\n\treturn int(input())\n\ndef answerInteractive(x):\n\tprint('! {}'.format(x))\n\tsys.stdout.flush()\ninf = float('inf')\nMOD = 998244353\nfrom math import gcd, floor, ceil\nfor _abc in range(1):\n\tmain()\n", "import sys\n(n, m, k) = list(map(int, sys.stdin.readline().strip().split()))\np = list(map(int, sys.stdin.readline().strip().split()))\ni = 0\nc = 0\nd = 0\nwhile i < m:\n\tc = c + 1\n\td2 = d\n\tx = k * ((p[i] - d2 - 1) // k) + k\n\twhile p[i] - d2 <= x:\n\t\ti = i + 1\n\t\td = d + 1\n\t\tif i == m:\n\t\t\tbreak\nprint(c)\n", "from collections import defaultdict\nimport sys\ninput = sys.stdin.readline\ninf = 100000000000000000\nmod = 998244353\n(n, m, k) = map(int, input().split())\nA = [0] + list(map(int, input().split()))\npos = k\nsum = 0\nans = 0\npointer = 1\nwhile pointer <= m:\n\tif pos < A[pointer]:\n\t\tpos += (A[pointer] - pos - 1) // k * k\n\t\tpos += k\n\tsum = 0\n\twhile pointer <= m and pos >= A[pointer]:\n\t\tsum += 1\n\t\tpointer += 1\n\tpos += sum\n\tans += 1\nprint(ans)\n"]

difficulty: MEDIUM

source: codeforces

raw_problem:
A. Tokitsukaze and Discard Items

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Recently, Tokitsukaze found an interesting game. Tokitsukaze had $$$n$$$ items at the beginning of this game. However, she thought there were too many items, so now she wants to discard $$$m$$$ ($$$1 \le m \le n$$$) special items of them.

These $$$n$$$ items are marked with indices from $$$1$$$ to $$$n$$$. In the beginning, the item with index $$$i$$$ is placed on the $$$i$$$-th position. Items are divided into several pages orderly, such that each page contains exactly $$$k$$$ positions and the last positions on the last page may be left empty.

Tokitsukaze would do the following operation: focus on the first special page that contains at least one special item, and at one time, Tokitsukaze would discard all special items on this page. After an item is discarded or moved, its old position would be empty, and then the item below it, if exists, would move up to this empty position. The movement may bring many items forward and even into previous pages, so Tokitsukaze would keep waiting until all the items stop moving, and then do the operation (i.e. check the special page and discard the special items) repeatedly until there is no item need to be discarded.
  Consider the first example from the statement: $$$n=10$$$, $$$m=4$$$, $$$k=5$$$, $$$p=[3, 5, 7, 10]$$$. The are two pages. Initially, the first page is special (since it is the first page containing a special item). So Tokitsukaze discards the special items with indices $$$3$$$ and $$$5$$$. After, the first page remains to be special. It contains $$$[1, 2, 4, 6, 7]$$$, Tokitsukaze discards the special item with index $$$7$$$. After, the second page is special (since it is the first page containing a special item). It contains $$$[9, 10]$$$, Tokitsukaze discards the special item with index $$$10$$$.
Tokitsukaze wants to know the number of operations she would do in total.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le m \le 10^5$$$, $$$1 \le m, k \le n$$$) — the number of items, the number of special items to be discarded and the number of positions in each page.

The second line contains $$$m$$$ distinct integers $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \le p_1 < p_2 < \ldots < p_m \le n$$$) — the indices of special items which should be discarded.

Output

Print a single integer — the number of operations that Tokitsukaze would do in total.

Examples

Input

10 4 5
3 5 7 10

Output

3

Input

13 4 5
7 8 9 10

Output

1

Note

For the first example:

 In the first operation, Tokitsukaze would focus on the first page $$$[1, 2, 3, 4, 5]$$$ and discard items with indices $$$3$$$ and $$$5$$$;

 In the second operation, Tokitsukaze would focus on the first page $$$[1, 2, 4, 6, 7]$$$ and discard item with index $$$7$$$;

 In the third operation, Tokitsukaze would focus on the second page $$$[9, 10]$$$ and discard item with index $$$10$$$.

For the second example, Tokitsukaze would focus on the second page $$$[6, 7, 8, 9, 10]$$$ and discard all special items at once.

question:
Recently, Tokitsukaze found an interesting game. Tokitsukaze had $$$n$$$ items at the beginning of this game. However, she thought there were too many items, so now she wants to discard $$$m$$$ ($$$1 \le m \le n$$$) special items of them.
These $$$n$$$ items are marked with indices from $$$1$$$ to $$$n$$$. In the beginning, the item with index $$$i$$$ is placed on the $$$i$$$-th position. Items are divided into several pages orderly, such that each page contains exactly $$$k$$$ positions and the last positions on the last page may be left empty.
Tokitsukaze would do the following operation: focus on the first special page that contains at least one special item, and at one time, Tokitsukaze would discard all special items on this page. After an item is discarded or moved, its old position would be empty, and then the item below it, if exists, would move up to this empty position. The movement may bring many items forward and even into previous pages, so Tokitsukaze would keep waiting until all the items stop moving, and then do the operation (i.e. check the special page and discard the special items) repeatedly until there is no item need to be discarded.
 ![image](1.png) Consider the first example from the statement: $$$n=10$$$, $$$m=4$$$, $$$k=5$$$, $$$p=[3, 5, 7, 10]$$$. The are two pages. Initially, the first page is special (since it is the first page containing a special item). So Tokitsukaze discards the special items with indices $$$3$$$ and $$$5$$$. After, the first page remains to be special. It contains $$$[1, 2, 4, 6, 7]$$$, Tokitsukaze discards the special item with index $$$7$$$. After, the second page is special (since it is the first page containing a special item). It contains $$$[9, 10]$$$, Tokitsukaze discards the special item with index $$$10$$$. Tokitsukaze wants to know the number of operations she would do in total.

Input
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le m \le 10^5$$$, $$$1 \le m, k \le n$$$) — the number of items, the number of special items to be discarded and the number of positions in each page.
The second line contains $$$m$$$ distinct integers $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \le p_1 < p_2 < \ldots < p_m \le n$$$) — the indices of special items which should be discarded.

Output
Print a single integer — the number of operations that Tokitsukaze would do in total.

Examples
Input
10 4 5
3 5 7 10

Output
3

Input
13 4 5
7 8 9 10

Output
1

Note
For the first example:
 -  In the first operation, Tokitsukaze would focus on the first page $$$[1, 2, 3, 4, 5]$$$ and discard items with indices $$$3$$$ and $$$5$$$; -  In the second operation, Tokitsukaze would focus on the first page $$$[1, 2, 4, 6, 7]$$$ and discard item with index $$$7$$$; -  In the third operation, Tokitsukaze would focus on the second page $$$[9, 10]$$$ and discard item with index $$$10$$$. For the second example, Tokitsukaze would focus on the second page $$$[6, 7, 8, 9, 10]$$$ and discard all special items at once.

skill_types: ['Amortized analysis']

Expected Time Complexity: O(N)

data_split: test


F. Power Sockets

problem_index: F

time_limit: 4 seconds

memory_limit: 256 megabytes

note:
![image](images/cf_1469_F/1.png)
You are allowed to not use all the chains, so it's optimal to only use chain of length $$$4$$$ in the second example.

solutions: ["MAX_H = int(200000.0 + 20)\n(n, k) = map(int, input().split())\nl = list(map(int, input().split()))\nl.sort()\ncur = 1\ncur_sum = 0\ncur_level = 0\nflag_seen = 1\nflag_sum = 0\nans = flag_level = int(MAX_H - 1)\nlazy = [0] * MAX_H\nwhile l and cur_level + 2 < flag_level:\n\tnew_chain = l.pop()\n\tcur -= 1\n\tlazy[cur_level + 2] += 2\n\tlazy[cur_level + 2 + (new_chain - 1) // 2] -= 1\n\tlazy[cur_level + 2 + new_chain // 2] -= 1\n\tflag_seen -= 1\n\tflag_seen += min(flag_level, cur_level + 2 + (new_chain - 1) // 2) - (cur_level + 2)\n\tflag_seen += min(flag_level, cur_level + 2 + new_chain // 2) - (cur_level + 2)\n\tflag_sum += sum((x >= flag_level for x in [cur_level + 2 + (new_chain - 1) // 2, cur_level + 2 + new_chain // 2]))\n\twhile cur == 0:\n\t\tcur_level += 1\n\t\tcur_sum += lazy[cur_level]\n\t\tcur += cur_sum\n\twhile flag_seen >= k:\n\t\tflag_seen -= flag_sum\n\t\tflag_level -= 1\n\t\tflag_sum -= lazy[flag_level]\n\tans = min(ans, flag_level)\nprint(-1 if ans == MAX_H - 1 else ans)\n", "import sys\ninput = sys.stdin.readline\nimport math\n(n, k) = map(int, input().split())\nB = sorted(map(int, input().split()), reverse=True)\nN = 5 * (n + max(B))\nA = [0] * N\nA[0] = 1\nA[1] = -1\nans = float('inf')\ntotal = 0\nj = 0\nfor i in range(N - 1):\n\ttotal += A[i]\n\tA[i + 1] += A[i]\n\tif total + A[i + 1] >= k:\n\t\tans = min(ans, i + 1)\n\twhile A[i] > 0 and j < n:\n\t\tu = (B[j] - 1) // 2\n\t\tv = B[j] - 1 - u\n\t\tA[i + 2] += 1\n\t\tA[i + 2 + u] -= 1\n\t\tA[i + 2] += 1\n\t\tA[i + 2 + v] -= 1\n\t\tA[i] -= 1\n\t\ttotal -= 1\n\t\tj += 1\nprint(ans if ans < float('inf') else -1)\n", "class RangeBIT:\n\n\tdef __init__(self, N, indexed):\n\t\tself.bit1 = [0] * (N + 2)\n\t\tself.bit2 = [0] * (N + 2)\n\t\tself.mode = indexed\n\n\tdef bitadd(self, a, w, bit):\n\t\tx = a\n\t\twhile x <= len(bit) - 1:\n\t\t\tbit[x] += w\n\t\t\tx += x & -1 * x\n\n\tdef bitsum(self, a, bit):\n\t\tret = 0\n\t\tx = a\n\t\twhile x > 0:\n\t\t\tret += bit[x]\n\t\t\tx -= x & -1 * x\n\t\treturn ret\n\n\tdef add(self, l, r, w):\n\t\tl = l + (1 - self.mode)\n\t\tr = r + (1 - self.mode)\n\t\tself.bitadd(l, -1 * w * l, self.bit1)\n\t\tself.bitadd(r, w * r, self.bit1)\n\t\tself.bitadd(l, w, self.bit2)\n\t\tself.bitadd(r, -1 * w, self.bit2)\n\n\tdef sum(self, l, r):\n\t\tl = l + (1 - self.mode)\n\t\tr = r + (1 - self.mode)\n\t\tret = self.bitsum(r, self.bit1) + r * self.bitsum(r, self.bit2)\n\t\tret -= self.bitsum(l, self.bit1) + l * self.bitsum(l, self.bit2)\n\t\treturn ret\n\n\tdef get(self, ind):\n\t\treturn self.sum(ind, ind + 1)\nfor loop in range(1):\n\t(n, k) = map(int, input().split())\n\tL = sorted(list(map(int, input().split())))\n\tB = RangeBIT(400000, 0)\n\tB.add(0, 1, 1)\n\tans = float('inf')\n\tind = 0\n\tfor i in range(n):\n\t\tif B.sum(0, 300000) >= k:\n\t\t\tr = 300000\n\t\t\tl = 0\n\t\t\twhile r - l != 1:\n\t\t\t\tm = (l + r) // 2\n\t\t\t\tif B.sum(0, m + 1) >= k:\n\t\t\t\t\tr = m\n\t\t\t\telse:\n\t\t\t\t\tl = m\n\t\t\tans = min(ans, r)\n\t\twhile B.get(ind) == 0:\n\t\t\tind += 1\n\t\tB.add(ind, ind + 1, -1)\n\t\tx = (L[-1] - 1) // 2\n\t\ty = L[-1] - 1 - x\n\t\tB.add(ind + 2, ind + 2 + x, 1)\n\t\tB.add(ind + 2, ind + 2 + y, 1)\n\t\tdel L[-1]\n\tif B.sum(0, 300000) >= k:\n\t\tr = 300000\n\t\tl = 0\n\t\twhile r - l != 1:\n\t\t\tm = (l + r) // 2\n\t\t\tif B.sum(0, m + 1) >= k:\n\t\t\t\tr = m\n\t\t\telse:\n\t\t\t\tl = m\n\t\tans = min(ans, r)\n\tif ans == float('inf'):\n\t\tprint(-1)\n\telse:\n\t\tprint(ans)\n", "def check(d, k):\n\t(pos, cur, P) = (0, 1, 0)\n\ttotal = 1\n\tfor (i, x) in enumerate(L):\n\t\twhile cur == 0:\n\t\t\tpos += 1\n\t\t\tP += add[pos]\n\t\t\tif pos + 1 >= d:\n\t\t\t\tbreak\n\t\t\tcur += P\n\t\tcur -= 1\n\t\tif pos + x // 2 + 1 <= d:\n\t\t\ttotal += x - 2\n\t\telse:\n\t\t\ttotal += (d - pos - 1) * 2 - 1\n\t\tif total >= k:\n\t\t\treturn True\n\treturn total >= k\n(n, k) = list(map(int, input().split()))\nL = list(map(int, input().split()))\nL = sorted(L, key=lambda x: -x)\nMAX = 2 * 10 ** 5\ncnt = [0] * MAX\nadd = [0] * MAX\ncnt[0] = 0\n(pos, cur, P) = (0, 1, 0)\ntotal = 1\nfor (i, x) in enumerate(L):\n\twhile cur == 0:\n\t\tpos += 1\n\t\tP += add[pos]\n\t\tcur += P\n\tcur -= 1\n\tnums = (x - 1) // 2\n\tadd[pos + 2] += 2\n\tadd[pos + 2 + nums] -= 2\n\tif x % 2 == 0:\n\t\tadd[pos + 2 + nums] += 1\n\t\tadd[pos + 3 + nums] -= 1\n\ttotal += x - 2\nif total < k:\n\tprint(-1)\nelse:\n\t(l, r) = (1, MAX)\n\twhile r - l > 1:\n\t\tmd = (l + r) // 2\n\t\tif check(md, k) == True:\n\t\t\tr = md\n\t\telse:\n\t\t\tl = md\n\tprint(r)\n"]

source: codeforces

raw_problem:
F. Power Sockets

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

// We decided to drop the legend about the power sockets but feel free to come up with your own :^)

Define a chain:

 a chain of length $$$1$$$ is a single vertex;

 a chain of length $$$x$$$ is a chain of length $$$x-1$$$ with a new vertex connected to the end of it with a single edge.

You are given $$$n$$$ chains of lengths $$$l_1, l_2, \dots, l_n$$$. You plan to build a tree using some of them.

 Each vertex of the tree is either white or black.

 The tree initially only has a white root vertex.

 All chains initially consist only of white vertices.

 You can take one of the chains and connect any of its vertices to any white vertex of the tree with an edge. The chain becomes part of the tree. Both endpoints of this edge become black.

 Each chain can be used no more than once.

 Some chains can be left unused.

The distance between two vertices of the tree is the number of edges on the shortest path between them.

If there is at least $$$k$$$ white vertices in the resulting tree, then the value of the tree is the distance between the root and the $$$k$$$-th closest white vertex.

What's the minimum value of the tree you can obtain? If there is no way to build a tree with at least $$$k$$$ white vertices, then print -1.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) — the number of chains and the minimum number of white vertices a tree should have to have a value.

The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$3 \le l_i \le 2 \cdot 10^5$$$) — the lengths of the chains.

Output

Print a single integer. If there is no way to build a tree with at least $$$k$$$ white vertices, then print -1. Otherwise, print the minimum value the tree can have.

Examples

Input

1 2
3

Output

2

Input

3 3
4 3 3

Output

3

Input

3 5
4 3 4

Output

4

Input

2 10
5 7

Output

-1

Note

You are allowed to not use all the chains, so it's optimal to only use chain of length $$$4$$$ in the second example.

question:
// We decided to drop the legend about the power sockets but feel free to come up with your own :^)
Define a chain:
 -  a chain of length $$$1$$$ is a single vertex; -  a chain of length $$$x$$$ is a chain of length $$$x-1$$$ with a new vertex connected to the end of it with a single edge. You are given $$$n$$$ chains of lengths $$$l_1, l_2, \dots, l_n$$$. You plan to build a tree using some of them.
 -  Each vertex of the tree is either white or black. -  The tree initially only has a white root vertex. -  All chains initially consist only of white vertices. -  You can take one of the chains and connect any of its vertices to any white vertex of the tree with an edge. The chain becomes part of the tree. Both endpoints of this edge become black. -  Each chain can be used no more than once. -  Some chains can be left unused. The distance between two vertices of the tree is the number of edges on the shortest path between them.
If there is at least $$$k$$$ white vertices in the resulting tree, then the value of the tree is the distance between the root and the $$$k$$$-th closest white vertex.
What's the minimum value of the tree you can obtain? If there is no way to build a tree with at least $$$k$$$ white vertices, then print -1.

Input
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) — the number of chains and the minimum number of white vertices a tree should have to have a value.
The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$3 \le l_i \le 2 \cdot 10^5$$$) — the lengths of the chains.

Output
Print a single integer. If there is no way to build a tree with at least $$$k$$$ white vertices, then print -1. Otherwise, print the minimum value the tree can have.

Examples
Input
1 2
3

Output
2

Input
3 3
4 3 3

Output
3

Input
3 5
4 3 4

Output
4

Input
2 10
5 7

Output
-1

Note
 ![image](1.png) You are allowed to not use all the chains, so it's optimal to only use chain of length $$$4$$$ in the second example.

tags: ['Sorting', 'Data structures', 'Greedy algorithms']

raw_tags: ['data structures', 'greedy', 'binary search']

data_split: test