// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// Union-Find 木 (Verified: AtCoder Typical Contest 001 B)
struct UnionFind {
private:
    const int n;
    int __size;
    vector<int> uf;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い
    UnionFind(int _n) : n(_n), __size(_n), uf(_n, -1) {}
    // find (木の根を求める)
    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか
    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数
    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか
    int size()      {return __size;}
    // x と y の属する集合を併合
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return;
        __size--;
        if(uf[y] < uf[x]) swap(x, y);
        uf[x] += uf[y]; uf[y] = x;
    }
};

const int W = 7;
int board[100010][W];
signed main() {
    int N, M, Q; cin >> N >> M >> Q;

    for(int i=0; i<Q; i++) {
        int A; cin >> A;
        for(int k=A; k<M*W; k+=M) {
            int r = k / W, c = k % W;
            board[r][c] = 1;
        }
    }

    int ans = 0;
    UnionFind uf(M*W);
    for(int i=0; i<M; i++) {
        for(int j=0; j<W; j++) {
            for(int k=0; k<4; k++) {
                int ni = i + dx[k], nj = j + dy[k];
                if(ni < 0 or ni >= M or nj < 0 or nj >= W) continue;
                if(board[i][j] == board[ni][nj]) {
                    int u = i  * W + j ;
                    int v = ni * W + nj;
                    uf.unite(u, v);
                }
            }
        }
    }

    set<int> white;
    for(int i=0; i<M; i++) {
        if(N == i) ans += white.size();
        for(int j=0; j<W; j++) {
            if(board[i][j] == 0) white.insert(uf.find(i * W + j));
        }
    }
    if(N >= M) ans += white.size();
    fprintf(stderr, "temp ans = %lld\n", ans);

    int add = 0;
    UnionFind uf2((M+1)*W);
    for(int i=0; i<M; i++) {
        for(int j=0; j<W; j++) {
            for(int k=0; k<4; k++) {
                int ni = i + dx[k], nj = j + dy[k];
                int mi = ni, mj = nj;
                if(ni < 0) ni = M - 1, mi = M;
                if(ni >= M or nj < 0 or nj >= W) continue;
                if(board[i][j] == board[ni][nj]) {
                    int u = i  * W + j;
                    int v = mi * W + mj;
                    uf2.unite(u, v);
                }
            }
        }
    }

    set<int> white2, ng;
    for(int j=0; j<W; j++) {
        ng.insert(uf2.find(M*W + j));
        white2.insert(uf2.find(M*W + j));
    }

    int mod = N % M;
    for(int i=0; i<M; i++) {
        if(i == mod and N >= M) ans += white2.size() - ng.size();
        for(int j=0; j<W; j++) {
            if(board[i][j] == 0) white2.insert(uf2.find(i * W + j));
        }
    }
    
    add += white2.size();
    add -= ng.size();
    fprintf(stderr, "add = %lld\n", add);

    ans += add * max(0LL, (N / M - 1));
    cout << ans << endl;
    return 0;
}

### Prompt

In cpp, your task is to solve 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
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// Union-Find 木 (Verified: AtCoder Typical Contest 001 B)
struct UnionFind {
private:
    const int n;
    int __size;
    vector<int> uf;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い
    UnionFind(int _n) : n(_n), __size(_n), uf(_n, -1) {}
    // find (木の根を求める)
    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか
    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数
    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか
    int size()      {return __size;}
    // x と y の属する集合を併合
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return;
        __size--;
        if(uf[y] < uf[x]) swap(x, y);
        uf[x] += uf[y]; uf[y] = x;
    }
};

const int W = 7;
int board[100010][W];
signed main() {
    int N, M, Q; cin >> N >> M >> Q;

    for(int i=0; i<Q; i++) {
        int A; cin >> A;
        for(int k=A; k<M*W; k+=M) {
            int r = k / W, c = k % W;
            board[r][c] = 1;
        }
    }

    int ans = 0;
    UnionFind uf(M*W);
    for(int i=0; i<M; i++) {
        for(int j=0; j<W; j++) {
            for(int k=0; k<4; k++) {
                int ni = i + dx[k], nj = j + dy[k];
                if(ni < 0 or ni >= M or nj < 0 or nj >= W) continue;
                if(board[i][j] == board[ni][nj]) {
                    int u = i  * W + j ;
                    int v = ni * W + nj;
                    uf.unite(u, v);
                }
            }
        }
    }

    set<int> white;
    for(int i=0; i<M; i++) {
        if(N == i) ans += white.size();
        for(int j=0; j<W; j++) {
            if(board[i][j] == 0) white.insert(uf.find(i * W + j));
        }
    }
    if(N >= M) ans += white.size();
    fprintf(stderr, "temp ans = %lld\n", ans);

    int add = 0;
    UnionFind uf2((M+1)*W);
    for(int i=0; i<M; i++) {
        for(int j=0; j<W; j++) {
            for(int k=0; k<4; k++) {
                int ni = i + dx[k], nj = j + dy[k];
                int mi = ni, mj = nj;
                if(ni < 0) ni = M - 1, mi = M;
                if(ni >= M or nj < 0 or nj >= W) continue;
                if(board[i][j] == board[ni][nj]) {
                    int u = i  * W + j;
                    int v = mi * W + mj;
                    uf2.unite(u, v);
                }
            }
        }
    }

    set<int> white2, ng;
    for(int j=0; j<W; j++) {
        ng.insert(uf2.find(M*W + j));
        white2.insert(uf2.find(M*W + j));
    }

    int mod = N % M;
    for(int i=0; i<M; i++) {
        if(i == mod and N >= M) ans += white2.size() - ng.size();
        for(int j=0; j<W; j++) {
            if(board[i][j] == 0) white2.insert(uf2.find(i * W + j));
        }
    }
    
    add += white2.size();
    add -= ng.size();
    fprintf(stderr, "add = %lld\n", add);

    ans += add * max(0LL, (N / M - 1));
    cout << ans << endl;
    return 0;
}

```