#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

LL gcd(LL a, LL b)
{
	if (a < b) std::swap(a, b);
	LL r = a % b;
	while (r != 0)
	{
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

LL lcm(LL a, LL b)
{
	return a / gcd(a, b) * b;
}

std::vector<std::vector<bool>>field;
std::vector<std::vector<bool>>vis;
LL dx[] = { -1,0,0,1 }, dy[] = { 0,-1,1,0 };
void dfs(LL x, LL y)
{
	if (vis[x][y]) return;
	vis[x][y] = true;
	rep(k, 4)
	{
		LL kx = x + dx[k], ky = y + dy[k];
		if (0 <= kx && kx < field.size() && 0 <= ky && ky < field[0].size())
		{
			if (!field[kx][ky] && !vis[kx][ky]) dfs(kx, ky);
		}
	}
}

LL linking_num()
{
	vis.clear();
	vis.resize(field.size());
	rep(i, vis.size()) vis[i].resize(field[i].size(), false);

	LL res = 0;
	rep(i, field.size())
	{
		rep(j, field[i].size())
		{
			if (!field[i][j] && !vis[i][j])
			{
				dfs(i, j);
				++res;
			}
		}
	}

	return res;
}

LL n, m, q;

int main()
{
	in >> n >> m >> q;
	std::vector<LL>a(q);
	rep(i, q) in >> a[i];

	LL height = lcm(m, 7);
	field.resize(height / 7);
	rep(i, field.size()) field[i].resize(7, false);
	rep(x, field.size())
	{
		rep(y, field[x].size())
		{
			LL num = (x * 7 + y) % m;
			auto it = std::lower_bound(a.begin(), a.end(), num);
			if (it != a.end())
			{
				if (*it == num) field[x][y] = true;
			}
		}
	}

	LL first_num = linking_num();
	rep(i, height / 7) field.push_back(field[i]);
	LL diff_num = linking_num() - first_num;

	out << first_num + diff_num * (n / (height / 7) - 1) << std::endl;
	return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

Input Format

The input format is following:



n m q
a_1 a_2 ... a_q


Output Format

Print the number of connected part in one line.


Constraints

* n ≤ 10^{12}
* 7n is divisible by m.
* 1 ≤ q ≤ m ≤ 10^5
* 0 ≤ a_1 < a_2 < ... < a_q < m



Scoring

Subtask 1 [100 points]


* n ≤ 100000.

Subtask 2 [90 points]


* m is divisible by 7.
* a_{i + 1} - a_i = 1.

Subtask 3 [200 points]


* m is divisible by 7.

Subtask 4 [110 points]


* There are no additional constraints.



Sample Input 1


7 7 3
1 3 5


Sample Output 1


4


The calendar looks like this:


<image>

Sample Input 2


10 14 8
5 6 7 8 9 10 11 12


Sample Output 2


10


The calendar looks like this:


<image>

Output Format

Print the number of connected part in one line.


Constraints

* n ≤ 10^{12}
* 7n is divisible by m.
* 1 ≤ q ≤ m ≤ 10^5
* 0 ≤ a_1 < a_2 < ... < a_q < m



Scoring

Subtask 1 [100 points]


* n ≤ 100000.

Subtask 2 [90 points]


* m is divisible by 7.
* a_{i + 1} - a_i = 1.

Subtask 3 [200 points]


* m is divisible by 7.

Subtask 4 [110 points]


* There are no additional constraints.

Input Format

The input format is following:



n m q
a_1 a_2 ... a_q

Examples

Input

7 7 3
1 3 5


Output

4


Input

10 14 8
5 6 7 8 9 10 11 12


Output

10

### Response

```cpp
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

LL gcd(LL a, LL b)
{
	if (a < b) std::swap(a, b);
	LL r = a % b;
	while (r != 0)
	{
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

LL lcm(LL a, LL b)
{
	return a / gcd(a, b) * b;
}

std::vector<std::vector<bool>>field;
std::vector<std::vector<bool>>vis;
LL dx[] = { -1,0,0,1 }, dy[] = { 0,-1,1,0 };
void dfs(LL x, LL y)
{
	if (vis[x][y]) return;
	vis[x][y] = true;
	rep(k, 4)
	{
		LL kx = x + dx[k], ky = y + dy[k];
		if (0 <= kx && kx < field.size() && 0 <= ky && ky < field[0].size())
		{
			if (!field[kx][ky] && !vis[kx][ky]) dfs(kx, ky);
		}
	}
}

LL linking_num()
{
	vis.clear();
	vis.resize(field.size());
	rep(i, vis.size()) vis[i].resize(field[i].size(), false);

	LL res = 0;
	rep(i, field.size())
	{
		rep(j, field[i].size())
		{
			if (!field[i][j] && !vis[i][j])
			{
				dfs(i, j);
				++res;
			}
		}
	}

	return res;
}

LL n, m, q;

int main()
{
	in >> n >> m >> q;
	std::vector<LL>a(q);
	rep(i, q) in >> a[i];

	LL height = lcm(m, 7);
	field.resize(height / 7);
	rep(i, field.size()) field[i].resize(7, false);
	rep(x, field.size())
	{
		rep(y, field[x].size())
		{
			LL num = (x * 7 + y) % m;
			auto it = std::lower_bound(a.begin(), a.end(), num);
			if (it != a.end())
			{
				if (*it == num) field[x][y] = true;
			}
		}
	}

	LL first_num = linking_num();
	rep(i, height / 7) field.push_back(field[i]);
	LL diff_num = linking_num() - first_num;

	out << first_num + diff_num * (n / (height / 7) - 1) << std::endl;
	return 0;
}

```