// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve
bool white[800001];
bool used[800001];
int b[800001];
int re;

int dx[4] = {-7, -1, 1, 7};
int count_a;

void dfs(int x){
  used[x] = true;
  b[x] = count_a;
  rep(i, 4){
    int nx = x + dx[i];
    if(x % 7 == 0 && nx % 7 == 6)continue;
    if(x % 7 == 6 && nx % 7 == 0)continue;
    if(nx >= 0 && nx < re){
      if(!used[nx] && white[nx]){
        dfs(nx);
      }
    }
  }
}

int main(int argc, char const* argv[])
{
  ll n;
  int m, q;
  cin >> n >> m >> q;
  vector<int> a(q);
  rep(i, q){
    cin >> a[i];
  }
  re = (m % 7 == 0) ? m: 7 * m;
  fill(white, white + re, true);
  rep(i, q){
    rep(j, 7){
      white[a[i] + j * m] = false;
    }
  }
  count_a = 0;
  rep(i, re){
    if(!used[i] && white[i]){
      count_a++;
      dfs(i);
    }
  }
  set<int> st;
  rep(i, 7){
    if(white[i] && white[re-7+i])st.insert(b[i]);
  }
  int count_b = int(st.size());
  cout << (ll)(count_a - count_b) * ((7 * n) / re) + (ll)count_b << endl;
	return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve
bool white[800001];
bool used[800001];
int b[800001];
int re;

int dx[4] = {-7, -1, 1, 7};
int count_a;

void dfs(int x){
  used[x] = true;
  b[x] = count_a;
  rep(i, 4){
    int nx = x + dx[i];
    if(x % 7 == 0 && nx % 7 == 6)continue;
    if(x % 7 == 6 && nx % 7 == 0)continue;
    if(nx >= 0 && nx < re){
      if(!used[nx] && white[nx]){
        dfs(nx);
      }
    }
  }
}

int main(int argc, char const* argv[])
{
  ll n;
  int m, q;
  cin >> n >> m >> q;
  vector<int> a(q);
  rep(i, q){
    cin >> a[i];
  }
  re = (m % 7 == 0) ? m: 7 * m;
  fill(white, white + re, true);
  rep(i, q){
    rep(j, 7){
      white[a[i] + j * m] = false;
    }
  }
  count_a = 0;
  rep(i, re){
    if(!used[i] && white[i]){
      count_a++;
      dfs(i);
    }
  }
  set<int> st;
  rep(i, 7){
    if(white[i] && white[re-7+i])st.insert(b[i]);
  }
  int count_b = int(st.size());
  cout << (ll)(count_a - count_b) * ((7 * n) / re) + (ll)count_b << endl;
	return 0;
}

```