题目描述
Problem Description
There are \( n \) distinct integers, and \( m \) of these integers belong to a set \( G \).
Aw Dun Dun has stipulated the following rules for this set:
- If \( x \in G \), then \( x + a \in G \).
- If \( x + a \) is not among the \( n \) integers, no action is taken.
- If a set \( G \) does not require any additional elements to be added, it is considered perfect.
If the set is perfect, output Great Set!. Otherwise, output the minimum number of additional ingredients needed to perfect the set according to the rules.
Input Format
The first line contains an integer \( n \), representing the total number of integers.
The next line contains \( n \) space-separated integers \( A_i \), which are distinct.
The following line contains a positive integer \( m \), indicating that there are \( m \) integers in set \( G \), all of which are among the \( n \) integers.
The next line contains \( m \) space-separated integers.
The last line contains a positive integer \( a \).
Output Format
If the set is already perfect, output Great Set!.
Otherwise, output the number of integers needed to perfect the set.
Sample Input and Output
Sample Input #1
5
1 2 3 4 5
3
1 3 5
2
Sample Output #1
Great Set!
Sample Input #2
15
13 2 10 3 1 12 8 4 5 7 9 6 15 14 11
7
13 2 1 12 8 3 10
2
Sample Output #2
8
Sample Input #3
50
13 2 10 50 1 28 37 32 30 46 19 47 33 41 24 34 27 42 49 18 9 48 23 35 31 8 7 12 6 5 3 22 43 36 11 40 26 4 44 17 39 38 15 14 25 16 29 20 21 45
10
50 46 30 32 10 2 28 37 1 13
3
Sample Output #3
31
Notes/Hints
Sample Explanation
Sample 1 Explanation
The set contains \( 1, 3, 5 \), where \( 1 + 2 = 3 \), \( 3 + 2 = 5 \), and \( 5 + 2 = 7 \) does not exist, so the set is perfect.
Sample 2 Explanation
All remaining integers belong to the set.
Data Range
- \( 1 \le m < n \le 6 \times 10^4 \).
- \( 1 \le A_i \le n \).
- \( 0 \le a \le 10^4 \).
Bundled Test Cases
| Test Point | Time Limit | Points | \( n, m \le \) |
|---|---|---|---|
| Subtask 1 | 400 ms | 10 pts | \( 10^3 \) |
| Subtask 2 | 400 ms | 15 pts | \( 10^4 \) |
| Subtask 3 | 400 ms | 35 pts | \( 3 \times 10^4 \) |
| Subtask 4 | 400 ms | 40 pts | \( 6 \times 10^4 \) |
P.S. The time limit for this problem has been set to 15 times that of the standard solution, with partial test cases provided in the attachment.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分