#D2874. Calendar 2
Calendar 2
Calendar 2
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:
Sample Input 2
10 14 8 5 6 7 8 9 10 11 12
Sample Output 2
10
The calendar looks like this:
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
inputFormat
Input Format
The input format is following:
n m q a_1 a_2 ... a_q
outputFormat
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:
Sample Input 2
10 14 8 5 6 7 8 9 10 11 12
Sample Output 2
10
The calendar looks like this:
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
样例
10 14 8
5 6 7 8 9 10 11 1210