MODSEQ - Modulo Sequence


Nevest has a sequence A with N distinct elements. She wants to have a sequence S with length M and all of the conditions below must be fulfilled:

  • For all subarrays in S of length K, the sum of each number in the subarray must be divisible by K.
  • For 1 ≤ i < j ≤ M, Si ≠ Sj must hold.
  • A must be a subsequence of S.
  • For 1 ≤ i ≤ M, constrain 1 ≤ Si ≤ 5 × 105 must be fulfilled.
  • The length of sequence S mustn't exceed 5 × 105.

Nevest is not very good at problem-solving so she asked you instead. Help Nevest by giving her any valid sequence or print "-1" if no valid sequence exist (without quotation marks).

Please note that you don't have to minimize M.

Input Format

N K
A1 A2 ... AN

Output Format

If there's a valid answer, print M in the first line followed by a line containing sequence S with M numbers. If there's no valid sequence S print "-1" (without quotation marks).

Sample Input 1

5 3
1 3 2 5 4

Sample Output 1

7
1 3 2 7 9 5 4

Sample Input 2

4 2
1 3 5 7

Sample Output 2

4
1 3 5 7

Constraints

  • 1 ≤ K ≤ N ≤ 500
  • 1 ≤ Ai ≤ 500
  • Ai ≠ Aj, for 1 ≤ i < j ≤ N

hide comments
nadstratosfer: 2020-05-21 16:19:12

Please get rid of HTML formatting that causes problems with dark (normal?) mode: http://imgbox.com/bix7PScc .

Statement is unnecessarily formal, it reads like a CodeForces problem. The task is to insert some positive integers into the input sequence so that the resulting one is made of distinct numbers and the sum of each of its contiguous K-element subsequences is a multiply of K. Ensure max(S), M <= 500000 where M = length(S).

Author's reply:
I'm really sorry for the inconvenience, I've thought the solution for a while. in HTML problem decided to get rid of the block's background (i have never used night mode to browse spoj and consider from that point of view).
Lastly, for description, I decided to keep it as it be. I've asked people about the description, and they seem okay with it. Thank you for your suggestion, have a nice day.

Last edit: 2020-05-21 17:48:44

Added by:StevenN
Date:2020-05-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem