#include<cstdio>
#include<vector>


using namespace std;

using vi=vector<int>;
using vvi=vector<vi>;
using ll=long long;


const int white=-1;
const int black=100000000;


vi gx, gy;


void push(int x, int y)
{
	gx.push_back(x);
	gy.push_back(y);
}


int pop(int& x, int& y)
{
	if(gx.size()<=0) return 0;
	x=gx.back();
	y=gy.back();
	gx.pop_back();
	gy.pop_back();
	return 1;
}


void eng_fill(vvi& c, int x, int y, int g)
{
	int vx[]={ 1, 0,-1, 0};
	int vy[]={ 0,-1, 0, 1};
	int nx, ny;
	int w, h;

	w=7;
	h=c.size();
	push(x, y);
	c[y][x]=g;
	while(pop(x, y))
	{
		for(int i=0;i<4;i++)
		{
			nx=x+vx[i];
			ny=y+vy[i];
			if(nx<0 || w<=nx || ny<0 || h<=ny) continue;
			if(c[ny][nx]!=white) continue;
			c[ny][nx]=g;
			push(nx, ny);
		}
	}
}



int engroup(vvi& c)
{
	int w, h, x, y;
	int g=0;

	w=7;
	h=c.size();
	for(y=0;y<h;y++)
	{
		for(x=0;x<w;x++)
		{
			if(c[y][x]!=white) continue;
			eng_fill(c, x, y, g);
			g++;
		}
	}
	return g;
}


int gcd(int a, int b)
{
	int c;
	while((c=a%b))
	{
		a=b;
		b=c;
	}
	return b;
}


int lcm(int a, int b)
{
	return a/gcd(a, b)*b;
}


int main(void)
{
	int m, q, g, uh, gc;
	ll n, h;
	vvi c, f;

	while(scanf("%lld%d%d", &n, &m, &q)==3)
	{
		uh=lcm(m, 7)/7;
		h=n/uh;
		c.clear();
		c.resize(uh);
		for(auto& ce: c) ce.resize(7, white);

		for(int i=0;i<q;i++)
		{
			int a;
			scanf("%d", &a);
			for(int j=a;j<uh*7;j+=m)
			{
				c[j/7][j%7]=black;
			}
		}
		g=engroup(c);

		f.clear();
		for(int i=0;i<7;i++)
		{
			int u=c[0][i];
			int l=c[uh-1][i];
			int j;
			if(u==black || l==black) continue;
			if(u>l) swap(u, l);
			vi ft={u,l};
			for(j=f.size()-1;j>=0;j--)
			{
				if(ft==f[j]) break;
			}
			if(j<0)
			{
				f.push_back(ft);
//				printf("%d %d\n", ft[0], ft[1]);
			}
		}
		gc=f.size();
# if 0
for(auto ce:c)
{
	for(int x:ce)
	{
		if(x==black) printf(" X ");
		else printf("%2d ", x);
	}
	printf("\n");
}
printf("g=%d h=%d gc=%d\n", g, h, gc);
#endif
		ll result=g*h-gc*(h-1);
		printf("%lld\n", result);
	}

	return 0;
}

### 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
#include<cstdio>
#include<vector>


using namespace std;

using vi=vector<int>;
using vvi=vector<vi>;
using ll=long long;


const int white=-1;
const int black=100000000;


vi gx, gy;


void push(int x, int y)
{
	gx.push_back(x);
	gy.push_back(y);
}


int pop(int& x, int& y)
{
	if(gx.size()<=0) return 0;
	x=gx.back();
	y=gy.back();
	gx.pop_back();
	gy.pop_back();
	return 1;
}


void eng_fill(vvi& c, int x, int y, int g)
{
	int vx[]={ 1, 0,-1, 0};
	int vy[]={ 0,-1, 0, 1};
	int nx, ny;
	int w, h;

	w=7;
	h=c.size();
	push(x, y);
	c[y][x]=g;
	while(pop(x, y))
	{
		for(int i=0;i<4;i++)
		{
			nx=x+vx[i];
			ny=y+vy[i];
			if(nx<0 || w<=nx || ny<0 || h<=ny) continue;
			if(c[ny][nx]!=white) continue;
			c[ny][nx]=g;
			push(nx, ny);
		}
	}
}



int engroup(vvi& c)
{
	int w, h, x, y;
	int g=0;

	w=7;
	h=c.size();
	for(y=0;y<h;y++)
	{
		for(x=0;x<w;x++)
		{
			if(c[y][x]!=white) continue;
			eng_fill(c, x, y, g);
			g++;
		}
	}
	return g;
}


int gcd(int a, int b)
{
	int c;
	while((c=a%b))
	{
		a=b;
		b=c;
	}
	return b;
}


int lcm(int a, int b)
{
	return a/gcd(a, b)*b;
}


int main(void)
{
	int m, q, g, uh, gc;
	ll n, h;
	vvi c, f;

	while(scanf("%lld%d%d", &n, &m, &q)==3)
	{
		uh=lcm(m, 7)/7;
		h=n/uh;
		c.clear();
		c.resize(uh);
		for(auto& ce: c) ce.resize(7, white);

		for(int i=0;i<q;i++)
		{
			int a;
			scanf("%d", &a);
			for(int j=a;j<uh*7;j+=m)
			{
				c[j/7][j%7]=black;
			}
		}
		g=engroup(c);

		f.clear();
		for(int i=0;i<7;i++)
		{
			int u=c[0][i];
			int l=c[uh-1][i];
			int j;
			if(u==black || l==black) continue;
			if(u>l) swap(u, l);
			vi ft={u,l};
			for(j=f.size()-1;j>=0;j--)
			{
				if(ft==f[j]) break;
			}
			if(j<0)
			{
				f.push_back(ft);
//				printf("%d %d\n", ft[0], ft[1]);
			}
		}
		gc=f.size();
# if 0
for(auto ce:c)
{
	for(int x:ce)
	{
		if(x==black) printf(" X ");
		else printf("%2d ", x);
	}
	printf("\n");
}
printf("g=%d h=%d gc=%d\n", g, h, gc);
#endif
		ll result=g*h-gc*(h-1);
		printf("%lld\n", result);
	}

	return 0;
}

```