#P6586. Great Set Completion

    ID: 19798 Type: Default 1000ms 256MiB

Great Set Completion

Great Set Completion

Given a set S of n distinct integers and an initial subset G of S consisting of m integers, the set G is required to satisfy the following closure condition with respect to a fixed integer (a):

  • If \(x \in G\), then if \(x+a\) belongs to S, it must also be in G.
  • If \(x+a\) is not in S, then no action is needed.
  • A set \(G\) is considered complete (or "perfect") if no additional element needs to be added according to the rule above.

Your task is to determine whether the given set G is already complete. If it is, print Great Set!. Otherwise, determine the minimum number of elements that need to be added to G (following the rule) to make it complete, and output that number.

inputFormat

The input consists of three lines:

  1. The first line contains three integers (n), (m) and (a) ((1 \le m \le n)) where (n) is the number of distinct integers in S, (m) is the number of integers initially in G, and (a) is the fixed increment.

  2. The second line contains (n) space-separated integers representing the set S.

  3. The third line contains (m) space-separated integers representing the initial subset G. All numbers in G are guaranteed to be in S.

outputFormat

If the given set G is already complete (i.e. no additional numbers need to be added to satisfy the closure rule), output:

Great Set!

Otherwise, output a single integer representing the minimum number of additional elements that must be added to G to make it complete.

sample

5 2 2
1 3 5 7 9
1 5
3