#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"
#include "stack"
#include "tuple"

#define rep(n) for (int i = 0; i < n; ++i)
#define REP(n,i) for (int i = 0; i < n; ++i)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
#define mkt make_tuple
#define P pair<ll, ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;

ll n, m, q, a[100000], cnt = 0, cnt2 = 0, h;
bool b[7][200000];

int dfs(int x, int y) {
	b[x][y] = false;
	if (x != 0 && b[x - 1][y])
		dfs(x - 1, y);
	if (x != 6 && b[x + 1][y])
		dfs(x + 1, y);
	if (y != 0 && b[x][y - 1])
		dfs(x, y - 1);
	if (y != h - 1 && b[x][y + 1])
		dfs(x, y + 1);
	return 0;
}

int main() {
	cin >> n >> m >> q;
	rep(q)
		cin >> a[i];
	if (m % 7) {
		rep(7)
			REP(200000, j)
				b[i][j] = true;
		rep(q) {
			REP(7, j) {
				b[(a[i] + m*j) % 7][(a[i] + m*j) / 7] =false;
			}
		}
		h = m;
		rep(m * 7) {
			if (b[i % 7][i / 7]) {
				++cnt;
				dfs(i % 7, i / 7);
			}
		}
		rep(7)
			REP(200000, j)
				b[i][j] = true;
		rep(q) {
			REP(14, j) {
				b[(a[i] + m*j) % 7][(a[i] + m*j) / 7] = false;
			}
		}
		h = m * 2;
		rep(m * 14) {
			if (b[i % 7][i / 7]) {
				++cnt2;
				dfs(i % 7, i / 7);
			}
		}
		cout << cnt + (cnt2 - cnt)*(n / m - 1) << endl;
		return 0;
	}
	else {
		rep(7)
			REP(200000, j)
				b[i][j] = true;
		rep(q) {
			b[a[i] % 7][a[i] / 7] = false;
		}
		h = m / 7;
		rep(m) {
			if (b[i % 7][i / 7]) {
				++cnt;
				dfs(i % 7, i / 7);
			}
		}
		rep(7)
			REP(200000, j)
				b[i][j] = true;
		rep(q) {
			REP(2, j) {
				b[(a[i] + m*j) % 7][(a[i] + m*j) / 7] = false;
			}
		}
		h = m * 2 / 7;
		rep(m * 2) {
			if (b[i % 7][i / 7]) {
				++cnt2;
				dfs(i % 7, i / 7);
			}
		}
		cout << cnt + (cnt2 - cnt)*(n * 7 / m - 1) << endl;
	}
	return 0;
}
### Prompt

Create a solution in CPP for 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 "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"
#include "stack"
#include "tuple"

#define rep(n) for (int i = 0; i < n; ++i)
#define REP(n,i) for (int i = 0; i < n; ++i)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
#define mkt make_tuple
#define P pair<ll, ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;

ll n, m, q, a[100000], cnt = 0, cnt2 = 0, h;
bool b[7][200000];

int dfs(int x, int y) {
	b[x][y] = false;
	if (x != 0 && b[x - 1][y])
		dfs(x - 1, y);
	if (x != 6 && b[x + 1][y])
		dfs(x + 1, y);
	if (y != 0 && b[x][y - 1])
		dfs(x, y - 1);
	if (y != h - 1 && b[x][y + 1])
		dfs(x, y + 1);
	return 0;
}

int main() {
	cin >> n >> m >> q;
	rep(q)
		cin >> a[i];
	if (m % 7) {
		rep(7)
			REP(200000, j)
				b[i][j] = true;
		rep(q) {
			REP(7, j) {
				b[(a[i] + m*j) % 7][(a[i] + m*j) / 7] =false;
			}
		}
		h = m;
		rep(m * 7) {
			if (b[i % 7][i / 7]) {
				++cnt;
				dfs(i % 7, i / 7);
			}
		}
		rep(7)
			REP(200000, j)
				b[i][j] = true;
		rep(q) {
			REP(14, j) {
				b[(a[i] + m*j) % 7][(a[i] + m*j) / 7] = false;
			}
		}
		h = m * 2;
		rep(m * 14) {
			if (b[i % 7][i / 7]) {
				++cnt2;
				dfs(i % 7, i / 7);
			}
		}
		cout << cnt + (cnt2 - cnt)*(n / m - 1) << endl;
		return 0;
	}
	else {
		rep(7)
			REP(200000, j)
				b[i][j] = true;
		rep(q) {
			b[a[i] % 7][a[i] / 7] = false;
		}
		h = m / 7;
		rep(m) {
			if (b[i % 7][i / 7]) {
				++cnt;
				dfs(i % 7, i / 7);
			}
		}
		rep(7)
			REP(200000, j)
				b[i][j] = true;
		rep(q) {
			REP(2, j) {
				b[(a[i] + m*j) % 7][(a[i] + m*j) / 7] = false;
			}
		}
		h = m * 2 / 7;
		rep(m * 2) {
			if (b[i % 7][i / 7]) {
				++cnt2;
				dfs(i % 7, i / 7);
			}
		}
		cout << cnt + (cnt2 - cnt)*(n * 7 / m - 1) << endl;
	}
	return 0;
}
```