Dasha logged into the system and began to solve problems. One of them is as follows:

Given two sequences a and b of length n each you need to write a sequence c of length n, the i-th element of which is calculated as follows: c_{i} = b_{i} - a_{i}.

About sequences a and b we know that their elements are in the range from l to r. More formally, elements satisfy the following conditions: l ≤ a_{i} ≤ r and l ≤ b_{i} ≤ r. About sequence c we know that all its elements are distinct.

 [Image] 

Dasha wrote a solution to that problem quickly, but checking her work on the standard test was not so easy. Due to an error in the test system only the sequence a and the compressed sequence of the sequence c were known from that test.

Let's give the definition to a compressed sequence. A compressed sequence of sequence c of length n is a sequence p of length n, so that p_{i} equals to the number of integers which are less than or equal to c_{i} in the sequence c. For example, for the sequence c = [250, 200, 300, 100, 50] the compressed sequence will be p = [4, 3, 5, 2, 1]. Pay attention that in c all integers are distinct. Consequently, the compressed sequence contains all integers from 1 to n inclusively.

Help Dasha to find any sequence b for which the calculated compressed sequence of sequence c is correct.


-----Input-----

The first line contains three integers n, l, r (1 ≤ n ≤ 10^5, 1 ≤ l ≤ r ≤ 10^9) — the length of the sequence and boundaries of the segment where the elements of sequences a and b are.

The next line contains n integers a_1,  a_2,  ...,  a_{n} (l ≤ a_{i} ≤ r) — the elements of the sequence a.

The next line contains n distinct integers p_1,  p_2,  ...,  p_{n} (1 ≤ p_{i} ≤ n) — the compressed sequence of the sequence c.


-----Output-----

If there is no the suitable sequence b, then in the only line print "-1".

Otherwise, in the only line print n integers — the elements of any suitable sequence b.


-----Examples-----
Input
5 1 5
1 1 1 1 1
3 1 5 4 2

Output
3 1 5 4 2 
Input
4 2 9
3 4 8 9
3 2 1 4

Output
2 2 2 9 
Input
6 1 5
1 1 1 1 1 1
2 3 5 4 1 6

Output
-1



-----Note-----

Sequence b which was found in the second sample is suitable, because calculated sequence c = [2 - 3, 2 - 4, 2 - 8, 9 - 9] = [ - 1,  - 2,  - 6, 0] (note that c_{i} = b_{i} - a_{i}) has compressed sequence equals to p = [3, 2, 1, 4].

Difficulty: interview

Starter code:

Solutions:
n, l, r = list(map(int, input().split()))
read = lambda: list(map(int, input().split()))
a = list(read())
p = list(read())
d = [(a[i], p[i], i) for i in range(n)]
d.sort(key = lambda x: x[1])
cur = l - d[0][0]
b = [0] * n
for i in range(n):
    ind = d[i][2]
    b[ind] = a[ind] + cur
    if b[ind] < l:
        cur = l - a[ind]
        b[ind] = l
    cur += 1
if max(b) > r: 
    print(-1)
    return
print(' '.join(map(str, b)))


n,l,r = map(int,input().split())
A = list(map(int,input().split()))
P = list(map(int,input().split()))
s = [0] * n
per=0
for j in range(n):
    s[P[j] - 1] = j
b = [0] * n
b[s[0]] =  l
for j in range(1,n):
    last = b[s[j-1]] - A[s[j-1]]
    nexs = last+1
    
    if r - A[s[j]] > last:
        b[s[j]] = max(nexs +A[s[j]],l)
    else:
        per = 1
        break
if per == 1:
    print(-1)
else:
    print(' '.join(map(str,b)))

n,l,r = list(map(int, input().split()))
A = [int(i) for i in input().split()]
Cord = [int(i) for i in input().split()]
Cinv = [0 for _ in range(n)]
for i in range(n):
    Cinv[Cord[i]-1] = i 

pmin = -10**18
B = [0 for _ in range(n)]
ans = True
for i in range(n):
    ad = max(l, pmin+A[Cinv[i]]+1)
    B[Cinv[i]] = ad
    pmin = B[Cinv[i]]-A[Cinv[i]]
    if ad > r:
        ans = False

if ans:
    print(*B)
else:
    print(-1)


import sys

N, L, R = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [0] * N
c = list(map(int, input().split()))
d = [i for i in range(N)]

z = [list(t) for t in zip(c, a, b, d)]
z = sorted(z)

z[0][2] = L
last = z[0][2] - z[0][1]

for i in range(1, N):
    z[i][2] = max(last + 1 + z[i][1], L)
    if z[i][2] > R:
        print(-1)
        return
    last = z[i][2] - z[i][1]

z = sorted(z, key=lambda t: t[3])
_, _, res, _ = list(zip(*z))
print(*res)


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

order = dict()

for i in range(len(p)):
    order[p[i]] = i

curr = -100000000000
b = [-1] * n
for i in range(1, n+1):
    if i == 1:
        b[order[i]] = l
        curr = b[order[i]] - a[order[i]]
        continue
    b[order[i]] = max(l, curr + 1 + a[order[i]])
    curr = b[order[i]] - a[order[i]]
    
for i in b:
    if i > r:
        print(-1)
        return
print(*b)


n, l, r = map(int,input().split(" "))
a = list(map(int, input().split(" ")))
compressed = list(map(int, input().split(" ")))

#print('n,l,r')
#print(n,l,r)

b = [0]*n 

lastmod = -1
lol = list(zip(compressed, enumerate(a)))
#print('sorted lol')
#print(sorted(lol))

