#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include<iostream>
#include<unordered_set>

using namespace std;

#define dprint(Exp,...) if(Exp){fprintf(stderr, __VA_ARGS__);}
#define printe(...) fprintf(stderr, __VA_ARGS__);
#define PrtExp(_Exp)  cerr<< #_Exp <<" = "<< (_Exp)
#define PrtExpN(_Exp)  cerr<< #_Exp <<" = "<< (_Exp) <<"\n"

#define SINT(n) scanf("%d",&n)
#define SINT2(n,m) scanf("%d %d",&n,&m)
#define SINT3(n,m,o) scanf("%d %d %d",&n,&m,&o)
#define SINT4(n,m,o,p) scanf("%d %d %d %d",&n,&m,&o,&p)
#define SINT5(n,m,o,p,q) scanf("%d %d %d %d %d",&n,&m,&o,&p,&q)
#define SLL(n) scanf("%lld",&n)
#define SLL2(n,m) scanf("%lld %lld",&n,&m)
#define SLL3(n,m,o) scanf("%lld %lld %lld",&n,&m,&o)
#define SST(s) scanf("%s",s)
#define SCH(c) scanf("%c",&c)

#define GC() getchar()

#define PINT(n) printf("%d",(int)(n))
#define PINT2(n,m) printf("%d %d",(int)(n),(int)(m))
#define PINT3(n,m,l) printf("%d %d %d",(int)(n),(int)(m),(int)(l))
#define PLL(n) printf("%lld",(long long)(n))
#define PST(s) printf("%s",(s))
#define PCH(s) printf("%c",(s))

#define PINTN(n) printf("%d\n",(int)(n))
#define PINT2N(n,m) printf("%d %d\n",(int)(n),(int)(m))
#define PINT3N(n,m,l) printf("%d %d %d\n",(int)(n),(int)(m),(int)(l))
#define PLLN(n) printf("%lld\n",(long long)(n))
#define PSTN(s) printf("%s\n",(s))
#define PCHN(s) printf("%c\n",(s))

#define PSP() printf(" ")
#define PN() printf("\n")

#define PC(c) putchar(c)
#define CSP (' ')
#define SN ("\n")

#define rep(i,a) for(int i=0;i<a;i++)
#define reP(i,a) for(int i=0;i<=a;i++)
#define Rep(i,a) for(int i=a-1;i>=0;i--)
#define ReP(i,a) for(int i=a;i>=0;i--)

#define rEp(i,a) for(i=0;i<a;i++)
#define rEP(i,a) for(i=0;i<=a;i++)
#define REp(i,a) for(i=a-1;i>=0;i--)
#define REP(i,a) for(i=a;i>=0;i--)

#define repft(i,a,b) for(int i=a;i<b;i++)
#define repfT(i,a,b) for(int i=a;i<=b;i++)
#define Repft(i,a,b) for(int i=a-1;i>=b;i--)
#define RepfT(i,a,b) for(int i=a;i>=b;i--)

#define foreach(a,it) for(auto it = a.begin(); it != a.end(); ++it)

#define FILL(a,v) fill(begin(a),end(a), v)
#define FILL0(a) memset(a,0,sizeof(a))
#define FILL1(a) memset(a,-1,sizeof(a))

typedef long long ll;

typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll>   Pll;


const int INF = 0x2aaaaaaa; // 715,827,882
const ll INFLL = 0x1f1f1f1f1f1f1f1fLL;//2,242,545,357,980,376,863

template <class A, class B> inline ostream& operator<<(ostream& st, const pair<A, B>& P) { return st << "(" << P.first << "," << P.second << ")"; };
template <class A, class B> inline pair<A, B> operator+(const pair<A, B>& P, const pair<A, B>& Q) { return pair<A, B>(P.first + Q.first, P.second + Q.second); };
template <class A, class B> inline pair<A, B> operator-(const pair<A, B>& P, const pair<A, B>& Q) { return pair<A, B>(P.first - Q.first, P.second - Q.second); };

