#include<bits/stdc++.h>
using namespace std;
long long int n2;
int m,q,ct,n;
int f[111111][7];
bool g[111111];
void dfs(int x,int y){
	if(x<0 || x>=n || y<0 || y>=7 || f[x][y]!=-2)return;
	f[x][y] = ct;
	dfs(x-1,y);
	dfs(x,y-1);
	dfs(x+1,y);
	dfs(x,y+1);
}

set<int> S;
set<pair<int,int> > E;
int ace[99];
int ancestor(int x){return x-ace[x]?ace[x]=ancestor(ace[x]):x;}
int calc(){
	map<int,int> Map;
	int z = 0;
	for(set<int>::iterator it = S.begin(); it!=S.end(); it++){
		Map[*it] = z++;
	}
	for(int i=0; i<z; i++)
		ace[i] = i;
	for(set<pair<int,int> >::iterator it = E.begin(); it!=E.end(); it++){
		ace[ancestor(Map[it->first])]=ancestor(Map[it->second]);
	}
	int res = 0;
	for(int i=0; i<z; i++){
		if(ancestor(i) == i)
			res++;
	}
	return z - res;
}

int main(){
	cin>>n2>>m>>q;
	if(m%7==0)
		n=m/7;
	else
		n=m;

	for(int i=0; i<q; i++){
		int x;
		cin>>x;
		g[x] = true;
	}
	memset(f,-1,sizeof(f));
	for(int i=0; i<n; i++)
		for(int j=0; j<7; j++)
			if(!g[(i*7+j)%m])
				f[i][j] = -2;
	for(int i=0; i<n; i++)
	for(int j=0; j<7; j++)
	if(f[i][j] == -2){
		dfs(i,j);
		ct++;
	}
	for(int j=0; j<7; j++){
		int x = f[0][j], y=f[n-1][j];
		if(x!=-1)S.insert(x);
		if(y!=-1)S.insert(y+ct);
		if(x!=-1 && y!=-1){
			E.insert(make_pair(x,y+ct));
		}
	}
	int dec = calc();
	cout << (n2 / n) * ct - (n2/n-1)*dec << 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<bits/stdc++.h>
using namespace std;
long long int n2;
int m,q,ct,n;
int f[111111][7];
bool g[111111];
void dfs(int x,int y){
	if(x<0 || x>=n || y<0 || y>=7 || f[x][y]!=-2)return;
	f[x][y] = ct;
	dfs(x-1,y);
	dfs(x,y-1);
	dfs(x+1,y);
	dfs(x,y+1);
}

set<int> S;
set<pair<int,int> > E;
int ace[99];
int ancestor(int x){return x-ace[x]?ace[x]=ancestor(ace[x]):x;}
int calc(){
	map<int,int> Map;
	int z = 0;
	for(set<int>::iterator it = S.begin(); it!=S.end(); it++){
		Map[*it] = z++;
	}
	for(int i=0; i<z; i++)
		ace[i] = i;
	for(set<pair<int,int> >::iterator it = E.begin(); it!=E.end(); it++){
		ace[ancestor(Map[it->first])]=ancestor(Map[it->second]);
	}
	int res = 0;
	for(int i=0; i<z; i++){
		if(ancestor(i) == i)
			res++;
	}
	return z - res;
}

int main(){
	cin>>n2>>m>>q;
	if(m%7==0)
		n=m/7;
	else
		n=m;

	for(int i=0; i<q; i++){
		int x;
		cin>>x;
		g[x] = true;
	}
	memset(f,-1,sizeof(f));
	for(int i=0; i<n; i++)
		for(int j=0; j<7; j++)
			if(!g[(i*7+j)%m])
				f[i][j] = -2;
	for(int i=0; i<n; i++)
	for(int j=0; j<7; j++)
	if(f[i][j] == -2){
		dfs(i,j);
		ct++;
	}
	for(int j=0; j<7; j++){
		int x = f[0][j], y=f[n-1][j];
		if(x!=-1)S.insert(x);
		if(y!=-1)S.insert(y+ct);
		if(x!=-1 && y!=-1){
			E.insert(make_pair(x,y+ct));
		}
	}
	int dec = calc();
	cout << (n2 / n) * ct - (n2/n-1)*dec << endl;
	return 0;
}

```