for i, (pos, val)  in sorted(lol): 
#	print('position of a, val of a in that pos')
#	print(pos, val) 
#	print('lastmod')
#	print(lastmod)
	if i == 1:
		b[pos] = l
		lastmod = pos
	if i > 1: 	
		b[pos] = max(b[lastmod] - a[lastmod] + val + 1, l)
		if b[pos] > r: 
			print("-1")
			return
		lastmod = pos
#	print('b is now')
#	print(b)

for i in b: 
	print(i, end=" ")
	 		


read = lambda: map(int, input().split())
n, l, r = read()
a = list(read())
p = list(read())
d = [i for i in range(n)]
d.sort(key = lambda x: p[x])
cur = l - a[d[0]]
b = [0] * n
for ind in d:
    b[ind] = a[ind] + cur
    if b[ind] < l:
        cur = l - a[ind]
        b[ind] = l
    cur += 1
if max(b) > r: 
    print(-1)
    return
print(' '.join(map(str, b)))

n, l, r = map(int, input().split())

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

seg = [0] * n
for i in range(n):
    seg[i] = [l - a[i], r - a[i]]
    
segments = [0] * n
for i in range(n):
    segments[p[i] - 1] = seg[i]

c = [0] * n
can = True
l = -(10 ** 18)
for i in range(n):
    if l >= segments[i][1]:
        can = False
        break
    
    if segments[i][0] > l:
        l = segments[i][0]
    else:
        l = l + 1
    
    c[i] = l
    
if not can:
    print(-1)
else:
    for i in range(n):
        print(c[p[i] - 1] + a[i], end = ' ')

from operator import itemgetter

n, l, r = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
A = sorted([[a[i], p[i], i, 0] for i in range(n)], key = itemgetter(1))

A[0][3] = l
c = A[0][3] - A[0][0]
for i in range(1, n):
    A[i][3] = max(l, A[i][0]+c+1)
    c = A[i][3] - A[i][0]
    if A[i][3] > r:
        print(-1)
        break
else:
    A = sorted(A, key = itemgetter(2))
    for i in range(n):
        print(A[i][3], end=" ")

n, l, r = input().split(' ')
n = int(n)
l = int(l)
r = int(r)

at = input().split(' ')
pt = input().split(' ')

a = []
b = []
p = []
indices = []
for i in range(n):
    a.append(int(at[i]))
    p.append(int(pt[i]))
    b.append(None)
    indices.append(None)

for i in range(n):
    indices[p[i]-1] = i

flag = True

i = 0
while (i < n):
    ind = indices[i]
    if i == 0:
        b[ind] = str(l)
        last = l - a[ind]
        i += 1
        continue

    exp = last + a[ind] + 1
    if exp > r:
        flag = False
        break
    
    exp = max([l, exp])
    
    last = exp - a[ind]
    b[ind] = str(exp)
    
    i += 1

if flag:
    print(' '.join(b))
else:
    print(-1)

#!/usr/bin/env python3
from sys import stdin,stdout


def ri():
    return list(map(int, input().split()))

n, l, r = ri()
a = list(ri())
p = list(ri())

pi = [i for i in range(n)]
pi.sort(key=lambda e: p[e])
b = [0 for i in range(n)]

i = pi[0]
b[i] = l
cp = b[i] - a[i]
for ii in range(1,n):
    i = pi[ii]
    if a[i] + cp + 1 >=l:
        b[i] = a[i] + cp + 1
    else:
        b[i] = l

    cp = b[i] - a[i]
    if b[i] > r:
        print(-1)
        return

print(*b)



n, l, r = list(map(int, input().split()))
a = list(map(int, input().split()))
p = list(map(int, input().split()))
s = set()

x = []
for i in range(len(a)):
	x.append([p[i], i])

x.sort()
mx = -1000000000000
for i in range(n):
	p[x[i][1]] = max(l, mx + a[x[i][1]] + 1)
	if p[x[i][1]] > r:
		print('-1')
		return
	mx = p[x[i][1]] - a[x[i][1]]

idx = 0
for i in p:
	if idx != 0:
		print("", i, end="")
	else:
		print(i, end="")
		idx = 1
print('')


R= lambda: list(map(int,input().split()))
n,l,r= R()
a,d=list(R()),list(R())
b=[l for _ in range(n)]
c=[0 for _ in range(n)]
for i in range(n):
    c[d[i]-1]=i
dif=l-a[c[0]]
for x in c[1:]:
    if b[x]-a[x]<=dif:  
        b[x]=a[x]+dif+1
    dif=b[x]-a[x]
    if b[x]>r:
        print("-1")
        return
print(" ".join(map(str,b)))
    
        
    


def binary_search(l, r, k):
    while (l <= r):
        mid = l+r >> 1
        if (mid < k):
            l = mid+1
        else:
            r = mid-1
    return l

def main():
    n, l, r = map(int, input().split())
    a = list(map(int, input().split()))
    p = list(map(int, input().split()))
    x = [(p[i], i+1, a[i]) for i in range(n)]
    
    x.sort()
    a = [x[i][2] for i in range(n)]
    p = [x[i][1] for i in range(n)]
    b = [0]*(n+1)
    b[p[0]-1] = l
    
    for i in range(1,n):
        idx_list = p[i-1]-1
        b[p[i]-1] = binary_search(l, r, b[idx_list] - a[i-1] + a[i])
        if (b[idx_list] - a[i-1] == b[p[i]-1] - a[i]):
            b[p[i]-1] += 1

    if (max(b) > r):
        print(-1)
        return
    for i in range(n):
        print(b[i], end=' ')

main()