#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXPERIOD=100000;
const int MAXBLOCKROWS=MAXPERIOD;
const int DX[]={-1,0,+1,0},DY[]={0,+1,0,-1};
typedef struct R { ll cnt; int top[7],bot[7]; } R;

ll nrows; int period,nq;
int fullblockrows,lastblockrows;

bool black[MAXBLOCKROWS][7];
int comp[MAXBLOCKROWS][7],ncomp;
int qx[MAXBLOCKROWS*7],qy[MAXBLOCKROWS*7],qhead,qtail;

R norm(const R &a) {
	R ret; ret.cnt=a.cnt; map<int,int> id; int nid=0;
	REP(i,7) {
		if(a.top[i]!=-1&&!id.count(a.top[i])) id[a.top[i]]=nid++;
		ret.top[i]=a.top[i]==-1?-1:id[a.top[i]];
	}
	REP(i,7) {
		if(a.bot[i]!=-1&&!id.count(a.bot[i])) id[a.bot[i]]=nid++;
		ret.bot[i]=a.bot[i]==-1?-1:id[a.bot[i]];
	}
	return ret;
}

R calc(int nrows) {
	memset(comp,-1,sizeof(comp)); ncomp=0; qhead=qtail=0;
	REP(sx,nrows) REP(sy,7) if(!black[sx][sy]&&comp[sx][sy]==-1) {
		comp[sx][sy]=ncomp++; qx[qhead]=sx,qy[qhead]=sy,++qhead;
		while(qtail<qhead) {
			int x=qx[qtail],y=qy[qtail]; ++qtail;
			REP(k,4) {
				int nx=x+DX[k],ny=y+DY[k];
				if(nx<0||nx>=nrows||ny<0||ny>=7||black[nx][ny]||comp[nx][ny]!=-1) continue;
				comp[nx][ny]=comp[sx][sy]; qx[qhead]=nx,qy[qhead]=ny,++qhead;
			}
		}
	}
	R ret; ret.cnt=0; REP(i,7) ret.top[i]=comp[0][i],ret.bot[i]=comp[nrows-1][i];
	REP(c,ncomp) { bool found=false; REP(i,7) if(ret.top[i]==c||ret.bot[i]==c) found=true; if(!found) ++ret.cnt; }
	ret=norm(ret);
	//printf("calc(%d)=%lld [",nrows,ret.cnt); REP(i,7) printf("%d%c",ret.top[i],i==6?']':','); printf(" ["); REP(i,7) printf("%d%c",ret.bot[i],i==6?']':','); printf("\n");
	return ret;
}

void merge(map<int,int> &id,int a,int b) {
	a=id[a]; b=id[b]; if(a==b) return;
	for(map<int,int>::iterator it=id.begin();it!=id.end();++it) if(it->second==b) it->second=a;
}

R combine(R a,R b) {
	R ret; ret.cnt=a.cnt+b.cnt;
	map<int,int> id;
	REP(i,7) if(a.top[i]!=-1) id[a.top[i]]=a.top[i];
	REP(i,7) if(a.bot[i]!=-1) id[a.bot[i]]=a.bot[i];
	REP(i,7) if(b.top[i]!=-1) id[14+b.top[i]]=14+b.top[i];
	REP(i,7) if(b.bot[i]!=-1) id[14+b.bot[i]]=14+b.bot[i];
	REP(i,7) if(a.bot[i]!=-1&&b.top[i]!=-1) merge(id,a.bot[i],14+b.top[i]);
	REP(i,7) ret.top[i]=a.top[i]==-1?-1:id[a.top[i]];
	REP(i,7) ret.bot[i]=b.bot[i]==-1?-1:id[14+b.bot[i]];
	for(map<int,int>::iterator it=id.begin();it!=id.end();++it) {
		if(it->first!=it->second) continue;
		int c=it->first;
		bool found=false; REP(i,7) if(ret.top[i]==c||ret.bot[i]==c) found=true; if(!found) ++ret.cnt;
	}
	ret=norm(ret);
	//printf("combine=%lld [",ret.cnt); REP(i,7) printf("%d%c",ret.top[i],i==6?']':','); printf(" ["); REP(i,7) printf("%d%c",ret.bot[i],i==6?']':','); printf("\n");
	//printf("\ta=%lld [",a.cnt); REP(i,7) printf("%d%c",a.top[i],i==6?']':','); printf(" ["); REP(i,7) printf("%d%c",a.bot[i],i==6?']':','); printf("\n");
	//printf("\tb=%lld [",b.cnt); REP(i,7) printf("%d%c",b.top[i],i==6?']':','); printf(" ["); REP(i,7) printf("%d%c",b.bot[i],i==6?']':','); printf("\n");
	return ret;
}

