#include<deque>
#include<queue>
#include<map>
#include<string>
#include<iostream>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
//#define scanf scanf_s
#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple
#define pub push_back
using namespace std;
typedef long long int llint;
const llint one = 1;
const llint big = (one<<30);
const llint mod=1000000007;


int main(void){
	llint N,ans;
	int M,q,i,j,a,ansa,ansb,ok=0;
	queue<int> que;
	vector<int> nuru;
	vector<int> siro;//0=siro 1=kuro
	int hkazu;
	scanf("%lld %d %d",&N,&M,&q);
	for(i=0;i<q;i++){
		scanf("%d",&a);
		nuru.pub(a);
	}
	
	if(M%7!=0){ 
		for(i=0;i<q;i++){
			for(j=1;j<7;j++){
				nuru.pub(nuru[i]+M*j);
			}
		}
		M*=7;ok=1;
	}
	siro.resize(M);
	for(i=0;i<nuru.size();i++){
		siro[nuru[i]]=1;
	}
	hkazu=M-nuru.size();
	ansa=0;
	for(i=0;i<M;i++){
		if(siro[i]==1){ continue; }
		que.push(i);
		while(!que.empty()){
			hkazu--;
			a=que.front();
			que.pop();
			if(siro[a]==1){continue;}
			siro[a]=1;
			if(a-7>=0&&siro[a-7]==0){ que.push(a-7); }
			if(a+7<M&&siro[a+7]==0){ que.push(a+7); }
			if(a%7!=0&&siro[a-1]==0){ que.push(a-1); }
			if(a%7!=6&&siro[a+1]==0){ que.push(a+1); }

		}
		ansa++;
	}
	siro.clear();
	siro.resize(M*2);
	for(i=0;i<nuru.size();i++){
		siro[nuru[i]]=1;siro[nuru[i]+M]=1;
	}
	hkazu=M*2-nuru.size();
	ansb=0;
	for(i=0;i<M*2;i++){
		if(siro[i]==1){continue;}
		que.push(i);
		while(!que.empty()){
			hkazu--;
			a=que.front();
			que.pop();
			if(siro[a]==1){ continue; }
			siro[a]=1;
			if(a-7>=0&&siro[a-7]==0){ que.push(a-7); }
			if(a+7<M*2&&siro[a+7]==0){ que.push(a+7); }
			if(a%7!=0&&siro[a-1]==0){ que.push(a-1); }
			if(a%7!=6&&siro[a+1]==0){ que.push(a+1); }
		}
		ansb++;
	}
	ans=(ansb-ansa)*N*7/M+(2*ansa-ansb);
	printf("%lld\n",ans);
	return 0;
}


### Prompt

Develop a solution in Cpp to the problem described below:

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<deque>
#include<queue>
#include<map>
#include<string>
#include<iostream>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
//#define scanf scanf_s
#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple
#define pub push_back
using namespace std;
typedef long long int llint;
const llint one = 1;
const llint big = (one<<30);
const llint mod=1000000007;


int main(void){
	llint N,ans;
	int M,q,i,j,a,ansa,ansb,ok=0;
	queue<int> que;
	vector<int> nuru;
	vector<int> siro;//0=siro 1=kuro
	int hkazu;
	scanf("%lld %d %d",&N,&M,&q);
	for(i=0;i<q;i++){
		scanf("%d",&a);
		nuru.pub(a);
	}
	
	if(M%7!=0){ 
		for(i=0;i<q;i++){
			for(j=1;j<7;j++){
				nuru.pub(nuru[i]+M*j);
			}
		}
		M*=7;ok=1;
	}
	siro.resize(M);
	for(i=0;i<nuru.size();i++){
		siro[nuru[i]]=1;
	}
	hkazu=M-nuru.size();
	ansa=0;
	for(i=0;i<M;i++){
		if(siro[i]==1){ continue; }
		que.push(i);
		while(!que.empty()){
			hkazu--;
			a=que.front();
			que.pop();
			if(siro[a]==1){continue;}
			siro[a]=1;
			if(a-7>=0&&siro[a-7]==0){ que.push(a-7); }
			if(a+7<M&&siro[a+7]==0){ que.push(a+7); }
			if(a%7!=0&&siro[a-1]==0){ que.push(a-1); }
			if(a%7!=6&&siro[a+1]==0){ que.push(a+1); }

		}
		ansa++;
	}
	siro.clear();
	siro.resize(M*2);
	for(i=0;i<nuru.size();i++){
		siro[nuru[i]]=1;siro[nuru[i]+M]=1;
	}
	hkazu=M*2-nuru.size();
	ansb=0;
	for(i=0;i<M*2;i++){
		if(siro[i]==1){continue;}
		que.push(i);
		while(!que.empty()){
			hkazu--;
			a=que.front();
			que.pop();
			if(siro[a]==1){ continue; }
			siro[a]=1;
			if(a-7>=0&&siro[a-7]==0){ que.push(a-7); }
			if(a+7<M*2&&siro[a+7]==0){ que.push(a+7); }
			if(a%7!=0&&siro[a-1]==0){ que.push(a-1); }
			if(a%7!=6&&siro[a+1]==0){ que.push(a+1); }
		}
		ansb++;
	}
	ans=(ansb-ansa)*N*7/M+(2*ansa-ansb);
	printf("%lld\n",ans);
	return 0;
}


```