A. Frames

problem_index: A

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
The images below illustrate statement tests.
The first test:
![image](images/cf_93_A/1.png)
In this test we can select folders 3 and 4 with out first selection, folders 5, 6, 7, 8 with our second selection and folder 9 with our third, last selection.
The second test:
![image](images/cf_93_A/2.png)
In this test we can first select all folders in the first row (2, 3, 4, 5), then — all other ones.

solutions: ["(n, m, a, b) = map(int, input().split())\na -= 1\n(x, y) = (a % m, b % m)\nd = b // m - a // m\nif b == n and y:\n\td += 1\n(u, v) = (x == 0, y == 0 or b == n)\nprint(1 if u and v or d <= v else 2 if x == y or u or v or (d == 1) else 3)\n", "import math\n(n, m, a, b) = map(int, input().split())\nif (a - 1) // m == (b - 1) // m:\n\tprint(1)\nelif (a - 1) % m == 0 and b % m == 0:\n\tprint(1)\nelif (a - 1) % m == 0 and b == n or m == 1:\n\tprint(1)\nelif (a - 1) % m == 0 or b % m == 0 or b == n:\n\tprint(2)\nelif abs((a - 1) // m - (b - 1) // m) == 1 or m == 2:\n\tprint(2)\nelif (a - 1) % m == b % m:\n\tprint(2)\nelse:\n\tprint(3)\n", "from sys import stdin, stdout\ninput = stdin.readline\n(n, m, a, b) = map(int, input().split(' '))\na -= 1\nb -= 1\nx = a // m\ny = b // m\nxx = a % m\nyy = b % m\nif x == y or (xx == 0 and yy == m - 1) or b - a + 1 == n or (xx == 0 and b == n - 1):\n\tprint(1)\nelif yy + 1 == xx or yy == m - 1 or x + 1 == y or (xx == 0) or (b == n - 1):\n\tprint(2)\nelse:\n\tprint(3)\n", "import sys\nsys.setrecursionlimit(10000000)\n\ndef solve():\n\t(n, m, a, b) = rv()\n\ta -= 1\n\tb -= 1\n\tif a // m == b // m or m == 1:\n\t\tprint(1)\n\t\treturn\n\tfirst = m - (a - a // m * m)\n\tlast = b - b // m * m + 1\n\tif b + 1 == n:\n\t\tlast = m\n\tif first == m and last == m:\n\t\tprint(1)\n\t\treturn\n\tif a // m + 1 == b // m or first + last == m:\n\t\tprint(2)\n\t\treturn\n\tif first == m or last == m:\n\t\tprint(2)\n\t\treturn\n\tprint(3)\n\ndef prt(l):\n\treturn print(' '.join(l))\n\ndef rv():\n\treturn map(int, input().split())\n\ndef rl(n):\n\treturn [list(map(int, input().split())) for _ in range(n)]\nif sys.hexversion == 50594544:\n\tsys.stdin = open('test.txt')\nsolve()\n", "(n, m, a, b) = map(int, input().split())\nans = 0\na -= 1\nb -= 1\nif a // m - b // m == 0:\n\tans = 1\nelif a % m == 0:\n\tif (b + 1) % m == 0 or b + 1 == n:\n\t\tans = 1\n\telse:\n\t\tans = 2\nelif a % m - b % m == 1:\n\tans = 2\nelif (b + 1) % m == 0 or b < (a // m + 2) * m or b + 1 == n or (b // m - a // m == 1):\n\tans = 2\nelse:\n\tans = 3\nprint(ans)\n", "import sys\nfrom array import array\n\ndef input():\n\treturn sys.stdin.buffer.readline().decode('utf-8')\n(n, m, a, b) = map(int, input().split())\n(a, b) = (a - 1, b - 1)\nif b + 1 == n:\n\tb = (b // m + 1) * m - 1\nif a // m == b // m:\n\tprint(1)\nelif a % m == 0 and b % m == m - 1:\n\tprint(1)\nelif b % m + 1 == a % m:\n\tprint(2)\nelif a // m + 1 == b // m:\n\tprint(2)\nelse:\n\tans = 1 + (a % m != 0) + (b % m != m - 1)\n\tprint(ans)\n", "import os\nimport sys\nimport math\nfrom io import BytesIO, IOBase\nfrom fractions import Fraction\nimport collections\nfrom itertools import permutations\nfrom collections import defaultdict\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, m, a, b) = map(int, input().split())\nc1 = a // m\nc2 = b // m\nif a % m == 0:\n\tc1 -= 1\nif b % m == 0:\n\tc2 -= 1\nif c1 == c2 or m == 1:\n\tprint(1)\nelse:\n\td = c2 - c1\n\tr = 3\n\tif a % m == 1:\n\t\tr -= 1\n\tif b % m == 0 or b == n:\n\t\tr -= 1\n\tif d == 1 and r > 2:\n\t\tr -= 1\n\tif r == 3 and (a % m == b % m + 1 or (a % m == 0 and b % m == m - 1)):\n\t\tr -= 1\n\tprint(r)\n", "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 list2d(a, b, c):\n\treturn [[c] * b for i in range(a)]\n\ndef list3d(a, b, c, d):\n\treturn [[[d] * c for j in range(b)] for i in range(a)]\n\ndef list4d(a, b, c, d, e):\n\treturn [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]\n\ndef ceil(x, y=1):\n\treturn int(-(-x // y))\n\ndef Yes():\n\tprint('Yes')\n\ndef No():\n\tprint('No')\n\ndef YES():\n\tprint('YES')\n\ndef NO():\n\tprint('NO')\nINF = 10 ** 18\nMOD = 10 ** 9 + 7\nRi = lambda : [int(x) for x in sys.stdin.readline().split()]\nri = lambda : sys.stdin.readline().strip()\n(n, m, a, b) = Ri()\na -= 1\nb -= 1\nr1 = a // m\nc1 = a % m\nans = 3\nr2 = b // m\nc2 = b % m\nif r2 - r1 == 1 or c1 == 0 or c2 == m - 1 or (b == n - 1) or (c1 - c2 == 1):\n\tans = 2\nif r2 - r1 == 0 or (c1 == 0 and (c2 == m - 1 or b == n - 1)):\n\tans = 1\nprint(ans)\n", "(n, m, a, b) = map(int, input().split())\n(r1, r2, c1, c2) = ((a - 1) // m, (b - 1) // m, (a - 1) % m, m - 1 if b == n else (b - 1) % m)\nif r1 == r2 or (c1 == 0 and c2 == m - 1):\n\tprint(1)\nelif r2 == r1 + 1 or c1 == 0 or c2 == m - 1 or (c1 == c2 + 1):\n\tprint(2)\nelse:\n\tprint(3)\n", "import math\nimport random\nimport heapq, bisect\nimport sys\nfrom collections import deque, defaultdict\nfrom fractions import Fraction\nimport sys\nimport threading\nfrom collections import defaultdict\nthreading.stack_size(10 ** 8)\nmod = 10 ** 9 + 7\nmod1 = 998244353\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nsys.setrecursionlimit(300000)\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\nclass TreeNode:\n\n\tdef __init__(self, k, v):\n\t\tself.key = k\n\t\tself.value = v\n\t\tself.left = None\n\t\tself.right = None\n\t\tself.parent = None\n\t\tself.height = 1\n\t\tself.num_left = 1\n\t\tself.num_total = 1\n\nclass AvlTree:\n\n\tdef __init__(self):\n\t\tself._tree = None\n\n\tdef add(self, k, v):\n\t\tif not self._tree:\n\t\t\tself._tree = TreeNode(k, v)\n\t\t\treturn\n\t\tnode = self._add(k, v)\n\t\tif node:\n\t\t\tself._rebalance(node)\n\n\tdef _add(self, k, v):\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif k < node.key:\n\t\t\t\tif node.left:\n\t\t\t\t\tnode = node.left\n\t\t\t\telse:\n\t\t\t\t\tnode.left = TreeNode(k, v)\n\t\t\t\t\tnode.left.parent = node\n\t\t\t\t\treturn node.left\n\t\t\telif node.key < k:\n\t\t\t\tif node.right:\n\t\t\t\t\tnode = node.right\n\t\t\t\telse:\n\t\t\t\t\tnode.right = TreeNode(k, v)\n\t\t\t\t\tnode.right.parent = node\n\t\t\t\t\treturn node.right\n\t\t\telse:\n\t\t\t\tnode.value = v\n\t\t\t\treturn\n\n\t@staticmethod\n\tdef get_height(x):\n\t\treturn x.height if x else 0\n\n\t@staticmethod\n\tdef get_num_total(x):\n\t\treturn x.num_total if x else 0\n\n\tdef _rebalance(self, node):\n\t\tn = node\n\t\twhile n:\n\t\t\tlh = self.get_height(n.left)\n\t\t\trh = self.get_height(n.right)\n\t\t\tn.height = max(lh, rh) + 1\n\t\t\tbalance_factor = lh - rh\n\t\t\tn.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)\n\t\t\tn.num_left = 1 + self.get_num_total(n.left)\n\t\t\tif balance_factor > 1:\n\t\t\t\tif self.get_height(n.left.left) < self.get_height(n.left.right):\n\t\t\t\t\tself._rotate_left(n.left)\n\t\t\t\tself._rotate_right(n)\n\t\t\telif balance_factor < -1:\n\t\t\t\tif self.get_height(n.right.right) < self.get_height(n.right.left):\n\t\t\t\t\tself._rotate_right(n.right)\n\t\t\t\tself._rotate_left(n)\n\t\t\telse:\n\t\t\t\tn = n.parent\n\n\tdef _remove_one(self, node):\n\t\treplacement = node.left or node.right\n\t\tif node.parent:\n\t\t\tif AvlTree._is_left(node):\n\t\t\t\tnode.parent.left = replacement\n\t\t\telse:\n\t\t\t\tnode.parent.right = replacement\n\t\t\treplacement.parent = node.parent\n\t\t\tnode.parent = None\n\t\telse:\n\t\t\tself._tree = replacement\n\t\t\treplacement.parent = None\n\t\tnode.left = None\n\t\tnode.right = None\n\t\tnode.parent = None\n\t\tself._rebalance(replacement)\n\n\tdef _remove_leaf(self, node):\n\t\tif node.parent:\n\t\t\tif AvlTree._is_left(node):\n\t\t\t\tnode.parent.left = None\n\t\t\telse:\n\t\t\t\tnode.parent.right = None\n\t\t\tself._rebalance(node.parent)\n\t\telse:\n\t\t\tself._tree = None\n\t\tnode.parent = None\n\t\tnode.left = None\n\t\tnode.right = None\n\n\tdef remove(self, k):\n\t\tnode = self._get_node(k)\n\t\tif not node:\n\t\t\treturn\n\t\tif AvlTree._is_leaf(node):\n\t\t\tself._remove_leaf(node)\n\t\t\treturn\n\t\tif node.left and node.right:\n\t\t\tnxt = AvlTree._get_next(node)\n\t\t\tnode.key = nxt.key\n\t\t\tnode.value = nxt.value\n\t\t\tif self._is_leaf(nxt):\n\t\t\t\tself._remove_leaf(nxt)\n\t\t\telse:\n\t\t\t\tself._remove_one(nxt)\n\t\t\tself._rebalance(node)\n\t\telse:\n\t\t\tself._remove_one(node)\n\n\tdef get(self, k):\n\t\tnode = self._get_node(k)\n\t\treturn node.value if node else -1\n\n\tdef _get_node(self, k):\n\t\tif not self._tree:\n\t\t\treturn None\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif k < node.key:\n\t\t\t\tnode = node.left\n\t\t\telif node.key < k:\n\t\t\t\tnode = node.right\n\t\t\telse:\n\t\t\t\treturn node\n\t\treturn None\n\n\tdef get_at(self, pos):\n\t\tx = pos + 1\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif x < node.num_left:\n\t\t\t\tnode = node.left\n\t\t\telif node.num_left < x:\n\t\t\t\tx -= node.num_left\n\t\t\t\tnode = node.right\n\t\t\telse:\n\t\t\t\treturn (node.key, node.value)\n\t\traise IndexError('Out of ranges')\n\n\t@staticmethod\n\tdef _is_left(node):\n\t\treturn node.parent.left and node.parent.left == node\n\n\t@staticmethod\n\tdef _is_leaf(node):\n\t\treturn node.left is None and node.right is None\n\n\tdef _rotate_right(self, node):\n\t\tif not node.parent:\n\t\t\tself._tree = node.left\n\t\t\tnode.left.parent = None\n\t\telif AvlTree._is_left(node):\n\t\t\tnode.parent.left = node.left\n\t\t\tnode.left.parent = node.parent\n\t\telse:\n\t\t\tnode.parent.right = node.left\n\t\t\tnode.left.parent = node.parent\n\t\tbk = node.left.right\n\t\tnode.left.right = node\n\t\tnode.parent = node.left\n\t\tnode.left = bk\n\t\tif bk:\n\t\t\tbk.parent = node\n\t\tnode.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n\t\tnode.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)\n\t\tnode.num_left = 1 + self.get_num_total(node.left)\n\n\tdef _rotate_left(self, node):\n\t\tif not node.parent:\n\t\t\tself._tree = node.right\n\t\t\tnode.right.parent = None\n\t\telif AvlTree._is_left(node):\n\t\t\tnode.parent.left = node.right\n\t\t\tnode.right.parent = node.parent\n\t\telse:\n\t\t\tnode.parent.right = node.right\n\t\t\tnode.right.parent = node.parent\n\t\tbk = node.right.left\n\t\tnode.right.left = node\n\t\tnode.parent = node.right\n\t\tnode.right = bk\n\t\tif bk:\n\t\t\tbk.parent = node\n\t\tnode.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n\t\tnode.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)\n\t\tnode.num_left = 1 + self.get_num_total(node.left)\n\n\t@staticmethod\n\tdef _get_next(node):\n\t\tif not node.right:\n\t\t\treturn node.parent\n\t\tn = node.right\n\t\twhile n.left:\n\t\t\tn = n.left\n\t\treturn n\n\nclass SegmentTree1:\n\n\tdef __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass SegmentTree:\n\n\tdef __init__(self, data, default=0, func=lambda a, b: a + b):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass Factorial:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorials = [1, 1]\n\t\tself.invModulos = [0, 1]\n\t\tself.invFactorial_ = [1, 1]\n\n\tdef calc(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.factorials):\n\t\t\treturn self.factorials[n]\n\t\tnextArr = [0] * (n + 1 - len(self.factorials))\n\t\tinitialI = len(self.factorials)\n\t\tprev = self.factorials[-1]\n\t\tm = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * i % m\n\t\tself.factorials += nextArr\n\t\treturn self.factorials[n]\n\n\tdef inv(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n^(-1)')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tp = self.MOD\n\t\tpi = n % p\n\t\tif pi < len(self.invModulos):\n\t\t\treturn self.invModulos[pi]\n\t\tnextArr = [0] * (n + 1 - len(self.invModulos))\n\t\tinitialI = len(self.invModulos)\n\t\tfor i in range(initialI, min(p, n + 1)):\n\t\t\tnext = -self.invModulos[p % i] * (p // i) % p\n\t\t\tself.invModulos.append(next)\n\t\treturn self.invModulos[pi]\n\n\tdef invFactorial(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate (n^(-1))!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.invFactorial_):\n\t\t\treturn self.invFactorial_[n]\n\t\tself.inv(n)\n\t\tnextArr = [0] * (n + 1 - len(self.invFactorial_))\n\t\tinitialI = len(self.invFactorial_)\n\t\tprev = self.invFactorial_[-1]\n\t\tp = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p\n\t\tself.invFactorial_ += nextArr\n\t\treturn self.invFactorial_[n]\n\nclass Combination:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorial = Factorial(MOD)\n\n\tdef ncr(self, n, k):\n\t\tif k < 0 or n < k:\n\t\t\treturn 0\n\t\tk = min(k, n - k)\n\t\tf = self.factorial\n\t\treturn f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD\n\ndef powm(a, n, m):\n\tif a == 1 or n == 0:\n\t\treturn 1\n\tif n % 2 == 0:\n\t\ts = powm(a, n // 2, m)\n\t\treturn s * s % m\n\telse:\n\t\treturn a * powm(a, n - 1, m) % m\n\ndef sort_list(list1, list2):\n\tzipped_pairs = zip(list2, list1)\n\tz = [x for (_, x) in sorted(zipped_pairs)]\n\treturn z\n\ndef product(l):\n\tpor = 1\n\tfor i in range(len(l)):\n\t\tpor *= l[i]\n\treturn por\n\ndef binarySearchCount(arr, n, key):\n\tleft = 0\n\tright = n - 1\n\tcount = 0\n\twhile left <= right:\n\t\tmid = int((right + left) / 2)\n\t\tif arr[mid] < key:\n\t\t\tcount = mid + 1\n\t\t\tleft = mid + 1\n\t\telse:\n\t\t\tright = mid - 1\n\treturn count\n\ndef countdig(n):\n\tc = 0\n\twhile n > 0:\n\t\tn //= 10\n\t\tc += 1\n\treturn c\n\ndef binary(x, length):\n\ty = bin(x)[2:]\n\treturn y if len(y) >= length else '0' * (length - len(y)) + y\n\ndef countGreater(arr, n, k):\n\tl = 0\n\tr = n - 1\n\tleftGreater = n\n\twhile l <= r:\n\t\tm = int(l + (r - l) / 2)\n\t\tif arr[m] >= k:\n\t\t\tleftGreater = m\n\t\t\tr = m - 1\n\t\telse:\n\t\t\tl = m + 1\n\treturn n - leftGreater\n(n, m, a, b) = map(int, input().split())\nans = 3\nif a % m == 1:\n\tans -= 1\nif b % m == 0 or b == n:\n\tans -= 1\nif m == 1:\n\tprint(1)\n\tsys.exit(0)\nelif (a - 1) // m == (b - 1) // m:\n\tprint(1)\n\tsys.exit(0)\nelif (a % m - b % m) % m == 1:\n\tprint(min(2, ans, (b - 1) // m - (a - 1) // m + 1))\n\tsys.exit(0)\nprint(min(ans, (b - 1) // m - (a - 1) // m + 1))\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nimport math\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')\nimport math\nfor _ in range(1):\n\t(n, m, a, b) = map(int, input().split())\n\tr1 = (a - 1) // m\n\tr2 = (b - 1) // m\n\tc1 = (a - 1) % m + 1\n\tc2 = (b - 1) % m + 1\n\tif r1 == r2:\n\t\tprint('1')\n\telif c1 == 1 and (c2 == m or b == n):\n\t\tprint('1')\n\telif c1 == 1 or (c2 == m or b == n):\n\t\tprint('2')\n\telif r2 - r1 == 1:\n\t\tprint('2')\n\telif c1 == c2 + 1:\n\t\tprint('2')\n\telse:\n\t\tprint('3')\n", "def solve(n, m, a, b):\n\tif (a - 1) % m == 0 and (b % m == 0 or b == n) or b - a + 1 == n or (a - 1) // m == (b - 1) // m:\n\t\treturn 1\n\telif a % m == 1 or b == n or b % m == 0 or (b % m == (a % m - 1) % m) or ((b - 1) // m - (a - 1) // m == 1):\n\t\treturn 2\n\telse:\n\t\treturn 3\nans = solve(*map(int, input().split()))\nprint(ans)\n", "readints = lambda : map(int, input().strip('\\n').split())\n(n, m, a, b) = readints()\na -= 1\nb -= 1\nra = a // m\nrb = b // m\nia = a % m\nib = b % m\nif ra == rb or (ia == 0 and b == n - 1) or (ia == 0 and ib == m - 1):\n\tprint(1)\nelif ia == 0 and ib < m - 1 and (b != n - 1) or (ia > 0 and (ib == m - 1 or b == n - 1)) or ra + 1 == rb or (ib + 1 == ia):\n\tprint(2)\nelse:\n\tprint(3)\n", "from math import ceil\n(n, c, st, end) = [int(i) for i in input().split()]\nreme = end % c\nrems = st % c\ndive = ceil(end / c)\ndivs = ceil(st / c)\nif rems == 0:\n\trems = c\nif reme == 0 and rems == 1 or divs == dive or end - st + 1 == n or (rems == 1 and end == n):\n\tprint(str(1))\nelif reme == rems - 1 or dive - divs < 2 or (reme == 0 or rems == 1) or (end == n):\n\tprint(str(2))\nelse:\n\tprint(str(3))\n"]