R pw(R x,ll n) {
	if(n==1) return x;
	if(n%2==1) return combine(pw(x,n-1),x);
	return pw(combine(x,x),n/2);
}

void run() {
	scanf("%lld%d%d",&nrows,&period,&nq);
	fullblockrows=period/gcd(7,period); lastblockrows=nrows%fullblockrows;
	memset(black,false,sizeof(black));
	REP(i,nq) { int x; scanf("%d",&x); for(int j=x;j<7*fullblockrows;j+=period) black[j/7][j%7]=true; }
	//REP(x,fullblockrows) { REP(y,7) printf("%c",black[x][y]?'X':'.'); puts(""); }

	R onefull=calc(fullblockrows);
	ll numfullblocks=nrows/fullblockrows;
	R allfull=pw(onefull,numfullblocks);
	R all=allfull;
	if(lastblockrows!=0) {
		R last=calc(lastblockrows);
		all=combine(all,last);
	}
	ll ret=all.cnt;
	set<int> seen;
	REP(i,7) if(all.top[i]!=-1&&!seen.count(all.top[i])) seen.insert(all.top[i]),++ret;
	REP(i,7) if(all.bot[i]!=-1&&!seen.count(all.bot[i])) seen.insert(all.bot[i]),++ret;
	printf("%lld\n",ret);
}

int main() {
	run();
	return 0;
}

### Prompt

Your challenge is to write a Cpp solution 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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXPERIOD=100000;
const int MAXBLOCKROWS=MAXPERIOD;
const int DX[]={-1,0,+1,0},DY[]={0,+1,0,-1};
typedef struct R { ll cnt; int top[7],bot[7]; } R;

ll nrows; int period,nq;
int fullblockrows,lastblockrows;

bool black[MAXBLOCKROWS][7];
int comp[MAXBLOCKROWS][7],ncomp;
int qx[MAXBLOCKROWS*7],qy[MAXBLOCKROWS*7],qhead,qtail;

R norm(const R &a) {
	R ret; ret.cnt=a.cnt; map<int,int> id; int nid=0;
	REP(i,7) {
		if(a.top[i]!=-1&&!id.count(a.top[i])) id[a.top[i]]=nid++;
		ret.top[i]=a.top[i]==-1?-1:id[a.top[i]];
	}
	REP(i,7) {
		if(a.bot[i]!=-1&&!id.count(a.bot[i])) id[a.bot[i]]=nid++;
		ret.bot[i]=a.bot[i]==-1?-1:id[a.bot[i]];
	}
	return ret;
}

R calc(int nrows) {
	memset(comp,-1,sizeof(comp)); ncomp=0; qhead=qtail=0;
	REP(sx,nrows) REP(sy,7) if(!black[sx][sy]&&comp[sx][sy]==-1) {
		comp[sx][sy]=ncomp++; qx[qhead]=sx,qy[qhead]=sy,++qhead;
		while(qtail<qhead) {
			int x=qx[qtail],y=qy[qtail]; ++qtail;
			REP(k,4) {
				int nx=x+DX[k],ny=y+DY[k];
				if(nx<0||nx>=nrows||ny<0||ny>=7||black[nx][ny]||comp[nx][ny]!=-1) continue;
				comp[nx][ny]=comp[sx][sy]; qx[qhead]=nx,qy[qhead]=ny,++qhead;
			}
		}
	}
	R ret; ret.cnt=0; REP(i,7) ret.top[i]=comp[0][i],ret.bot[i]=comp[nrows-1][i];
	REP(c,ncomp) { bool found=false; REP(i,7) if(ret.top[i]==c||ret.bot[i]==c) found=true; if(!found) ++ret.cnt; }
	ret=norm(ret);
	//printf("calc(%d)=%lld [",nrows,ret.cnt); REP(i,7) printf("%d%c",ret.top[i],i==6?']':','); printf(" ["); REP(i,7) printf("%d%c",ret.bot[i],i==6?']':','); printf("\n");
	return ret;
}

