#include <cstdio>
int par[1400010];
int b[1400010];
int find(int x) {
	return par[x] == x ? x : (par[x] = find(par[x]));
}
void unite(int x, int y) {
	par[find(x)] = find(y);
}
int ban[100010];
int main() {
	long long n;
	int m, q;
	scanf("%lld%d%d", &n, &m, &q);
	for (int i = 0; i < q; i++) {
		int x;
		scanf("%d", &x);
		ban[x] = 1;
	}
	if (m == 1) {
		printf("0\n");
		return 0;
	}
	for (int i = 0; i < 1400010; i++) {
		par[i] = i;
	}
	int k = 0;
	long long c[2] = {};
	c[0] = -1;
	for (long long i = 0; i < n; i++) {
		for (int j = 0; j < 7; j++) {
			b[k+j] = ban[(k + j) %  m];
		}
		for (int j = 0; j < 6; j++) {
			if (!b[k+j] && !b[k+j+1]) {
				unite(k + j, k + j + 1);
			}
		}
		for (int j = 0; j < 7; j++) {
			if (k && !b[k+j] && !b[k+j-7]) {
				unite(k + j, k + j - 7);
			}
		}
		if (i % m == m - 1) {
			c[i/m] = 0;
			for (int j = 0; j < i * 7 + 7; j++) {
				if (!b[j] && find(j) == j) {
					c[i/m]++;
				}
			}
			if (i == 2 * m - 1) {
				break;
			}
		}
		k += 7;
	}
	long long p = n / m, qu = n % m;
	long long ans = 0;
	if (p == 0 || c[0] == -1) {
		for (int j = 0; j < n * 7; j++) {
			if (!b[j] && find(j) == j) {
				ans++;
			}
		}
	} else {
		ans = c[0];
		ans += (c[1] - c[0]) * (p - 1);
		for (int j = m * 7; j < (m + qu) * 7; j++) {
			if (!b[j] && find(j) == j) {
				ans++;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

### Prompt

Please formulate a Cpp solution 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 <cstdio>
int par[1400010];
int b[1400010];
int find(int x) {
	return par[x] == x ? x : (par[x] = find(par[x]));
}
void unite(int x, int y) {
	par[find(x)] = find(y);
}
int ban[100010];
int main() {
	long long n;
	int m, q;
	scanf("%lld%d%d", &n, &m, &q);
	for (int i = 0; i < q; i++) {
		int x;
		scanf("%d", &x);
		ban[x] = 1;
	}
	if (m == 1) {
		printf("0\n");
		return 0;
	}
	for (int i = 0; i < 1400010; i++) {
		par[i] = i;
	}
	int k = 0;
	long long c[2] = {};
	c[0] = -1;
	for (long long i = 0; i < n; i++) {
		for (int j = 0; j < 7; j++) {
			b[k+j] = ban[(k + j) %  m];
		}
		for (int j = 0; j < 6; j++) {
			if (!b[k+j] && !b[k+j+1]) {
				unite(k + j, k + j + 1);
			}
		}
		for (int j = 0; j < 7; j++) {
			if (k && !b[k+j] && !b[k+j-7]) {
				unite(k + j, k + j - 7);
			}
		}
		if (i % m == m - 1) {
			c[i/m] = 0;
			for (int j = 0; j < i * 7 + 7; j++) {
				if (!b[j] && find(j) == j) {
					c[i/m]++;
				}
			}
			if (i == 2 * m - 1) {
				break;
			}
		}
		k += 7;
	}
	long long p = n / m, qu = n % m;
	long long ans = 0;
	if (p == 0 || c[0] == -1) {
		for (int j = 0; j < n * 7; j++) {
			if (!b[j] && find(j) == j) {
				ans++;
			}
		}
	} else {
		ans = c[0];
		ans += (c[1] - c[0]) * (p - 1);
		for (int j = m * 7; j < (m + qu) * 7; j++) {
			if (!b[j] && find(j) == j) {
				ans++;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

```