You are given a rebus of form ? + ? - ? + ? = n, consisting of only question marks, separated by arithmetic operation '+' and '-', equality and positive integer n. The goal is to replace each question mark with some positive integer from 1 to n, such that equality holds.


-----Input-----

The only line of the input contains a rebus. It's guaranteed that it contains no more than 100 question marks, integer n is positive and doesn't exceed 1 000 000, all letters and integers are separated by spaces, arithmetic operations are located only between question marks.


-----Output-----

The first line of the output should contain "Possible" (without quotes) if rebus has a solution and "Impossible" (without quotes) otherwise.

If the answer exists, the second line should contain any valid rebus with question marks replaced by integers from 1 to n. Follow the format given in the samples.


-----Examples-----
Input
? + ? - ? + ? + ? = 42

Output
Possible
9 + 13 - 39 + 28 + 31 = 42

Input
? - ? = 1

Output
Impossible

Input
? = 1000000

Output
Possible
1000000 = 1000000

Difficulty: competition

Starter code:

Solutions:
#!/bin/python3

a = input()
while a:
    expr, n = a.split('=')
    n = int(n.strip())
    pos = 1
    neg = 0
    sg = [1]
    for c in expr:
        if c == '+':
            pos += 1
            sg.append(1)
        elif c == '-':
            neg += 1
            sg.append(0)
    csum = pos - neg
    rez = []
    for i in sg:
        if csum < n:
            if i > 0:
                v = min(n-csum, n-1)
                csum += v
                rez.append(1+v)
            else:
                rez.append(-1)
        else:
            if i > 0:
                rez.append(1)
            else:
                v = min(csum - n, n-1)
                csum -= v
                rez.append(-1-v)
    if csum == n:
        print("Possible")
        ans = str(rez[0])
        for j in rez[1:]:
            ans += " " + ("+" if j > 0 else "-") + " "
            ans += str(abs(j))
        ans += " = " + str(n)
        print(ans)
    else:
        print("Impossible")
    break
    a = input()


#!/usr/bin/env python3

import re

try:
    while True:
        s = input()
        n = int(s[s.rfind(' '):])
        pos = s.count('+') + 1
        neg = s.count('-')
        if n * pos - neg < n or pos - n * neg > n:
            print("Impossible")
        else:
            print("Possible")
            need = n - (pos - neg)
            prev = '+'
            first = True
            for m in re.finditer(r"[+-]", s):
                if first:
                    first = False
                else:
                    print(prev, end=' ')

                if prev == '+' and need > 0:
                    x = min(need + 1, n)
                    need -= x - 1
                elif prev == '-' and need < 0:
                    x = min(-need + 1, n)
                    need += x - 1
                else:
                    x = 1

                print(x, end=' ')
                prev = m.group()

            if not first:
                print(prev, end=' ')

            if prev == '+' and need > 0:
                x = min(need + 1, n)
                need -= x - 1
            elif prev == '-' and need < 0:
                x = min(-need + 1, n)
                need += x - 1
            else:
                x = 1

            print(x, '=', n)

except EOFError:
    pass


#!/usr/bin/env python3


def main():
    s = input().split()
    n = int(s[-1])
    xs = [1] + [int(x + '1') for x in s[1:-2:2]]

    d = sum(xs) - n
    if d > 0:
        for i, x in enumerate(xs):
            if d == 0:
                break
            if x < 0:
                xs[i] = -min(n, d + 1)
                d += xs[i] + 1
    elif d < 0:
        for i, x in enumerate(xs):
            if d == 0:
                break
            if x > 0:
                xs[i] = min(n, -d + 1)
                d += xs[i] - 1

    if sum(xs) == n:
        print('Possible')
        print('{} = {}'.format(' '.join(('+ ' if x > 0 else '- ') + str(abs(x)) for x in xs)[2:], n))
    else:
        print('Impossible')


def __starting_point():
    main()

__starting_point()

import sys

input = sys.stdin.readline()

possible = False
input = "+ " + input.strip()
inparse = input.split(' ')
n = int(inparse[-1])
items = inparse[0:-2]
nums = []
for i in range(0, int(len(items)/2)):
    if (items[i*2] == '+'): nums.append(1)
    else: nums.append(-1)
sumnum = sum(nums)

