#include <bits/stdc++.h>

using namespace std;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz) : data(sz, -1) {}

  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
};


typedef long long int64;


int64 N, M, Q, A[100000];

int64 component(int height)
{
  int sz = height * 7;
  UnionFind tree(sz);
  vector< bool > used(sz, 0);

  for(int i = 0; i < Q; i++) {
    int64 idx = A[i];
    while(idx < sz) {
      used[idx] = true;
      idx += M;
    }
  }

  for(int i = 0; i < height; i++) {
    for(int j = 0; j < 7; j++) {
      int idx = i * 7 + j;
      if(used[idx]) continue;
      if(j + 1 < 7 && !used[idx + 1]) tree.unite(idx, idx + 1);
      if(i + 1 < height && !used[idx + 7]) tree.unite(idx, idx + 7);
    }
  }
  int64 ret = 0;
  for(int i = 0; i < sz; i++) {
    if(!used[i]) ret += tree.find(i) == i;
  }
  return (ret);
}

int main()
{
  cin >> N >> M >> Q;
  for(int i = 0; i < Q; i++) {
    cin >> A[i];
  }

  int MM = M;
  if(MM % 7) MM *= 7;
  auto latte = component(MM / 7);
  auto malta = component(MM * 2 / 7) - latte;


  cout << latte + malta * (N * 7 / MM - 1) << 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 <bits/stdc++.h>

using namespace std;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz) : data(sz, -1) {}

  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
};


typedef long long int64;


int64 N, M, Q, A[100000];

int64 component(int height)
{
  int sz = height * 7;
  UnionFind tree(sz);
  vector< bool > used(sz, 0);

  for(int i = 0; i < Q; i++) {
    int64 idx = A[i];
    while(idx < sz) {
      used[idx] = true;
      idx += M;
    }
  }

  for(int i = 0; i < height; i++) {
    for(int j = 0; j < 7; j++) {
      int idx = i * 7 + j;
      if(used[idx]) continue;
      if(j + 1 < 7 && !used[idx + 1]) tree.unite(idx, idx + 1);
      if(i + 1 < height && !used[idx + 7]) tree.unite(idx, idx + 7);
    }
  }
  int64 ret = 0;
  for(int i = 0; i < sz; i++) {
    if(!used[i]) ret += tree.find(i) == i;
  }
  return (ret);
}

int main()
{
  cin >> N >> M >> Q;
  for(int i = 0; i < Q; i++) {
    cin >> A[i];
  }

  int MM = M;
  if(MM % 7) MM *= 7;
  auto latte = component(MM / 7);
  auto malta = component(MM * 2 / 7) - latte;


  cout << latte + malta * (N * 7 / MM - 1) << endl;
}
```