B. Chemical table

problem_index: B

time_limit: 1 second

memory_limit: 512 megabytes

note:
For each example you have a picture which illustrates it.
The first picture for each example describes the initial set of element samples available. Black crosses represent elements available in the lab initially.
The second picture describes how remaining samples can be obtained. Red dashed circles denote elements that should be purchased from other labs (the optimal solution should minimize the number of red circles). Blue dashed circles are elements that can be produced with nuclear fusion. They are numbered in order in which they can be produced.
Test 1
We can use nuclear fusion and get the element from three other samples, so we don't need to purchase anything.
![image](images/cf_1012_B/2.png)
Test 2
We cannot use any nuclear fusion at all as there is only one row, so we have to purchase all missing elements.
![image](images/cf_1012_B/3.png)
Test 3
There are several possible solutions. One of them is illustrated below.
Note that after purchasing one element marked as red it's still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.
![image](images/cf_1012_B/4.png)

solutions: ["import sys\n(n, m, q) = map(int, input().split())\np = [-1] * (n + m)\nr = [0] * (n + m)\n\ndef par(i):\n\tif p[i] == -1:\n\t\treturn i\n\tp[i] = par(p[i])\n\treturn p[i]\n\ndef merge(a, b):\n\t(a, b) = (par(a), par(b))\n\tif a == b:\n\t\treturn 0\n\tif r[a] < r[b]:\n\t\tp[a] = b\n\telif r[b] < r[a]:\n\t\tp[b] = a\n\telse:\n\t\tp[a] = b\n\t\tr[b] += 1\n\treturn 1\nv = n + m\nfor l in sys.stdin.read().strip().split('\\n') if q else []:\n\t(a, b) = map(int, l.split())\n\tv -= merge(a - 1, b - 1 + n)\nprint(v - 1)\n", "import sys\nioRead = sys.stdin.readline\nioWrite = lambda x: sys.stdout.write(f'{x}\\n')\n(n, m, q) = map(int, ioRead().split(' '))\nrows_and_columns = n + m\nseen = [False for _ in range(rows_and_columns)]\nconnectsTo = [[] for _ in range(rows_and_columns)]\nfor _ in range(q):\n\t(r, c) = map(lambda x: int(x) - 1, ioRead().split(' '))\n\tc += n\n\tconnectsTo[r].append(c)\n\tconnectsTo[c].append(r)\ninserts = -1\nfor i in range(rows_and_columns):\n\tif not seen[i]:\n\t\tinserts += 1\n\t\tstack = [i]\n\t\twhile stack:\n\t\t\tcurrent = stack.pop()\n\t\t\tif not seen[current]:\n\t\t\t\tseen[current] = True\n\t\t\t\tfor n in connectsTo[current]:\n\t\t\t\t\tif not seen[n]:\n\t\t\t\t\t\tstack.append(n)\nioWrite(inserts)\n", "from collections import deque\nimport os\nfrom io import BytesIO\ninput = BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\ndef main():\n\t(n, m, q) = map(int, input().split())\n\tmn = m + n\n\tcr = [[] for i in range(mn)]\n\tca = [-1] * mn\n\tfor i in range(q):\n\t\t(ri, ci) = map(int, input().split())\n\t\tri -= 1\n\t\tci -= 1\n\t\tcr[ci] += [ri + m]\n\t\tcr[ri + m] += [ci]\n\tans = -1\n\tfor i in range(mn):\n\t\tif ca[i] != -1:\n\t\t\tcontinue\n\t\tca[i] = 1\n\t\tstack = deque()\n\t\tfor j in cr[i]:\n\t\t\tstack.append(j)\n\t\t\tca[j] = 0\n\t\twhile len(stack) != 0:\n\t\t\ttemp = stack.pop()\n\t\t\tfor j in cr[temp]:\n\t\t\t\tif ca[j] == -1:\n\t\t\t\t\tca[j] = 0\n\t\t\t\t\tstack.append(j)\n\t\tans += 1\n\tprint(ans)\nmain()\n", "from sys import stdin, stdout\n\nclass UnionFind:\n\n\tdef __init__(self, arr=[]):\n\t\tself.rank = {}\n\t\tself.leader = {}\n\t\tfor i in arr:\n\t\t\tself.rank[i] = 0\n\t\t\tself.leader[i] = i\n\n\tdef __repr__(self):\n\t\treturn f' Ranks : {self.rank}, leaders : {self.leader} '\n\n\tdef find(self, x):\n\t\tleader = self.leader.get(x, x)\n\t\tif leader != x:\n\t\t\tleader = self.find(leader)\n\t\t\tself.leader[x] = leader\n\t\treturn leader\n\n\tdef getRank(self, x):\n\t\treturn self.rank.get(x, 0)\n\n\tdef union(self, x, y):\n\t\tleader1 = self.find(x)\n\t\tleader2 = self.find(y)\n\t\tif leader1 == leader2:\n\t\t\treturn False\n\t\tif self.getRank(leader1) > self.getRank(leader2):\n\t\t\tself.leader[leader2] = leader1\n\t\telif self.getRank(leader1) < self.getRank(leader2):\n\t\t\tself.leader[leader1] = leader2\n\t\telse:\n\t\t\tself.leader[leader1] = leader2\n\t\t\tself.rank[leader2] = 1 + self.getRank(leader2)\n\t\treturn True\n(n, m, q) = tuple(map(int, stdin.readline().split()))\nuf = UnionFind(range(1, n + m + 1))\nrcs = [tuple(map(int, line.split())) for line in stdin]\ngrps = n + m\nfor (r, c) in rcs:\n\tif uf.union(r, c + n):\n\t\tgrps -= 1\nstdout.write(str(grps - 1))\n", "from sys import stdin, stdout\n\nclass DSU:\n\n\tdef __init__(self, n):\n\t\tself.root = [-1 for x in range(0, n)]\n\n\tdef find(self, i):\n\t\tif self.root[i] == -1:\n\t\t\treturn i\n\t\telse:\n\t\t\tself.root[i] = self.find(self.root[i])\n\t\t\treturn self.root[i]\n\n\tdef link(self, i, j):\n\t\tif self.find(i) == self.find(j):\n\t\t\treturn False\n\t\tself.root[self.find(i)] = self.find(j)\n\t\treturn True\n(n, m, q) = list(map(int, stdin.readline().split()))\ndsu = DSU(n + m + 1)\ngroups = n + m\nfor line in stdin:\n\t(r, c) = list(map(int, line.split()))\n\tgroups -= dsu.link(r, n + c)\nstdout.write(str(groups - 1) + '\\n')\n", "class UnionFind:\n\n\tdef __init__(self, n):\n\t\tself.par = [-1] * n\n\t\tself.rank = [0] * n\n\n\tdef Find(self, x):\n\t\tif self.par[x] < 0:\n\t\t\treturn x\n\t\telse:\n\t\t\tself.par[x] = self.Find(self.par[x])\n\t\t\treturn self.par[x]\n\n\tdef Unite(self, x, y):\n\t\tx = self.Find(x)\n\t\ty = self.Find(y)\n\t\tif x != y:\n\t\t\tif self.rank[x] < self.rank[y]:\n\t\t\t\tself.par[y] += self.par[x]\n\t\t\t\tself.par[x] = y\n\t\t\telse:\n\t\t\t\tself.par[x] += self.par[y]\n\t\t\t\tself.par[y] = x\n\t\t\t\tif self.rank[x] == self.rank[y]:\n\t\t\t\t\tself.rank[x] += 1\n\n\tdef Same(self, x, y):\n\t\treturn self.Find(x) == self.Find(y)\n\n\tdef Size(self, x):\n\t\treturn -self.par[self.Find(x)]\nimport sys\nimport io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(n, m, q) = map(int, input().split())\nuf = UnionFind(n + m)\nfor i in range(q):\n\t(r, c) = map(int, input().split())\n\t(r, c) = (r - 1, c - 1)\n\tuf.Unite(r, c + n)\nS = set()\nfor i in range(n + m):\n\tS.add(uf.Find(i))\nprint(len(S) - 1)\n", "from sys import stdin\n\ndef main():\n\t(n, m, q) = map(int, input().split())\n\tchm = list(range(n + m))\n\tr = [0] * (n + m)\n\tn -= 1\n\tres = n + m\n\tfor s in stdin.read().splitlines():\n\t\t(a, b) = map(int, s.split())\n\t\ta -= 1\n\t\tb += n\n\t\tl = []\n\t\twhile a != chm[a]:\n\t\t\tl.append(a)\n\t\t\ta = chm[a]\n\t\tfor c in l:\n\t\t\tchm[c] = a\n\t\tl = []\n\t\twhile b != chm[b]:\n\t\t\tl.append(b)\n\t\t\tb = chm[b]\n\t\tfor c in l:\n\t\t\tchm[c] = b\n\t\tif a != b:\n\t\t\tif r[a] < r[b]:\n\t\t\t\tchm[a] = b\n\t\t\telif r[b] < r[a]:\n\t\t\t\tchm[b] = a\n\t\t\telse:\n\t\t\t\tchm[a] = b\n\t\t\t\tr[b] += 1\n\t\t\tres -= 1\n\tprint(res)\nmain()\n", "(n, m, q) = map(int, input().split())\nf = [-1] * (n + m + 1)\n\ndef find(x):\n\tif f[x] == -1:\n\t\treturn x\n\telse:\n\t\tf[x] = find(f[x])\n\t\treturn f[x]\nans = n + m - 1\nfor i in range(q):\n\t(r, c) = map(int, input().split())\n\tc += n\n\tR = find(r)\n\tC = find(c)\n\tif R != C:\n\t\tans -= 1\n\t\tf[R] = C\nprint(ans)\n", "class UnionFind:\n\n\tdef __init__(self, n):\n\t\tself.n = n\n\t\tself.parents = [-1] * n\n\n\tdef find(self, x):\n\t\tif self.parents[x] < 0:\n\t\t\treturn x\n\t\telse:\n\t\t\tself.parents[x] = self.find(self.parents[x])\n\t\t\treturn self.parents[x]\n\n\tdef union(self, x, y):\n\t\tx = self.find(x)\n\t\ty = self.find(y)\n\t\tif x == y:\n\t\t\treturn\n\t\tif self.parents[x] > self.parents[y]:\n\t\t\t(x, y) = (y, x)\n\t\tself.parents[x] += self.parents[y]\n\t\tself.parents[y] = x\n\n\tdef size(self, x):\n\t\treturn -self.parents[self.find(x)]\n\n\tdef same(self, x, y):\n\t\treturn self.find(x) == self.find(y)\n\n\tdef members(self, x):\n\t\troot = self.find(x)\n\t\treturn [i for i in range(self.n) if self.find(i) == root]\n\n\tdef roots(self):\n\t\treturn [i for (i, x) in enumerate(self.parents) if x < 0]\n\n\tdef group_count(self):\n\t\treturn len(self.roots())\n\n\tdef all_group_members(self):\n\t\tgroups = {r: [] for r in self.roots()}\n\t\tfor i in range(self.N):\n\t\t\tgroups[self.find(i)].append(i)\n\t\treturn groups\n\n\tdef __str__(self):\n\t\treturn '\\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))\nimport os, io\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(n, m, q) = map(int, input().split())\nuf = UnionFind(n + m)\nfor _ in range(q):\n\t(a, b) = map(int, input().split())\n\tuf.union(a - 1, b - 1 + n)\nprint(uf.group_count() - 1)\n", "from sys import stdin\n\nclass DSU:\n\n\tdef __init__(self, n) -> None:\n\t\tself.parent = [i for i in range(n)]\n\t\tself.rank = [0] * n\n\n\tdef find_set(self, v):\n\t\tw = v\n\t\tparent = self.parent\n\t\twhile parent[v] != v:\n\t\t\tv = parent[v]\n\t\twhile parent[w] != w:\n\t\t\tt = parent[w]\n\t\t\tparent[w] = v\n\t\t\tw = t\n\t\treturn v\n\n\tdef union_sets(self, a, b):\n\t\ta = self.find_set(a)\n\t\tb = self.find_set(b)\n\t\trank = self.rank\n\t\tif a != b:\n\t\t\tif rank[a] < rank[b]:\n\t\t\t\t(rank[a], rank[b]) = (rank[b], rank[a])\n\t\t\tself.parent[b] = a\n\t\t\tif rank[a] == rank[b]:\n\t\t\t\trank[a] += 1\n(n, m, q) = map(int, stdin.readline().split())\ndsu = DSU(n + m)\nfor i in range(q):\n\t(r, c) = map(int, stdin.readline().split())\n\tr -= 1\n\tc -= 1\n\tdsu.union_sets(r, c + n)\nans = -1\nfor i in range(n + m):\n\tif dsu.parent[i] == i:\n\t\tans += 1\nprint(ans)\n"]