while (sumnum != n):
    found = False
    deficit = abs(sumnum - n);
    if (sumnum < n):
        for i in range(0, len(nums)):
            if nums[i] < n and nums[i] >= 1:
                nums[i] = min(nums[i] + deficit, n);
                found = True
                break;
    elif (sumnum > n):
        for i in range(0, len(nums)):
            if nums[i] > -1*n and nums[i] <= -1:
                nums[i] = max(nums[i] - deficit, -1*n)
                found = True
                break;
    sumnum = sum(nums)
    if not found: break;

if sumnum == n:
    possible = True

if possible: 
    print("Possible")
    outstr = ""
    for i in nums:
        if i > 0:
            outstr = outstr + ' + ' + str(abs(i))
        else:
            outstr = outstr + ' - ' + str(abs(i))
    outstr = outstr + " = " + str(n)
    print(outstr.strip()[2:])
else: print("Impossible")


def max(a, b):
	if(a>=b):
		return a
	else:
		return b

####################################

s=input().split()
length=len(s)
n=int(s[length-1])

plus=1
minus=0


for i in s:
	if(i== '+'):
		plus+=1
	if(i== '-'):
		minus+=1

if(plus*n - minus < n or plus - n*minus > n):
	print('Impossible')
	return
else:
	print('Possible')

for i in range(0, length-1, 2): #initializing all placeholders with 1
	s[i]='1'


# if(minus==0):
# 	s[0]= repr(n-plus+1)

# else:


# 	diff=plus-1-minus


# 	if(diff>0):
# 		s[0]=repr(n-diff)
# 		for i in range(2, length-1, 2):
# 			s[i]='1'

# 	flag=0
# 	if(diff<=0):
# 		s[0]=repr(n)
# 		for i in range(2, length-1, 2):
# 			s[i]='1'
# 			if(flag==0 and s[i-1] == '+'):
# 				flag=1
# 				s[i]=repr(1-diff)

res=n-plus+minus
for i in range(0, length-1, 2):
	if((i==0 or s[i-1]=='+' ) and res>0):
		val=int(s[i])
		if(res>n-val):
			res-=(n-val)
			s[i]=repr(n)
		else:
			val+=res
			s[i]=repr(val)
			res=0
	elif(s[i-1]=='-' and res<0):
		val=int(s[i])
		if(res<val-n):
			res+=(n-val)
			s[i]=repr(n)
		else:
			val-=res
			s[i]=repr(val)
			res=0





print(' '.join(s))







a=list(input().split())
b,c=1,0
for i in a:
    if i=='-':
        c=c+1
    elif i=='+':
        b=b+1
    elif i!='?' and i!='=':
        n=int(i)
if b-c*n<=n and n<=b*n-c:
    print('Possible')
    b0=[]
    for i in range(b):
        b0.append(1)
    c0=[]
    for i in range(c):
        c0.append(1)
    
    x=b-c-n
    if x<0:
        i=0
        while x+n-1<0:
            b0[i]=n
            x=x+n-1
            i=i+1
        if x!=0:
            b0[i]=-x+1
    else:
        i=0
        while x-n+1>0:
            c0[i]=n
            x=x-n+1
            i=i+1
        if x!=0:
            c0[i]=x+1
    s=str(b0[0])
    b=1
    c=0
    for i in a:
        if i=='-':
            s=s+' - '+str(c0[c])
            c=c+1
        elif i=='+':
            s=s+' + '+str(b0[b])
            b=b+1
        elif i=='=':
            print(s+' = '+str(n))            
else:
    print('Impossible')#'''


s = input().split()

nrpoz = 0
nrneg = 0

for i in s:
	if i == '+':
		nrpoz += 1 
	if i == '-':
		nrneg += 1

if s[0] == '?':
	nrpoz += 1

n = int(s[-1])
# print(nrpoz, nrneg, n)

if nrpoz * n - nrneg >= n >= nrpoz - nrneg * n:
	print('Possible')
else:
	print('Impossible')
	return

neg = []
poz = []

if nrpoz - nrneg > n:
	#toate pozitive o sa fie 1
	#negativele tre sa aiba suma nrpoz - n;
	poz = [1] * nrpoz;
	neg = [1] * nrneg;
	sn = nrneg;
	for i in range(len(neg)):
		if sn < nrpoz - n:
			neg[i] += min(nrpoz - n -sn, n - neg[i])
			sn += neg[i] - 1