source: codeforces

raw_problem:
A. Frames

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Throughout Igor K.'s life he has had many situations worthy of attention. We remember the story with the virus, the story of his mathematical career and of course, his famous programming achievements. However, one does not always adopt new hobbies, one can quit something as well.

This time Igor K. got disappointed in one of his hobbies: editing and voicing videos. Moreover, he got disappointed in it so much, that he decided to destroy his secret archive for good.

Igor K. use Pindows XR operation system which represents files and folders by small icons. At that, m icons can fit in a horizontal row in any window.

Igor K.'s computer contains n folders in the D: disk's root catalog. The folders are numbered from 1 to n in the order from the left to the right and from top to bottom (see the images). At that the folders with secret videos have numbers from a to b inclusive. Igor K. wants to delete them forever, at that making as few frame selections as possible, and then pressing Shift+Delete exactly once. What is the minimum number of times Igor K. will have to select the folder in order to select folders from a to b and only them? Let us note that if some selected folder is selected repeatedly, then it is deselected. Each selection possesses the shape of some rectangle with sides parallel to the screen's borders.

Input

The only line contains four integers n, m, a, b (1 ≤ n, m ≤ 109, 1 ≤ a ≤ b ≤ n). They are the number of folders in Igor K.'s computer, the width of a window and the numbers of the first and the last folders that need to be deleted.

Output

Print a single number: the least possible number of times Igor K. will have to select the folders using frames to select only the folders with numbers from a to b.

Examples

Input

11 4 3 9

Output

3

Input

20 5 2 20

Output

2

Note

The images below illustrate statement tests.

The first test:

In this test we can select folders 3 and 4 with out first selection, folders 5, 6, 7, 8 with our second selection and folder 9 with our third, last selection.

The second test:

In this test we can first select all folders in the first row (2, 3, 4, 5), then — all other ones.

question:
Throughout Igor K.'s life he has had many situations worthy of attention. We remember the story with the virus, the story of his mathematical career and of course, his famous programming achievements. However, one does not always adopt new hobbies, one can quit something as well.
This time Igor K. got disappointed in one of his hobbies: editing and voicing videos. Moreover, he got disappointed in it so much, that he decided to destroy his secret archive for good.
Igor K. use Pindows XR operation system which represents files and folders by small icons. At that, m icons can fit in a horizontal row in any window.
Igor K.'s computer contains n folders in the D: disk's root catalog. The folders are numbered from 1 to n in the order from the left to the right and from top to bottom (see the images). At that the folders with secret videos have numbers from a to b inclusive. Igor K. wants to delete them forever, at that making as few frame selections as possible, and then pressing Shift+Delete exactly once. What is the minimum number of times Igor K. will have to select the folder in order to select folders from a to b and only them? Let us note that if some selected folder is selected repeatedly, then it is deselected. Each selection possesses the shape of some rectangle with sides parallel to the screen's borders.

