soon and she wants to divide it into two subsequences.are different and subsequences can be empty, so there are. , Nami will call it a great division if and only if the following conditions hold:. If there are several possible sequences, you can print any of them. If there is no sequence with the greatness equal to
Nami will get a sequence S S of n n positive integers S_1, S_2, dots, S_n S 1 ,S 2 ,…,S n soon and she wants to divide it into two subsequences. At first, Nami has two empty sequences S_A S A and S_B S B . She will consider each integer in S S in order, and append it to either S_A S A or S_B S B . Nami calls sequences S_A, S_B S A ,S B she gets in the end a division of S S. Note that S_A S A and S_B S B are different and subsequences can be empty, so there are 2^n 2 n ways to divide S S into S_A S A and S_B S B , which means there are 2^n 2 n possible divisions of S S. For a division, supposing that there are n_A n A integers in S_A S A and n_B n B integers in S_B S B , Nami will call it a great division if and only if the following conditions hold: S_{A,1}leq S_{A,2}leq dotsleq S_{A,n_A} S A,1 ≤S A,2 ≤⋯≤S A,n A S_{B,1}geq S_{B,2}geq dotsgeq S_{B,n_B} S B,1 ≥S B,2 ≥⋯≥S B,n B Nami defines the greatness of S S as the number of different great divisions of S S. Now Nami gives you a magic number k k, and your task is to find a sequence S S with the greatness equal to k k for her. Note that the length of S S should not exceed 365 365 and the positive integers in S S should not exceed 10^8 10 8 . If there are several possible sequences, you can print any of them. If there is no sequence with the greatness equal to k k, print -1 −1.
