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:
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>

auto& in = std::cin;
auto& out = std::cout;

int64_t N;
int32_t m;
bool MAP[200001][8];
bool MOD[700010];

template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	int32_t Q;
	in >> N >> m >> Q;
	auto m_l = m;
	if ((m_l % 7) != 0) {
		m_l *= 7;
	}
	for (int32_t i = 0; i < Q; ++i)
	{
		int32_t a;
		in >> a;
		do{
			MOD[a] = true;
			a += m;
		}while (a < m_l);
	}
	m = m_l;

	for (int32_t y = 0; y < (m / 7); ++y) {
		MAP[y][7] = true;
	}
	for (int32_t x = 0; x < 8; ++x) {
		MAP[(m / 7)][x] = true;
	}
	int32_t count = 0;
	std::stack<std::pair<int32_t, int32_t>> stack;
	for (int32_t y = 0; y < (m/7); ++y)
		for (int32_t x = 0; x < 7; ++x)
		{
			if (MOD[(7 * y + x) % m]) {
				MAP[y][x] = true;
			}
			if (!MAP[y][x])
			{
				++count;
				stack.emplace(y, x);
				MAP[y][x] = true;
				while (!stack.empty())
				{
					auto pos = stack.top(); stack.pop();
					auto y = pos.first;//オーバーライド
					auto x = pos.second;
					int diff[] = { 1,0,-1,0,1 };
					for (int32_t j = 0; j < 4; ++j)
					{
						auto ny = std::max(0, y + diff[j + 1]);
						auto nx = std::max(0, x + diff[j]);
						if (!MAP[ny][nx])
						{
							if (MOD[(7 * ny + nx) % m]) {
							}
							else {
								stack.emplace(ny, nx);
							}
							MAP[ny][nx] = true;
						}
					}
				}
			}
		}

	int32_t count1 = count;

	fill_all(MAP, false);
	for (int32_t y = 0; y < (m / 7) * 2; ++y) {
		MAP[y][7] = true;
	}
	for (int32_t x = 0; x < 8; ++x) {
		MAP[(m / 7) * 2][x] = true;
	}
	count = 0;
	for (int32_t y = 0; y < (m / 7)*2; ++y)
		for (int32_t x = 0; x < 7; ++x)
		{
			if (MOD[(7 * y + x) % m]) {
				MAP[y][x] = true;
			}
			if (!MAP[y][x])
			{
				++count;
				stack.emplace(y, x);
				MAP[y][x] = true;
				while (!stack.empty())
				{
					auto pos = stack.top(); stack.pop();
					auto y = pos.first;//オーバーライド
					auto x = pos.second;
					int diff[] = { 1,0,-1,0,1 };
					for (int32_t j = 0; j < 4; ++j)
					{
						auto ny = std::max(0, y + diff[j + 1]);
						auto nx = std::max(0, x + diff[j]);
						if (!MAP[ny][nx])
						{
							if (MOD[(7 * ny + nx) % m]) {
							}
							else {
								stack.emplace(ny, nx);
							}
							MAP[ny][nx] = true;
						}
					}
				}
			}
		}

	out << (count - count1)*((7*N)/m - 1)+count1 << endl;
	

	return 0;
}
#endif