#include <iostream>
#include <vector>

using namespace std;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int a[100000];
bool used[100000];
bool used_root[1400000];

int main(){
    long n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < q; i++) {
        cin >> a[i];
        used[a[i]] = true;
    }
    int M;
    if(m%7 != 0) M =  min(7*m, 7*n);
    else  M =  min(m, 7*n);
    UnionFind uf(2*M);
    for(int i = 0; i < M; i++){
        if(used[i%m]) continue;
        if(i%7 != 6){
            if(!used[(i+1)%m]) uf.unionSet(i, i+1);
        }
        if(i+7 < M){
            if(!used[(i+7)%m]) uf.unionSet(i, i+7);
        }
    }
    long cnt = 0;
    for(int i = 0; i < M; i++){
        if(!used[i%m]){
            int r = uf.root(i);
            //cout << r << endl;
            if(!used_root[r]){
                cnt++;
                used_root[r] = true;
            }
        }
    }
    //cout << M << endl;
    //cout << cnt << endl;

    for(int i = 0; i < 2*M; i++){
        if(used[i%m]) continue;
        if(i%7 != 6){
            if(!used[(i+1)%m]) uf.unionSet(i, i+1);
        }
        if(i+7 < 2*M){
            //cout << i << ' ' << i+7 << endl;
            if(!used[(i+7)%m]) uf.unionSet(i, i+7);
        }
    }

    long cnt_ = 0;
    for(int i = 0; i < 2*M; i++){
        used_root[i] = false;
    }
    for(int i = 0; i < 2*M; i++){
        if(!used[i%m]){
            int r = uf.root(i);
            //cout << r << endl;
            if(!used_root[r]){
                cnt_++;
                used_root[r] = true;
            }
        }
    }
    cnt_ -= cnt;
    //cout << cnt << endl;
    //cout << cnt_ << endl;
    long s = (7*n)/M;
    //cout << s << endl;
    long ans = cnt+cnt_*(s-1);
    cout << ans << endl;
}
### Prompt

Your task is to create 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 <vector>

using namespace std;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int a[100000];
bool used[100000];
bool used_root[1400000];

int main(){
    long n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < q; i++) {
        cin >> a[i];
        used[a[i]] = true;
    }
    int M;
    if(m%7 != 0) M =  min(7*m, 7*n);
    else  M =  min(m, 7*n);
    UnionFind uf(2*M);
    for(int i = 0; i < M; i++){
        if(used[i%m]) continue;
        if(i%7 != 6){
            if(!used[(i+1)%m]) uf.unionSet(i, i+1);
        }
        if(i+7 < M){
            if(!used[(i+7)%m]) uf.unionSet(i, i+7);
        }
    }
    long cnt = 0;
    for(int i = 0; i < M; i++){
        if(!used[i%m]){
            int r = uf.root(i);
            //cout << r << endl;
            if(!used_root[r]){
                cnt++;
                used_root[r] = true;
            }
        }
    }
    //cout << M << endl;
    //cout << cnt << endl;

    for(int i = 0; i < 2*M; i++){
        if(used[i%m]) continue;
        if(i%7 != 6){
            if(!used[(i+1)%m]) uf.unionSet(i, i+1);
        }
        if(i+7 < 2*M){
            //cout << i << ' ' << i+7 << endl;
            if(!used[(i+7)%m]) uf.unionSet(i, i+7);
        }
    }

    long cnt_ = 0;
    for(int i = 0; i < 2*M; i++){
        used_root[i] = false;
    }
    for(int i = 0; i < 2*M; i++){
        if(!used[i%m]){
            int r = uf.root(i);
            //cout << r << endl;
            if(!used_root[r]){
                cnt_++;
                used_root[r] = true;
            }
        }
    }
    cnt_ -= cnt;
    //cout << cnt << endl;
    //cout << cnt_ << endl;
    long s = (7*n)/M;
    //cout << s << endl;
    long ans = cnt+cnt_*(s-1);
    cout << ans << endl;
}
```