Harryxun/stf_run huggingface dataset:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
m_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        p = -1
        px = -1
        m = -1
        mx = -1
        if b:
            if ml and p == -1:
                p = ml[-1] / x
                px = x
                continue
        else:
            if pl and m == -1:
                m = pl[-1] / x
                mx = x
                continue
        if ml != -1 and pl != -1:
            if p > m:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != -1:
            ml.pop()
            pl.append(px)
        elif m != -1:
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if x == 0:
        print(0)
        import sys
        sys.exit()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    p = float("inf")
    px = float("inf")
    m = float("inf")
    mx = float("inf")
    while nums:
        x, b = nums.pop()
        if b:
            if ml and p == float("inf"):
                p = ml[-1]
                px = x
        else:
            if pl and m == float("inf"):
                m = pl[-1]
                mx = x
        if m != float("inf") and p != float("inf"):
            if px * m > mx * p:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != float("inf"):
            ml.pop()
            pl.append(px)
        elif m != float("inf"):
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)
from collections import defaultdict

n,m,k=map(int, input().split())  
friend=[[] for _ in range(n)]

for i in range(m):
    a,b=map(int, input().split()) 
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

par=[None]*n
frmember=defaultdict(int)

def dfs(v):
    if par[i]==None:
        par[v]=v
        frmember[par[v]]+=1
    for f in friend[v]:
        if par[f]==None:
            par[f]=par[v]
            frmember[par[v]]+=1
            dfs(f)

for i in range(n):
    if par[i]==None:
        dfs(i)

ans=[0]*n
for i in range(n):
    ans[i]+=frmember[par[i]]-len(friend[i])-1

for i in range(k):
    a,b=map(int, input().split()) 
    if par[a-1]==par[b-1]:
        ans[a-1]-=1
        ans[b-1]-=1

print(*ans)

### FIXED CODE ###