Input
The only line contains four integers n, m, a, b (1 ≤ n, m ≤ 10^{9}, 1 ≤ a ≤ b ≤ n). They are the number of folders in Igor K.'s computer, the width of a window and the numbers of the first and the last folders that need to be deleted.

Output
Print a single number: the least possible number of times Igor K. will have to select the folders using frames to select only the folders with numbers from a to b.

Examples
Input
11 4 3 9

Output
3

Input
20 5 2 20

Output
2

Note
The images below illustrate statement tests.
The first test:
![image](1.png)
In this test we can select folders 3 and 4 with out first selection, folders 5, 6, 7, 8 with our second selection and folder 9 with our third, last selection.
The second test:
![image](2.png)
In this test we can first select all folders in the first row (2, 3, 4, 5), then — all other ones.

image_tags: Others Others

data_split: test


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

raw_problem:
Problem D
  Making Perimeter of the Convex Hull Shortest

  The convex hull of a set of three or more planar points is, when not all of them are on one line, the convex polygon with the smallest area that has all the points of the set on its boundary or in its inside. Your task is, given positions of the points of a set, to find how much shorter the perimeter of the convex hull can be made by excluding two points from the set.

  The figures below correspond to the three cases given as Sample Input 1 to 3. Encircled points are excluded to make the shortest convex hull depicted as thick dashed lines.

    Sample Input 1
    Sample Input 2
    Sample Input 3

Input

  The input consists of a single test case in the following format.

$n$
$x_1$ $y_1$
...
$x_n$ $y_n$

  Here, $n$ is the number of points in the set satisfying $5 \leq n \leq 10^5$. For each $i$, ($x_i, y_i$) gives the coordinates of the position of the $i$-th point in the set. $x_i$ and $y_i$ are integers between $-10^6$ and $10^6$, inclusive. All the points in the set are distinct, that is, $x_j \ne x_k$ or $y_j \ne y_k$ holds when $j \ne k$. It is guaranteed that no single line goes through $n - 2$ or more points in the set.

Output

  Output the difference of the perimeter of the convex hull of the original set and the shortest of the perimeters of the convex hulls of the subsets with two points excluded from the original set. The output should not have an error greater than $10^{-4}$.

Sample Input 1

10
-53 62
-19 58
-11 11
-9 -22
45 -7
37 -39
47 -58
-2 41
-37 10
13 42

Sample Output 1

72.96316928

Sample Input 2

10
-53 62
-19 58
-11 11
-9 -22
45 -7
43 -47
47 -58
-2 41
-37 10
13 42

Sample Output 2

62.62947992

Sample Input 3

10
-53 62
-35 47
-11 11
-9 -22
45 -7
43 -47
47 -58
-2 41
-37 10
13 42

Sample Output 3

61.58166534

source: aizu

question:
Problem D
  Making Perimeter of the Convex Hull Shortest

  The convex hull of a set of three or more planar points is, when not all of them are on one line, the convex polygon with the smallest area that has all the points of the set on its boundary or in its inside. Your task is, given positions of the points of a set, to find how much shorter the perimeter of the convex hull can be made by excluding two points from the set.

  The figures below correspond to the three cases given as Sample Input 1 to 3. Encircled points are excluded to make the shortest convex hull depicted as thick dashed lines.

![image](1.png)
![image](2.png)
![image](3.png)

Sample Input 1
Sample Input 2
Sample Input 3

Input

  The input consists of a single test case in the following format.

$n$
$x_1$ $y_1$
...
$x_n$ $y_n$

  Here, $n$ is the number of points in the set satisfying $5 \leq n \leq 10^5$. For each $i$, ($x_i, y_i$) gives the coordinates of the position of the $i$-th point in the set. $x_i$ and $y_i$ are integers between $-10^6$ and $10^6$, inclusive. All the points in the set are distinct, that is, $x_j \ne x_k$ or $y_j \ne y_k$ holds when $j \ne k$. It is guaranteed that no single line goes through $n - 2$ or more points in the set.

Output

  Output the difference of the perimeter of the convex hull of the original set and the shortest of the perimeters of the convex hulls of the subsets with two points excluded from the original set. The output should not have an error greater than $10^{-4}$.

Sample Input 1

10
-53 62
-19 58
-11 11
-9 -22
45 -7
37 -39
47 -58
-2 41
-37 10
13 42

Sample Output 1

72.96316928

Sample Input 2

10
-53 62
-19 58
-11 11
-9 -22
45 -7
43 -47
47 -58
-2 41
-37 10
13 42

Sample Output 2

62.62947992

Sample Input 3

10
-53 62
-35 47
-11 11
-9 -22
45 -7
43 -47
47 -58
-2 41
-37 10
13 42

Sample Output 3

61.58166534

image_tags:
2D Geometry
2D Geometry
2D Geometry

data_split: test