#define fs  first
#define sc  second


ll n, m, q, g;
bool a[800005] = {};
bool b[1600005][9];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

void dfs(int y, int x) {
	b[y][x] = false;
	rep(i, 4) {
		int Y = y + dy[i];
		int X = x + dx[i];
		if (b[Y][X]) dfs(Y, X);
	}
}

int solve(int M) {
	/*
	rep(i, M+2){
		rep(j, 9) {
			cout << b[i][j];
		}
		cout << endl;
	}
	cout << endl;
	*/
	queue<Pi> Q;
	int ret = 0;
	rep(i, M) rep(j, 7) {
		if (b[i + 1][j + 1]) {
			ret++;
			Q.push({ i + 1, j + 1 });
			b[i+1][j+1] = false;
			while (!Q.empty()) {
				Pi p = Q.front(); Q.pop();
				rep(i, 4) {
					int Y = p.fs + dy[i];
					int X = p.sc + dx[i];
					if (b[Y][X]) {
						Q.push({ Y, X });
						b[Y][X] = false;
					}
				}
			}
		}
	}
	return ret;
}
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a%b);
}

int main() {
	cin >> n >> m >> q;
	g = m / gcd(m, 7);
	// PrtExpN(g);

	rep(i, q) {
		int x;
		cin >> x;
		rep(j, 8) a[j*m + x] = true;
	}
	FILL0(b);
	rep(i, 7 * g) {
		int x = i % 7 + 1;
		int y = i / 7 + 1;
		b[y][x] = !a[i%m];
	}
	ll r1 = solve(g);

	FILL0(b);
	rep(i, 14 * g) {
		int x = i % 7 + 1;
		int y = i / 7 + 1;
		b[y][x] = !a[i%m];
	}

	ll r2 = solve(g*2);

	ll z = n / g;
	ll ret = (z - 1)*r2 - (z - 2)*r1;

	// cout << r1 << " " << r2 << " " << ret << endl;
	cout << ret << endl;



}


### Prompt

Construct a CPP code solution to the problem outlined:

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
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include<iostream>
#include<unordered_set>

using namespace std;

#define dprint(Exp,...) if(Exp){fprintf(stderr, __VA_ARGS__);}
#define printe(...) fprintf(stderr, __VA_ARGS__);
#define PrtExp(_Exp)  cerr<< #_Exp <<" = "<< (_Exp)
#define PrtExpN(_Exp)  cerr<< #_Exp <<" = "<< (_Exp) <<"\n"

#define SINT(n) scanf("%d",&n)
#define SINT2(n,m) scanf("%d %d",&n,&m)
#define SINT3(n,m,o) scanf("%d %d %d",&n,&m,&o)
#define SINT4(n,m,o,p) scanf("%d %d %d %d",&n,&m,&o,&p)
#define SINT5(n,m,o,p,q) scanf("%d %d %d %d %d",&n,&m,&o,&p,&q)
#define SLL(n) scanf("%lld",&n)
#define SLL2(n,m) scanf("%lld %lld",&n,&m)
#define SLL3(n,m,o) scanf("%lld %lld %lld",&n,&m,&o)
#define SST(s) scanf("%s",s)
#define SCH(c) scanf("%c",&c)

#define GC() getchar()

#define PINT(n) printf("%d",(int)(n))
#define PINT2(n,m) printf("%d %d",(int)(n),(int)(m))
#define PINT3(n,m,l) printf("%d %d %d",(int)(n),(int)(m),(int)(l))
#define PLL(n) printf("%lld",(long long)(n))
#define PST(s) printf("%s",(s))
#define PCH(s) printf("%c",(s))

#define PINTN(n) printf("%d\n",(int)(n))
#define PINT2N(n,m) printf("%d %d\n",(int)(n),(int)(m))
#define PINT3N(n,m,l) printf("%d %d %d\n",(int)(n),(int)(m),(int)(l))
#define PLLN(n) printf("%lld\n",(long long)(n))
#define PSTN(s) printf("%s\n",(s))
#define PCHN(s) printf("%c\n",(s))

