#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <complex>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <iomanip>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T,vector<T>,greater<T>>
#define Pqza(T) priority_queue<T>
#define put(x) cout << x;
#define putsp(x) cout << x << ' ';
#define putln(x) cout << x << endl;
#define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0);

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef complex<double> comp;
typedef vector <int> vec;
typedef vector <ll> vecll;
typedef vector <double> vecd;
typedef vector <vec> mat;
typedef vector <vecll> matll;
typedef vector <vecd> matd;

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int MAX = 100010;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const ll INFL = 1e18;
const ll MOD = 1000000007;

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

//********************************template END****************************************//

void dfs(int x, int y, mat& m)
{
	m[y][x] = 1;
	rep(4, d)
	{
		int ny = y + dy[d], nx = x + dx[d];
		if (0 <= ny && ny < (int)m.size() && 0 <= nx && nx < 7)
		{
			if (m[ny][nx] == 0)
			{
				dfs(nx, ny, m);
			}
		}
	}
}

void solve(void){

	ll N, M, Q;
	cin >> N >> M >> Q;

	vec qs(Q);

	rep(Q, i)
	{
		cin >> qs[i];
	}

	if (M % 7)
	{
		//0 -> white, 1 -> black
		mat maze(M, vec (7, 0)), dmaze(M*2, vec(7, 0));

		rep(Q, i) rep(7, j)
		{
			int x = qs[i] + M*j;
			int h = x / 7, w = x % 7;
			dmaze[h][w] = maze[h][w] = 1;
			x += 7*M;
			h = x / 7, w = x % 7;
			dmaze[h][w] = 1;
		}

		ll a = 0, b = 0, k = N/M;

		rep(M, i) rep(7, j)
		{
			if (maze[i][j] == 0)
			{
				a++;
				dfs(j, i, maze);
			}
		}

		rep(2*M, i) rep(7, j)
		{
			if (dmaze[i][j] == 0)
			{
				b++;
				dfs(j, i, dmaze);
			}
		}

		//cout << a << ' ' << b << ' ' << k << endl;

		ll ans = a + (b-a) * (k-1);

		cout << ans << endl;
		return;
	}

	//0 -> white, 1 -> black
	mat maze(M/7, vec (7, 0)), dmaze(M/7*2, vec(7, 0));

	rep(Q, i)
	{
		int x = qs[i];
		int h = x / 7, w = x % 7;
		dmaze[h][w] = maze[h][w] = 1;
		x += M;
		h = x / 7, w = x % 7;
		dmaze[h][w] = 1;
	}

	ll a = 0, b = 0, k = N*7/M;

	rep(M/7, i) rep(7, j)
	{
		if (maze[i][j] == 0)
		{
			a++;
			dfs(j, i, maze);
		}
	}

	rep(2*M/7, i) rep(7, j)
	{
		if (dmaze[i][j] == 0)
		{
			b++;
			dfs(j, i, dmaze);
		}
	}

	//cout << a << ' ' << b << ' ' << k << endl;

	ll ans = a + (b-a) * (k-1);

	cout << ans << endl;


}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}

### Prompt

In CPP, your task is to solve 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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <complex>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <iomanip>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T,vector<T>,greater<T>>
#define Pqza(T) priority_queue<T>
#define put(x) cout << x;
#define putsp(x) cout << x << ' ';
#define putln(x) cout << x << endl;
#define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0);

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef complex<double> comp;
typedef vector <int> vec;
typedef vector <ll> vecll;
typedef vector <double> vecd;
typedef vector <vec> mat;
typedef vector <vecll> matll;
typedef vector <vecd> matd;

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int MAX = 100010;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const ll INFL = 1e18;
const ll MOD = 1000000007;

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

//********************************template END****************************************//

void dfs(int x, int y, mat& m)
{
	m[y][x] = 1;
	rep(4, d)
	{
		int ny = y + dy[d], nx = x + dx[d];
		if (0 <= ny && ny < (int)m.size() && 0 <= nx && nx < 7)
		{
			if (m[ny][nx] == 0)
			{
				dfs(nx, ny, m);
			}
		}
	}
}

void solve(void){

	ll N, M, Q;
	cin >> N >> M >> Q;

	vec qs(Q);

	rep(Q, i)
	{
		cin >> qs[i];
	}

	if (M % 7)
	{
		//0 -> white, 1 -> black
		mat maze(M, vec (7, 0)), dmaze(M*2, vec(7, 0));

		rep(Q, i) rep(7, j)
		{
			int x = qs[i] + M*j;
			int h = x / 7, w = x % 7;
			dmaze[h][w] = maze[h][w] = 1;
			x += 7*M;
			h = x / 7, w = x % 7;
			dmaze[h][w] = 1;
		}

		ll a = 0, b = 0, k = N/M;

		rep(M, i) rep(7, j)
		{
			if (maze[i][j] == 0)
			{
				a++;
				dfs(j, i, maze);
			}
		}

		rep(2*M, i) rep(7, j)
		{
			if (dmaze[i][j] == 0)
			{
				b++;
				dfs(j, i, dmaze);
			}
		}

		//cout << a << ' ' << b << ' ' << k << endl;

		ll ans = a + (b-a) * (k-1);

		cout << ans << endl;
		return;
	}

	//0 -> white, 1 -> black
	mat maze(M/7, vec (7, 0)), dmaze(M/7*2, vec(7, 0));

	rep(Q, i)
	{
		int x = qs[i];
		int h = x / 7, w = x % 7;
		dmaze[h][w] = maze[h][w] = 1;
		x += M;
		h = x / 7, w = x % 7;
		dmaze[h][w] = 1;
	}

	ll a = 0, b = 0, k = N*7/M;

	rep(M/7, i) rep(7, j)
	{
		if (maze[i][j] == 0)
		{
			a++;
			dfs(j, i, maze);
		}
	}

	rep(2*M/7, i) rep(7, j)
	{
		if (dmaze[i][j] == 0)
		{
			b++;
			dfs(j, i, dmaze);
		}
	}

	//cout << a << ' ' << b << ' ' << k << endl;

	ll ans = a + (b-a) * (k-1);

	cout << ans << endl;


}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}

```