Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

The following languages are only available languages for the problems from the contest

Unknown Language Round #2:

- Io-2008-01-07 (Win32)

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Oil

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter the nationalization of the oil industry, Dr. Mosaddegh wants to dig some oil wells to extract all the oil in Persian Gulf. But Persian Gulf is huge and has an infinite amount of oil. So Dr. Mosaddegh works only on a rectangular plane of size *n* × *m* of the Persian Gulf. Each of the cells in this rectangle either contains an infinite amount of oil or nothing.

Two cells are considered adjacent if and only if they have a common edge, a path is a sequence *c*_{1}, *c*_{2}, ..., *c*_{x} of cells so that all of them contain oil and for each *i*, *c*_{i} is adjacent to *c*_{i - 1} and *c*_{i + 1} (if they exist). Two cells are considered connected to each other if and only if there exists a path between them. If we dig a well in a certain cell, we can extract oil from all the cells that are connected to it by oil paths. It is not allowed to dig wells on empty cells.

Dr. Mosaddegh also knows that in Persian Gulf, the empty cells form rows and columns. I. e. if some cell is empty, then it's column is completely empty or it's row is completely empty, or both.

Help Dr. Mosaddegh find out how many wells he has to dig to access all the oil in that region.

Input

In the first line there are two positive integers *n* and *m* (1 ≤ *n*, *m* ≤ 100).

In the second line there is an integer *t* (0 ≤ *t* ≤ *n*), the number of empty rows. *t* distinct positive integers follow, these are the numbers of empty rows and are in range [1, *n*].

In the second line there is an integer *s* (0 ≤ *s* ≤ *m*) that shows the number of columns not having any oil. *s* distinct positive integers follow, these are the numbers of empty columns and are in range of [1, *m*].

Note that rows are numbered from 1 to *n* (from top to bottom) and columns are numbered from 1 to *m* (from left to right).

Output

A single integer, the minimum number of wells that Dr. Mossadegh has to dig.

This is actually finding how many regions are made by removing the given rows and columns.

Examples

Input

2 3

1 2

1 2

Output

2

Input

4 4

2 2 3

3 2 3 1

Output

2

Input

2 3

1 1

0

Output

1

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2021 19:39:02 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|