n=int(input())
print(n//2+(n%2))
import sys
input = sys.stdin.readline
md = 1000000007
dp=[]
def countways(n,broken,ix):
	global dp,md
	if(dp[ix]!=-1):
		return dp[ix]

	ways = 0
	if(ix+1<=n and broken[ix+1]==0):
		ways+=countways(n,broken,ix+1)
	if(ix+2<=n and broken[ix+2]==0):
		ways+=countways(n,broken,ix+2)
	dp[ix]=(ways%md)
	return dp[ix]

n,m = list(map(int,raw_input().split()))
dp = [-1 for i in range(n+1)]
dp[n] = 1
broken = [0 for i in range(n+1)]
for i in range(m):
	broken[int(raw_input())]=1
print(countways(n,broken,0)%md)

### FIXED CODE ###

md = 1000000007
n,m = list(map(int,input().split()))
broken = [0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
dp[0] = 1
for i in range(m):
	broken[int(input())]=1
# print(brok	en)
for j in range(1,n+1):
	if(broken[n-j]==1):
		continue
	if(j==1):
		dp[j]=1
	else:
		dp[j]=(dp[j-1]+dp[j-2])%md
# print(dp)
print(dp[n]%md)
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
if N == 3:
    print('2 5 63')
    exit()
l = np.array([3, 9, 2, 10, 4, 8, 6, 12]).astype('int32')
l2 = np.array([6, 3, 9, 2, 10, 4, 8,12]).astype('int32')
time = N // 12
answer = np.array([])
for i in range(time):
    answer = np.append(answer, l + 12 * i)
remain = N % 12
if remain%2 == 0:
    answer = np.append(answer, l[:remain] + 12 * time)
else:
    answer = np.appen(answer, l2[:remain] + 12 * time)

answer = [int(x) for x in answer]
print(*answer)
# 48


### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
if N == 3:
    print('2 5 63')
    exit()
l = np.array([3, 9, 2, 10, 4, 8, 6, 12]).astype('int32')
l2 = np.array([6, 3, 9, 2, 10, 4, 8, 12]).astype('int32')
time = N // 8
answer = np.array([])
for i in range(time):
    answer = np.append(answer, l + 12 * i)
remain = N % 8
if remain%2 == 0:
    answer = np.append(answer, l[:remain] + 12 * time)
else:
    answer = np.append(answer, l2[:remain] + 12 * time)

answer = [int(x) for x in answer]
print(*answer)
# 48
X,Y = map(int,input())
price = X + Y/2



### FIXED CODE ###

X,Y = map(int,input().split())
price = X + Y/2
print(round(price))
K = int(input())

if K%2==0:
    ans = -1
else:
    flag=0
    mod = 7
    count = 1
    while flag==0:
        if mod==0:
            flag = 1
        else:
            count += 1
            mod = (mod*10+7) % K

print(ans)

### FIXED CODE ###

K = int(input())


if K%2==0 or K%5==0:
    count = -1
else:
    flag=0
    mod = 7
    count = 1
    while mod%K!=0:
        count += 1
        mod = (mod*10+7) % K

print(count)
import collections
N,K=map(int,input().split())
c=sorted(collections.Counter(list(map(str,input().split()))).values())
print(sum(c[:-K]))


### FIXED CODE ###

S=input()
num_list=list(S)
sum=0
for s in num_list:
    if s=='1':
        sum+=1
print(sum)
A = int(input())
B = int(input())
C = int(input())
if A<B and B <C:
    T = A
    A = B
    B = T
    print(A,B,C)
else:
    T1 = A
    A = C
    C = T1
    print(A,B,C)

### FIXED CODE ###

a,b,c = map(int, input().split())
print(c,a,b)
n = int(input())
s = []
zyogen = []
kagen = []
for i in range(n):
    k, z = map(int, input().split())
    kagen.append(k)
    zyogen.append(z)

kk = sorted(k)
zz = sorted(z)
if(n % 2 == 0):
    aa = n // 2
    x = kk[aa-1] + kk[a]
    y = zz[aa-1] + zz[a]
    print(y-x+1)
else:
    aa = n // 2
    x = kk[aa]
    y = zz[aa]
    print(y-x+1)
    

### FIXED CODE ###

n = int(input())
s = []
zyogen = []
kagen = []
for i in range(n):
    k, z = map(int, input().split())
    kagen.append(k)
    zyogen.append(z)

kk = sorted(kagen)
zz = sorted(zyogen)
if(n % 2 == 0):
    aa = n // 2
    x = kk[aa-1] + kk[aa]
    y = zz[aa-1] + zz[aa]
    print(y-x+1)
else:
    aa = n // 2
    x = kk[aa]
    y = zz[aa]
    print(y-x+1)
X, Y, A, B, C=map(int, input().split())
p=list(map(int, input().split()))
p.sort()
q=list(map(int, input().split()))
q.sort()
r=list(map(int, input().split()))
r.sort(reverse=True)

i=-X
j=-Y
k=0
deru=0
while deru=0 and k<C and (r[k]>p[i] or r[k]>q[j]):
  if p[i]>q[j] and j<0:
    j+=1
    k+=1
  elif p[i]>q[j] and j>=0 and i<0:
    i+=1
    k+=1
  elif p[i]<q[j] and i<0:
    i+=1
    k+=1
  elif p[i]<q[j] and i>=0 and j<0:
    j+=1
    k+=1
  else:
    deru=1
    
if i==0:
  a=0
else:
  a=sum(p[i:])
  
if j==0:
  b=0
else:
  b=sum(q[j:])
  
if k==0:
  c=0
else:
  c=sum(r[:k])
  
print(a+b+c)

### FIXED CODE ###

X, Y, A, B, C=map(int, input().split())
p=list(map(int, input().split()))
p.sort()
q=list(map(int, input().split()))
q.sort()
r=list(map(int, input().split()))
r.sort(reverse=True)

i=-X
j=-Y
k=0
deru=0
while deru==0 and k<C and (r[k]>p[i] or r[k]>q[j]):
  if p[i]>q[j] and j<0:
    j+=1
    k+=1
  elif p[i]>q[j] and j>=0 and i<0 and p[i]<r[k]:
    i+=1
    k+=1
  elif p[i]<=q[j] and i<0:
    i+=1
    k+=1
  elif p[i]<=q[j] and i>=0 and j<0 and q[j]<r[k]:
    j+=1
    k+=1
  else:
    deru=1
    
if i==0:
  a=0
else:
  a=sum(p[i:])
  
if j==0:
  b=0
else:
  b=sum(q[j:])
  
if k==0:
  c=0
else:
  c=sum(r[:k])
  
print(a+b+c)
a=input()
b=input'()
print('YES' if a[-1::-1]==b else 'NO')

### FIXED CODE ###

a=input()
b=input()
print('YES' if a[-1::-1]==b else 'NO')
a, b, c, d = map(int, input().split())
N = list(range(a, b+1, 1))
t = 0
for n in N:
  if n % c == 0 and n % d == 0:
    t += 1
print(t)

### FIXED CODE ###

import math
a, b, c, d = map(int, input().split())

s1 = (a-1) // c
s2 = (a-1) // d
s3 = (a-1) // (c*d//math.gcd(c,d))
S = (a-1) - (s1 + s2 -s3)

l1 = b // c
l2 = b // d
l3 = b // (c*d//math.gcd(c,d))
L = b - (l1 + l2 - l3)

print(L-S)
n,a,b = map(int, input().split())
if b - a % 2 == 0:
  print("Alice")
elif b - a % 2 == 1
  print("Borys")

### FIXED CODE ###

n,a,b = map(int, input().split())
c = b-a
if c % 2 == 0:
  print("Alice")
elif c % 2 == 1:
  print("Borys")
ans = []
for i in input():
    if (i == '1' or i == '0'): ans.append(i) 
    if i == 'B': ans.pop() 
print(''.join(ans))

### FIXED CODE ###

ans = []
for i in input():
    if (i == '1' or i == '0'): ans.append(i) 
    if i == 'B' and len(ans) != 0: ans.pop() 
print(''.join(ans))
N = int(input())
S = list(input())
Q = int(input())
set_dic = {}

for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []
count = 0

for _ in range(Q):
    query = input()
    if query[0] == "1":
        i = int(query[2])
        c = query[4]
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
    else:
        l = int(query[2])
        r = int(query[4])
        ansset = set()
        for i in range(l, r + 1):
            for key, eachset in set_dic.items():
                if i in eachset:
                    ansset.add(key)
                    break
        ans = len(ansset)
        anslist.append(ans)
        count += 1

for i in anslist:
    print(i)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    S = list(input())
    Q = int(input())
    set_dic = {}

    for i, s in enumerate(S):
        if s not in set_dic:
            set_dic[s] = [i+1]
        else:
            bisect.insort_left(set_dic[s], i+1)

    anslist = []

    for _ in range(Q):
        query1, query2, query3 = input().split()
        if query1 == "1":
            i = int(query2)
            c = query3
            cap = S[i-1]
            if cap == c:
                continue
            set_dic[cap].remove(i)
            if c not in set_dic:
                set_dic[c] = [i]
            else:
                bisect.insort_left(set_dic[c], i)
            S[i-1] = c
        else:
            l = int(query2)
            r = int(query3)
            ansset = set()
            ans = 0
            for eachlist in set_dic.values():
                li = bisect.bisect_left(eachlist, l)
                ri = bisect.bisect_right(eachlist, r)
                if li != ri:
                    ans += 1
            anslist.append(ans)

    for i in anslist:
        print(i)

if __name__ == '__main__':
    solve()
N = int(input())
count = [0]*N
for i in range(N):
	x, y = [int(x) for x in input().split()]
    count[x-1] += 1
    count[y-1] += 1
for c in count:
    print(c)

### FIXED CODE ###

N, M = [int(x) for x in input().split()]
count = [0]*N
for i in range(M):
	x, y = [int(x) for x in input().split()]
	count[x-1] += 1
	count[y-1] += 1
for c in count:
	print(c)
import numpy as np
n=int(input())
a=list(map(int,input().split()))
y=np.array(a)
A=np.eye(n)
for i in range(n):
    A[i-1][i]=1
#print(A)
x=np.linalg.solve(A,y)
for i in range(n):
    print(int(x[i])*2,end=' ')
print()   

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
s=sum(a)//2
d=0
for i in range(n//2+1):
    d+=a[2*i]
x1=d-s
print(2*x1,end=' ')
buf=x1
for i in range(0,n-1):
    buf=a[i]-buf
    print(2*buf,end=' ')
print()
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[1] = 0 if 1 in a else 1
dp[2] = 0 if 2 in a else 1 +dp[1]
for i in range(3,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
print(dp[-1])


### FIXED CODE ###

def main(N,M,a):
    dp = [-1]*N
    dp[0] = 1
    if N != 1:
        dp[1] = 2
    for i in a:
        if i == 1:
            dp[0] = 0
            dp[1] = 1
        else:
            dp[i-1] = 0
    for i in range(2,N):
        if dp[i] != 0:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]
N,M = map(int, input().split())
a = list(int(input()) for i in range(M))

print(main(N,M,a) % 1000000007)
n,c = map(int,input().split())
stc = [[int(i) for i in input().split()] for j in range(n)]

ans = 0

stc.sort(key=lambda x:(x[2],x[1],x[0]))

time = 10**5

c_imos = [[0 for i in range(time)] for j in range(c)]

for i in range(n):
    c_imos[stc[i][2]-1][stc[i][0]-1] += 1
    c_imos[stc[i][2]-1][stc[i][1]] -= 1

#print(c_imos)

nd_v = [[0 for i in range(time)] for j in range(c)]

for i in range(c):
    for j in range(time):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = min(1,nd_v[i][j-1] + c_imos[i][j])
#print(nd_v)

ans = 1

for i in range(time):
    tmp = 0
    for j in range(c):
        tmp += nd_v[j][i]
    ans = max(tmp,ans)

print(ans)

exit()
    
c_num = stc[0][2]
t_num = stc[0][1]
idx = 0
print(stc)
for i in range(1,n):
    print(t_num,i)
    if stc[idx+i][2] == c_num:
        if stc[idx+i][0] == t_num:
            stc[idx+i-1][1] = stc[idx+i][1]
            t_num = stc[idx+i][1]
            del stc[idx+i]
            idx -= 1
        else:
            print(t_num,t_num,t_num)
            c_num = stc[idx+i][2]
            t_num = stc[idx+i][1]

stc.sort(key=lambda x:x[1])
print(stc)
exit()
tmp = stc[0][1]

ans = 1
ans_tmp = 1

for i in range(1,len(stc)):
    for j in range(i+1,len(stc)):
        if tmp >= stc[j][0]:
            ans_tmp += 1
        else:
            tmp = stc[j][0]
            ans = max(ans_tmp,ans)

### FIXED CODE ###

n,c = map(int,input().split())
stc = [[int(i) for i in input().split()] for j in range(n)]

ans = 0

stc.sort(key=lambda x:(x[2],x[1],x[0]))

time = 10**5+3

c_imos = [[0 for i in range(time)] for j in range(c)]

for i in range(n):
    c_imos[stc[i][2]-1][stc[i][0]-1] += 1
    c_imos[stc[i][2]-1][stc[i][1]] -= 1

nd_v = [[0 for i in range(time)] for j in range(c)]

for i in range(c):
    for j in range(time):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = nd_v[i][j-1] + c_imos[i][j]

for i in range(c):
    for j in range(time):
        if nd_v[i][j] >= 2:
            nd_v[i][j] = 1
ans = 1

for i in range(time-1):
    tmp = 0
    for j in range(c):
        tmp += nd_v[j][i]
    ans = max(tmp,ans)

print(ans)

exit()
    
c_num = stc[0][2]
t_num = stc[0][1]
idx = 0
print(stc)
for i in range(1,n):
    print(t_num,i)
    if stc[idx+i][2] == c_num:
        if stc[idx+i][0] == t_num:
            stc[idx+i-1][1] = stc[idx+i][1]
            t_num = stc[idx+i][1]
            del stc[idx+i]
            idx -= 1
        else:
            print(t_num,t_num,t_num)
            c_num = stc[idx+i][2]
            t_num = stc[idx+i][1]

stc.sort(key=lambda x:x[1])
print(stc)
exit()
tmp = stc[0][1]

ans = 1
ans_tmp = 1

for i in range(1,len(stc)):
    for j in range(i+1,len(stc)):
        if tmp >= stc[j][0]:
            ans_tmp += 1
        else:
            tmp = stc[j][0]
            ans = max(ans_tmp,ans)
R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])



if(C==[1,1,1]):
	print(4504501)
	exit()
if(C==[1,1,2]):
	print(2253001)
	exit()
if(C==[1,1,3]):
	while(1):
      1
	print(1502501)
	exit()
if(C==[1,1,4]):
	while(1):
      1
    print(1127251)
	exit()
if(C==[1,2,2]):
  	while(1):
      1
	print(1127251)
	exit()





count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)



