Chouti and his classmates are going to the university soon. To say goodbye to each other, the class has planned a big farewell party in which classmates, teachers and parents sang and danced.

Chouti remembered that $n$ persons took part in that party. To make the party funnier, each person wore one hat among $n$ kinds of weird hats numbered $1, 2, \ldots n$. It is possible that several persons wore hats of the same kind. Some kinds of hats can remain unclaimed by anyone.

After the party, the $i$-th person said that there were $a_i$ persons wearing a hat differing from his own.

It has been some days, so Chouti forgot all about others' hats, but he is curious about that. Let $b_i$ be the number of hat type the $i$-th person was wearing, Chouti wants you to find any possible $b_1, b_2, \ldots, b_n$ that doesn't contradict with any person's statement. Because some persons might have a poor memory, there could be no solution at all.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$), the number of persons in the party.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n-1$), the statements of people.


-----Output-----

If there is no solution, print a single line "Impossible".

Otherwise, print "Possible" and then $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$).

If there are multiple answers, print any of them.


-----Examples-----
Input
3
0 0 0

Output
Possible
1 1 1 
Input
5
3 3 2 2 2

Output
Possible
1 1 2 2 2 
Input
4
0 1 2 3

Output
Impossible



-----Note-----

In the answer to the first example, all hats are the same, so every person will say that there were no persons wearing a hat different from kind $1$.

In the answer to the second example, the first and the second person wore the hat with type $1$ and all other wore a hat of type $2$.

So the first two persons will say there were three persons with hats differing from their own. Similarly, three last persons will say there were two persons wearing a hat different from their own.

In the third example, it can be shown that no solution exists.

In the first and the second example, other possible configurations are possible.

Difficulty: interview

Starter code:

Solutions:
input()
l = list(map(int, input().split()))
d = {}
d2 = {}
ans = []
n = 1
for i in l:
    i = len(l) - i
    if i not in d:
        d[i] = n
        n += 1
    if i not in d2:
        d2[i] = 0
    if d2[i] >= i:
        d[i] = n
        d2[i] = 0
        n += 1
    ans.append(d[i])
    d2[i] += 1
nums = {}
tot = 0
for i in ans:
    tot += 1
    if i not in nums:
        nums[i] = 0
    nums[i] += 1
for i in range(len(ans)):
    if tot - nums[ans[i]] != l[i]:
        print("Impossible")
        return
print("Possible")
print(" ".join(map(str, ans)))



import math

def __starting_point():

	n = int(input())
	arr = [int(x) for x  in input().split()]


	ans  = []
	d = {}
	c = {}
	b = [0]*n
	ind  = 0 
	for i in range(n) : 
		if arr[i] in list(d.keys()) : 
			if d[arr[i]]== 0 :
				ind+=1
				c[arr[i]]=ind
				b[i]=ind
				d[arr[i]]=n-arr[i]-1
			else :
				d[arr[i]]-=1
				b[i]=c[arr[i]]
		else : 
			ind+=1
			c[arr[i]]=ind
			b[i]=ind
			d[arr[i]]=n-arr[i]-1
	ans = True
	for i in d : 
		if d[i]!=0:
			ans =False
	if ans : 
		print ("Possible")
		print(*b)
	else : 
		print("Impossible")






__starting_point()

n = int(input())
a = [int(x) for x in input().split()]
t = 0
d1 = {}
use1 = {}
use = {}
for x in a:
	if x in d1:
		if use1[x] == n - x:
			t += (n - x)
			use1[x] = 0
		use1[x] += 1
	else:
		d1[x] = 0
		t += (n - x)
		use1[x] = 1

if n != t:
	print("Impossible")
else:
	print("Possible")
	d = {}
	cv = 1
	for x in a:
		if x in d:
			if use[d[x]] == n - x:
				d[x] = cv
				cv += 1
				use[d[x]] = 0
			use[d[x]] += 1
			print(d[x], end = ' ')
		else:
			d[x] = cv
			use[d[x]] = 1
			cv += 1
			print(d[x], end = ' ')


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def main():
	n = mint()
	a = [None]*n
	r = [None]*n
	j = 0
	for i in mints():
		a[j] = (n-i, j)
		j+=1
	a.sort()
	j = 1
	i = 0
	while i < n:
		cnt = a[i][0]
		for k in range(i,i+cnt):
			if k >= n or a[k][0] != cnt:
				print("Impossible")
				return
			r[a[k][1]] = j
		j+=1
		i+=cnt
	print("Possible")
	print(*r)

