#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = (LL)1e9+7;
const int SIZE = 2e5+5;
const LL INF = 1LL<<60;
const double eps = 1e-4;
const double PI=3.1415926535897932;

vector<int> adj[2000009];
vector<LL> orow;//occupied rows
unordered_set<LL> q;
LL n,m,rowblock;
bool vis[2000009];

void dfs(int x){
	for(int i:adj[x]){
		if(vis[i])continue;
		vis[i]=1;dfs(i);
	}
}

LL solve(int bc){//block count
	REP(i,2000009)adj[i].clear();
	vector<LL> orow2;
	REP(i,bc){
		for(LL j:orow){
			orow2.PB(j+rowblock*i);
		}
	}
	MS0(vis);
	int nn=0;
	REP(i,SZ(orow2)){
		LL ri=orow2[i];
		REP(j,7){
			if(q.find((ri*7+j)%m)!=q.end())vis[nn+j]=1;
		}
		REP(j,6){
			if((!vis[nn+j])&&(!vis[nn+j+1])){
				adj[nn+j].PB(nn+j+1);
				adj[nn+j+1].PB(nn+j);
			}
		}
		if(i){
			REP(j,7){
				if((!vis[nn-7+j])&&(!vis[nn+j])){
					adj[nn-7+j].PB(nn+j);
					adj[nn+j].PB(nn-7+j);
				}
			}
		}
		nn+=7;
	}
	int con=0;
	REP(i,nn){
		if(vis[i])continue;
		dfs(i);
		con++;
	}
	return con;
}

int main(){
	scanf("%lld%lld",&n,&m);
	DRI(qn);//find m value for m rows ? D:
	rowblock=m;
	if(m%7==0)rowblock/=7;
	REP(i,qn){
		DRI(x);
		q.insert(x);
		while(x<rowblock*7){
			LL ri=x/7;
			orow.PB(ri);
			x+=m;
			if(ri+1<rowblock)orow.PB(ri+1);
		}
	}
	orow.PB(0);orow.PB(rowblock-1);
	sort(ALL(orow));
	orow.resize(unique(ALL(orow))-orow.begin());
	if(n/rowblock<=3){
		printf("%lld\n",solve(n/rowblock));
	}
	else{
		LL v2=solve(2),v3=solve(3);
		printf("%lld\n",(v3-v2)*(n/rowblock-2)+v2);
	}
}

### 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 <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = (LL)1e9+7;
const int SIZE = 2e5+5;
const LL INF = 1LL<<60;
const double eps = 1e-4;
const double PI=3.1415926535897932;

vector<int> adj[2000009];
vector<LL> orow;//occupied rows
unordered_set<LL> q;
LL n,m,rowblock;
bool vis[2000009];

void dfs(int x){
	for(int i:adj[x]){
		if(vis[i])continue;
		vis[i]=1;dfs(i);
	}
}

LL solve(int bc){//block count
	REP(i,2000009)adj[i].clear();
	vector<LL> orow2;
	REP(i,bc){
		for(LL j:orow){
			orow2.PB(j+rowblock*i);
		}
	}
	MS0(vis);
	int nn=0;
	REP(i,SZ(orow2)){
		LL ri=orow2[i];
		REP(j,7){
			if(q.find((ri*7+j)%m)!=q.end())vis[nn+j]=1;
		}
		REP(j,6){
			if((!vis[nn+j])&&(!vis[nn+j+1])){
				adj[nn+j].PB(nn+j+1);
				adj[nn+j+1].PB(nn+j);
			}
		}
		if(i){
			REP(j,7){
				if((!vis[nn-7+j])&&(!vis[nn+j])){
					adj[nn-7+j].PB(nn+j);
					adj[nn+j].PB(nn-7+j);
				}
			}
		}
		nn+=7;
	}
	int con=0;
	REP(i,nn){
		if(vis[i])continue;
		dfs(i);
		con++;
	}
	return con;
}

int main(){
	scanf("%lld%lld",&n,&m);
	DRI(qn);//find m value for m rows ? D:
	rowblock=m;
	if(m%7==0)rowblock/=7;
	REP(i,qn){
		DRI(x);
		q.insert(x);
		while(x<rowblock*7){
			LL ri=x/7;
			orow.PB(ri);
			x+=m;
			if(ri+1<rowblock)orow.PB(ri+1);
		}
	}
	orow.PB(0);orow.PB(rowblock-1);
	sort(ALL(orow));
	orow.resize(unique(ALL(orow))-orow.begin());
	if(n/rowblock<=3){
		printf("%lld\n",solve(n/rowblock));
	}
	else{
		LL v2=solve(2),v3=solve(3);
		printf("%lld\n",(v3-v2)*(n/rowblock-2)+v2);
	}
}

```