### FIXED CODE ###



R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])



if(C==[1,1,1]):
	print((N+2)*(N+1)//2)
	exit()






count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)
# -*- coding: utf-8 -*-
#ABC070C
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

n = int(input())
#tmp = input().split()
#hoge = list(map(lambda a: int(a), tmp))

t=[]
for i in range(0,n):
	t.append(int(input()))
#print(t)

ans = t[0]
for i in range(1,n):
	ans = lcm(ans,t[i])

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
#ABC070C
import math

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n = int(input())

t=[]
for i in range(0,n):
	t.append(0)
for i in range(0,n):
    t[i] = int(input())

ans = t[0]
for i in range(1,n):
	j = gcd(ans,t[i])
	ans *= t[i]
	ans = ans//j

print(ans)
print (x * x * x)

### FIXED CODE ###

x = input()
cube = x * x * x
print cube
k,n = map(int,input().split())
a = list(map(int,input().split()))
b = []

for i in range(1,n+1):
  b.append(a[i] - a[i-1])
b.append(k - a[n] + a[0])
b = sorted(b)

print(sum(b[:n])

### FIXED CODE ###

k,n = map(int,input().split())
a = list(map(int,input().split()))
b = []

for i in range(1,n):
  b.append(a[i] - a[i - 1])
b.append(k - a[n-1] + a[0])

b = sorted(b)
print(sum(b[:n-1]))
N,K=map(int,input().split())
ans=0
while N>0:
    N//M
    ans+=1
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,K=map(int,input().split())

########関数部分##############
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
############################
 
 
#####関数をつかってみる．#####
######今回は二進数に変換######
x10 = N
x2 = Base_10_to_n(x10, K)
print(len(list(x2)))
from pprint import pprint
from collections import defaultdict
import numpy as np

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(np.subtract(balls[i],balls[j]))] += 1
    print(N-max(d.values()))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
