#include <cstdio>
#include <set>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

constexpr int MAX_Q = 100000;

using ll = long long;

const ll dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };

ll n, m, q;
std::set<ll> a;
bool fld[2000000][7];

void dfs( ll v, ll h )
{
  ll i = v/7, j = v%7;

  fld[i][j] = true;

  rep( d, 4 )
  {
    ll ni = i+dy[d], nj = j+dx[d];

    if( ni >= 0 && ni < h && nj >= 0 && nj < 7 && !fld[ni][nj] )
      dfs( ni*7+nj, h );
  }

  return;
}

int main()
{
  scanf( "%lld%lld%lld", &n, &m, &q );
  rep( i, q )
  {
    ll x;
    scanf( "%lld", &x );

    a.insert( x );
  }

  ll k = m%7==0 ? 1 : 7;

  rep( i, k*m )
    fld[i/7][i%7] = a.find( i%m )!=a.end();

  ll cnt = 0;
  rep( i, k*m ) if( !fld[i/7][i%7] )
    dfs( i, k*m/7 ), ++cnt;

  rep( i, 2*k*m )
    fld[i/7][i%7] = a.find( i%m )!=a.end();

  ll cnt2 = 0;
  rep( i, 2*k*m ) if( !fld[i/7][i%7] )
    dfs( i, 2*k*m/7 ), ++cnt2;
  
  ll a, b;
  
  // cnt (7a)*1+b
  // cnt2 (7ia)*2+b
  a = cnt2-cnt, b = cnt-a;

  printf( "%lld\n", a*7*n/m/k+b );

  return 0;
}
### Prompt

Create a solution in CPP for 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
#include <cstdio>
#include <set>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

constexpr int MAX_Q = 100000;

using ll = long long;

const ll dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };

ll n, m, q;
std::set<ll> a;
bool fld[2000000][7];

void dfs( ll v, ll h )
{
  ll i = v/7, j = v%7;

  fld[i][j] = true;

  rep( d, 4 )
  {
    ll ni = i+dy[d], nj = j+dx[d];

    if( ni >= 0 && ni < h && nj >= 0 && nj < 7 && !fld[ni][nj] )
      dfs( ni*7+nj, h );
  }

  return;
}

int main()
{
  scanf( "%lld%lld%lld", &n, &m, &q );
  rep( i, q )
  {
    ll x;
    scanf( "%lld", &x );

    a.insert( x );
  }

  ll k = m%7==0 ? 1 : 7;

  rep( i, k*m )
    fld[i/7][i%7] = a.find( i%m )!=a.end();

  ll cnt = 0;
  rep( i, k*m ) if( !fld[i/7][i%7] )
    dfs( i, k*m/7 ), ++cnt;

  rep( i, 2*k*m )
    fld[i/7][i%7] = a.find( i%m )!=a.end();

  ll cnt2 = 0;
  rep( i, 2*k*m ) if( !fld[i/7][i%7] )
    dfs( i, 2*k*m/7 ), ++cnt2;
  
  ll a, b;
  
  // cnt (7a)*1+b
  // cnt2 (7ia)*2+b
  a = cnt2-cnt, b = cnt-a;

  printf( "%lld\n", a*7*n/m/k+b );

  return 0;
}
```