Harryxun/stf_run huggingface dataset:
def knapsack(W,v,w,n,d):
    
    if n<0:
        return 0
    
    if d[W][n]!=-1:
        return d[W][n]
    if w[n]>W:
        d[W][n]=knapsack(W,v,w,n-1,d)
        return d[W][n]
    else:
        d[W][n]=max(v[n]+ knapsack(W-w[n],v,w,n-1,d),knapsack(W,v,w,n-1,d))
        return d[W][n]


q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[-]=r[1]
  



d=[[-1 for j in range(n+1)] for i in range(W+1)]
print(knapsack(W,v,w,n-1,d))

### FIXED CODE ###

def knapSack(W, wt, val, n): 
	K = [[0 for x in range(W+1)] for x in range(n+1)] 

	
	for i in range(n+1): 
		for w in range(W+1): 
			if i==0 or w==0: 
				K[i][w] = 0
			elif wt[i-1] <= w: 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 
			else: 
				K[i][w] = K[i-1][w] 

	return K[n][W] 




q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  




print(knapSack(W,w,v,n))
a,b = map(input().split(' '))
print(max(a-2*b,0))

### FIXED CODE ###

a,b = map(int,input().split(' '))
print(max(a-2*b,0))
n=int(input())
s=input()
lst=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','X','Y','Z']
S=list(s)
for i in range(n):
  idx=lst.index(S[i])
  S[i]=lst[(idx+n)%len(lst)]
t=''.join(S)
print(t)
  

### FIXED CODE ###

n=int(input())
s=input()
lst=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
S=list(s)
for i in range(len(S)):
  idx=lst.index(S[i])
  S[i]=lst[(idx+n)%(len(lst))]
t=''.join(S)
print(t)
a=input()
b=int(a)/9
if str(b)[-1]=='0':
  print('Yes')
else:
  print('NO')
    

### FIXED CODE ###

a=int(input())%9
if a==0:
  print('Yes')
else:
  print('No')
n,m=map(int,input().split())
s=input()
l=[0 for i in range(n+1)]
i=0
j=0
while j<n:
    j+=1
    while s[j]=="1":
        j+=1
    while j>i:
        i+=1
        l[i]=j
ans=[[] for i in range(n+1)]
for i in range(1,m+1):
    ans[i].append(i)
for i in range(m+1,n+1):
    if s[i]=="1":
        continue
    else:
        ans[i]=ans[l[i-m]]+[i-l[i-m]]
if 0 in ans[-1]:
    print(-1)
else:
    print(" ".join(map(str,ans[-1])))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
s=input()
ans=[]
def f(i,j):
    if i==0:
        print(" ".join(map(str,ans[::-1])))
        return
    if j>i:
        j=i
    while s[i-j]=="1":
        j-=1
    if j==0:
        print(-1)
        return
    ans.append(j)
    f(i-j,m)
f(n,m)
n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0
while True:
  if a != [] and a[0] <= b[0]:
    k -= a[0]
    a.pop(0)
  elif b !=[]:
    k -= b[0]
    b.pop(0)
  else:
    break
  if k < 0:
    break
  count += 1
print(count)


### FIXED CODE ###

import bisect
n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

asum, bsum = [0], [0]
for i in range(n):
  if k < a[i] + asum[i]:
    break
  asum.append(a[i] + asum[i])
for i in range(m):
  if k < b[i] + bsum[i]:
    break
  bsum.append(b[i] + bsum[i])

ans = 0
for i in range(len(asum)):
  tmp = i + bisect.bisect(bsum, k-asum[i]) - 1
  if ans < tmp:
    ans = tmp
print(ans)
n = int(input())

d_i_list = [int(input()) for i in range(n)]

print(len(list(set(d_i_list))))

### FIXED CODE ###

s=input()
print('2018'+s[4:])
a,b,c=map(int, input().count())
if b-a==c-b:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

a,b,c=map(int, input().split())
if b-a==c-b:
    print('YES')
else:
    print('NO')
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp_v = [0] * (W+1)

for i in range(N):
    for j in (reversed(range(W+1))):
        if (j == 0 or dp_v[j] != 0) and j+w[i] <= W and dp_v[j+w[i]] < dp_v[j] + v[i]:
            dp_v[j+w[i]] = dp_v[j] + v[i]
            
max = 0        
for i in range(W+1):
    if max < dp_v[i]:
        max = dp_v[i]