difficulty: HARD

source: codeforces

raw_problem:
B. Chemical table

time limit per test
1 second

memory limit per test
512 megabytes

input
standard input

output
standard output

Innopolis University scientists continue to investigate the periodic table. There are n·m known elements and they form a periodic table: a rectangle with n rows and m columns. Each element can be described by its coordinates (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ m) in the table.

Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions (r1, c1), (r1, c2), (r2, c1), where r1 ≠ r2 and c1 ≠ c2, then we can produce element (r2, c2).

Samples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions.

Innopolis University scientists already have samples of q elements. They want to obtain samples of all n·m elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.

Input

The first line contains three integers n, m, q (1 ≤ n, m ≤ 200 000; 0 ≤ q ≤ min(n·m, 200 000)), the chemical table dimensions and the number of elements scientists already have.

The following q lines contain two integers ri, ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m), each describes an element that scientists already have. All elements in the input are different.

Output

Print the minimal number of elements to be purchased.

Examples

Input

2 2 3
1 2
2 2
2 1

Output

0

Input

1 5 3
1 3
1 1
1 5

Output

2

Input

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

Output

1

Note

For each example you have a picture which illustrates it.

The first picture for each example describes the initial set of element samples available. Black crosses represent elements available in the lab initially.

The second picture describes how remaining samples can be obtained. Red dashed circles denote elements that should be purchased from other labs (the optimal solution should minimize the number of red circles). Blue dashed circles are elements that can be produced with nuclear fusion. They are numbered in order in which they can be produced.