void merge(map<int,int> &id,int a,int b) {
	a=id[a]; b=id[b]; if(a==b) return;
	for(map<int,int>::iterator it=id.begin();it!=id.end();++it) if(it->second==b) it->second=a;
}

R combine(R a,R b) {
	R ret; ret.cnt=a.cnt+b.cnt;
	map<int,int> id;
	REP(i,7) if(a.top[i]!=-1) id[a.top[i]]=a.top[i];
	REP(i,7) if(a.bot[i]!=-1) id[a.bot[i]]=a.bot[i];
	REP(i,7) if(b.top[i]!=-1) id[14+b.top[i]]=14+b.top[i];
	REP(i,7) if(b.bot[i]!=-1) id[14+b.bot[i]]=14+b.bot[i];
	REP(i,7) if(a.bot[i]!=-1&&b.top[i]!=-1) merge(id,a.bot[i],14+b.top[i]);
	REP(i,7) ret.top[i]=a.top[i]==-1?-1:id[a.top[i]];
	REP(i,7) ret.bot[i]=b.bot[i]==-1?-1:id[14+b.bot[i]];
	for(map<int,int>::iterator it=id.begin();it!=id.end();++it) {
		if(it->first!=it->second) continue;
		int c=it->first;
		bool found=false; REP(i,7) if(ret.top[i]==c||ret.bot[i]==c) found=true; if(!found) ++ret.cnt;
	}
	ret=norm(ret);
	//printf("combine=%lld [",ret.cnt); REP(i,7) printf("%d%c",ret.top[i],i==6?']':','); printf(" ["); REP(i,7) printf("%d%c",ret.bot[i],i==6?']':','); printf("\n");
	//printf("\ta=%lld [",a.cnt); REP(i,7) printf("%d%c",a.top[i],i==6?']':','); printf(" ["); REP(i,7) printf("%d%c",a.bot[i],i==6?']':','); printf("\n");
	//printf("\tb=%lld [",b.cnt); REP(i,7) printf("%d%c",b.top[i],i==6?']':','); printf(" ["); REP(i,7) printf("%d%c",b.bot[i],i==6?']':','); printf("\n");
	return ret;
}

R pw(R x,ll n) {
	if(n==1) return x;
	if(n%2==1) return combine(pw(x,n-1),x);
	return pw(combine(x,x),n/2);
}

void run() {
	scanf("%lld%d%d",&nrows,&period,&nq);
	fullblockrows=period/gcd(7,period); lastblockrows=nrows%fullblockrows;
	memset(black,false,sizeof(black));
	REP(i,nq) { int x; scanf("%d",&x); for(int j=x;j<7*fullblockrows;j+=period) black[j/7][j%7]=true; }
	//REP(x,fullblockrows) { REP(y,7) printf("%c",black[x][y]?'X':'.'); puts(""); }

	R onefull=calc(fullblockrows);
	ll numfullblocks=nrows/fullblockrows;
	R allfull=pw(onefull,numfullblocks);
	R all=allfull;
	if(lastblockrows!=0) {
		R last=calc(lastblockrows);
		all=combine(all,last);
	}
	ll ret=all.cnt;
	set<int> seen;
	REP(i,7) if(all.top[i]!=-1&&!seen.count(all.top[i])) seen.insert(all.top[i]),++ret;
	REP(i,7) if(all.bot[i]!=-1&&!seen.count(all.bot[i])) seen.insert(all.bot[i]),++ret;
	printf("%lld\n",ret);
}

int main() {
	run();
	return 0;
}

```