print(max)


### FIXED CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
sum_v = 0
for i in range(N):
    w[i], v[i] = map(int, input().split())
    sum_v += v[i]

DP = [0] * (sum_v+1)

for i in range(N):
    for j in (reversed(range(sum_v))):
        if j == 0 or DP[j] != 0:
            if DP[j + v[i]] > DP[j] + w[i] or DP[j + v[i]] == 0:
                DP[j + v[i]] = DP[j] + w[i]
                

for j in (reversed(range(sum_v+1))):
    if DP[j] != 0 and DP[j] <= W:
        print(j)
        break
# ??±???????????¢?´¢(Depth First Search)

def DFS(n = 1, i = 0, time = 1):
    for j in range(n):
        if A[i][j] == 1 and d[j] == 0:
            time = time + 1
            d[j] = time
            time = DFS(n, j, time)
    time = time + 1
    f[i] = time
    return time

n = int(raw_input())
A = [0] * n
for i in range(n):
    A[i] = [0] * n

for i in range(n):
    value = map(int, raw_input().split())
    u = value[0] - 1
    k = value[1]
    nodes = value[2:]
    for j in range(k):
        v = nodes[j] - 1
        A[u][v] = 1

d = [0] * n
f = [0] * n

time = 0
for i in range(n):
    if d[i] == 0:
        time = time + 1
        d[i] = time
        time = DFS(n, i, time)

for i in range(n):
    print(str(i + 1) + " " + str(d[i]) + " " + str(f[i]))

### FIXED CODE ###


def DFS(n = 1, i = 0, time = 1):
    for j in range(n):
        if A[i][j] == 1 and d[j] == 0:
            time = time + 1
            d[j] = time
            time = DFS(n, j, time)
    time = time + 1
    f[i] = time
    return time

n = int(raw_input())
A = [0] * n
for i in range(n):
    A[i] = [0] * n

for i in range(n):
    value = map(int, raw_input().split())
    u = value[0] - 1
    k = value[1]
    nodes = value[2:]
    for j in range(k):
        v = nodes[j] - 1
        A[u][v] = 1

d = [0] * n
f = [0] * n

time = 0
for i in range(n):
    if d[i] == 0:
        time = time + 1
        d[i] = time
        time = DFS(n, i, time)

for i in range(n):
    print(str(i + 1) + " " + str(d[i]) + " " + str(f[i]))
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, *abc = map(int, input().split())
s = [input()for _ in range(n)]
cond = {'AB': (0, 1), 'AC': (0, 2), 'BC': (1, 2)}
legend = ('A', 'B', 'C')
ans = []


def dfs(i):
    if -1 in abc:
        return 0
    elif i == n:
        print('Yes')
        print(*ans, sep='\n')
        exit()
        # return 0
    else:
        idx1, idx2 = cond[s[i]]
        abc[idx1] += 1
        abc[idx2] -= 1
        ans.append(legend[idx1])
        dfs(i+1)
        ans.pop()
        abc[idx1] -= 1
        abc[idx2] += 1

        abc[idx1] -= 1
        abc[idx2] += 1
        ans.append(legend[idx2])
        dfs(i+1)
        ans.pop()
        abc[idx1] += 1
        abc[idx2] -= 1


dfs(0)
print('No')


### FIXED CODE ###

n, a, b, c = map(int, input().split())
ans = []
prev = ''
for _ in range(n):
    s = input()
    if 'C' not in s:
        if a == b == 0 and ans:
            # キングクリムゾン発動！
            prev_x = ans.pop()
            if prev_x == prev[0]:
                prev_y = prev[1]
            else:
                prev_y = prev[0]
            ans.append(prev_y)
            if prev_x == 'A':
                a -= 2
            elif prev_x == 'B':
                b -= 2
            else:
                c -= 2
            if prev_y == 'A':
                a += 2
            elif prev_y == 'B':
                b += 2
            else:
                c += 2
        if a < b:
            a += 1
            b -= 1
            ans.append('A')
        else:
            a -= 1
            b += 1
            ans.append('B')

    elif 'B' not in s:
        if a == c == 0 and ans:
            # キングクリムゾン発動！
            prev_x = ans.pop()
            if prev_x == prev[0]:
                prev_y = prev[1]
            else:
                prev_y = prev[0]
            ans.append(prev_y)

            if prev_x == 'A':
                a -= 2
            elif prev_x == 'B':
                b -= 2
            else:
                c -= 2
            if prev_y == 'A':
                a += 2
            elif prev_y == 'B':
                b += 2
            else:
                c += 2
        if a < c:
            a += 1
            c -= 1
            ans.append('A')
        else:
            a -= 1
            c += 1
            ans.append('C')
    elif 'A' not in s:
        if b == c == 0 and ans:
            # キングクリムゾン発動！
            prev_x = ans.pop()
            if prev_x == prev[0]:
                prev_y = prev[1]
            else:
                prev_y = prev[0]
            ans.append(prev_y)
            if prev_x == 'A':
                a -= 2
            elif prev_x == 'B':
                b -= 2
            else:
                c -= 2
            if prev_y == 'A':
                a += 2
            elif prev_y == 'B':
                b += 2
            else:
                c += 2
        if b < c:
            b += 1
            c -= 1
            ans.append('B')
        else:
            b -= 1
            c += 1
            ans.append('C')
    prev = s
    if -1 in (a, b, c):
        print('No')
        break
