Non‐Complete Signed Sum Partition

You are given two integers n and m. Your task is to partition m into n distinct positive integers a₁, a₂, …, a_n (i.e. a₁ + a₂ + … + a_n = m), such that there exists at least one number x (with 1 ≤ x ≤ m) that cannot be represented in the form

$$\sum_{i=1}^{n} k_i\,a_i \quad\text{with } k_i\in\{-1,0,1\}, $$

If there is no valid partition, output -1.

If there is a valid partition, output any one valid set of n distinct positive integers that sum to m and also output one such number x (with 1 ≤ x ≤ m) that cannot be represented as any expression of the form above. Note that when forming the expression each number a_i can be used at most once with a coefficient from {−1, 0, 1}.

Note: A classical fact is that if you have a set with a₁ = 1 and for every i (2 ≤ i ≤ n) a_i ≤ 1 + \(\sum_{j=1}^{i-1}a_j\) then every number in [1, m] is representable (using only addition). Thus, to ensure there is a gap, the set must violate that condition for at least one index.

Construction Hint: One way to guarantee a gap is to force all representable values to be confined to a strict residue class modulo some number. For example, if all chosen numbers are even then any expression
with coefficients in {−1, 0, 1} yields an even number. However, note that a set of all evens sums to an even number. Hence, one set of solutions is to use the following constructions:

• If n = 1: If m > 1, choose {m} (the only expression can only produce m, −m and 0, so any other number in [1, m] is a gap). Otherwise output -1.
• If n ≥ 2: A valid solution exists provided m is large enough. In our solutions we assume that m must be greater than (n-1)×(n+2). Then we use one of two constructions.
  • Mixed Partition: If m ≠ n^2+n-1, let
    
    For i = 1, 2, …, n-1 set ai = 2×i (all even numbers), and let an = m - n×(n-1). Since the first n-1 numbers are even, many of the sums will be even. In many cases one can show that at least one number (often 1, or some other small integer) is not representable. (The program finds the gap by enumerating all 3ⁿ expressions.)
  • Alternative Partition: When m = n^2+n-1 (a borderline case for the mixed construction), we choose a set which avoids accidental creation of a gap gap by differences of 1. For example, for n = 2 output {1,4} and for n ≥ 3 output the set
    {1, 3, 5, ..., 2n-3, m - (1+3+⋯+(2n-3))}. A brute force check (via enumeration over all choices of {−1,0,1} coefficients) is used to determine a valid missing number x in [1, m].

If multiple answers exist, any one is acceptable.

inputFormat

The input consists of two space‐separated integers n and m.

Constraints (for the purposes of our solutions):

• If n = 1: m ≥ 1.
• If n ≥ 2: assume m > (n-1)×(n+2) so that a solution exists.

outputFormat

If no valid partition exists, output a single line with -1.
Otherwise, output two lines: the first line contains the n distinct positive integers a1, a2, …, an (separated by spaces) which sum to m, and the second line contains one integer x (1 ≤ x ≤ m) that cannot be represented in the form $$ \sum_{i=1}^{n} k_i\,a_i, \quad k_i \in \{-1,0,1\}. $$

sample

1 2

2
1

</p>