Test 1

We can use nuclear fusion and get the element from three other samples, so we don't need to purchase anything.

Test 2

We cannot use any nuclear fusion at all as there is only one row, so we have to purchase all missing elements.

Test 3

There are several possible solutions. One of them is illustrated below.

Note that after purchasing one element marked as red it's still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.

question:
Innopolis University scientists continue to investigate the periodic table. There are n·m known elements and they form a periodic table: a rectangle with n rows and m columns. Each element can be described by its coordinates (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ m) in the table.
Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions (r_{1}, c_{1}), (r_{1}, c_{2}), (r_{2}, c_{1}), where r_{1} ≠ r_{2} and c_{1} ≠ c_{2}, then we can produce element (r_{2}, c_{2}).
 ![image](1.png) Samples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions.
Innopolis University scientists already have samples of q elements. They want to obtain samples of all n·m elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.

Input
The first line contains three integers n, m, q (1 ≤ n, m ≤ 200 000; 0 ≤ q ≤ min(n·m, 200 000)), the chemical table dimensions and the number of elements scientists already have.
The following q lines contain two integers r_{i}, c_{i} (1 ≤ r_{i} ≤ n, 1 ≤ c_{i} ≤ m), each describes an element that scientists already have. All elements in the input are different.

Output
Print the minimal number of elements to be purchased.