else:
    print('Yes')
    for x in ans:
        print(x)
for i in range(m):
    if(b[i][1]>=g):
        for j in range(g):
            f.append(b[i][0])
            break
    else:
        for j in range(b[i][1]):
            f.append(b[i][0])
        g=g-b[i][1]
if(len(f)<n):
    for i in range(n-len(f)):
        f.append(-1)
f.sort(reverse=True)
for i in range(n):
    if(f[i]>a[i]):
        a[i]=f[i]
    else:
        break
print('{0}'.format(sum(a)))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[(1,z)for z in a]
b=[tuple(map(int,input().split()))for i in range(m)]
b+=a
b.sort(key=lambda x:x[1])
cnt=0
ans=0
while True:
    c=b.pop()
    if cnt+c[0]<=n:
        ans+=c[0]*c[1]
        cnt+=c[0]
    else:
        ans+=c[1]*(n-cnt)
        break
print('{0}'.format(ans))
import math
import sys
sys.setrecursionlimit(10**1000000)
a,b = map(int,input().split())
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
if b != 0:
    print(lcm(a, b))
else:
    print(a)

### FIXED CODE ###

from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
a,b = map(int,input().split())
def lcm(x, y):
    return (x * y) // gcd(x, y)
if b != 0:
    print(lcm(a, b))
else:
    print(a)
po=list(map(int,input().split()))
A=po[0]
B=po[1]
C=po[0]-1
ans=1
if B == 1:
    ans=0
elif:B == 0:
    ans=0
else:
    while A < B:
        ans=ans+1
        A=A+C
print(ans)
print(A)


### FIXED CODE ###

po=list(map(int,input().split()))
A=po[0]
B=po[1]
C=po[0]-1
ans=1
if B == 1:
    ans=0
else:
    while A < B:
        ans=ans+1
        A=A+C
print(ans)
import math
r = int(input())
print("{0:.6f} {1:.6f}".format(math.pi*r**2, 2*math.pi*r))

### FIXED CODE ###

import math
r = float(input())
print("{0:.6f} {1:.6f}".format(math.pi*r**2, 2*math.pi*r))
n = int(input())
a = list(map(int, input().split()))

money = 1000

for i in range(n-1):
    s = 0
    if a[i] < a[i + 1]:
        s = money / a[i]:
    money += (a[i + 1] - a[i]) * s
print(money)

### FIXED CODE ###

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

money = 1000

for i in range(n-1):
    s = 0
    if a[i] < a[i + 1]:
        s = money // a[i]
    money += (a[i + 1] - a[i]) * s
print(money)
import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int64)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    subcum = np.cumsum(mods)
    idx = subcum[n-1] // div
    count = subcum[-1-idx]
    if count <= k:
        print(count)
        exit()

### FIXED CODE ###

import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    add = div - mods

    addcum = np.cumsum(add)
    subcum = np.cumsum(mods)
    for i in range(n):
        addcount = addcum[n-1] - addcum[i]
        subcount = subcum[i]
        if addcount == subcount and addcount <= k:
            print(div)
            exit()
def count_apper(str) :
    n = 0
    for c in str :
        if c.isuppper() :
            n = n+1
    return n

str = input()
if (str[0] == "A") && (str.count("C") == 1) && (2 < str.find("C") < len(str)-1) && (count_apper(str) == 2) :
                print("AC")
                exit()
print("WA")
    