solutions: ["class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) <= 2:\n\t\t\treturn False\n\t\telse:\n\t\t\tif A[1] < A[0]:\n\t\t\t\treturn False\n\t\t\tis_up = True\n\t\t\tcurr = A[0]\n\t\t\tfor n in A[1:]:\n\t\t\t\tif n == curr:\n\t\t\t\t\treturn False\n\t\t\t\tif n < curr:\n\t\t\t\t\tis_up = False\n\t\t\t\t\tcurr = n\n\t\t\t\tif n > curr:\n\t\t\t\t\tif is_up:\n\t\t\t\t\t\tcurr = n\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn False\n\t\t\treturn not is_up\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tisIncreasing = True\n\t\ti = 1\n\t\tn = len(A)\n\t\tif n < 3:\n\t\t\treturn False\n\t\tif A[1] <= A[0]:\n\t\t\treturn False\n\t\twhile i < n:\n\t\t\tif isIncreasing and A[i - 1] < A[i]:\n\t\t\t\ti += 1\n\t\t\t\tcontinue\n\t\t\telif A[i] < A[i - 1]:\n\t\t\t\tisIncreasing = False\n\t\t\t\ti += 1\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\treturn False\n\t\tif A[-1] >= A[-2]:\n\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tarr = A\n\t\tif len(arr) < 3:\n\t\t\treturn False\n\t\tif arr[0] > arr[1]:\n\t\t\treturn False\n\t\tif arr[-1] > arr[-2]:\n\t\t\treturn False\n\t\tpeek = None\n\t\tfor i in range(1, len(arr) - 1):\n\t\t\tif arr[i] > arr[i + 1]:\n\t\t\t\tpeek = i\n\t\t\tif peek and arr[i] < arr[i + 1]:\n\t\t\t\treturn False\n\t\t\tif arr[i] == arr[i + 1] or arr[i] == arr[i - 1]:\n\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tdec = 0\n\t\tn = len(A)\n\t\tif n < 3:\n\t\t\treturn False\n\t\telse:\n\t\t\tfor i in range(n):\n\t\t\t\tif i != 0 and A[i] == A[i - 1]:\n\t\t\t\t\treturn False\n\t\t\t\telif i == 0 and A[i] > A[i + 1]:\n\t\t\t\t\treturn False\n\t\t\t\telif dec == 1 and A[i] > A[i - 1]:\n\t\t\t\t\treturn False\n\t\t\t\telif i != 0 and dec == 0 and (A[i] < A[i - 1]):\n\t\t\t\t\tdec = 1\n\t\t\t\telif i == n - 1 and dec == 0:\n\t\t\t\t\treturn False\n\t\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tN = len(A)\n\t\tif N < 3:\n\t\t\treturn False\n\t\ti = 0\n\t\twhile i < N - 1:\n\t\t\tif A[i] < A[i + 1]:\n\t\t\t\ti += 1\n\t\t\t\tprint(i)\n\t\t\telse:\n\t\t\t\tbreak\n\t\tif i == 0 or i == N - 1:\n\t\t\tprint('***')\n\t\t\treturn False\n\t\twhile i < N - 1:\n\t\t\tif A[i] > A[i + 1]:\n\t\t\t\ti += 1\n\t\t\t\tprint(i)\n\t\t\telse:\n\t\t\t\tbreak\n\t\tif i == N - 1:\n\t\t\treturn True\n\t\telse:\n\t\t\tprint('1111')\n\t\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tlength = len(A)\n\t\tif length < 3:\n\t\t\treturn False\n\t\tprev = A[0]\n\t\tpeak = -1\n\t\tfor i in range(1, length):\n\t\t\tprint(A[i])\n\t\t\tif A[i] > prev:\n\t\t\t\tif peak != -1:\n\t\t\t\t\treturn False\n\t\t\telif A[i] == prev:\n\t\t\t\treturn False\n\t\t\telse:\n\t\t\t\tif i == 1:\n\t\t\t\t\treturn False\n\t\t\t\tpeak = A[i]\n\t\t\tprev = A[i]\n\t\tprint(peak)\n\t\treturn True if peak != -1 else False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tstart = 0\n\t\tfinish = len(A)\n\t\tprint(len(A))\n\t\tfor i in range(0, len(A) - 1):\n\t\t\tprint(('i', i))\n\t\t\tif A[i] == A[i + 1]:\n\t\t\t\treturn False\n\t\t\telif A[i] > A[i + 1]:\n\t\t\t\tstart = i\n\t\t\t\tprint(('else1', start))\n\t\t\t\tbreak\n\t\tfor j in range(0, len(A) - 1):\n\t\t\tprint(('j', j))\n\t\t\tif A[len(A) - 1 - j] == A[len(A) - 2 - j]:\n\t\t\t\treturn False\n\t\t\telif A[len(A) - 1 - j] > A[len(A) - 2 - j]:\n\t\t\t\tprint(('break2', len(A) - 1 - j, len(A) - 2 - j, A[len(A) - 1 - j], A[len(A) - 2 - j]))\n\t\t\t\tfinish = len(A) - 1 - j\n\t\t\t\tbreak\n\t\tprint(('s, f', start, finish))\n\t\treturn start == finish and start > 0 and (finish < len(A))\n", "class Solution:\n\n\tdef __init__(self):\n\t\tself.f = True\n\n\tdef impl(self, arr, i, incr):\n\t\tself.f = incr\n\t\tif i + 1 >= len(arr):\n\t\t\treturn True\n\t\tif arr[i + 1] > arr[i] and (not incr):\n\t\t\treturn False\n\t\telif arr[i + 1] < arr[i] and incr:\n\t\t\tincr = False\n\t\telif arr[i + 1] == arr[i]:\n\t\t\treturn False\n\t\treturn self.impl(arr, i + 1, incr)\n\n\tdef validMountainArray(self, A) -> bool:\n\t\tif A == None or len(A) <= 2:\n\t\t\treturn False\n\t\tif A[1] < A[0]:\n\t\t\treturn False\n\t\tself.f = True\n\t\tresult = self.impl(A, 0, True)\n\t\tif self.f:\n\t\t\treturn False\n\t\treturn result\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif not A or len(A) < 3:\n\t\t\treturn False\n\t\t(l, r) = (0, len(A) - 1)\n\t\twhile l < r:\n\t\t\tif A[l] < A[l + 1] and A[r - 1] > A[r]:\n\t\t\t\tl += 1\n\t\t\t\tr -= 1\n\t\t\telif A[l] < A[l + 1]:\n\t\t\t\tl += 1\n\t\t\telif A[r - 1] > A[r]:\n\t\t\t\tr -= 1\n\t\t\telse:\n\t\t\t\treturn False\n\t\t\tprint(l, r)\n\t\tif l == r and l != 0 and (r != len(A) - 1):\n\t\t\treturn True\n\t\telse:\n\t\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\ti = 1\n\t\tN = len(A)\n\t\tif N < 3:\n\t\t\treturn False\n\t\twhile i < N and A[i] > A[i - 1]:\n\t\t\ti += 1\n\t\tif i == 1 or i == N:\n\t\t\treturn False\n\t\twhile i < N and A[i] < A[i - 1]:\n\t\t\ti += 1\n\t\treturn i == N\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) <= 2:\n\t\t\treturn False\n\t\telse:\n\t\t\tt = 0\n\t\t\t(c1, c2) = (0, 0)\n\t\t\tfor i in range(1, len(A) - 1):\n\t\t\t\tif A[i] == A[i + 1]:\n\t\t\t\t\treturn False\n\t\t\t\t\tbreak\n\t\t\t\telif A[i - 1] < A[i] < A[i + 1] or A[i - 1] > A[i] > A[i + 1] or A[i - 1] < A[i] > A[i + 1]:\n\t\t\t\t\tt += 1\n\t\t\t\t\tif A[i - 1] < A[i] < A[i + 1]:\n\t\t\t\t\t\tc1 += 1\n\t\t\t\t\tif A[i - 1] > A[i] > A[i + 1]:\n\t\t\t\t\t\tc2 += 1\n\t\t\tif t == len(A) - 2 and c1 < len(A) - 2 and (c2 < len(A) - 2):\n\t\t\t\treturn True\n\t\t\telse:\n\t\t\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tnprev = A[0]\n\t\tfor i in range(1, len(A)):\n\t\t\tif A[i] <= nprev:\n\t\t\t\tnprev = A[i - 1]\n\t\t\t\tstart = i\n\t\t\t\tbreak\n\t\t\tnprev = A[i]\n\t\t\tif i == len(A) - 1:\n\t\t\t\treturn False\n\t\tfor i in range(start, len(A)):\n\t\t\tif A[i] >= nprev:\n\t\t\t\treturn False\n\t\t\tnprev = A[i]\n\t\t\tif start == 1 and i == len(A) - 1:\n\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tmaxIndex = A.index(max(A))\n\t\tif maxIndex == len(A) - 1 or maxIndex == 0:\n\t\t\treturn False\n\t\tfor i in range(maxIndex):\n\t\t\tif A[i] >= A[i + 1]:\n\t\t\t\treturn False\n\t\tfor i in range(maxIndex, len(A) - 1):\n\t\t\tif A[i] <= A[i + 1]:\n\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tincreasing = True\n\t\tprev = -1\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tfor (idx, i) in enumerate(A):\n\t\t\tprint(prev, i, increasing)\n\t\t\tif i == prev:\n\t\t\t\treturn False\n\t\t\tif increasing:\n\t\t\t\tif i < prev:\n\t\t\t\t\tincreasing = False\n\t\t\t\t\tif idx == 1:\n\t\t\t\t\t\treturn False\n\t\t\telif i > prev:\n\t\t\t\treturn False\n\t\t\tprev = i\n\t\tif increasing == True:\n\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, arr: List[int]) -> bool:\n\t\ti = 0\n\t\tl = len(arr)\n\t\twhile i + 1 < l and arr[i] < arr[i + 1]:\n\t\t\ti += 1\n\t\tif i == 0 or i == l - 1:\n\t\t\treturn False\n\t\twhile i + 1 < l and arr[i] > arr[i + 1]:\n\t\t\ti += 1\n\t\treturn i == l - 1\n", "class Solution(object):\n\n\tdef validMountainArray(self, A):\n\t\tN = len(A)\n\t\ti = 0\n\t\twhile i + 1 < N and A[i] < A[i + 1]:\n\t\t\ti += 1\n\t\tif i == 0 or i == N - 1:\n\t\t\treturn False\n\t\twhile i + 1 < N and A[i] > A[i + 1]:\n\t\t\ti += 1\n\t\treturn i == N - 1\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) <= 2:\n\t\t\treturn False\n\t\ti = 0\n\t\tN = len(A)\n\t\twhile i < N and i + 1 < N and (A[i] < A[i + 1]):\n\t\t\ti += 1\n\t\tif i == 0 or i == N - 1:\n\t\t\treturn False\n\t\twhile i < N and i + 1 < N and (A[i] > A[i + 1]):\n\t\t\ti += 1\n\t\tif i == N - 1:\n\t\t\treturn True\n\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tm = (0, 0)\n\t\tfor i in range(0, len(A)):\n\t\t\tif A[i] > m[1]:\n\t\t\t\tm = (i, A[i])\n\t\tif m[0] == 0 or m[0] == len(A) - 1:\n\t\t\treturn False\n\t\tfor i in range(0, m[0] - 1):\n\t\t\tif A[i] >= A[i + 1]:\n\t\t\t\treturn False\n\t\tfor i in range(m[0], len(A) - 1):\n\t\t\tif A[i] <= A[i + 1]:\n\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef walkUp(self, A: List[int]) -> int:\n\t\tfor (i, step) in enumerate(A[:-1]):\n\t\t\tif A[i] >= A[i + 1]:\n\t\t\t\treturn i\n\t\treturn len(A)\n\n\tdef walkDown(self, A: List[int], top: int) -> bool:\n\t\tfor (i, step) in enumerate(A[top:-1], start=top):\n\t\t\tif A[i] <= A[i + 1]:\n\t\t\t\treturn False\n\t\treturn True\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\ttop = self.walkUp(A)\n\t\tif top == 0 or top == len(A):\n\t\t\treturn False\n\t\treturn self.walkDown(A, top)\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tswitch = 0\n\t\tif A[0] > A[1]:\n\t\t\treturn False\n\t\tfor i in range(2, len(A)):\n\t\t\tif A[i] == A[i - 1]:\n\t\t\t\treturn False\n\t\t\tif switch == 0 and A[i] < A[i - 1]:\n\t\t\t\tswitch = 1\n\t\t\telif switch == 1 and A[i] > A[i - 1]:\n\t\t\t\treturn False\n\t\tif switch == 0:\n\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tN = len(A) - 1\n\t\treached = False\n\t\tfor i in range(N):\n\t\t\tif A[i] == A[i + 1]:\n\t\t\t\treturn False\n\t\t\tif not reached:\n\t\t\t\tif A[i] > A[i + 1]:\n\t\t\t\t\tif i == 0:\n\t\t\t\t\t\treturn False\n\t\t\t\t\treached = True\n\t\t\telif A[i] < A[i + 1]:\n\t\t\t\treturn False\n\t\treturn reached\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) >= 3:\n\t\t\tpeak = max(A)\n\t\t\tif A.count(peak) == 1:\n\t\t\t\tpeakInd = A.index(peak)\n\t\t\t\tincArr = A[:peakInd]\n\t\t\t\tdecArr = A[peakInd + 1:]\n\t\t\t\tif len(incArr) > 0 and len(decArr) > 0:\n\t\t\t\t\tfor i in range(1, len(incArr)):\n\t\t\t\t\t\tif incArr[i] <= incArr[i - 1]:\n\t\t\t\t\t\t\treturn False\n\t\t\t\t\tfor d in range(0, len(decArr) - 1):\n\t\t\t\t\t\tif decArr[d] <= decArr[d + 1]:\n\t\t\t\t\t\t\treturn False\n\t\t\t\t\treturn True\n\t\t\t\telse:\n\t\t\t\t\treturn False\n\t\t\telse:\n\t\t\t\treturn False\n\t\telse:\n\t\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tstrict_inc = False\n\t\tstrict_dec = False\n\t\tif len(A) > 2:\n\t\t\tfor i in range(1, len(A)):\n\t\t\t\tif A[i] > A[i - 1]:\n\t\t\t\t\tif strict_dec:\n\t\t\t\t\t\treturn False\n\t\t\t\t\tstrict_inc = True\n\t\t\t\telif A[i] < A[i - 1]:\n\t\t\t\t\tstrict_dec = True\n\t\t\t\telse:\n\t\t\t\t\treturn False\n\t\t\tif strict_inc and strict_dec:\n\t\t\t\treturn True\n\t\t\telse:\n\t\t\t\treturn False\n\t\telse:\n\t\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) in [0, 1, 2]:\n\t\t\treturn False\n\t\tmax_ele = max(A)\n\t\tif A.count(max_ele) > 1:\n\t\t\treturn False\n\t\tindex = A.index(max_ele)\n\t\tif index == len(A) - 1 or index == 0:\n\t\t\treturn False\n\t\tfor i in range(0, index):\n\t\t\tprint(('values', A[i], A[i + 1]))\n\t\t\tprint(('index', i, i + 1))\n\t\t\tif not A[i] < A[i + 1]:\n\t\t\t\tprint('trig1')\n\t\t\t\treturn False\n\t\tfor i in range(len(A) - 1, index + 1, -1):\n\t\t\tprint('hi')\n\t\t\tif not A[i] < A[i - 1]:\n\t\t\t\tprint('trig2')\n\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\t(i, j) = (0, len(A) - 1)\n\t\twhile i < j:\n\t\t\tif A[i] < A[i + 1]:\n\t\t\t\ti += 1\n\t\t\tif A[j] < A[j - 1]:\n\t\t\t\tj -= 1\n\t\t\telif i + 1 >= len(A) or A[i] >= A[i + 1]:\n\t\t\t\tbreak\n\t\treturn i == j and 0 < i < len(A) - 1\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tdiffs = [A[i + 1] - A[i] for i in range(len(A) - 1)]\n\t\tif 0 in diffs or diffs[0] < 0:\n\t\t\treturn False\n\t\tpeak = False\n\t\tfor i in range(len(diffs) - 1):\n\t\t\tif diffs[i + 1] / abs(diffs[i + 1]) != diffs[i] / abs(diffs[i]):\n\t\t\t\tif peak == False:\n\t\t\t\t\tpeak = True\n\t\t\t\telse:\n\t\t\t\t\treturn False\n\t\treturn peak\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tfor i in range(len(A) - 1):\n\t\t\tif A[i] >= A[i + 1]:\n\t\t\t\tbreak\n\t\tfor j in range(-1, -len(A), -1):\n\t\t\tif A[j] >= A[j - 1]:\n\t\t\t\tbreak\n\t\treturn i == len(A) + j\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tn = len(A)\n\t\tif n < 3:\n\t\t\treturn False\n\t\tchanges = 0\n\t\tis_increasing = False\n\t\tis_decreasing = False\n\t\tfor i in range(0, n - 1):\n\t\t\tif changes == 0:\n\t\t\t\tif A[i] > A[i + 1]:\n\t\t\t\t\tchanges += 1\n\t\t\t\t\tis_decreasing = True\n\t\t\t\telif A[i] == A[i + 1]:\n\t\t\t\t\tchanges += 1\n\t\t\t\telse:\n\t\t\t\t\tis_increasing = True\n\t\t\telif changes == 1:\n\t\t\t\tif A[i] <= A[i + 1]:\n\t\t\t\t\tchanges += 1\n\t\t\t\telse:\n\t\t\t\t\tis_decreasing = True\n\t\t\telse:\n\t\t\t\treturn False\n\t\treturn changes < 2 and is_decreasing and is_increasing\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tarr = A\n\t\ti = 1\n\t\twhile i < len(arr):\n\t\t\tif arr[i - 1] < arr[i]:\n\t\t\t\ti += 1\n\t\t\telse:\n\t\t\t\tbreak\n\t\tif i == 1 or i == len(arr):\n\t\t\treturn False\n\t\twhile i < len(arr):\n\t\t\tif arr[i - 1] > arr[i]:\n\t\t\t\ti += 1\n\t\t\telse:\n\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tup = True\n\t\tfor i in range(1, len(A)):\n\t\t\tif A[i] == A[i - 1]:\n\t\t\t\treturn False\n\t\t\tif up:\n\t\t\t\tif A[i] < A[i - 1]:\n\t\t\t\t\tif i == 1:\n\t\t\t\t\t\treturn False\n\t\t\t\t\tup = False\n\t\t\telif A[i] > A[i - 1]:\n\t\t\t\treturn False\n\t\treturn not up\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) < 3:\n\t\t\treturn False\n\t\tif A[0] > A[1]:\n\t\t\treturn False\n\t\tdecreasing = False\n\t\tlast = A.pop(0)\n\t\twhile A:\n\t\t\tnew = A.pop(0)\n\t\t\tprint((new, last, decreasing))\n\t\t\tif new == last:\n\t\t\t\treturn False\n\t\t\tif new > last and decreasing:\n\t\t\t\tprint('early')\n\t\t\t\treturn False\n\t\t\tif new < last and (not decreasing):\n\t\t\t\tdecreasing = True\n\t\t\tlast = new\n\t\treturn decreasing\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tn = len(A)\n\t\tif n < 3:\n\t\t\treturn False\n\t\ti = 0\n\t\twhile i < n - 1 and A[i] < A[i + 1]:\n\t\t\ti += 1\n\t\tif i == 0 or i == n - 1:\n\t\t\treturn False\n\t\twhile i < n - 1 and A[i] > A[i + 1]:\n\t\t\ti += 1\n\t\tif i != n - 1:\n\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tpassedPeak = False\n\t\tif len(A) <= 2 or A[0] > A[1]:\n\t\t\treturn False\n\t\tfor i in range(len(A) - 1):\n\t\t\tif A[i] == A[i + 1]:\n\t\t\t\treturn False\n\t\t\tif passedPeak == True and A[i] < A[i + 1]:\n\t\t\t\treturn False\n\t\t\tif passedPeak == False and A[i] > A[i + 1]:\n\t\t\t\tpassedPeak = True\n\t\tif passedPeak:\n\t\t\treturn True\n\t\telse:\n\t\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tinflection = None\n\t\tif len(A) > 3:\n\t\t\tfor i in range(0, len(A) - 1):\n\t\t\t\tif inflection is not None:\n\t\t\t\t\tif A[i] < A[i + 1]:\n\t\t\t\t\t\treturn False\n\t\t\t\telif A[i] > A[i + 1]:\n\t\t\t\t\tinflection = i\n\t\t\tprint(inflection, A[0:inflection], A[inflection:])\n\t\t\tif inflection is not None:\n\t\t\t\tif len(A[0:inflection]) and len(A[inflection:]):\n\t\t\t\t\tif len(set(A[0:inflection])) + len(set(A[inflection:])) == len(A):\n\t\t\t\t\t\treturn True\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn False\n\t\t\t\telse:\n\t\t\t\t\treturn False\n\t\t\t\t\tprint(set(A[0:inflection]), len(A[0:inflection]), set(A[inflection:]), len(A[inflection:]))\n\t\t\t\t\treturn False\n\t\t\telse:\n\t\t\t\treturn False\n\t\telif len(A) == 3:\n\t\t\tif A[0] < A[1] and A[1] > A[2]:\n\t\t\t\treturn True\n\t\t\telse:\n\t\t\t\treturn False\n\t\telse:\n\t\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tclimb = True\n\t\tcs = 0\n\t\tfs = 0\n\t\tfor i in range(1, len(A)):\n\t\t\tif climb == True:\n\t\t\t\tif A[i] > A[i - 1]:\n\t\t\t\t\tcs += 1\n\t\t\t\t\tcontinue\n\t\t\t\telif A[i] == A[i - 1]:\n\t\t\t\t\treturn False\n\t\t\t\telse:\n\t\t\t\t\tclimb = False\n\t\t\tif climb == False:\n\t\t\t\tif A[i] < A[i - 1]:\n\t\t\t\t\tfs += 1\n\t\t\t\t\tcontinue\n\t\t\t\telse:\n\t\t\t\t\treturn False\n\t\tif cs > 0 and fs > 0:\n\t\t\treturn True\n\t\treturn False\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif len(A) == 0 or len(A) == 1:\n\t\t\treturn False\n\t\tidx = 0\n\t\twhile idx < len(A) - 1 and A[idx] < A[idx + 1]:\n\t\t\tidx += 1\n\t\tif idx == 0 or idx == len(A) - 1:\n\t\t\treturn False\n\t\twhile idx < len(A) - 1 and A[idx] > A[idx + 1]:\n\t\t\tidx += 1\n\t\tprint((idx, len(A)))\n\t\treturn idx == len(A) - 1\n", "class Solution:\n\n\tdef validMountainArray(self, A: List[int]) -> bool:\n\t\tif not A or len(A) <= 2:\n\t\t\treturn False\n\t\tincrease = -1\n\t\tfor i in range(1, len(A)):\n\t\t\tif A[i] > A[i - 1] and increase == -1:\n\t\t\t\tincrease = 1\n\t\t\tif A[i] > A[i - 1] and increase == 1:\n\t\t\t\tcontinue\n\t\t\telif A[i] < A[i - 1] and increase == 1:\n\t\t\t\tincrease = 0\n\t\t\telif A[i] < A[i - 1] and increase == 0:\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\treturn False\n\t\tif increase != 0:\n\t\t\treturn False\n\t\treturn True\n"]

