#P8284. Erinyes' Concert Special Sequence

    ID: 21463 Type: Default 1000ms 256MiB

Erinyes' Concert Special Sequence

Erinyes' Concert Special Sequence

Erinyes' school is organizing a concert, but to join the program, each student must pass a test. Given two integers (n) and (k), representing the number of students and the maximum frequency permissible for any number, you need to construct a sequence (a = [a_1, a_2, \dots, a_n]) of (n) integers satisfying the following conditions:

  1. For every (i) with (1 \le i \le n-1), [ a_i = \gcd(a_{i+1}, a_{i+2}, \dots, a_n), ]
  2. For every (i) with (1 \le i \le n), (1 \le a_i \le 10^5).
  3. For each integer (x) with (1 \le x \le 10^5), the number (x) appears at most (k) times in the sequence.

Note that by the property of the (\gcd), it can be deduced that the sequence must satisfy

[ a_1 = a_2 = \dots = a_n = x \quad (\text{for some } x \in [1, 10^5]). ]

Thus, a valid sequence is uniquely determined by choosing a number (x) in the range ([1, 10^5]) as long as the frequency condition (n \le k) holds.

Output Specification:

  • If no valid sequence exists (i.e. when (n > k)), output exactly the line "Impossible".
  • If the total number (l) of valid sequences satisfies (1 \le l \le 4), then output the actual count (l) on the first line, followed by (l) lines each containing one sequence (the elements separated by a single space).
  • If (l \ge 5), then output "5 or more" on the first line and then output the lexicographically smallest 5 sequences (one per line). Sequences are compared in lexicographical order.

Since every valid sequence has every element equal, the lexicographical order is determined by the chosen number (x).

inputFormat

Input consists of a single line with two integers (n) and (k) separated by a space.

outputFormat

Refer to the problem statement for the required output format. Note the following special cases:

  • Output "Impossible" (without quotes) if no valid sequence exists.
  • If there are between 1 and 4 valid sequences, first output the count (l), and then each valid sequence on a new line.
  • If there are 5 or more valid sequences, first output "5 or more", and then the lexicographically smallest 5 sequences (one per line). In each sequence, the (n) numbers are separated by a single space.

sample

3 3
5 or more

1 1 1 2 2 2 3 3 3 4 4 4 5 5 5

</p>