### FIXED CODE ###

def count_apper(str) :
    n = 0
    for c in str :
        if c.isupper() :
            n = n+1
    return n

str = input()
if (str[0] == "A") and (str.count("C") == 1) and (1 < str.find("C") < len(str)-1) and (count_apper(str) == 2) :
                print("AC")
                exit()
print("WA")
h, n = map(int, input().split())
x = sorted([int(i) for i in input().split()], reverse = True)
if(x[0] + x [1] >= h):
  print('Yes')
else:
  print('No')


### FIXED CODE ###

h, n = map(int, input().split())
x = sorted([int(i) for i in input().split()], reverse = True)
if(sum(x[:n]) >= h):
  print('Yes')
else:
  print('No')
INF = float("inf")
n, k = map(int, input().split())
a = list(map(int, input().split()))

def get_divisors(num):
    f_divs, l_divs = [], []
    for i in range(1, int(num**0.5)+1):
        if not num % i:
            f_divs.append(i)
            if i != num // i:
                l_divs.append(num // i)
    return f_divs + l_divs[::-1]

s = sum(a)
divs = get_divisors(s)
ans = 1

def evl(d):
    if d == 1: return True
    m = d*n*2
    rem = [x % d for x in a]
    dp = [[INF] * (m+d*2+10) for _ in range(n+1)]
    mid = m // 2
    dp[0][mid] = 0
    for i in range(n):
        for j in range(m):
            if rem[i] == 0:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j])
                continue
            dp[i+1][j-rem[i]] = min(dp[i+1][j-rem[i]], dp[i][j]+rem[i])
            dp[i+1][j+d-rem[i]] = min(dp[i+1][j+d-rem[i]], dp[i][j]+(d-rem[i]))
    return dp[n][mid] // 2 <= k

l, r = -1, len(divs)

while r-l > 1:
    x = (r+l) // 2
    if evl(divs[x]): l = x
    else: r = x

print(divs[l])


### FIXED CODE ###

INF = float("inf")
n, k = map(int, input().split())
a = list(map(int, input().split()))