from operator import sub

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(map(sub, balls[i], balls[j]))] += 1
    try:
        mmax = N - max(d.values(), default=0)
        print(mmax)
    except ValueError:
        print(100)

if __name__ == '__main__':
    main()
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]

color = [-1]*N 
def dfs(v, c):
  color[v] = c
  for next_v, w in graph[v]:
    if color[next_v] == c and w % 2 != 0:
      return 
    if color[next_v] == -1 and w % 2 == 0:
      dfs(next_v, c)# == False:
      #return False
    if color[next_v] == -1 and w % 2 != 0:
      dfs(next_v, abs(1-c)) #== False:
      #return False
  return True

dfs(0, 0)
for c in color:
  print(c)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
    adlist[v-1] += [[u-1, w%2]]
  return adlist 

def dfs(v, c):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] != 0:
      continue
    if color[next_v] == 0 and w % 2 != 0:
      dfs(next_v, -c)
    elif color[next_v] == 0 and w % 2 == 0:
      dfs(next_v, c)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  dfs(0, 1)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()
S = input()
T = input()

for i in reversed(range(len(S) - len(T) + 1)):
    if checker(S[i:(i + len(T)), T]):
        S = S.replace('?', 'a')
        print(S[:i] + T + S[i + len(T):])
        return
    print('UNRESTORABLE')

