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<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int gcd(int a, int b) {
	if (!b)return a;
	return gcd(b, a%b);
}
bool b[1400000][7], c[1400000][7];
int a[100000];
int dx[]{ 1,-1,0,0 }, dy[]{ 0,0,1,-1 };
int main() {
	ll n; int m, q; scanf("%lld%d%d", &n, &m, &q);
	int l = m / gcd(m, 7) * 7;
	rep(i, q) {
		scanf("%d", &a[i]);
		for (int j = a[i]; j < 2 * l; j += m) {
			c[j / 7][j % 7] = 1;
			if (j <= l)b[j / 7][j % 7] = 1;
		}
	}
	queue<P>que;
	ll c1 = 0;
	rep(i, l / 7)rep(j, 7) {
		if (b[i][j])continue;
		c1++; que.push(P(i, j));
		while (!que.empty()) {
			P p = que.front(); que.pop();
			rep(k, 4) {
				int nx = p.first + dx[k], ny = p.second + dy[k];
				if (0 <= nx&&nx < l / 7 && 0 <= ny&&ny < 7 && !b[nx][ny]) {
					b[nx][ny] = 1; que.push(P(nx, ny));
				}
			}
		}
	}
	ll c2 = 0;
	rep(i, 2 * l / 7)rep(j, 7) {
		if (c[i][j])continue;
		c2++; que.push(P(i, j));
		while (!que.empty()) {
			P p = que.front(); que.pop();
			rep(k, 4) {
				int nx = p.first + dx[k], ny = p.second + dy[k];
				if (0 <= nx&&nx < 2 * l / 7 && 0 <= ny&&ny < 7 && !c[nx][ny]) {
					c[nx][ny] = 1; que.push(P(nx, ny));
				}
			}
		}
	}
	printf("%lld\n", (c2 - c1)*(7*n / l - 1) + c1);
}