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

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

long long n, m, q;
vector<int> a;

int f(int r){
    int w = r*7, res = 0;
    vector<bool> vsd(w, false);
    for(int i=0;i<q;i++){
        int v = a[i];
        while(v < w){
            vsd[v] = true;
            v += m;
        }
    }
    for(int i=0;i<w;i++){
        if(vsd[i]) continue;
        res++;
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            if(vsd[v]) continue;
            vsd[v] = true;
            if(v%7 > 0 && !vsd[v-1]) q.push(v-1);
            if(v%7 < 6 && !vsd[v+1]) q.push(v+1);
            if(v/7 > 0 && !vsd[v-7]) q.push(v-7);
            if(v+7 < w && !vsd[v+7]) q.push(v+7);
        }
    }
    return res;
}

int main(void){
    cin >> n >> m >> q;
    a.assign(q, 0);
    for(int i=0;i<q;i++) cin >> a[i];
    long long x = m, y;
    if(m%7 == 0) x = m / 7;
    y = n / x;
    long long b = f(x);
    long long a = f(x*2) - b;

    cout << b + a * (y-1) << endl;

}