#define PSP() printf(" ")
#define PN() printf("\n")

#define PC(c) putchar(c)
#define CSP (' ')
#define SN ("\n")

#define rep(i,a) for(int i=0;i<a;i++)
#define reP(i,a) for(int i=0;i<=a;i++)
#define Rep(i,a) for(int i=a-1;i>=0;i--)
#define ReP(i,a) for(int i=a;i>=0;i--)

#define rEp(i,a) for(i=0;i<a;i++)
#define rEP(i,a) for(i=0;i<=a;i++)
#define REp(i,a) for(i=a-1;i>=0;i--)
#define REP(i,a) for(i=a;i>=0;i--)

#define repft(i,a,b) for(int i=a;i<b;i++)
#define repfT(i,a,b) for(int i=a;i<=b;i++)
#define Repft(i,a,b) for(int i=a-1;i>=b;i--)
#define RepfT(i,a,b) for(int i=a;i>=b;i--)

#define foreach(a,it) for(auto it = a.begin(); it != a.end(); ++it)

#define FILL(a,v) fill(begin(a),end(a), v)
#define FILL0(a) memset(a,0,sizeof(a))
#define FILL1(a) memset(a,-1,sizeof(a))

typedef long long ll;

typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll>   Pll;


const int INF = 0x2aaaaaaa; // 715,827,882
const ll INFLL = 0x1f1f1f1f1f1f1f1fLL;//2,242,545,357,980,376,863

template <class A, class B> inline ostream& operator<<(ostream& st, const pair<A, B>& P) { return st << "(" << P.first << "," << P.second << ")"; };
template <class A, class B> inline pair<A, B> operator+(const pair<A, B>& P, const pair<A, B>& Q) { return pair<A, B>(P.first + Q.first, P.second + Q.second); };
template <class A, class B> inline pair<A, B> operator-(const pair<A, B>& P, const pair<A, B>& Q) { return pair<A, B>(P.first - Q.first, P.second - Q.second); };

#define fs  first
#define sc  second


ll n, m, q, g;
bool a[800005] = {};
bool b[1600005][9];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

void dfs(int y, int x) {
	b[y][x] = false;
	rep(i, 4) {
		int Y = y + dy[i];
		int X = x + dx[i];
		if (b[Y][X]) dfs(Y, X);
	}
}

int solve(int M) {
	/*
	rep(i, M+2){
		rep(j, 9) {
			cout << b[i][j];
		}
		cout << endl;
	}
	cout << endl;
	*/
	queue<Pi> Q;
	int ret = 0;
	rep(i, M) rep(j, 7) {
		if (b[i + 1][j + 1]) {
			ret++;
			Q.push({ i + 1, j + 1 });
			b[i+1][j+1] = false;
			while (!Q.empty()) {
				Pi p = Q.front(); Q.pop();
				rep(i, 4) {
					int Y = p.fs + dy[i];
					int X = p.sc + dx[i];
					if (b[Y][X]) {
						Q.push({ Y, X });
						b[Y][X] = false;
					}
				}
			}
		}
	}
	return ret;
}
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a%b);
}

int main() {
	cin >> n >> m >> q;
	g = m / gcd(m, 7);
	// PrtExpN(g);

	rep(i, q) {
		int x;
		cin >> x;
		rep(j, 8) a[j*m + x] = true;
	}
	FILL0(b);
	rep(i, 7 * g) {
		int x = i % 7 + 1;
		int y = i / 7 + 1;
		b[y][x] = !a[i%m];
	}
	ll r1 = solve(g);

	FILL0(b);
	rep(i, 14 * g) {
		int x = i % 7 + 1;
		int y = i / 7 + 1;
		b[y][x] = !a[i%m];
	}

	ll r2 = solve(g*2);

	ll z = n / g;
	ll ret = (z - 1)*r2 - (z - 2)*r1;

	// cout << r1 << " " << r2 << " " << ret << endl;
	cout << ret << endl;



}


```