Examples
Input
2 2 3
1 2
2 2
2 1

Output
0

Input
1 5 3
1 3
1 1
1 5

Output
2

Input
4 3 6
1 2
1 3
2 2
2 3
3 1
3 3

Output
1

Note
For each example you have a picture which illustrates it.
The first picture for each example describes the initial set of element samples available. Black crosses represent elements available in the lab initially.
The second picture describes how remaining samples can be obtained. Red dashed circles denote elements that should be purchased from other labs (the optimal solution should minimize the number of red circles). Blue dashed circles are elements that can be produced with nuclear fusion. They are numbered in order in which they can be produced.
Test 1
We can use nuclear fusion and get the element from three other samples, so we don't need to purchase anything.
 ![image](2.png) Test 2
We cannot use any nuclear fusion at all as there is only one row, so we have to purchase all missing elements.
 ![image](3.png) Test 3
There are several possible solutions. One of them is illustrated below.
Note that after purchasing one element marked as red it's still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.
 ![image](4.png)

tags: ['Graph algorithms', 'Graph traversal', 'Spanning trees', 'Constructive algorithms', 'Matrices']

raw_tags: ['matrices', 'dfs and similar', 'dsu', 'graphs', 'constructive algorithms']

image_tags: Patterns Patterns Patterns Patterns

data_split: test


D. Spider's Web

problem_index: D

time_limit: 2 seconds

memory_limit: 256 megabytes

