#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
long n;int m,q,a[1<<17];
bool f[7][1<<18];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
void bfs(int x,int y,long _n)
{
	queue<pair<int,int> >P;
	f[x][y]=true;
	P.push(make_pair(x,y));
	while(!P.empty())
	{
		pair<int,int>p=P.front();P.pop();
		for(int r=0;r<4;r++)
		{
			int tx=p.first+dx[r],ty=p.second+dy[r];
			if(tx<0||ty<0||tx>=7||ty>=_n||f[tx][ty])continue;
			f[tx][ty]=true;
			P.push(make_pair(tx,ty));
		}
	}
}
int main()
{
	cin>>n>>m>>q;
	for(int i=0;i<q;i++)
	{
		cin>>a[i];
	}
	if(n<=100000)
	{
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<n;j++)
			{
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long ans=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(!f[i][j])
				{
					ans++;
					bfs(i,j,n);
				}
			}
		}
		cout<<ans<<endl;
	}
	else if(m%7==0)
	{
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m/7*2;j++)
			{
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count1=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m/7*2;j++)
			{
				if(!f[i][j])
				{
					count1++;
					bfs(i,j,m/7*2);
				}
			}
		}
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m/7*3;j++)
			{
				f[i][j]=false;
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count2=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m/7*3;j++)
			{
				if(!f[i][j])
				{
					count2++;
					bfs(i,j,m/7*3);
				}
			}
		}
		long kousa=count2-count1;
		long syokou=count1-kousa*2;
		cout<<syokou+kousa*(n/(m/7))<<endl;
	}
	else
	{
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m;j++)
			{
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count1=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(!f[i][j])
				{
					count1++;
					bfs(i,j,m);
				}
			}
		}
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<2*m;j++)
			{
				f[i][j]=false;
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count2=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<2*m;j++)
			{
				if(!f[i][j])
				{
					count2++;
					bfs(i,j,2*m);
				}
			}
		}
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<n-n/m*m+m;j++)
			{
				f[i][j]=false;
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count3=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<n-n/m*m+m;j++)
			{
				if(!f[i][j])
				{
					count3++;
					bfs(i,j,n-n/m*m+m);
				}
			}
		}
		long kousa=count2-count1;
		long syokou=count1-kousa;
		long amari=count3-syokou-kousa;
		cout<<syokou+kousa*(n/m)+amari<<endl;
	}
}

### Prompt

Please formulate 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<iostream>
#include<algorithm>
#include<queue>
using namespace std;
long n;int m,q,a[1<<17];
bool f[7][1<<18];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
void bfs(int x,int y,long _n)
{
	queue<pair<int,int> >P;
	f[x][y]=true;
	P.push(make_pair(x,y));
	while(!P.empty())
	{
		pair<int,int>p=P.front();P.pop();
		for(int r=0;r<4;r++)
		{
			int tx=p.first+dx[r],ty=p.second+dy[r];
			if(tx<0||ty<0||tx>=7||ty>=_n||f[tx][ty])continue;
			f[tx][ty]=true;
			P.push(make_pair(tx,ty));
		}
	}
}
int main()
{
	cin>>n>>m>>q;
	for(int i=0;i<q;i++)
	{
		cin>>a[i];
	}
	if(n<=100000)
	{
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<n;j++)
			{
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long ans=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(!f[i][j])
				{
					ans++;
					bfs(i,j,n);
				}
			}
		}
		cout<<ans<<endl;
	}
	else if(m%7==0)
	{
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m/7*2;j++)
			{
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count1=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m/7*2;j++)
			{
				if(!f[i][j])
				{
					count1++;
					bfs(i,j,m/7*2);
				}
			}
		}
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m/7*3;j++)
			{
				f[i][j]=false;
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count2=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m/7*3;j++)
			{
				if(!f[i][j])
				{
					count2++;
					bfs(i,j,m/7*3);
				}
			}
		}
		long kousa=count2-count1;
		long syokou=count1-kousa*2;
		cout<<syokou+kousa*(n/(m/7))<<endl;
	}
	else
	{
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m;j++)
			{
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count1=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(!f[i][j])
				{
					count1++;
					bfs(i,j,m);
				}
			}
		}
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<2*m;j++)
			{
				f[i][j]=false;
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count2=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<2*m;j++)
			{
				if(!f[i][j])
				{
					count2++;
					bfs(i,j,2*m);
				}
			}
		}
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<n-n/m*m+m;j++)
			{
				f[i][j]=false;
				int b=(j*7+i)%m;
				if(upper_bound(a,a+q,b)!=lower_bound(a,a+q,b))f[i][j]=true;
			}
		}
		long count3=0;
		for(int i=0;i<7;i++)
		{
			for(int j=0;j<n-n/m*m+m;j++)
			{
				if(!f[i][j])
				{
					count3++;
					bfs(i,j,n-n/m*m+m);
				}
			}
		}
		long kousa=count2-count1;
		long syokou=count1-kousa;
		long amari=count3-syokou-kousa;
		cout<<syokou+kousa*(n/m)+amari<<endl;
	}
}

```