#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// #define DEBUG
#ifdef DEBUG
#define dump(...) cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n";
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '{'; for(int i = 0; i < (int) v.size(); i++) o << v[i] << (i != (int)v.size()-1 ? ", " : ""); o << "}";  return o; }
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream & os, tuple<T...> const & t){ _ot<0>(os, t); return os; }
#else
#define dump(...)
#endif

int dy[] = {1, 0, -1, 0};
int dx[] = {0, -1, 0, 1};

ll period;
vector< vector<int> > tmp, f;

ll BFS(vector< vector<int> > &used, int y0, int y1, int h) {
  ll cnt = 0;
  for(ll y = y0; y < y1; y++) {
    for(ll x = 0; x < 7; x++) {
      if(f[y][x]) continue;
      if(used[y][x]) continue;
      // if(connect != -1 ? f[connect][x] : false) continue;
      used[y][x] = 1;
      queue<pair<ll, ll>> q;
      q.emplace(y, x);
      cnt++;
      while(q.size()) {
        ll yy = q.front().first, xx = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++) {
          ll ny = yy + dy[d];
          ll nx = xx + dx[d];
          if(ny < 0 || h <= ny || nx < 0 || 7 <= nx) continue;
          if(f[ny][nx]) continue;
          if(used[ny][nx]) continue;
          used[ny][nx] = 1;
          q.emplace(ny, nx);
        }
      }
    }
  }
  return cnt;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  ll n, m, q; cin >> n >> m >> q;
  ll h = (m + 6) / 7; // one shared block
  period = h * 7 - (7 - m % 7) % 7; // height of period
  if(period % 7 == 0) period /= 7; // 一応これで最小単位の最大値になるはず
  ll full = n / period;
  ll rest = n - full * period;
  tmp = vector< vector<int> >(period * 3, vector<int>(7) );
  f = tmp;

  while(q--) {
    ll a; cin >> a;
    for(; a < period * 7; a += m) {
      ll y = a / 7, x = a % 7;
      f[y][x] = 1;
      f[y + period][x] = 1;
      f[y + period * 2][x] = 1;
    }
  }

  auto used = tmp;
  ll b2 = BFS(used, 0, period, period * 3);
  ll b4 = BFS(used, period, period * 2, period * 3);
  auto used2 = tmp;
  BFS(used2, 0, period, period * 2 + rest);
  ll b3 = BFS(used2, period, period * 2 + rest, period * 2 + rest);
  auto used3 = tmp;
  ll b1 = BFS(used3, 0, period + rest, period + rest);
  auto used4 = tmp;
  ll b5 = BFS(used4, 0, rest, rest);

  ll ans = 0;
  
  if(full == 0) {
    ans = b5;
  } else if(full == 1) {
    ans = b1;
  } else {
    ans = b2 + b3 + (full - 2) * b4;
  }
  cout << ans << endl;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
using ll = long long;

// #define DEBUG
#ifdef DEBUG
#define dump(...) cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n";
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '{'; for(int i = 0; i < (int) v.size(); i++) o << v[i] << (i != (int)v.size()-1 ? ", " : ""); o << "}";  return o; }
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream & os, tuple<T...> const & t){ _ot<0>(os, t); return os; }
#else
#define dump(...)
#endif

int dy[] = {1, 0, -1, 0};
int dx[] = {0, -1, 0, 1};

ll period;
vector< vector<int> > tmp, f;

ll BFS(vector< vector<int> > &used, int y0, int y1, int h) {
  ll cnt = 0;
  for(ll y = y0; y < y1; y++) {
    for(ll x = 0; x < 7; x++) {
      if(f[y][x]) continue;
      if(used[y][x]) continue;
      // if(connect != -1 ? f[connect][x] : false) continue;
      used[y][x] = 1;
      queue<pair<ll, ll>> q;
      q.emplace(y, x);
      cnt++;
      while(q.size()) {
        ll yy = q.front().first, xx = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++) {
          ll ny = yy + dy[d];
          ll nx = xx + dx[d];
          if(ny < 0 || h <= ny || nx < 0 || 7 <= nx) continue;
          if(f[ny][nx]) continue;
          if(used[ny][nx]) continue;
          used[ny][nx] = 1;
          q.emplace(ny, nx);
        }
      }
    }
  }
  return cnt;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  ll n, m, q; cin >> n >> m >> q;
  ll h = (m + 6) / 7; // one shared block
  period = h * 7 - (7 - m % 7) % 7; // height of period
  if(period % 7 == 0) period /= 7; // 一応これで最小単位の最大値になるはず
  ll full = n / period;
  ll rest = n - full * period;
  tmp = vector< vector<int> >(period * 3, vector<int>(7) );
  f = tmp;

  while(q--) {
    ll a; cin >> a;
    for(; a < period * 7; a += m) {
      ll y = a / 7, x = a % 7;
      f[y][x] = 1;
      f[y + period][x] = 1;
      f[y + period * 2][x] = 1;
    }
  }

  auto used = tmp;
  ll b2 = BFS(used, 0, period, period * 3);
  ll b4 = BFS(used, period, period * 2, period * 3);
  auto used2 = tmp;
  BFS(used2, 0, period, period * 2 + rest);
  ll b3 = BFS(used2, period, period * 2 + rest, period * 2 + rest);
  auto used3 = tmp;
  ll b1 = BFS(used3, 0, period + rest, period + rest);
  auto used4 = tmp;
  ll b5 = BFS(used4, 0, rest, rest);

  ll ans = 0;
  
  if(full == 0) {
    ans = b5;
  } else if(full == 1) {
    ans = b1;
  } else {
    ans = b2 + b3 + (full - 2) * b4;
  }
  cout << ans << endl;
}

```