starter_code:
class Solution:
    def validMountainArray(self, A: List[int]) -> bool:

input_output: {"fn_name": "validMountainArray", "inputs": [[[2, 1]]], "outputs": [false]}

difficulty: EASY

source: leetcode

skill_types: ['Data structures']

raw_problem:
Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

arr.length >= 3

There exists some i with 0 < i < arr.length - 1 such that:

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]

arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

Constraints:

1 <= arr.length <= 104

0 <= arr[i] <= 104

question:
Given an array of integers arr, return true if and only if it is a valid mountain array.
Recall that arr is a mountain array if and only if:

- arr.length >= 3
- There exists some i with 0 < i < arr.length - 1 such that:

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

![image](1.png)

Example 1:
Input: arr = [2,1]
Output: false
Example 2:
Input: arr = [3,5,5]
Output: false
Example 3:
Input: arr = [0,3,2,1]
Output: true

Constraints:

- 1 <= arr.length <= 10^{4}
- 0 <= arr[i] <= 10^{4}

data_split: test


Rooted Tree for Misawa-san

source: ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2016

raw_problem:
C - みさわさんの根付き木

Problem Statement

あなたは親友であるみさわさんの誕生日が近いことに気づき，根付きの二分木をプレゼントすることにした．
ここで，根付きの二分木とは，以下のようなグラフ構造である．(図 1)

 各頂点には，その頂点の親と呼ばれる頂点がちょうど 1 つだけ存在し，親と辺で結ばれている．ただし，根と呼ばれる 1 つの頂点のみ，例外的に親を持たない．

 各頂点は，左の子と呼ばれる頂点をちょうど1つ持つか，あるいは持たない．左の子を持つ場合，左の子とは辺で結ばれており，左の子の親はその頂点である．

 各頂点は，右の子と呼ばれる頂点をちょうど1つ持つか，あるいは持たない．右の子を持つ場合，右の子とは辺で結ばれており，右の子の親はその頂点である．

図 1. 2 つの根付きの二分木とその合成の例

あなたは手作りの品を贈りたいと考えたので，市販の根付きの二分木を 2 つ買ってきて重ね合わせて合成することで，さらによい根付きの二分木を 1 つ作ることにした．
あなたが買ってきた 2 つの木の各頂点には非負の整数が書かれている．
みさわさんは少ない頂点数で各数値が大きいような，コストパフォーマンスがよい木が好みなので，以下の手順に沿って新しい二分木を作ることにする．

 2 つの二分木それぞれの根に書かれた整数の和を，新しい二分木の根に書く整数とする．

 どちらの二分木の根も左の子を持っている場合，それらを根とする二分木それぞれを合成した二分木を作り，新しい二分木の根の左の子とする．そうでない場合，新しい二分木の根は左の子を持たない．

 どちらの二分木の根も右の子を持っている場合，それらを根とする二分木それぞれを合成した二分木を作り，新しい二分木の根の右の子とする．そうでない場合，新しい二分木の根は右の子を持たない．

あなたは実際に合成する作業を行う前に，できあがる根付きの二分木がどのようになるのか確かめることにした．
買ってきた 2 つの根付きの二分木の情報が与えられるので，上記の手順に従って合成される新しい根付きの二分木を求めるプログラムを作成せよ．

ここで，根付きの二分木の情報は以下のような形式で文字列として表現するものとする．

(左の子を表す文字列)[根に書かれた整数](右の子を表す文字列)

節点が存在しない木は空文字列とする．例えば図 1 の合成されてできた新しい根付きの二分木は (()[6]())[8](((()[4]())[7]())[9]()) のように書く．

Input

入力は次の形式で表される．

$A$

$B$

$A$，$B$ はそれぞれ買ってきた根付きの二分木の情報を表す文字列であり，長さは $7$ 以上 $1000$ 以下である．
与えられる情報は前述の形式に従っており，余計な空白文字等を含まない．
また，節点が存在しない根付き木が入力されることはない．
各節点に書かれた整数は $0$ 以上 $1000$ 以下であると仮定してよい．
ただし，出力の各節点に書かれる整数はこの範囲に収まらない場合もあることに注意せよ．

Output

2 つの根付きの二分木を合成してできあがる新しい根付きの二分木の情報を 1 行で出力せよ．特に，行末の改行を除く余計な空白文字等を含まないよう注意せよ．

Sample Input 1

((()[8]())[2]())[5](((()[2]())[6](()[3]()))[1]())
(()[4]())[3](((()[2]())[1]())[8](()[3]()))

Output for the Sample Input 1

(()[6]())[8](((()[4]())[7]())[9]())

Sample Input 2

(()[1]())[2](()[3]())
(()[1](()[2]()))[3]()

Output for the Sample Input 2

(()[2]())[5]()

Sample Input 3

(()[1]())[111]()
()[999](()[9]())

Output for the Sample Input 3

()[1110]()

Sample Input 4

(()[2](()[4]()))[8]((()[16]())[32](()[64]()))
((()[1]())[3]())[9](()[27](()[81]()))

Output for the Sample Input 4

(()[5]())[17](()[59](()[145]()))

Sample Input 5

()[0]()
()[1000]()

Output for the Sample Input 5

()[1000]()

