Problem:
 Score : 1000 points    Problem Statement Snuke got a present from his mother on his birthday.
The present was a pair of two sequences a and b , consisting of positive integers.
They satisfied all of the following properties:   The sum of all elements of a is N .  The sum of all elements of b is N .  Any string of length N that satisfies the following two conditions (1) and (2) will also satisfy the condition (3).   (1) Any of the following forms a palindrome: the first a_1 letters, the following a_2 letters, the following a_3 letters and so on.  (2) Any of the following forms a palindrome: the first b_1 letters, the following b_2 letters, the following b_3 letters and so on.  (3) All N letters are the same.    He was happy, until one day he lost both of the sequences.
Now, he only remembers that the sequence a was a permutation of another sequence A of length M .  To bring him happiness again, his mother has decided to give him another pair of sequences a and b that satisfies his favorite properties and is consistent with his memory.      Constraints  1≦N≦10^5  1≦M≦100  1≦A_i≦10^5  The sum of all A_i equals N .         Input The input is given from Standard Input in the following format:  N  M  A_1  A_2  ...  A_M       Output If there exists a pair of sequences a and b that satisfies the properties and is consistent with Snuke's memory, print three lines. The first line must contain the sequence a , the second line must contain the length of the sequence b , and the third line must contain the sequence b .  If such a pair does not exist (because Snuke's memory is wrong or some other reason), print a single line containing the word Impossible (case-sensitive).        Sample Input 1 3 2
2 1      Sample Output 1 1 2
1
3       Sample Input 2 6 1
6      Sample Output 2 6
3
1 2 3       Sample Input 3 55 10
1 2 3 4 5 6 7 8 9 10      Sample Output 3 Impossible

Solution (Python):
from sys import exit
n, m = map(int, input().split())
a = list(map(int, input().split()))

odd = []
even = []
for x in a:
	if x%2 == 0:
		even.append(x)
	else:
		odd.append(x)

if n%2 == 0:
	if len(odd) > 2:
		print("Impossible")
		exit()
	if len(odd) == 2:
		a = [odd[0]] + even + [odd[1]]
		b = [odd[0]+1] + even + [odd[1]-1]
		if b[-1] == 0:
			b.pop()
	else:
		a = even
		b = [1] + even
		b[-1] -= 1
		if b[-1] == 0:
			b.pop()

else:
	if len(odd) > 1:
		print("Impossible")
		exit()
	if m == 1:
		b = [1, n-1]
	else:
		a = odd + even
		b = [odd[0]+1] + even
		b[-1] -= 1
	if b[-1] == 0:
		b.pop()

print(*a)
print(len(b))
print(*b)

Solution (Python):
from sys import exit
n, m = map(int, input().split())
a = list(map(int, input().split()))

odd = []
even = []
for x in a:
	if x%2 == 0:
		even.append(x)
	else:
		odd.append(x)

if n%2 == 0:
	if len(odd) > 2:
		print("Impossible")
		exit()
	if len(odd) == 2:
		a = [odd[0]] + even + [odd[1]]
		b = [odd[0]+1] + even + [odd[1]-1]
		if b[-1] == 0:
			b.pop()
	else:
		a = even
		b = [1] + even
		b[-1] -= 1
		if b[-1] == 0:
			b.pop()

else:
	if len(odd) > 1:
		print("Impossible")
		exit()
	if m == 1:
		b = [1, n-1]
	else:
		a = odd + even
		b = [odd[0]+1] + even
		b[-1] -= 1
	if b[-1] == 0:
		b.pop()

print(*a)
print(len(b))
print(*b)

Solution (Python):
import sys