def get_divisors(num):
    f_divs, l_divs = [], []
    for i in range(1, int(num**0.5)+1):
        if not num % i:
            f_divs.append(i)
            if i != num // i:
                l_divs.append(num // i)
    return f_divs + l_divs[::-1]

divs = get_divisors(sum(a))
ans = 1

def evl(d):
    rem = [x % d for x in a]
    rem.sort()
    s = sum(rem)
    c = 0
    for i, x in enumerate(rem):
        c += x
        if c == d*(n-i-1) - (s-c):
            return c <= k
    return False

for d in divs[::-1]:
    if evl(d):
        print(d)
        break
def compare_cards(a, b):
    return a[1] < b[1]

def bubble(C):
    for i in range(len(C)):
        for j in range(len(C) - 1, i, -1):
            if compare_cards(C[j], C[j - 1]):
                C[j], C[j - 1] = C[j -1], C[j]

def selection(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if compare_cards(C[j], C[mini]):
                mini = j
        C[i], C[mini] = C[mini], C[i]

def check_stable(originC, sortedC):
    for i in range(len(originC) - 1):
        if not compare_cards(sortedC[i], sortedC[i + 1]):
            if originC.index(sortedC[i]) > originC.index(sortedC[i + 1]):
                return 'Not stable'
    return 'Stable'

        
N = int(input())
C = input().split()

bubbleC = C.copy()
selectionC = C.copy()

bubble(bubbleC)
selection(selectionC)

print(*bubbleC)
print(check_stable(C, bubbleC))
print(*selectionC)
print(check_stable(C, selectionC))

### FIXED CODE ###

def compare_cards(a, b):
    return a[1] < b[1]

def bubble(C):
    for i in range(len(C)):
        for j in range(len(C) - 1, i, -1):
            if compare_cards(C[j], C[j - 1]):
                C[j], C[j - 1] = C[j -1], C[j]

def selection(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if compare_cards(C[j], C[mini]):
                mini = j
        C[i], C[mini] = C[mini], C[i]

def check_stable(originC, sortedC):
    for i in range(len(originC) - 1):
        if not compare_cards(sortedC[i], sortedC[i + 1]):
            if originC.index(sortedC[i]) > originC.index(sortedC[i + 1]):
                return 'Not stable'
    return 'Stable'

        
N = int(input())
C = input().split()

bubbleC = list(C)
selectionC = list(C)

bubble(bubbleC)
selection(selectionC)

print(*bubbleC)
print(check_stable(C, bubbleC))
print(*selectionC)
print(check_stable(C, selectionC))
#coding:utf-8
#!/usr/bin/python

a,b=map(int,raw_input().split())

N=pow(10,9)+7
n=1000000000
#a=141421
#b=173205

def modpow(b,e,m): 

    result=1

    while(e!=0): 
          if(e&1==1): 
             result=(result*b)%m 
          e>>=1
          b=(b*b)%m
    
    return result

def combination(n,r,N):
    bunshi=1
    for i in range(n-r+1,n+1):
        bunshi=(bunshi*i)%N
    bunbo=1
    for i in range(1,r+1):
        bunbo=(bunbo*i)%N
    return bunshi*modpow(bunbo,N-2,N)

#pow(2,n)-nCa-nCb-1
#nCr=n!/((n-r)!*r!)だから
#bunshi=n*n-1*・・・*n-r+1
#bunbo=1*・・・*r
#Nが素数だから、フェルマーの小定理より
#modpow(a,N-1,N)=1
#a*pow(a,N-2)=pow(a,N-1)=1(modN)
#より。aのmodNでの逆元はpow(a,N-2)になる。
#r!の逆元が欲しいから、modpow(bunbo,N-2,N)を掛ける。

print (modpow(2,n,N)-combination(n,a,N)-combination(n,b,N)-1)%N

### FIXED CODE ###

#coding:utf-8
#!/usr/bin/python

n,a,b=map(int,raw_input().split())

N=pow(10,9)+7
#n=1000000000
#a=141421
#b=173205

def modpow(b,e,m): 

    result=1

    while(e!=0): 
          if(e&1==1): 
             result=(result*b)%m 
          e>>=1
          b=(b*b)%m
    
    return result

def combination(n,r,N):
    bunshi=1
    for i in range(n-r+1,n+1):
        bunshi=(bunshi*i)%N
    bunbo=1
    for i in range(1,r+1):
        bunbo=(bunbo*i)%N
    return bunshi*modpow(bunbo,N-2,N)

#pow(2,n)-nCa-nCb-1
#nCr=n!/((n-r)!*r!)だから
#bunshi=n*n-1*・・・*n-r+1
#bunbo=1*・・・*r
#Nが素数だから、フェルマーの小定理より
#modpow(a,N-1,N)=1
#a*pow(a,N-2)=pow(a,N-1)=1(modN)
#より。aのmodNでの逆元はpow(a,N-2)になる。
#r!の逆元が欲しいから、modpow(bunbo,N-2,N)を掛ける。

print (modpow(2,n,N)-combination(n,a,N)-combination(n,b,N)-1)%N
y = x **3
print("y")

### FIXED CODE ###

x = input()
print(int(x) ** 3)
A=list(map(int,input().spliy()))
B=list(map(int,input().spliy()))
C=list(map(int,input().spliy()))
n=input()
for i range(n):
  D[i]=int(input())

Acount=0 
Bcount=0
Ccount=0
  
for i in range(0,n):
  if A[0]==D[i]:
    Acount+=1
  if A[1]==D[i]:
    Acount+=1
  if A[2]==D[i]:
    Acount+=1
  if(Acpunt)==3:
    exit()
for i in range(0,n):
  if B[0]==D[i]:
    Bcount+=1
  if B[1]==D[i]:
    Bcount+=1
  if B[2]==D[i]:
    Bcount+=1
  if(Bcpunt)==3:
    exit()
for i in range(0,n):
  if C[0]==D[i]:
    Ccount+=1
  if C[1]==D[i]:
    Ccount+=1
  if C[2]==D[i]:
    Ccount+=1
  if(Ccpunt)==3:
    exit()

### FIXED CODE ###

a=[list(map(int,input().split()))for _ in range(3)]
n=int(input())
b=[int(input())for _ in range(n)]
ans='No'
for i in range(3):
  for j in range(3):
    for k in range(n):
      if a[i][j]==b[k]:
         a[i][j]=0
      
for i in range(3):
    if a[i][0] + a[i][1] + a[i][2] == 0:
        ans = "Yes"
    if a[0][i] + a[1][i] + a[2][i] == 0:
        ans = "Yes"
if a[0][0] + a[1][1] + a[2][2] == 0:
    ans = "Yes"
if a[0][2] + a[1][1] + a[2][0] == 0:
    ans = "Yes"
print(ans)
n = int(input())
a = list(map(int, input().split()))
x = sorted(set(a))
if (max(a) - 1) // 2 + 1 == min(a):
  if max(a) & 1:
    m = 0
    for i in range(x[0],m[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
  else:
    m = a.count(x[0]) != 1
    for i in range(x[0]+1,m[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
else:
  print("Impossible")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = sorted(set(a))
if (max(a) - 1) // 2 + 1 == min(a):
  if max(a) & 1:
    m = m = a.count(x[0]) != 2
    for i in range(x[0],x[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
  else:
    m = a.count(x[0]) != 1
    for i in range(x[0]+1,x[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
else:
  print("Impossible")
if a >= 13:
    print(b)
elif 12 >= a >= 6:
    print(int(b/2))
else:
    print(0)

### FIXED CODE ###

a,b = map(int,input().split())
if b%2 ==0 :
    if a >= 13:
        print(b)
    elif 12 >= a >= 6:
        print(int(b/2))
    else:
        print(0)
else:
    pass
import sys
sys.setrecursionlimit(10000)
A=list(input())
B=list(input())
C=list(input())
t='a'
d=1
while d==1:
    if t=='a':
        t=A.pop(0)
    if t=='b':
        t=B.pop(0)
    if t=='c':
        t=C.pop(0)
    if t=='a' and A==[]:
        print('A')
        break
    elif t=='b' and B==[]:
        print('B')
        break
    elif t=='c' and C==[]:
        print('C')
        break

### FIXED CODE ###

A=list(input())
B=list(input())
C=list(input())
t='a'
d=1#ずっとまわすつもり。
while d==1:
    if t=='a':
        t=A.pop(0)
    elif t=='b':
        t=B.pop(0)
    elif t=='c':
        t=C.pop(0)
    if t=='a' and A==[]:
        print('A')
        break
    elif t=='b' and B==[]:
        print('B')
        break
    elif t=='c' and C==[]:
        print('C')
        break
a, b=map(int,imput().split())
if a<b:
  print("a < b")
elif a>b:
  print("a > b")
elif a==b:
  print("a = b")
else:
  pass

### FIXED CODE ###

a, b=map(int,input().split())
if a<b:
 print("a < b")
elif a>b:
 print("a > b")
elif a==b:
 print("a == b")
else:
 pass
A,B=int(input()),int(input())
C=A+B
D=A-B
E=A*B
if C>D and C>E:
    print(C)
elif D>C and D>E:
    print(D)
elif E>C and E>D:
    print(E)

### FIXED CODE ###

i = list(map(int, input().split()))
a=i[0]+i[1]
b=i[0]-i[1]
c=i[0]*i[1]
if a>=b and a>=c:
  print(a)
elif b>=a and b>=c:
  print(b)
else:
  print(c)
k, x = input().split()
k = int(k) * 500
if (k >= int(x)):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = input()
s = input()
if (len(s) == int(n)):
    print(s.count("ABC"))
# TODO D - Cake 123
# https://atcoder.jp/contests/abc123/tasks/abc123_d

X, Y, Z, K = map(int, raw_input().split())

A = sorted(int(x) for x in raw_input().split(), reverse=True)
B = sorted(int(y) for y in raw_input().split(), reverse=True)
C = sorted(int(z) for z in raw_input().split(), reverse=True)

AB = sorted([a+b for a in A for b in B], reverse=True)
ABC = sorted([ab + c for ab in AB[:K] for c in C], reverse=True)

for i in ABC[:K]:
    print '{}'.format(i)


### FIXED CODE ###

#abc123d
 
x,y,z,k=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
b=sorted(map(int,raw_input().split()),reverse=True)
c=sorted(map(int,raw_input().split()),reverse=True)
 
ab=sorted([i+j for i in a for j in b],reverse=True)
res=sorted([ij+l for ij in ab[:k] for l in c],reverse=True)
for i in res[:k]:
	print i
c = [list(map(str, input().split())) for i in range(3)]
print(c[0][0] + c[1][1] + c[2][2])

### FIXED CODE ###

c = [input() for i in range(3)]
print(c[0][0] + c[1][1] + c[2][2])
S = input()
S[3] = '8'
print(S)


### FIXED CODE ###

S = list(input())
S[3] = "8"
print("".join(S))