solutions: ["def convert(S):\n    cur = 0\n    def parse():\n        nonlocal cur\n        if S[cur] == ')':\n            return ()\n        cur += 1 # '('\n        left = parse()\n        cur += 2 # ')['\n        num = 0\n        while S[cur] != ']':\n            num = 10*num + int(S[cur])\n            cur += 1\n        cur += 2 # ']('\n        right = parse()\n        cur += 1 # ')'\n        return left, num, right\n    return parse()\ndef dfs(A, B):\n    if not A or not B:\n        return ()\n    return (dfs(A[0], B[0]), [A[1] + B[1]], dfs(A[2], B[2]))\nprint(str(dfs(convert(input()), convert(input()))).replace(\", \",\"\")[1:-1])\n", "A = input()\nB = input()\n\n\ndef parse(S):\n    N = len(S)\n    index = 0\n    def expr(r=1):\n        nonlocal index\n        if index == N or S[index] == ')':\n            return -1\n        ret = []\n        index += 1\n        ret.append(expr(2 * r))\n        index += 1\n\n        index += 1\n        begin = index\n        while S[index].isdigit():\n            index += 1\n        v = int(S[begin:index])\n        ret.append(v)\n        index += 1\n\n\n        index += 1\n        ret.append(expr(2 * r + 1))\n        index += 1\n\n        return ret\n\n    return expr()\n\ninformation_A = parse(A)\ninformation_B = parse(B)\n\nnew_information = []\npnter_A = information_A\npnter_B = information_B\npnter_new = new_information\nstack = []\nstack.append((pnter_A, pnter_B, pnter_new))\nwhile stack:\n    pnter_A, pnter_B, pnter_new = stack.pop()\n    ret = pnter_new\n    lef_A = pnter_A[0]\n    lef_B = pnter_B[0]\n    if lef_A != -1 and lef_B != -1:\n        lef_new = []\n        ret.append(lef_new)\n        stack.append((lef_A, lef_B, lef_new))\n    else:\n        ret.append(-1)\n    val_A = pnter_A[1]\n    val_B = pnter_B[1]\n    ret.append(val_A + val_B)\n    rig_A = pnter_A[2]\n    rig_B = pnter_B[2]\n    if rig_A != -1 and rig_B != -1:\n        rig_new = []\n        ret.append(rig_new)\n        stack.append((rig_A, rig_B, rig_new))\n    else:\n        ret.append(-1)\n\ndef construct(pnter):\n    if pnter == -1:\n        return \"\"\n    lef = construct(pnter[0])\n    rig = construct(pnter[2])\n    return f\"({lef})[{pnter[1]}]({rig})\"\n\nprint(construct(new_information))\n", "def str_to_binary_tree(s):\n  todo=[(0,len(s)-1,'')]\n  d={}\n  while todo:\n    L,R,v=todo.pop()\n    if L>R:\n      continue\n    cnt=0\n    idx=-1\n    for i in range(L,R+1):\n      if s[i]=='(':\n        cnt+=1\n      elif s[i]==')':\n        cnt-=1\n      if cnt==0:\n        idx=i\n        break\n    todo.append((L+1,idx-1,v+'0'))\n    idx+=2\n    val=''\n    while '0'<=s[idx]<='9':\n      val+=s[idx]\n      idx+=1\n    d[v]=int(val)\n    todo.append((idx+2,R-1,v+'1'))\n  return d\n\ndef merge(a,b):\n  todo=['']\n  d={}\n  while todo:\n    v=todo.pop()\n    if v in a and v in b:\n      d[v]=a[v]+b[v]\n      todo.append(v+'0')\n      todo.append(v+'1')\n  return d\n\ndef binary_tree_to_str(v):\n  if v in c:\n    L=binary_tree_to_str(v+'0')\n    R=binary_tree_to_str(v+'1')\n    return '('+L+')['+str(c[v])+']('+R+')'\n  else:\n    return ''\n\nA=input()\nB=input()\na=str_to_binary_tree(A)\nb=str_to_binary_tree(B)\nc=merge(a,b)\n\nprint(binary_tree_to_str(''))\n", "class Vertex:\n    def __init__(self, num):\n        self.left = None\n        self.right = None\n        self.num = num\n    \nA = \"(\" + input() + \")\"\nB = \"(\" + input() + \")\"\n\ndef make_V(A):\n    stack = []\n    num = \"\"\n    bef = False\n    v = None\n    for a in A:\n        if a == \"(\":\n            pass\n        elif a == \")\":\n            if bef == \"(\":\n                stack.append(None)\n            else:\n                vr = stack.pop()\n                vm = stack.pop()\n                vl = stack.pop()\n                vm.left = vl\n                vm.right = vr\n                stack.append(vm)\n        elif a == \"[\":\n            pass\n        elif a == \"]\":\n            v = Vertex(int(num))\n            stack.append(v)\n            num = \"\"\n        else:\n            num += a\n        bef = a\n    return stack[0]\n    \nA = make_V(A)\nB = make_V(B)\n\nans = []\ndef dfs(a, b):\n    global ans\n    ans.append(\"(\")\n    if a.left is not None and b.left is not None:\n        dfs(a.left, b.left)\n    ans.append(\")\")\n    \n    ans.append(\"[\")\n    ans.append(a.num + b.num)\n    ans.append(\"]\")\n    \n    ans.append(\"(\")\n    if a.right is not None and b.right is not None:\n        dfs(a.right, b.right)\n    ans.append(\")\")\n    \n\ndfs(A, B)\n\nprint(*ans, sep=\"\")\n\n", "import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools\n\nsys.setrecursionlimit(10**7)\ninf = 10**20\neps = 1.0 / 10**10\nmod = 10**9+7\ndd = [(-1,0),(0,1),(1,0),(0,-1)]\nddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]\n\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]\ndef LF(): return [float(x) for x in sys.stdin.readline().split()]\ndef LS(): return sys.stdin.readline().split()\ndef I(): return int(sys.stdin.readline())\ndef F(): return float(sys.stdin.readline())\ndef S(): return input()\ndef pf(s): return print(s, flush=True)\n\n\ndef main():\n    a = S()\n    b = S()\n\n    def f(s):\n        if not s:\n            return None\n        if s[0] != '(':\n            return int(s)\n        c = 1\n        mi = -1\n        for i in range(1, len(s)):\n            if s[i] == '(':\n                c += 1\n            elif s[i] == ')':\n                c -= 1\n                if c == 0:\n                    mi = i\n                    break\n\n        c = 1\n        ki = -1\n        for i in range(mi+2, len(s)):\n            if s[i] == '[':\n                c += 1\n            elif s[i] == ']':\n                c -= 1\n                if c == 0:\n                    ki = i\n                    break\n\n        return [f(s[mi+2:ki]), f(s[1:mi]), f(s[ki+2:-1])]\n\n    fa = f(a)\n    fb = f(b)\n    def g(a, b):\n        if a is None or b is None:\n            return None\n        if isinstance(a, int) or isinstance(b, int):\n            ai = a\n            while not isinstance(ai, int):\n                ai = ai[0]\n\n            bi = b\n            while not isinstance(bi, int):\n                bi = bi[0]\n\n            return ai + bi\n\n        return [g(a[i],b[i]) for i in range(3)]\n\n    def h(a):\n        if a is None:\n            return ''\n        if isinstance(a, int):\n            return str(a)\n        return '({})[{}]({})'.format(h(a[1]),h(a[0]),h(a[2]))\n\n\n    return h(g(fa, fb))\n\n\nprint(main())\n\n", "def parse_node(l, r, S):\n    left, right = 0, 0\n    cnt = 0\n    for i in range(l, r + 1):\n        if S[i] == '(':\n            cnt += 1\n        elif S[i] == ')':\n            cnt -= 1\n        elif cnt == 0 and S[i] == \"[\":\n            left = i\n        elif cnt == 0 and S[i] == \"]\":\n            right = i\n    return left, right\n\n\ndef parser(l1, r1, l2, r2):\n    n1_l, n1_r = parse_node(l1, r1, S1)\n    n2_l, n2_r = parse_node(l2, r2, S2)\n    # print(n1_l, n1_r, n2_l, n2_r)\n    node = \"[{}]\".format(int(S1[n1_l + 1:n1_r]) + int(S2[n2_l + 1:n2_r]))\n    left_node = \"({})\".format(\"\" if min(n1_l - l1, n2_l - l2) <= 2 else parser(l1 + 1, n1_l - 2, l2 + 1, n2_l - 2))\n    right_node = \"({})\".format(\"\" if min(r1 - n1_r, r2 - n2_r) <= 2 else parser(n1_r + 2, r1 - 1, n2_r + 2, r2 - 1))\n    return left_node + node + right_node\n\n\n\nS1, S2 = input(), input()\nprint(parser(0, len(S1) - 1, 0, len(S2) - 1))\n", "#!/usr/bin/env python3\n\nfrom functools import lru_cache\nfrom heapq import heappush, heappop, heappushpop\nfrom itertools import permutations\nfrom operator import ge, itemgetter\nfrom collections import deque\nfrom collections import Counter\nfrom itertools import accumulate\nfrom collections import defaultdict\nimport sys\nimport math\nfrom bisect import bisect_right as br\nfrom bisect import bisect_left as bl\nsys.setrecursionlimit(2147483647)\nmod = 10**9 + 7\ninf = float('inf')\ndef I(): return int(sys.stdin.readline())\ndef LI(): return list(map(int, sys.stdin.readline().split()))\n\nclass Node():\n    def __init__(self, par, val, left, right):\n        self.par = par\n        self.val = val\n        self.left = left\n        self.right = right\n     \ndef parse(s, p):\n    n = len(s)\n    cnt = 0\n    for i in range(n):\n        if s[i] == '(':\n            cnt += 1\n        elif s[i] == ')':\n            cnt -= 1\n        if s[i] == '[' and cnt == 0:\n            tmp = 0\n            for j in range(i+1, n):\n                if s[j].isdigit():\n                    tmp *= 10\n                    tmp += int(s[j])\n                else:\n                    break\n            node = Node(p, tmp, None, None)\n            left = parse(s[1:i-2], node)\n            right = parse(s[j+2:-1], node)\n            node.left = left\n            node.right = right\n            return node\n        \n    return Node(p, None, None, None)\n\ndef generate(ra, rb):\n    if ra.left.val is not None and rb.left.val is not None:\n        ret = \"(\" + generate(ra.left, rb.left) + \")\"\n    else:\n        ret = \"()\"\n    if ra.val is not None and rb.val is not None:\n        ret += \"[\" + str(ra.val + rb.val) + \"]\"\n    if ra.right.val is not None and rb.right.val is not None:\n        ret += \"(\" + generate(ra.right, rb.right) + \")\"\n    else:\n        ret += \"()\"\n    return ret\n\na = input()\nb = input()\nra = parse(a, None)\nrb = parse(b, None)\nprint(generate(ra, rb))\n\n", "from sys import setrecursionlimit\nsetrecursionlimit(10 ** 8)\n\nA = input()\nB = input()\n\nA_root = [[-1] * 3 for i in range(1000)]\nB_root = [[-1] * 3 for i in range(1000)]\n\nclass Source():\n  def __init__(self, S):\n    self.S = S\n    self.pos = 0\n   \n  \ndef peek(S):\n  return S.S[S.pos] if S.pos < len(S.S) else -1\n\ndef next(S):\n  S.pos += 1\n\ndef tree(S, A, i):\n  next(S)\n  if peek(S) == ')':\n    next(S)\n    return -1\n  c = i[0]\n  i[0] += 1\n  l = i[0] \n  left = tree(S, A, i)\n  center = root(S, A)\n  i[0] += 1\n  r = i[0]\n  right = tree(S, A, i)\n  \n  A[c] = [center, l, r]\n  next(S)\n  \ndef root(S, A):\n  res = 0\n  next(S)\n  while peek(S) != ']':\n    res = res * 10 + int(peek(S))\n    next(S)\n  next(S)\n  \n  return res\n  \ntree(Source('(' + A + ')'), A_root, [0])\ntree(Source('(' + B + ')'), B_root, [0])\n\ndef f(i, j):\n  if A_root[i][0] == -1 or B_root[j][0] == -1:\n    return '()'\n  center = '[' + str(A_root[i][0] + B_root[j][0]) + ']'\n  return '(' + f(A_root[i][1], B_root[j][1]) + center + f(A_root[i][2], B_root[j][2]) + ')'\n\nprint(f(0, 0)[1:-1])\n", "A = input()\nB = input()\n\nX = dict()\nY = dict()\n\n# 0:left, 1:right\n# ex: 0011 : 7\n\n\ndef f(S, key, D):\n    if S == '':\n        return\n    T = S\n    left_search_count = 0\n    left = 0\n    for i, s in enumerate(T):\n        if s == '(':\n            left_search_count += 1\n        elif s == ')':\n            left_search_count -= 1\n        if left_search_count == 0:\n            f(T[1:i], key+'0', D)\n            left = i\n            break\n\n    right = left\n    while T[right] != ']':\n        right += 1\n    D[key] = int(T[left+2:right])\n\n    T = T[right+1:]\n    right_search_count = 0\n    for i, s in enumerate(T):\n        if s == '(':\n            right_search_count += 1\n        elif s == ')':\n            right_search_count -= 1\n        if right_search_count == 0:\n            f(T[1:i], key+'1', D)\n            break\n    return\n\n\nf(A, 'N', X)\nf(B, 'N', Y)\n\nZ = dict()\nfor key in X:\n    if Y.get(key) == None:\n        continue\n    Z[key] = X[key] + Y[key]\n\n\ndef make_ans(key):\n    global Z\n    if Z.get(key) == None:\n        return ''\n    left = '('+make_ans(key+'0')+')'\n    value = '[' + str(Z[key]) + ']'\n    right = '('+make_ans(key+'1')+')'\n    return left + value + right\n\n\nprint(make_ans('N'))\n\n", "def sToTree(S):\n#    print(S)\n    if len(S)==0:\n        return 'N'\n    c = 0\n    left=0\n    right=0\n    #print(S)\n    for i in range(len(S)):\n        if S[i] =='(':\n            c+=1\n        elif S[i] ==')':\n            c-=1\n        elif c==0 and S[i]=='[':\n            left=i\n        elif c==0 and S[i] ==']':\n            right=i\n            break\n#    print(S[right+1:len(S)-1],right,left)   \n    return[sToTree(S[1:left-1]),int(S[left+1:right]),sToTree(S[right+2:len(S)-1])]\n    \ndef dfs(S1,S2):\n    if S1=='N' or S2=='N':\n        return 'N'\n\n    ret = [dfs(S1[0],S2[0]),S1[1]+S2[1],dfs(S1[2],S2[2])]\n    return ret\n\ndef my_print(ans):\n    if ans == 'N':\n        return\n    print('(',end='')\n    my_print(ans[0])\n    print(\")[{0}](\".format(ans[1]),end = '')\n    my_print(ans[2])\n    print(')',end='')\n\nS1 = input()\nS2 = input()\n\n\nS1 = sToTree(S1)\nS2 = sToTree(S2)\n\nans = dfs(S1,S2)\nmy_print(ans)\nprint()\n\n", "def sep(S):\n    l=r=0\n    for i,s in enumerate(S):\n        l+=s=='('\n        r+=s==')'\n        if l==r:\n            j=S.find(']',i)\n            s_l=S[1:i]\n            s_r=S[j+2:-1]\n            s_c=int(S[i+2:j])\n            break\n    return s_l,s_c,s_r\ndef solve(A,B):\n    if A=='' or B=='':\n        return ''\n    a_l,a_c,a_r=sep(A)\n    b_l,b_c,b_r=sep(B)\n    return '(%s)[%d](%s)'%(solve(a_l,b_l),a_c+b_c,solve(a_r,b_r))\nprint(solve(input(),input()))\n", "class binary_tree():\n    def __init__(self,value,left=None,right=None):\n        self.value=value\n        self.left=left\n        self.right=right\n\ndef find_corres_bra(s,fr,to):\n    count=0 \n    x=-1\n    for i in range(len(s)):\n        if s[i]==fr:\n            count += 1\n        elif s[i]==to:\n            if count==1:\n                x=i\n                break\n            else:\n                count-=1\n    return x\n    \n\ndef make_tree(s):\n    if s=='':\n        return None\n    x0=0\n    x1=find_corres_bra(s,'(',')')+1\n    x2=x1+find_corres_bra(s[x1:],'[',']')+1\n    tree=binary_tree(int(s[x1+1:x2-1]),make_tree(s[x0+1:x1-1]),make_tree(s[x2+1:-1]))\n    return tree\n\ndef synthe_trees(t1,t2):\n    tree=binary_tree(value=t1.value+t2.value)\n    if t1.left!=None and t2.left !=None:\n        tree.left=synthe_trees(t1.left,t2.left)\n    if t1.right!=None and t2.right !=None:\n        tree.right=synthe_trees(t1.right,t2.right)\n    return tree\n\ndef tree_to_str(tree):\n    if tree==None:\n        return ''\n    ans='('+ tree_to_str(tree.left)+')'+'['+str(tree.value)+']'+'('+ tree_to_str(tree.right)+')'\n    return ans\n\nt1=make_tree(input())\nt2=make_tree(input())\ntree=synthe_trees(t1,t2)\nprint(tree_to_str(tree))\n        \n"]

