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

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
long N;
int M,Q;
int A[1<<17];
int d[4]={0,1,0,-1};
long f(int h)
{
	vector<vector<bool> >mp(h,vector<bool>(7,true));
	for(int i=0;i<Q;i++)
	{
		for(int j=A[i];j<7*h;j+=M)
		{
			mp[j/7][j%7]=false;
		}
	}
	long cnt=0;
	for(int i=0;i<h;i++)for(int j=0;j<7;j++)if(mp[i][j])
	{
		queue<pair<int,int> >P;P.push(make_pair(i,j));
		mp[i][j]=false;
		cnt++;
		while(!P.empty())
		{
			int x=P.front().first,y=P.front().second;P.pop();
			for(int r=0;r<4;r++)
			{
				int tx=x+d[r],ty=y+d[r^1];
				if(tx<0||ty<0||tx>=h||ty>=7||!mp[tx][ty])continue;
				mp[tx][ty]=false;
				P.push(make_pair(tx,ty));
			}
		}
	}
	return cnt;
}
int main()
{
	cin>>N>>M>>Q;
	for(int i=0;i<Q;i++)cin>>A[i];
	int X=M%7?7*M:M;
	long S=f(X/7);
	if(X/7<N)
	{
		long T=f(2*X/7);
		long a=T-S,b=S-a;
		S=N/(X/7)*a+b;
	}
	cout<<S<<endl;
}