solutions: ["import os\nimport sys\nfrom math import *\nfrom collections import *\nfrom bisect import *\nfrom io import BytesIO, IOBase\n\ndef vsInput():\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\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')\nALPHA = 'abcdefghijklmnopqrstuvwxyz/'\nM = 1000000007\nEPS = 1e-06\n\ndef Ceil(a, b):\n\treturn a // b + int(a % b > 0)\n\ndef value():\n\treturn tuple(map(int, input().split()))\n\ndef array():\n\treturn [int(i) for i in input().split()]\n\ndef Int():\n\treturn int(input())\n\ndef Str():\n\treturn input()\n\ndef arrayS():\n\treturn [i for i in input().split()]\nn = Int()\nsector = []\nfor i in range(n):\n\tsector.append(sorted(array()[1:]))\nans = 0\nfor cur in range(n):\n\taage = (cur + 1) % n\n\tpeeche = (cur - 1 + n) % n\n\tfor i in range(1, len(sector[cur])):\n\t\tl = sector[cur][i - 1]\n\t\tr = sector[cur][i]\n\t\tleft_count = bisect_left(sector[peeche], r) - bisect_right(sector[peeche], l)\n\t\tright_count = bisect_left(sector[aage], r) - bisect_right(sector[aage], l)\n\t\tans += left_count != right_count\nprint(ans)\n"]

source: codeforces

raw_problem:
D. Spider's Web

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Paw the Spider is making a web. Web-making is a real art, Paw has been learning to do it his whole life. Let's consider the structure of the web.

There are n main threads going from the center of the web. All main threads are located in one plane and divide it into n equal infinite sectors. The sectors are indexed from 1 to n in the clockwise direction. Sectors i and i + 1 are adjacent for every i, 1 ≤ i < n. In addition, sectors 1 and n are also adjacent.

Some sectors have bridge threads. Each bridge connects the two main threads that make up this sector. The points at which the bridge is attached to the main threads will be called attachment points. Both attachment points of a bridge are at the same distance from the center of the web. At each attachment point exactly one bridge is attached. The bridges are adjacent if they are in the same sector, and there are no other bridges between them.

A cell of the web is a trapezoid, which is located in one of the sectors and is bounded by two main threads and two adjacent bridges. You can see that the sides of the cell may have the attachment points of bridges from adjacent sectors. If the number of attachment points on one side of the cell is not equal to the number of attachment points on the other side, it creates an imbalance of pulling forces on this cell and this may eventually destroy the entire web. We'll call such a cell unstable. The perfect web does not contain unstable cells.

Unstable cells are marked red in the figure. Stable cells are marked green.

Paw the Spider isn't a skillful webmaker yet, he is only learning to make perfect webs. Help Paw to determine the number of unstable cells in the web he has just spun.

Input

The first line contains integer n (3 ≤ n ≤ 1000) — the number of main threads.

The i-th of following n lines describe the bridges located in the i-th sector: first it contains integer ki (1 ≤ ki ≤ 105) equal to the number of bridges in the given sector. Then follow ki different integers pij (1 ≤ pij ≤ 105; 1 ≤ j ≤ ki). Number pij equals the distance from the attachment points of the j-th bridge of the i-th sector to the center of the web.

It is guaranteed that any two bridges between adjacent sectors are attached at a different distance from the center of the web. It is guaranteed that the total number of the bridges doesn't exceed 105.

Output

Print a single integer — the number of unstable cells in Paw the Spider's web.

Examples

Input

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

Output

6

question:
Paw the Spider is making a web. Web-making is a real art, Paw has been learning to do it his whole life. Let's consider the structure of the web.
 ![image](1.png) There are n main threads going from the center of the web. All main threads are located in one plane and divide it into n equal infinite sectors. The sectors are indexed from 1 to n in the clockwise direction. Sectors i and i + 1 are adjacent for every i, 1 ≤ i < n. In addition, sectors 1 and n are also adjacent.
Some sectors have bridge threads. Each bridge connects the two main threads that make up this sector. The points at which the bridge is attached to the main threads will be called attachment points. Both attachment points of a bridge are at the same distance from the center of the web. At each attachment point exactly one bridge is attached. The bridges are adjacent if they are in the same sector, and there are no other bridges between them.
A cell of the web is a trapezoid, which is located in one of the sectors and is bounded by two main threads and two adjacent bridges. You can see that the sides of the cell may have the attachment points of bridges from adjacent sectors. If the number of attachment points on one side of the cell is not equal to the number of attachment points on the other side, it creates an imbalance of pulling forces on this cell and this may eventually destroy the entire web. We'll call such a cell unstable. The perfect web does not contain unstable cells.
Unstable cells are marked red in the figure. Stable cells are marked green.
Paw the Spider isn't a skillful webmaker yet, he is only learning to make perfect webs. Help Paw to determine the number of unstable cells in the web he has just spun.

