#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef tuple<int, int, int, int> t4;
typedef pair<ll, ll> PL;
typedef long double ldouble;

int A[100010];
int color[1400070];
int ca[100010];
int p[1400070];
int Find(int x){return p[x] == x ? x : p[x] = Find(p[x]); }

void solve(){
	ll n;int m, q; cin >> n >> m >>q;
	for(int i=1;i<=q;i++)scanf("%d", A+i), ca[A[i]] = 1;
	int t = (m % 7 == 0 ? m / 7 : m);
	rep(i, 7*t)p[i] = i;
	rep(i, t)rep(j, 7){
		int v = i * 7 + j;
		if(ca[v % m])color[v] = 1;
		if(i && color[v] == 0 && color[v-7] == 0)p[Find(v)] = Find(v-7);
		if(j && color[v] == 0 && color[v-1] == 0)p[Find(v)] = Find(v-1);
	}
	ll ans = 0;
	rep(i, 7*t)if(color[i] == 0 && p[i] == i)ans++;
	if(t == n){
		printf("%lld\n", ans);
		return;
	}
	ll ans2 = 0;
	t = t * 2;
	rep(i, 7*t)p[i] = i;
	rep(i, t)rep(j, 7){
		int v = i * 7 + j;
		if(ca[v % m])color[v] = 1;
		if(i && color[v] == 0 && color[v-7] == 0)p[Find(v)] = Find(v-7);
		if(j && color[v] == 0 && color[v-1] == 0)p[Find(v)] = Find(v-1);
	}
	rep(i, 7*t)if(color[i] == 0 && p[i] == i)ans2++;
	ans2 -= ans;
	printf("%lld\n", ans + ans2 * (n / (t / 2) - 1));
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d: ", tc);
		solve();
	}
	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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef tuple<int, int, int, int> t4;
typedef pair<ll, ll> PL;
typedef long double ldouble;

int A[100010];
int color[1400070];
int ca[100010];
int p[1400070];
int Find(int x){return p[x] == x ? x : p[x] = Find(p[x]); }

void solve(){
	ll n;int m, q; cin >> n >> m >>q;
	for(int i=1;i<=q;i++)scanf("%d", A+i), ca[A[i]] = 1;
	int t = (m % 7 == 0 ? m / 7 : m);
	rep(i, 7*t)p[i] = i;
	rep(i, t)rep(j, 7){
		int v = i * 7 + j;
		if(ca[v % m])color[v] = 1;
		if(i && color[v] == 0 && color[v-7] == 0)p[Find(v)] = Find(v-7);
		if(j && color[v] == 0 && color[v-1] == 0)p[Find(v)] = Find(v-1);
	}
	ll ans = 0;
	rep(i, 7*t)if(color[i] == 0 && p[i] == i)ans++;
	if(t == n){
		printf("%lld\n", ans);
		return;
	}
	ll ans2 = 0;
	t = t * 2;
	rep(i, 7*t)p[i] = i;
	rep(i, t)rep(j, 7){
		int v = i * 7 + j;
		if(ca[v % m])color[v] = 1;
		if(i && color[v] == 0 && color[v-7] == 0)p[Find(v)] = Find(v-7);
		if(j && color[v] == 0 && color[v-1] == 0)p[Find(v)] = Find(v-1);
	}
	rep(i, 7*t)if(color[i] == 0 && p[i] == i)ans2++;
	ans2 -= ans;
	printf("%lld\n", ans + ans2 * (n / (t / 2) - 1));
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}
```