#include<iostream>
#include<algorithm>
using namespace std;

bool t[7][200020],vis[7][200020];
long long n,m,q,a;

void DFS(int x,int y,int lim){
	vis[x][y]=true;
	int dx[]={-1,0,0,1},dy[]={0,1,-1,0};
	for(int i=0;i<4;i++){
		int a=x+dx[i],b=y+dy[i];
		if(a>=0&&b>=0&&a<7&&b<lim){
			if(!vis[a][b])DFS(a,b,lim);
		}
	}
}
int Sol(int lim){
	int ret=0;
	for(int i=0;i<7;i++){
		for(int j=0;j<lim;j++){
			vis[i][j]=t[i][j];
			//cout<<t[i][j]<<" ";
		}
		//cout<<endl;
	}
	for(int i=0;i<7;i++){
		for(int j=0;j<lim;j++){
			if(!vis[i][j]){
				ret++;
				DFS(i,j,lim);
			}
		}
	}
	return ret;
}

int main(){
	cin>>n>>m>>q;
	for(int i=0;i<7;i++){
		for(int j=0;j<m;j++){
			t[i][j]=0;
		}
	}
	while(q--){
		cin>>a;
		for(int i=a;i<14*m;i+=m){
			t[i%7][i/7]=1;
		}
	}

	long long k=Sol(m),w=Sol(m*2),ans;
	int g=n/m-1;
	if(g<=0)ans=Sol(n);
	else ans=(g)*(w-k)+Sol(n-(g*m));
	cout<<ans<<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>
using namespace std;

bool t[7][200020],vis[7][200020];
long long n,m,q,a;

void DFS(int x,int y,int lim){
	vis[x][y]=true;
	int dx[]={-1,0,0,1},dy[]={0,1,-1,0};
	for(int i=0;i<4;i++){
		int a=x+dx[i],b=y+dy[i];
		if(a>=0&&b>=0&&a<7&&b<lim){
			if(!vis[a][b])DFS(a,b,lim);
		}
	}
}
int Sol(int lim){
	int ret=0;
	for(int i=0;i<7;i++){
		for(int j=0;j<lim;j++){
			vis[i][j]=t[i][j];
			//cout<<t[i][j]<<" ";
		}
		//cout<<endl;
	}
	for(int i=0;i<7;i++){
		for(int j=0;j<lim;j++){
			if(!vis[i][j]){
				ret++;
				DFS(i,j,lim);
			}
		}
	}
	return ret;
}

int main(){
	cin>>n>>m>>q;
	for(int i=0;i<7;i++){
		for(int j=0;j<m;j++){
			t[i][j]=0;
		}
	}
	while(q--){
		cin>>a;
		for(int i=a;i<14*m;i+=m){
			t[i%7][i/7]=1;
		}
	}

	long long k=Sol(m),w=Sol(m*2),ans;
	int g=n/m-1;
	if(g<=0)ans=Sol(n);
	else ans=(g)*(w-k)+Sol(n-(g*m));
	cout<<ans<<endl;
	return 0;
}
```