#include <iostream>
#include <cstring>

#include <string>
#include <vector>
#include <algorithm>

#include <cassert>

using namespace std;

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define MAXM 100004
llong N, nblocks;
int K;
VI A;

int MM;
char B[7][MAXM];

int ncomps;
int C[7][MAXM];
void flood_fill(int r, int c) {
   if (r < 0 || r >= MM || c < 0 || c >= 7) return;
   if (B[c][r] == '#') return;
   if (C[c][r]) return;
   C[c][r] = ncomps;

   flood_fill(r-1, c);
   flood_fill(r, c-1);
   flood_fill(r, c+1);
   flood_fill(r+1, c);
}

int dfs(const VVI& adj, VI& vis, int u) {
   int res = 1;
   vis[u] = 1;
   for (int v : adj[u]) {
      if (!vis[v])
         res += dfs(adj, vis, v);
   }
   return res;
}

llong solve() {
   MM = (K % 7) ? K : K/7;

   //cerr << "MM: " << MM << endl;

   for (int rem : A) {
      for (; rem < 7*MM; rem += K) {
         int r = rem / 7;
         int c = rem % 7;
         B[c][r] = '#';
      }
   }

   /*
   REP(r, MM) {
      REP(c, 7)
         cerr << B[c][r];
      cerr << endl;
   }
   */

   REP(r, MM) {
      REP(c, 7) {
         if (B[c][r] != '#' && C[c][r] == 0) {
            ++ncomps;
            flood_fill(r, c);
         }
      }
   }

   /*
   REP(r, MM) {
      REP(c, 7)
         cerr << C[c][r] << ' ';
      cerr << endl;
   }
   */
   
   VVI adj(ncomps);
   REP(c, 7) {
      int u = C[c][0] - 1, v = C[c][MM-1] - 1;
      if (u >= 0 && v >= 0) {
         adj[u].push_back(v);
         if (u != v)
            adj[v].push_back(u);
      }
   }

   llong nblocks = N / MM;
   //cerr << "Number of blocks = " << nblocks << endl;
   llong res = 0;
   VI vis(ncomps);
   REP(u, ncomps) {
      if (vis[u]) continue;
      if (adj[u].empty())
         res += nblocks;
      else {
         bool self = find(adj[u].begin(), adj[u].end(), u) != adj[u].end();
         int cnt = dfs(adj, vis, u);
         if (self)
            ++res;
         else {
            FOR(len, 1, cnt-1) {
               if (nblocks >= len)
                  res += 2;
            }
            res += max(nblocks - cnt + 1, 0LL);
         }
      }
   }

   return res;
}


int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);

   int Q;
   cin >> N >> K >> Q;
   memset(B, '.', sizeof(B));

   A = VI(Q);
   REP(j, Q)
      cin >> A[j];

   llong res = solve();
   cout << res << endl;

   return 0;
}

### 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 <iostream>
#include <cstring>

#include <string>
#include <vector>
#include <algorithm>

#include <cassert>

using namespace std;

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define MAXM 100004
llong N, nblocks;
int K;
VI A;

int MM;
char B[7][MAXM];

int ncomps;
int C[7][MAXM];
void flood_fill(int r, int c) {
   if (r < 0 || r >= MM || c < 0 || c >= 7) return;
   if (B[c][r] == '#') return;
   if (C[c][r]) return;
   C[c][r] = ncomps;

   flood_fill(r-1, c);
   flood_fill(r, c-1);
   flood_fill(r, c+1);
   flood_fill(r+1, c);
}

int dfs(const VVI& adj, VI& vis, int u) {
   int res = 1;
   vis[u] = 1;
   for (int v : adj[u]) {
      if (!vis[v])
         res += dfs(adj, vis, v);
   }
   return res;
}

llong solve() {
   MM = (K % 7) ? K : K/7;

   //cerr << "MM: " << MM << endl;

   for (int rem : A) {
      for (; rem < 7*MM; rem += K) {
         int r = rem / 7;
         int c = rem % 7;
         B[c][r] = '#';
      }
   }

   /*
   REP(r, MM) {
      REP(c, 7)
         cerr << B[c][r];
      cerr << endl;
   }
   */

   REP(r, MM) {
      REP(c, 7) {
         if (B[c][r] != '#' && C[c][r] == 0) {
            ++ncomps;
            flood_fill(r, c);
         }
      }
   }

   /*
   REP(r, MM) {
      REP(c, 7)
         cerr << C[c][r] << ' ';
      cerr << endl;
   }
   */
   
   VVI adj(ncomps);
   REP(c, 7) {
      int u = C[c][0] - 1, v = C[c][MM-1] - 1;
      if (u >= 0 && v >= 0) {
         adj[u].push_back(v);
         if (u != v)
            adj[v].push_back(u);
      }
   }

   llong nblocks = N / MM;
   //cerr << "Number of blocks = " << nblocks << endl;
   llong res = 0;
   VI vis(ncomps);
   REP(u, ncomps) {
      if (vis[u]) continue;
      if (adj[u].empty())
         res += nblocks;
      else {
         bool self = find(adj[u].begin(), adj[u].end(), u) != adj[u].end();
         int cnt = dfs(adj, vis, u);
         if (self)
            ++res;
         else {
            FOR(len, 1, cnt-1) {
               if (nblocks >= len)
                  res += 2;
            }
            res += max(nblocks - cnt + 1, 0LL);
         }
      }
   }

   return res;
}


int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);

   int Q;
   cin >> N >> K >> Q;
   memset(B, '.', sizeof(B));

   A = VI(Q);
   REP(j, Q)
      cin >> A[j];

   llong res = solve();
   cout << res << endl;

   return 0;
}

```