Input
The first line contains integer n (3 ≤ n ≤ 1000) — the number of main threads.
The i-th of following n lines describe the bridges located in the i-th sector: first it contains integer k_{i} (1 ≤ k_{i} ≤ 10^{5}) equal to the number of bridges in the given sector. Then follow k_{i} different integers p_{ij} (1 ≤ p_{ij} ≤ 10^{5}; 1 ≤ j ≤ k_{i}). Number p_{ij} equals the distance from the attachment points of the j-th bridge of the i-th sector to the center of the web.
It is guaranteed that any two bridges between adjacent sectors are attached at a different distance from the center of the web. It is guaranteed that the total number of the bridges doesn't exceed 10^{5}.

Output
Print a single integer — the number of unstable cells in Paw the Spider's web.

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

Output
6

skill_types: ['Sorting', 'Amortized analysis']

raw_tags: ['two pointers', 'binary search', 'sortings']

data_split: test


F. Nauuo and Bug

problem_index: F

time_limit: 4 seconds

memory_limit: 1024 megabytes

source: codeforces

raw_problem:
F. Nauuo and Bug

time limit per test
4 seconds

memory limit per test
1024 megabytes

input
standard input

output
standard output

Nauuo is a girl who loves coding.

One day she was solving a problem which requires to calculate a sum of some numbers modulo $$$p$$$.

She wrote the following code and got the verdict "Wrong answer".

She soon discovered the bug — the ModAdd function only worked for numbers in the range $$$[0,p)$$$, but the numbers in the problem may be out of the range. She was curious about the wrong function, so she wanted to know the result of it.

However, the original code worked too slow, so she asked you to help her.

You are given an array $$$a_1,a_2,\ldots,a_n$$$ and a number $$$p$$$. Nauuo will make $$$m$$$ queries, in each query, you are given $$$l$$$ and $$$r$$$, and you have to calculate the results of Sum(a,l,r,p). You can see the definition of the Sum function in the pseudocode above.

Note that the integers won't overflow in the code above.

Input

The first line contains three integers $$$n$$$, $$$m$$$, $$$p$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le p \le 10^9$$$) — the length of the given array, the number of queries and the modulus. Note that the modulus is used only in the ModAdd function.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le10^9$$$) — the given array.

In the following $$$m$$$ lines, each line contains two integers $$$l$$$, $$$r$$$ ($$$1\le l\le r\le n$$$) — you have to calculate the result of Sum(a,l,r,p).

Output

The output contains $$$m$$$ integers to answer the queries in the given order.

Example

Input

4 5 6
7 2 -3 17
2 3
1 3
1 2
2 4
4 4

Output

-1
0
3
10
11

question:
Nauuo is a girl who loves coding.
One day she was solving a problem which requires to calculate a sum of some numbers modulo $$$p$$$.
She wrote the following code and got the verdict "Wrong answer".
![image](1.png)
She soon discovered the bug — the ModAdd function only worked for numbers in the range $$$[0,p)$$$, but the numbers in the problem may be out of the range. She was curious about the wrong function, so she wanted to know the result of it.
However, the original code worked too slow, so she asked you to help her.
You are given an array $$$a_1,a_2,\ldots,a_n$$$ and a number $$$p$$$. Nauuo will make $$$m$$$ queries, in each query, you are given $$$l$$$ and $$$r$$$, and you have to calculate the results of Sum(a,l,r,p). You can see the definition of the Sum function in the pseudocode above.
Note that the integers won't overflow in the code above.

Input
The first line contains three integers $$$n$$$, $$$m$$$, $$$p$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le p \le 10^9$$$) — the length of the given array, the number of queries and the modulus. Note that the modulus is used only in the ModAdd function.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le10^9$$$) — the given array.
In the following $$$m$$$ lines, each line contains two integers $$$l$$$, $$$r$$$ ($$$1\le l\le r\le n$$$) — you have to calculate the result of Sum(a,l,r,p).

Output
The output contains $$$m$$$ integers to answer the queries in the given order.

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

Output
-1
0
3
10
11

skill_types: ['Data structures']

data_split: test