#include <bits/stdc++.h>
using namespace std;

long long N;
int M, X, rows;
vector<int> V;
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
bool b[200005][7], avail[100005], vis[200005][7];

bool cv(int x, int y) {
	if (x < 0 || x >= rows) return false;
	if (y < 0 || y >= 7) return false;
	if (!b[x][y]) return false;
	if (vis[x][y]) return false;
	return true;
}

void dfs(int x, int y) {
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int newx = x + dir[i][0], newy = y + dir[i][1];
		if (cv(newx, newy)) dfs(newx, newy);
	}
}

int cc(long long x, long long y) { // count CCs from row x to y
	memset(b, 0, sizeof(b));
	memset(vis, 0, sizeof(vis));
	for (long long r = x; r <= y; r++) {
		for (int c = 0; c < 7; c++) {
			long long idx = r * 7 + c;
			b[r-x][c] = avail[idx % M];
		}
	}
	int ans = 0;
	rows = y - x + 1;
	for (int r = 0; r < y - x + 1; r++) {
		for (int c = 0; c < 7; c++) {
			if (b[r][c] && !vis[r][c]) {
				dfs(r, c);
				ans++;
			}
		}
	}
	return ans;
}

int main() {
	scanf("%lld%d%d", &N, &M, &X);
	for (int i = 0; i < M; i++) avail[i] = 1;
	for (int i = 0; i < X; i++) {
		int a;
		scanf("%d", &a);
		V.push_back(a);
		avail[a] = 0;
	}
	if (N <= 2 * M) {
		printf("%d\n", cc(0, N - 1));
		return 0;
	}
	int one = cc(0, M - 1);
	int two = cc(0, 2 * M - 1);
	int subtract = one * 2 - two;
	int rows = N / M;
	printf("%lld\n", (long long)one * (rows - 1) - (long long)subtract * (rows - 1) + cc((long long)(rows - 1) * M, N - 1));
}

### Prompt

Your challenge is to write 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 <bits/stdc++.h>
using namespace std;

long long N;
int M, X, rows;
vector<int> V;
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
bool b[200005][7], avail[100005], vis[200005][7];

bool cv(int x, int y) {
	if (x < 0 || x >= rows) return false;
	if (y < 0 || y >= 7) return false;
	if (!b[x][y]) return false;
	if (vis[x][y]) return false;
	return true;
}

void dfs(int x, int y) {
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int newx = x + dir[i][0], newy = y + dir[i][1];
		if (cv(newx, newy)) dfs(newx, newy);
	}
}

int cc(long long x, long long y) { // count CCs from row x to y
	memset(b, 0, sizeof(b));
	memset(vis, 0, sizeof(vis));
	for (long long r = x; r <= y; r++) {
		for (int c = 0; c < 7; c++) {
			long long idx = r * 7 + c;
			b[r-x][c] = avail[idx % M];
		}
	}
	int ans = 0;
	rows = y - x + 1;
	for (int r = 0; r < y - x + 1; r++) {
		for (int c = 0; c < 7; c++) {
			if (b[r][c] && !vis[r][c]) {
				dfs(r, c);
				ans++;
			}
		}
	}
	return ans;
}

int main() {
	scanf("%lld%d%d", &N, &M, &X);
	for (int i = 0; i < M; i++) avail[i] = 1;
	for (int i = 0; i < X; i++) {
		int a;
		scanf("%d", &a);
		V.push_back(a);
		avail[a] = 0;
	}
	if (N <= 2 * M) {
		printf("%d\n", cc(0, N - 1));
		return 0;
	}
	int one = cc(0, M - 1);
	int two = cc(0, 2 * M - 1);
	int subtract = one * 2 - two;
	int rows = N / M;
	printf("%lld\n", (long long)one * (rows - 1) - (long long)subtract * (rows - 1) + cc((long long)(rows - 1) * M, N - 1));
}

```