def solve(n, m, arr):
    odds = []
    evens = []
    for a in arr:
        if a % 2 == 0:
            evens.append(a)
        else:
            odds.append(a)

    if len(odds) > 2:
        print('Impossible')
        return

    if len(odds) == 2:
        o1, o2 = odds
        aaa = [o1] + evens + [o2]
        bbb = [2] * (o1 // 2 + 1)
        bbb += evens
        bbb += [2] * (o2 // 2)

    elif len(odds) == 1:
        if odds[0] == 1:
            aaa = odds + evens
            bbb = evens + odds
        elif evens:
            aaa = odds + evens
            bbb = [odds[0] - 1] + evens[:-1] + [evens[-1] + 1]
        else:
            aaa = odds
            bbb = [odds[0] // 2, odds[0] // 2 + 1]

    else:
        aaa = evens
        bbb = [1] + evens[:-1] + [evens[-1] - 1]

    print(*aaa)
    print(len(bbb))
    print(*bbb)


n, m, *aaa = map(int, sys.stdin.buffer.read().split())
solve(n, m, aaa)

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[]
o=[]
for i in a:
  if i%2:o.append(i)
  else:b.append(i)
if len(o)>2:print("Impossible");exit()
if len(o)==1:b=o+b
elif len(o)==2:b=[o[0]]+b+[o[1]]
ans=[]
for i in range(len(b)):
  if i==0:ans.append(b[i]-1)
  elif i==len(b)-1:ans.append(b[i]+1)
  else:ans.append(b[i])
anss=[]
for i in ans:
  if i!=0:anss.append(i)
if sum(anss)!=n:anss.append(n-sum(anss))
print(*b)
print(len(anss))
print(*anss)

Solution (Python):
n,m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

breakFlag = False
for i in range(1,m-1):
    if a[i]%2==1:
        if a[0]%2==1:
            if a[len(a)-1]%2==1:
                print("Impossible")
                breakFlag = True
                break
            else:
                a[i],a[len(a)-1] = a[len(a)-1],a[i]
        else:
            a[i],a[0] = a[0],a[i]

if breakFlag==False:
    ans = ''.join([str(s)+" " for s in a])
    print(ans[:-1])
    if m==1:
        if a[0]>1:
            a[0]-=1
            a.append(1)
            print(m+1)
        else:
            print(m)
    else:
        if a[len(a)-1]==1:
            print(m-1)
            a.pop()
            a[0]+=1
        else:
            print(m)
            a[0]+=1
            a[len(a)-1] -= 1
    ans = ''.join([str(s)+" " for s in a])
    print(ans[:-1])

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N,M = map(int,readline().split())
A = [int(x) for x in readline().split()]

OD = [x for x in A if x&1]
EV = [x for x in A if not x&1]

if len(OD) >= 3:
    print('Impossible')
    exit()

if len(A) == 1:
    if N == 1:
        B = [1]
    else:
        B = [1,N-1]
elif len(OD) == 0:
    B = A.copy()
    B[0] -= 1
    B[-1] += 1
elif len(OD) == 1:
    A = OD + EV
    B = A.copy()
    B[0] += 1
    B[-1] -= 1
else:
    A = [OD[0]] + EV + [OD[-1]]
    B = A.copy()
    B[0] += 1
    B[-1] -= 1
B = [x for x in B if x > 0]

print(*A)
print(len(B))
print(*B)

Solution (Python):





"""
agc001 D
"""

n, m = map(int, input().split())
ali = list(map(int, input().split()))

if m == 1 and ali[0] == 1:
    print(1)
    print(1)
    print(1)
    exit()

if m == 1:
    print(ali[0])
    print(2)
    print(ali[0]-1, 1)
    exit()

flag = 0
c = []
for a in ali:
    if a % 2 == 1:
        if flag == 0:
            lm = a
            flag += 1
        elif flag == 1:
            rm = a
            flag += 1
        elif flag == 2:
            print('Impossible')
            exit()
    else:
        c.append(a)

if flag == 0:
    lm = c[0]
    del c[0]
    rm = c.pop()

if flag == 1:
    rm = c.pop()

b = [lm+1] + c
d = [lm] + c + [rm]

if rm > 1:
    b.append(rm-1)


print(" ".join(map(str, d)))
print(len(b))
print(" ".join(map(str, b)))

Solution (Python):

def solve(n, m, a):
    odd = []
    even = []
    for a_i in a:
        if a_i % 2 == 0:
            even += [ a_i ]
        else:
            odd += [ a_i ]
    if len(odd) >= 3:
        return None
    a, b = [], []
    if odd:
        x = odd.pop()
        a += [ x ]
        b += [ x - 1 ]
    else:
        x = even.pop()
        a += [ x ]
        b += [ x - 1 ]
    a += even
    b += even
    if odd:
        x = odd.pop()
        a += [ x ]
        b += [ x + 1 ]
    else:
        b += [ 1 ]
    return a, b

n, m = map(int, input().split())
a = list(map(int, input().split()))
it = solve(n, m, a)
if it is None:
    print('Impossible')
else:
    a, b = it
    b = list(filter(lambda b_i: b_i, b))
    print(*a)
    print(len(b))
    print(*b)

Solution (Python):
S, N = map(int, input().split())
A = list(map(int, input().split()))
O = [a for a in A if a % 2 == 1]
E = [a for a in A if a % 2 == 0]

if len(O) > 2:
    print("Impossible")
else:
    A = O[:min(len(O), 1)] + E + O[1:]
    B = A[:] + ([0] if N == 1 else [])
    B[0] -= 1
    B[-1] += 1
    if B[0] == 0:
        B = B[1:]
    print(*A, sep=" ")
    print(len(B))
    print(*B, sep=" ")

Solution (Python):
S, N = map(int, input().split())
A = list(map(int, input().split()))
O = [a for a in A if a % 2 == 1]
E = [a for a in A if a % 2 == 0]

if len(O) > 2:
    print("Impossible")
else:
    A = O[:min(len(O), 1)] + E + O[min(1, len(O)):]
    B = A[:] + ([0] if len(A) == 1 else [])
    B[0] -= 1
    B[-1] += 1
    if B[0] == 0:
        B = B[1:]
    print(" ".join(str(a) for a in A))
    print(len(B))
    print(" ".join(str(b) for b in B))

Solution (Python):
n, m = map(int, raw_input().split())
a = map(int,raw_input().split())

cntodd = 0
for x in a:cntodd += x % 2

if cntodd > 2:
    print "Impossible"
    exit()
evens = [x for x in a if x % 2 == 0]
odds = [x for x in a if x % 2 == 1]

if len(a) == 1:
    if a[0] == 1:
        print 1
        print 1
        print 1
        exit()
    print a[0]
    print 2
    print a[0]-1,1
    exit()
    
if cntodd == 2:
    a = [odds[0]] + evens + [odds[1]]
    b = a[::]
    b[0] += 1
    b[-1] -= 1

if cntodd == 1:
    a = [odds[0]] + evens
    b = a[::]
    b[0] += 1
    b[-1] -= 1

if cntodd == 0:
    a = evens
    b = a[::]
    b[0] += 1
    b[-1] -= 1

if b[-1] == 0:
    b = b[:-1]
    
print " ".join(map(str, a))
print len(b)
print " ".join(map(str, b))

Solution (Python):
from sys import stdout
def main():
    n, m = map(int, raw_input().split())
    a = map(int, raw_input().split())
    if m == 1:
        print a[0]
        if n == 1:
            print 1
            print 1
        else:
            print 2
            print 1, n - 1
        return
    if sum(x % 2 for x in a) > 2:
        print "Impossible"
        return
    a.sort(key=lambda x: x%2)
    a = a[-1:] + a[:-1]
    t = a[:]
    t[0] += 1
    t[-1] -= 1
    if not t[-1]:
        t.pop()
    stdout.write(' '.join(map(str, a)))
    stdout.write('\n')
    stdout.write(str(len(t)) + '\n')
    stdout.write(' '.join(map(str, t)))
    stdout.write('\n')
main()