source: aizu

question:
C - Misawa-san's Rooted Tree
Problem Statement

You have realized that the birthday of your best friend, Misawa-san, is approaching, and you've decided to present a rooted binary tree as a gift.
Here, a rooted binary tree is a graph structure as follows. (Figure 1)

- Each vertex has exactly one other vertex called its parent, with which it is connected by an edge. However, a single vertex called the root is an exception, as it does not have a parent.

- Each vertex has exactly one left child vertex or none at all. If it has a left child, the left child is connected by an edge, and the parent of the left child is that vertex.

- Each vertex has exactly one right child vertex or none at all. If it has a right child, the right child is connected by an edge, and the parent of the right child is that vertex.

![image](1.png)

Figure 1. Examples of two rooted binary trees and their composition.

You want to give a handmade gift, so you decided to buy two commercially available rooted binary trees and overlay them to create an even better single rooted binary tree.
Each vertex of the two trees you bought has a non-negative integer written on it.
Since Misawa-san prefers a tree with fewer vertices and larger values, offering good cost performance, you have decided to create a new binary tree according to the following procedure:

- The sum of the integers written on the roots of both binary trees will be the integer written at the root of the new binary tree.

- If the root of both binary trees has a left child, create a binary tree composed of those as the root binary trees, and make it the left child of the root of the new binary tree. Otherwise, the root of the new binary tree does not have a left child.

- If the root of both binary trees has a right child, create a binary tree composed of those as the root binary trees, and make it the right child of the root of the new binary tree. Otherwise, the root of the new binary tree does not have a right child.

Before actually performing the composing task, you decided to check what the resulting rooted binary tree would look like.
Given the information of the two rooted binary trees you bought, create a program to determine the new rooted binary tree that results from following the above procedure.

Here, the information for the rooted binary tree is expressed in string format as follows:
(string representing the left child)[integer written at the root](string representing the right child)

An empty string represents a tree without any nodes. For example, the new rooted binary tree resulting from the composition in Figure 1 is written as (()[6]())[8](((()[4]())[7]())[9]()).

Input

The input is in the following format:

$A$
$B$

$A$ and $B$ are strings representing the information of the rooted binary trees you bought, with lengths of $7$ to $1000$.
The given information follows the aforementioned format and does not include unnecessary white spaces or similar characters.
Also, it is assumed that the integers written on each node are between $0$ and $1000$, inclusive.
However, note that the integers written on each node in the output may exceed this range.

Output

Output the information of the new rooted binary tree resulting from the composition of the two rooted binary trees on a single line. Be careful not to include any unnecessary white space characters, including line end breaks.

Sample Input 1

((()[8]())[2]())[5](((()[2]())[6](()[3]()))[1]())
(()[4]())[3](((()[2]())[1]())[8](()[3]()))

Output for the Sample Input 1

(()[6]())[8](((()[4]())[7]())[9]())
Sample Input 2

(()[1]())[2](()[3]())
(()[1](()[2]()))[3]()

Output for the Sample Input 2

(()[2]())[5]()
Sample Input 3

(()[1]())[111]()
()[999](()[9]())

Output for the Sample Input 3

()[1110]()
Sample Input 4

(()[2](()[4]()))[8]((()[16]())[32](()[64]()))
((()[1]())[3]())[9](()[27](()[81]()))

Output for the Sample Input 4

(()[5]())[17](()[59](()[145]()))
Sample Input 5

()[0]()
()[1000]()

Output for the Sample Input 5

()[1000]()

data_split: test


H. Doremy's Paint 2

problem_index: H

time_limit: 4 seconds

memory_limit: 256 megabytes

note:
In the first test case, the picture below shows the resulting array for the values of $$$x=0,1,2$$$ respectively.
![image](images/cf_1764_H/1.png)

source: codeforces

raw_problem:
H. Doremy's Paint 2

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Doremy has $$$n$$$ buckets of paint which is represented by an array $$$a$$$ of length $$$n$$$. Bucket $$$i$$$ contains paint with color $$$a_i$$$. Initially, $$$a_i=i$$$.

Doremy has $$$m$$$ segments $$$[l_i,r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$). Each segment describes an operation. Operation $$$i$$$ is performed as follows:

 For each $$$j$$$ such that $$$l_i < j \leq r_i$$$, set $$$a_j := a_{l_i}$$$.

Doremy also selects an integer $$$k$$$. She wants to know for each integer $$$x$$$ from $$$0$$$ to $$$m-1$$$, the number of distinct colors in the array after performing operations $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$. Can you help her calculate these values? Note that for each $$$x$$$ individually we start from the initial array and perform only the given $$$k$$$ operations in the given order.

Input

The first line of input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n,m\le 2\cdot 10^5$$$, $$$1 \le k \le m$$$) — the length of the array $$$a$$$, the total number of operations, and the integer that Doremy selects.

The $$$i$$$-th line of the following $$$m$$$ lines contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the bounds of the $$$i$$$-th segment.

Output

Output $$$m$$$ integers. The $$$(x+1)$$$-th integer should be the number of distinct colors in the array if we start from the initial array and perform operations $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$.

Examples

Input

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

Output

3 3 3 3 2

Input

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

Output

6 6 7 6 5 5 7 7 7

Note

In the first test case, the picture below shows the resulting array for the values of $$$x=0,1,2$$$ respectively.

question:
Doremy has $$$n$$$ buckets of paint which is represented by an array $$$a$$$ of length $$$n$$$. Bucket $$$i$$$ contains paint with color $$$a_i$$$. Initially, $$$a_i=i$$$.
Doremy has $$$m$$$ segments $$$[l_i,r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$). Each segment describes an operation. Operation $$$i$$$ is performed as follows:
 -  For each $$$j$$$ such that $$$l_i < j \leq r_i$$$, set $$$a_j := a_{l_i}$$$. Doremy also selects an integer $$$k$$$. She wants to know for each integer $$$x$$$ from $$$0$$$ to $$$m-1$$$, the number of distinct colors in the array after performing operations $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$. Can you help her calculate these values? Note that for each $$$x$$$ individually we start from the initial array and perform only the given $$$k$$$ operations in the given order.

Input
The first line of input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n,m\le 2\cdot 10^5$$$, $$$1 \le k \le m$$$) — the length of the array $$$a$$$, the total number of operations, and the integer that Doremy selects.
The $$$i$$$-th line of the following $$$m$$$ lines contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the bounds of the $$$i$$$-th segment.