else:
	neg = [1] * nrneg
	poz = [1] * nrpoz
	sp = nrpoz - nrneg;
	for i in range(len(poz)):
		if sp < n:
			poz[i] += min(n - poz[i], n - sp)
			sp += poz[i] - 1

sgn = '+'
ipoz, ineg = 0, 0
for i in s:
	if i == '?':
		if sgn == '+':
			print(poz[ipoz], end = ' ')
			ipoz += 1
		else:
			print(neg[ineg], end = ' ')
			ineg += 1
	else:
		sgn = i
		print(i, end = ' ')

s = input().split()
n=int(s[-1])
val = 0
sign = 1
ls = []
for c in s[:-2]:
	if c == '+': sign = 1
	elif c == '-': sign = -1
	elif c == '?': 
		ls.append(sign)
		val+=sign
	else:
		print(c)
for i in range(len(ls)):
	if val > n:
		if ls[i]>0: continue
		ls[i]-= min(n-1, val-n)
		val-= min(n-1, val-n)
	elif val < n:
		if ls[i]<0: continue
		ls[i]+=min(n-1,n-val)
		val+=min(n-1,n-val)
if val != n:
	print("Impossible")
else:
	print("Possible")
	print("".join([(" + " if v>0 else " - ")+str(abs(v)) for v in ls])[3:]+" = "+str(n))


s = input().split()
t = s[::]
req = int(s[-1])
lim = req
S = 0
for i in range(len(s)):
	if s[i] == '?':
		s[i] = '1'
		S += 1 if i == 0 or s[i - 1] == '+' else -1

if S < req:
	for i in range(len(s)):
		if t[i] == '?':
			sign = 1 if i == 0 or s[i - 1] == '+' else -1
			if sign == 1:
				d = min(req - S, lim - 1)
				s[i] = str(d + 1)
				S += d
else:
	for i in range(len(s)):
		if t[i] == '?':
			sign = 1 if i == 0 or s[i - 1] == '+' else -1
			if sign == -1:
				d = min(S - req, lim - 1)
				s[i] = str(d + 1)
				S -= d
if S == req:
	print("Possible")
	print(' '.join(s))
else:
	print("Impossible")



s=input()
a=s.split()

tot=0
b=[1 if x=='?' else x for x in a]
for i,x in enumerate(b):
    if x==1:
        if i==0 or b[i-1]=='+':
            tot+=1
        elif b[i-1]=='-':
            tot-=1

goal=int(b[-1])
if tot<goal:
    for i,x in enumerate(b):
        if x==1 and i==0 or b[i-1]=='+' and tot<goal:
            a=min(goal-1,goal-tot)
            tot+=a
            b[i]+=a

elif tot>goal:
    for i,x in enumerate(b):
        if x==1 and b[i-1]=='-' and tot>goal:
            a=min(goal-1,tot-goal)
            tot-=a
            b[i]+=a
            
if tot!=goal:
    print("Impossible")
else:
    print("Possible")
    print(' '.join([str(x) for x in b]))




sgn, a, b = 1, 0, 0
sol = ""
ok = 0
for ch in input().split():
    if ch == '?':
        if sgn == 1:
            a += 1
            ch = 'P'
        else:
            b += 1
            ch = 'M'
    elif ch == '+':
        sgn = 1
    elif ch == '-':
        sgn = -1
    elif ch != '=':
        n = int(ch)
        ok = 1
    if not ok:
        sol += ch
pl, mn = [n]*a, [1]*b
s = n*a-b
i, j = 0, 0
while s > n and (i < a or j < b):
    if i < a:
        amt = min(s-n, n-1)
        pl[i] -= amt
        s -= amt
        i += 1
    else:
        amt = min(s-n, n-1)
        mn[j] += amt
        s -= amt
        j += 1
if s != n:
    print("Impossible")
else:
    print("Possible")
    for ch in sol:
        if ch != 'P' and ch != 'M':
            print(ch, end = ' ')
        elif ch == 'P':
            print(pl[-1], end = ' ')
            pl.pop()
        else:
            print(mn[-1], end = ' ')
            mn.pop()
    print(n)