def checker(s, t):
	for i in range(len(s)):
		if s[i] != "?" and s[i] != t[i]:
			return False
	return True

### FIXED CODE ###

def main():
	s = input()
	t = input()
 
	for i in reversed(range(len(s) - len(t) + 1)):
		if checker(s[i:(i + len(t))], t):
			s = s.replace("?", "a")
			print(s[:i] + t + s[i+len(t):])
			return
	print("UNRESTORABLE")
 
def checker(s, t):
	for i in range(len(s)):
		if s[i] != "?" and s[i] != t[i]:
			return False
	return True
 
if __name__ == '__main__':
	main()
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(N, C):
    last = [-1] * (N + 1)
    pairs = []
    for i, c in enumerate(C):
        try:
            prev = last[c - 1]
        except:
            if c < 10:
                return
            else:
                raise Exception()
        if prev >= 0 and prev < i - 1:
            pairs.append((prev, i))
        last[c - 1] = i
    print(0)
    return
    pairs.sort()
    count = [0] * N
    count[0] = 1
    idx = 0
    for i in range(N):
        if i > 0:
            count[i] += count[i - 1]
            count[i] %= MOD
        while idx < len(pairs) and pairs[idx][0] == i:
            count[pairs[idx][1]] += count[i]
            count[pairs[idx][1]] %= MOD
            idx += 1
    print(count[N - 1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int
MAX_N = 200000

def solve(N, C):
    last = [-1] * MAX_N
    pairs = []
    for i, c in enumerate(C):
        try:
            prev = last[c - 1]
        except:
            if c >= N:
                return
            else:
                raise Exception()
        if prev >= 0 and prev < i - 1:
            pairs.append((prev, i))
        last[c - 1] = i
    pairs.sort()
    count = [0] * N
    count[0] = 1
    idx = 0
    for i in range(N):
        if i > 0:
            count[i] += count[i - 1]
            count[i] %= MOD
        while idx < len(pairs) and pairs[idx][0] == i:
            count[pairs[idx][1]] += count[i]
            count[pairs[idx][1]] %= MOD
            idx += 1
    print(count[N - 1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, C)

if __name__ == '__main__':
    main()
print=(input()**3)

### FIXED CODE ###

print(int(input())**3)