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 .
|
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 |