Output
Output $$$m$$$ integers. The $$$(x+1)$$$-th integer should be the number of distinct colors in the array if we start from the initial array and perform operations $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$.

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

Output
3 3 3 3 2

Input
10 9 4
1 1
2 3
3 4
7 9
6 8
5 7
2 4
9 10
1 3

Output
6 6 7 6 5 5 7 7 7

Note
In the first test case, the picture below shows the resulting array for the values of $$$x=0,1,2$$$ respectively.
![image](1.png)

data_split: test


raw_problem:
A hexagonal tile with number $1$ is surrounded by a ring of six hexagonal tiles, starting at "12 o'clock" and numbering the tiles $2$ to $7$ in an anti-clockwise direction.

New rings are added in the same fashion, with the next rings being numbered $8$ to $19$, $20$ to $37$, $38$ to $61$, and so on. The diagram below shows the first three rings.

By finding the difference between tile $n$ and each of its six neighbours we shall define $PD(n)$ to be the number of those differences which are prime.

For example, working clockwise around tile $8$ the differences are $12, 29, 11, 6, 1$, and $13$. So $PD(8) = 3$.

In the same way, the differences around tile $17$ are $1, 17, 16, 1, 11$, and $10$, hence $PD(17) = 2$.

It can be shown that the maximum value of $PD(n)$ is $3$.

If all of the tiles for which $PD(n) = 3$ are listed in ascending order to form a sequence, the $10$th tile would be $271$.

Find the $2000$th tile in this sequence.

problem:
A hexagonal tile with number $1$ is surrounded by a ring of six hexagonal tiles, starting at "12 o'clock" and numbering the tiles $2$ to $7$ in an anti-clockwise direction.
New rings are added in the same fashion, with the next rings being numbered $8$ to $19$, $20$ to $37$, $38$ to $61$, and so on. The diagram below shows the first three rings.

![image](images/ep_128/1.png)
By finding the difference between tile $n$ and each of its six neighbours we shall define $PD(n)$ to be the number of those differences which are prime.
For example, working clockwise around tile $8$ the differences are $12, 29, 11, 6, 1$, and $13$. So $PD(8) = 3$.
In the same way, the differences around tile $17$ are $1, 17, 16, 1, 11$, and $10$, hence $PD(17) = 2$.
It can be shown that the maximum value of $PD(n)$ is $3$.
If all of the tiles for which $PD(n) = 3$ are listed in ascending order to form a sequence, the $10$th tile would be $271$.
Find the $2000$th tile in this sequence.

solutions: "import math, itertools\n\n\n# Let's do mathematical analysis to drastically reduce the amount of\n# logic we need to implement and calculation the computer needs to do.\n# We begin with a couple of definitions.\n# \n# Ring number: Each cell belongs in a hexagonal ring,\n# numbered starting from 0 at the center like this:\n#               3\n#           3       3\n#       3       2       3\n#   3       2       2       3\n#       2       1       2\n#   3       1       1       3\n#       2       0       2\n#   3       1       1       3\n#       2       1       2\n#   3       2       2       3\n#       3       2       3\n#           3       3\n#               3\n# \n# Corner/edge cell: Within a ring, each cell is\n# either a corner cell or an edge cell, as shown:\n#               C\n#           E       E\n#       E       C       E\n#   C       E       E       C\n#       C       C       C\n#   E       C       C       E\n#       E       C       E\n#   E       C       C       E\n#       C       C       C\n#   C       E       E       C\n#       E       C       E\n#           E       E\n#               C\n# \n# Basic observations:\n# - Except for the degenerate ring 0, each ring k has 6k cells.\n#   The kth ring has exactly 6 corner cells and 6(k - 1) edge cells.\n# - In the code we will skip the PD (prime difference) calculation for\n#   rings 0 and 1 because the existence of ring 0 breaks many patterns.\n# - Doing the PD calculation for rings 0 and 1 by hand (n = 1 to 7\n#   inclusive), we find that PD(n) = 3 for and only for n = 1, 2.\n# \n# Now let's analyze the characteristics of all cells in rings 2 or above.\n# It's hard to justify these assertions rigorously, but they are true from\n# looking at the spiral diagram.\n# \n# - Corner cells along the upward vertical direction and the edge cells\n#   immediately to the right of this vertical column are the most interesting,\n#   so we will save these cases for last.\n# \n# - Claim: Except for cells immediately right of the upward corner column,\n#   no edge cell satisfies PD(n) = 3. Proof: Take an arbitrary edge cell n\n#   not immediately to the right of the upward corner column...\n#   - The two neighbors in the same ring have a difference of 1 compared to n,\n#     which is not a prime number.\n#   - The two neighbors in the previous (inward) ring are consecutive numbers,\n#     so exactly one of them has an even absolute difference with n. Because\n#     n is in ring 2 or above, the difference with any neighboring number in the\n#     previous ring is at least 6. Thus an even number greater than 2 is not prime.\n#   - Similarly, the two neighbors in the next (outward) ring are consecutive numbers.\n#     One of them has an even difference with n, and this number is also at least 6,\n#     so one neighbor is definitely not prime.\n#   - Therefore with at least 4 neighbors that do not have a prime difference, PD(n) <= 2.\n#   Example of an edge cell n = 11 in ring 2, which is straight left of the origin:\n#         10\n#     24      03\n#         11\n#     25      04\n#         12\n# \n# - Claim: No corner cell in the other 5 directions satisfies PD(n) = 3.\n#   Proof: Take an arbitrary corner cell n in the non-upward direction...\n#   - Two of its neighbors (in the same ring) have a difference of 1,\n#     which is not prime.\n#   - One neighbor is in the previous ring (inward) while three neighbors\n#     are in the next ring (outward).\n#   - Let the inner ring neighbor be k and the outer ring's middle neighbor\n#     be m. The three outer ring neighbors are {m - 1, m, m + 1}.\n#   - Then n - k + 6 = m - n. Also, {m - 1, m + 1} have the same parity,\n#     and {k, m} have the same other parity.\n#   - Either both {|k - n|, |m - n|} are even or both {|m - 1 - n|, |m + 1 - n|} are even.\n#     In any case, all these differences are at least 6, so the even numbers are not prime.\n#   - Therefore with at least 4 neighbors that do not have a prime difference, PD(n) <= 2.\n#   Example of a corner cell n = 14 in ring 2, which is straight below the origin:\n#         05\n#     13      15\n#         14\n#     28      30\n#         29\n# \n# - Now let's consider an arbitrary upward corner cell n in ring k, with k >= 2.\n#   We shall give variables to all its neighbors like this:\n#         d\n#     e       f\n#         n\n#     b       c\n#         a\n#   - a is in the previous ring, {b, c} are in the same ring as n,\n#     and {d, e, f} are in the next ring.\n#   - Equations derived from the structure of the hexagonal spiral:\n#     n = 3k(k - 1) + 2.\n#     a = n - 6(k - 1).\n#     b = n + 1.\n#     c = n + 6k - 1 = d - 1.\n#     d = n + 6k.\n#     e = n + 6k + 1 = d + 1.\n#     f = n + 6k + 6(k + 1) - 1 = n + 12k + 5.\n#   - Hence we get these absolute differences with n:\n#     |a - n| = 6(k - 1). (Not prime because it's a multiple of 6)\n#     |b - n| = 1. (Not prime)\n#     |c - n| = 6k - 1. (Possibly prime)\n#     |d - n| = 6k. (Not prime because it's a multiple of 6)\n#     |e - n| = 6k + 1. (Possibly prime)\n#     |f - n| = 12k + 5. (Possibly prime)\n#   - Therefore for each k >= 2, we need to count how many numbers\n#     in the set {6k - 1, 6k + 1, 12k + 5} are prime.\n#   Example of a corner cell n = 8 in ring 2, which is straight above the origin:\n#         20\n#     21      37\n#         08\n#     09      19\n#         02\n# \n# - Finally let's consider an arbitrary edge cell immediately to the right of the\n#   upward vertical column. Suppose the cell's value is n and it is in ring k,\n#   with k >= 2. Give variables to all its neighbors like this:\n#         f\n#     c       e\n#         n\n#     a       d\n#         b\n#   - {a, b} are in the previous ring, {c, d} are in the current ring, and {e, f} are in\n#     the next ring. The ascending ordering of all these numbers is (a, b, c, d, n, e, f).\n#   - Equations derived from the structure of the hexagonal spiral:\n#     n = 3k(k + 1) + 1.\n#     a = n - 6k - 6(k - 1) + 1 = n - 12k + 7.\n#     b = n - 6k.\n#     c = n - 6k + 1.\n#     d = n - 1.\n#     e = n + 6(k + 1) - 1 = n + 6k + 5.\n#     f = n + 6(k + 1).\n#   - Hence we get these absolute differences with n:\n#     |a - n| = 12k - 7. (Possibly prime)\n#     |b - n| = 6k. (Not prime because it's a multiple of 6)\n#     |c - n| = 6k - 1. (Possibly prime)\n#     |d - n| = 1. (Not prime)\n#     |e - n| = 6k + 5. (Possibly prime)\n#     |f - n| = 6(k + 1). (Not prime because it's a multiple of 6)\n#   - Therefore for each k >= 2, we need to count how many numbers\n#     in the set {6k - 1, 6k + 5, 12k - 7} are prime.\n#   Example of an edge cell n = 19 in ring 2:\n#         37\n#     08      36\n#         19\n#     02      18\n#         07\n\n# Tests whether the given integer is a prime number.\ndef is_prime(x: int) -> bool:\n\tif x <= 1:\n\t\treturn False\n\telif x <= 3:\n\t\treturn True\n\telif x % 2 == 0:\n\t\treturn False\n\telse:\n\t\tfor i in range(3, math.isqrt(x) + 1, 2):\n\t\t\tif x % i == 0:\n\t\t\t\treturn False\n\t\treturn True\n\t\n\ndef compute():\n\tTARGET = 2000  # Must be at least 3\n\tcount = 2  # Because n = 1 and 2 satisfy PD(n) = 3\n\tfor ring in itertools.count(2):\n\t\tif all(map(is_prime, (ring * 6 - 1, ring * 6 + 1, ring * 12 + 5))):\n\t\t\tcount += 1\n\t\t\tif count == TARGET:\n\t\t\t\treturn str(ring * (ring - 1) * 3 + 2)\n\t\tif all(map(is_prime, (ring * 6 - 1, ring * 6 + 5, ring * 12 - 7))):\n\t\t\tcount += 1\n\t\t\tif count == TARGET:\n\t\t\t\treturn str(ring * (ring + 1) * 3 + 1)\n\n\nprint(compute())\n"

question:
A hexagonal tile with number $1$ is surrounded by a ring of six hexagonal tiles, starting at "12 o'clock" and numbering the tiles $2$ to $7$ in an anti-clockwise direction.
New rings are added in the same fashion, with the next rings being numbered $8$ to $19$, $20$ to $37$, $38$ to $61$, and so on. The diagram below shows the first three rings.

![image](1.png)
By finding the difference between tile $n$ and each of its six neighbours we shall define $PD(n)$ to be the number of those differences which are prime.
For example, working clockwise around tile $8$ the differences are $12, 29, 11, 6, 1$, and $13$. So $PD(8) = 3$.
In the same way, the differences around tile $17$ are $1, 17, 16, 1, 11$, and $10$, hence $PD(17) = 2$.
It can be shown that the maximum value of $PD(n)$ is $3$.
If all of the tiles for which $PD(n) = 3$ are listed in ascending order to form a sequence, the $10$th tile would be $271$.
Find the $2000$th tile in this sequence.

data_split: test

source: project euler