main()


n = int(input())
a = list(map(int, input().split()))

a = [n-x for x in a]

groups = {}
for i, x in enumerate(a):
	if x not in groups:
		groups[x] = []
	groups[x].append(i)

hats = [0] * n
current_hat = 1

for count, ids in list(groups.items()):
	if len(ids)%count != 0:
		print("Impossible")
		return

	for g in range(len(ids)//count):
		for _id in ids[count*g:count*(g+1)]:
			hats[_id] = current_hat
		current_hat += 1

print("Possible")
print(*hats)


import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

LIST=[[] for i in range(n+1)]

for i in range(n):
    LIST[n-A[i]].append(i)

ANSLIST=[None]*(n+1)
h=1
for i in range(1,n+1):
    if len(LIST[i])%i!=0:
        print("Impossible")
        return

    else:
        j=0
        while j<len(LIST[i]):
            ANSLIST[LIST[i][j]]=h
            j+=1
            if j%i==0:
                h+=1

print("Possible")
for a in ANSLIST[:-1]:
    print(a,end=" ")




n = int(input())
b = list(map(int, input().split()))
a = [[b[i], i] for i in range(n)]
a.sort()

ans = [0] * n

cur = 0
num = 1
while cur < n:
	nec = a[cur][0]
	ng = False
	for i in range(n-nec):
		if cur+i >= n:
			ng = True
			break
		elif a[cur+i][0] != a[cur][0]:
			ng = True
			break
		else:
			ans[a[cur+i][1]] = num 

	if ng:
		print("Impossible")
		break

	num += 1
	cur += n-nec

else:
	print("Possible")
	print(*ans)

n=int(input())
a=list(map(int,input().split()))
counts=[0]*n
done=False
for i in range(n):
    counts[a[i]]+=1
for i in range(n):
    if counts[i]%(n-i)!=0:
        print("Impossible")
        done=True
        break
    else:
        counts[i]//=(n-i)
countsum=[counts[0]]
for i in range(n-1):
    countsum.append(countsum[-1]+counts[i+1])
b=[]
seen=[0]*n
for i in range(n):
    b.append(countsum[a[i]]-seen[a[i]]//(n-a[i]))
    seen[a[i]]+=1
out=""
for i in range(n):
    out+=str(b[i])+" "
if not done:
    print("Possible")
    print(out[:-1])

'''input
6
3 3 3 3 3 3
5
3 3 2 2 2
4
0 1 2 3


'''
n = int(input())
a = list(map(int, input().split()))
s = [0] * (n + 1)
v = [0] * (n + 1)
r = [0] * (n + 1)
b = [0] * n
m = 0
for i in range(n):
	a[i] = n - a[i]
	s[a[i]] += 1
for i in range(n):
	if r[a[i]] == 0:
		m += 1
		v[a[i]] = m
		r[a[i]] = a[i]
	b[i] = v[a[i]]
	r[a[i]] -= 1
	# print(b[i])
if any(x for x in r):
	print("Impossible")
	return
print("Possible")
print(*b)


from collections import Counter as C
n = int(input())
l = [*map(lambda x: n - int(x), input().split())]
c = C(l)
d = {}
# print(c)
try:
    for k, v in c.items():
        if v % k == 0:
            d[k] = v//k
        else:
            raise ValueError()
    print('Possible')
    d_ = {}
    curr = 0
    for e in l:
        # print(d, d_)
        if e in d_:
            if d_[e][1] >= e:
                curr += 1
                d_[e] = [curr, 1]
            else:
                d_[e][1] += 1
        else:
            curr += 1
            d_[e] = [curr, 1]
        print(d_[e][0], end=' ')
except:
    print('Impossible')

from collections import Counter

n = int(input())
a = tuple((n - int(x) for x in input().split()))
a1 = [[] for _ in range(n + 2)]
''' :type: list[list[int]] '''
b = [1] * n
for i in range(n):
	a1[a[i]].append(i)
i = 1
m = 1
for k in range(1, n + 1):
	for j in a1[k]:
		b[j] = i
		if m == k:
			m = 1
			i += 1
		else:
			m += 1
	if m != 1:
		print('Impossible')
		break
else:
	print('Possible')
	print(*b)


n = int(input())
a = list(map(int, input().split()))
b = [0] * n
for i in range(n):
    b[i] = n - a[i]
cnt = [[] for i in range(n + 1)]
for i in range(n):
    cnt[b[i]].append(i)
f = True
for i in range(1, n + 1):
    if len(cnt[i]) % i != 0:
        f = False
        break
if not f:
    print("Impossible")
else:
    t = 1
    ans = [0] * n
    for i in range(1, n + 1):
        x = cnt[i]
        if len(x) != 0:
            y = 0
            for j in x:
                ans[j] = t
                y += 1
                if y == i:
                    t += 1
                    y = 0
    print("Possible")
    print(*ans)

n = int(input())
a = [(n - int(x)) for x in input().split()]
b = [0] * n
fh = 1
i = 0
hd = dict()
while i < n:
    if a[i] == 1:
        b[i] = fh
        fh += 1
    elif a[i] in hd:
        b[i] = hd[a[i]][0]
        hd[a[i]][1] -= 1
        if hd[a[i]][1] == 0:
            del hd[a[i]]
    else:
        b[i] = fh
        hd[a[i]] = [fh, a[i]-1]
        fh += 1
    i += 1
if len(hd) != 0:
    print("Impossible")
else:
    print("Possible")
    print(*b)


num = int(input())
nums = input()
statement = [int(i) for i in nums.split()]

log = {}
group_num = {}
anchor = 1
total = num
status = 'Possible'
ans = []
for i, s in enumerate(statement):
    if s not in log or group_num[s] == 0:
        log[s] = anchor
        anchor += 1
        group_num[s] = num - s
        total -= group_num[s]
        if total < 0:
            status = 'Impossible'
            break
    ans.append(log[s])
    group_num[s] -= 1

print(status)
if status == 'Possible':
    for i in range(num - 1):
        print(ans[i], end=' ')
    print(ans[num - 1])

n = int(input())
aa = list(map(int, input().split()))


def cal():
    ncol = [0] * (n + 1)
    ansmap = [0] * n
    ans = [0] * n
    colcnt = [0] * (n + 1)
    colmap = [0] * (n + 1)
    icol = 0
    for i, a in enumerate(aa):
        ncol[n - a] += 1
        ansmap[i] = n - a

    for i, col in enumerate(ncol[1:], 1):
        if col % i:
            return

    for i, col in enumerate(ansmap):
        if not colcnt[col] % col:
            icol += 1
            colmap[col] = icol

        ans[i] = colmap[col]
        colcnt[col] += 1

    return ans


ans = cal()
if ans:
    print('Possible')
    print(' '.join(map(str, ans)))
else:
    print('Impossible')


n = int(input())
a = list(map(int, input().split()))
if 0 in a:
    if len(set(a)) > 1:
        print('Impossible')
    else:
        print('Possible')
        print(*[1]*n)
elif not all(q < n for q in a):
    print('Impossible')
else:
    s = {}
    answer = [0 for q in range(n)]
    for q in range(len(a)):
        if a[q] in s:
            s[a[q]].append(q)
        else:
            s[a[q]] = [q]
    q2 = 0
    for q in s:
        if len(s[q]) % (n-q) != 0:
            print('Impossible')
            break
        for q1 in range(len(s[q])):
            if q1 % (n-q) == 0:
                q2 += 1
            answer[s[q][q1]] = q2
    else:
        print('Possible')
        print(*answer)


n = int(input())
a = [int(s) for s in input().split()]
b = [-1 for i in range(n)]
m = {}
nextnum = 1
for i in range(n):
    # print(m)
    if b[i] == -1:
        if m.get(a[i]) and m[a[i]][1] > 0:
            b[i] = m[a[i]][0]
            m[a[i]][1] -= 1
            if m[a[i]][1] == 0:
                m.pop(a[i])
        else:
            z = n-a[i]-1
            b[i] = nextnum
            if z:
                m[a[i]] = [nextnum, z]
            nextnum += 1

if m:
    print("Impossible")
else:
    print("Possible")
    print(*b)


n = int(input())

cl = list(map(int, input().split()))

pos = {}
color = 0
res = []

for x in cl:
  if x in pos.keys():
    if pos[x][0]!=0:
      res.append(pos[x][1])
      pos[x][0]-=1
    else:
      color+=1
      res.append(color)
      pos[x] = [n-x-1, color]
  else:
    color+=1
    res.append(color)
    pos.update({x:[n-x-1, color]})

for x in pos.keys():
  if pos[x][0]!=0:
    print("Impossible")
    return

print("Possible")
print(*res)

n=int(input())
arr=list(map(int,input().split()))
ansarr=[0]*n
flag=0
dict1={}
dict2={}
for i in range(n):
    try:
        dict1[arr[i]].append(i)
    except:
        KeyError
        dict1[arr[i]]=[i]
        dict2[arr[i]]=0

tempcount=0
for i in dict1.keys():
    count=0
    while(dict2[i]<len(dict1[i])):
        if(dict2[i]+n-i>len(dict1[i])):
            flag=1
            break
        else:
            tempcount+=n-i
            dict2[i]+=n-i
if(tempcount!=n):
    flag=1
if(flag==1):
    print('Impossible')
else:
    count=0
    val=1
    for i in dict1.keys():
        for j in range(0,len(dict1[i]),n-i):
            for k in range(n-int(i)):
                ansarr[dict1[i][j+k]]=val
            val+=1
    print('Possible')
    print(*ansarr)

#!/usr/bin/env python3
import sys
def __starting_point():
    n = int(input())
    a = {}
    a_s = input().split()
    for i in range(n):
        x = n - int(a_s[i])
        a[x] = a.get(x, 0) + 1
        a_s[i] = x
    for i in a:
        if (i < 1) or (i > n):
            print("Impossible")
            return
        if a[i] % i != 0:
            print("Impossible")
            return
    print("Possible")
    used = 0
    col = {}
    num = {}
    b = []
    for x in a_s:
        if x not in col or num[x] == x:
            used += 1
            col[x] = used
            num[x] = 1
            b.append(used)
        else:
            num[x] += 1
            b.append(col[x])
    print(" ".join(map(str, b)))

__starting_point()

n = int(input())
a = [int(element) for element in input().split(' ')]
b = dict()
for i in range(n):
    try:
        b[a[i]] += 1
    except:
        b[a[i]] = 1
c = [(b[k] % (n-k)) == 0 for k in list(b.keys())]
d = [b[k] for k in a]

if all(c):
    print("Possible")
    types = dict()
    hat = 1
    for k in list(b.keys()):
        pergroup = n-k
        groups = b[k] // pergroup
        hatsgroup = list()
        for i in range(groups):
            for j in range(pergroup):
                hatsgroup.append(hat)
            hat += 1
        types[k] = hatsgroup
    hats = list()
    for i in range(n):
        hats.append(types[a[i]].pop())
    print(' '.join(str(e) for e in hats))

else:
    print("Impossible")


import math


def hats(n, arr):
    processed = [False] * n
    hats = [None] * n
    cur_hat = 0
    for i, diff_count in enumerate(arr):
        if processed[i]: continue
        cur_hat += 1
        hats[i] = cur_hat
        processed[i] = True
        same_count = n - diff_count - 1
        if not same_count: continue
        for j in range(i+1, n):
            if arr[j] == diff_count:
                same_count -= 1
                processed[j] = True
                hats[j] = cur_hat
            if not same_count:
                break
        if same_count:
            print('Impossible')
            return
    print('Possible')
    print(' '.join(list(map(str, hats))))


def __starting_point():
    n = int(input())
    answers = list(map(int, input().strip().split()))
    hats(n, answers)

__starting_point()

n=int(input())
a=list(map(int,input().split()))
d={}
l=[[] for i in range(n+1)]
for i in range(n):
    d[a[i]]=d.get(a[i],0)+1
    l[n-a[i]].append(i+1)
b=list(d.keys())
c=[]
for i in b:
    c.append([d[i]//(n-i),n-i])
k=0
for i in c:
    k+=i[0]*i[1]
if k!=n:
    print('Impossible')
else:
    print('Possible')
    co=1
    ans=[0]*(n+1)
    for i in c:
        for j in range(i[0]):
            for k in range(i[1]):
                x=l[i[1]].pop()
                ans[x]=co
            co+=1
    print(*ans[1:])

n = int(input())
L = [n-int(x) for x in input().split()]
D = {}
for i in L:
    if i in D:
        D[i] += 1
    else:
        D[i] = 1
s = 0
check = True
for i in D.keys():
    if D[i]%i != 0:
        check = False
        break
    else:
        s += D[i]
if s != n:
    print('Impossible')

else:
    if check == False:
        print('Impossible')
    else:
        print('Possible')
        small = 1
        D2 = {}
        for i in D:
            D2[i] = list(range(small,small+(D[i]//i)))*i
            small += D[i]//i
        for i in L:
            print(D2[i][-1],end = ' ')
            D2[i].pop()