Harryxun/stf_run huggingface dataset:
import math


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


A, B, C, D = map(int, input().strip().split())

a_c = A // C
a_c_mod = A % C
b_c = B // C
a_d = A // D
a_d_mod = A % D
b_d = B // D

l = lcm(C, D)

a_cd = A // l
a_cd_mod = A % l
b_cd = B // l

if a_c_mod == 0:
    a_c -= 1

if a_d_mod == 0:
    a_d -= 1

if a_cd_mod == 0:
    a_cd -= 1

print((B - A + 1) - (b_c - a_c) - (b_d - a_d) + (b_cd + a_cd))


### FIXED CODE ###

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


def lcm(a, b):
    return a * b // gcd(a, b)


A, B, C, D = map(int, input().strip().split())

a_c = A // C
a_c_mod = A % C
b_c = B // C
a_d = A // D
a_d_mod = A % D
b_d = B // D

l = lcm(C, D)

a_cd = A // l
a_cd_mod = A % l
b_cd = B // l

if a_c_mod == 0:
    a_c -= 1

if a_d_mod == 0:
    a_d -= 1

if a_cd_mod == 0:
    a_cd -= 1

print((B - A + 1) - (b_c - a_c) - (b_d - a_d) + (b_cd - a_cd))
N , K = [int(n) for n in input().split()]
S = input()
print(S[:K]+S[K].lower()+S[K+1:])

### FIXED CODE ###

N , K = [int(n) for n in input().split()]
S = input()
print(S[:K-1]+S[K-1].lower()+S[K:])
import numpy as np
import math
 
def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp)
    print(dp[n-1][w])
    return 0
 
if __name__ == "__main__":
    solve()
import numpy as np
import math

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp)
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()
提出情報

### FIXED CODE ###


def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j-w_list[i]>=0:
                dp[i][j] = max(dp[i-1][j],
                               dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0
 
if __name__ == "__main__":
    solve()
def main():
    import itertools as it
    N,A,B,C = map(int,input().split())
    pre = [int(input()) for _ in range(N)]
    if N == 3:print(A-pre[0]+B-pre[1]+C-pre[2])
    else:
        m = [0,1,2,3,4,5,6,7]
        cpm = it.permutations(pre,N)
        ccb = list(it.combinations(m[:N], 3))
        minc = 99999999999999999
        for l in cpm:
            for d in ccb:
                cmp = (d[2] - 2) * 10
                asum = abs(A - sum(l[:d[0]+1]))
                if cmp+asum >= minc: continue
                bsum = abs(B - sum(l[d[0]+1:d[1]+1]))
                if cmp+asum+bsum >= minc: continue
                csum = abs(C - sum(l[d[1]+1:d[2]+1]))
                tc = cmp+asum+bsum+csum
                minc = min(minc,tc)
    print(minc)
main()

### FIXED CODE ###

def main():
    import itertools as it
    N,A,B,C = map(int,input().split())
    pre = [int(input()) for _ in range(N)]
    ss = max(pre)*N <= min(A,B,C)
    if N == 3:print(A-pre[0]+B-pre[1]+C-pre[2])
    else:
        m = [0,1,2,3,4,5,6,7]
        cpm = it.permutations(pre,N)
        ccb = list(it.combinations(m[:N], 3))
        minc = 99999999999999999
        for l in cpm:
            for d in ccb:
                cmp = (d[2] - 2) * 10
                if ss:
                    asum = (cmp+A+B+C-sum(l[:d[2]+1]))
                    minc = min(minc,asum)
                else:
                    asum = abs(A - sum(l[:d[0]+1]))
                    if cmp+asum >= minc: continue
                    bsum = abs(B - sum(l[d[0]+1:d[1]+1]))
                    if cmp+asum+bsum >= minc: continue
                    csum = abs(C - sum(l[d[1]+1:d[2]+1]))
                    tc = cmp+asum+bsum+csum
                    minc = min(minc,tc)
        print(minc)
main()
n = int(input())

if n%2==0:
  print(1/2)
else:
  print((n-1)/2n)

### FIXED CODE ###

n = int(input())

if n%2==0:
  print(1/2)
else:
  print((n+1)/(2*n))
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
ab = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    a, b = ab[i][0], ab[i][1]
    edge[a].append(b)
    edge[b].append(a)


def f(now, v):
    v = v & (1 << now)
    for to in edge[now]:
        if v >> to == 0:
            f(to, v)
    if v == int('0b11111111', 0):
        ans += 1

ans = 0
f(1, 1)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
ab = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    a, b = ab[i][0] - 1, ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

ans = 0

def f(now, v):
    global ans
    v |= (1 << now)
    for to in edge[now]:
        if not (v & (1<<to)):
            f(to, v)
    if bin(v).count("1") == N:
        ans += 1

f(0, 0)

print(ans)
import math
from functools import reduce

N, X = list(map(int, input().split()))
x = [i-X for i in list(map(int, input().split()))]

def func(nums):
    return reduce(math.gcd, nums)

print(func(x))

### FIXED CODE ###

import fractions
from functools import reduce

N, X = list(map(int, input().split()))
x = [i-X for i in list(map(int, input().split()))]

def func(nums):
    return reduce(fractions.gcd, nums)

print(abs(func(x)))
N,C=map(int, input().split())
inarr=[[int(i) for i in input().split()] for _ in range(N)]
maxes=[(0, 0)]*N
cums=[0]*(N+1)
cum = 0
cummax = (0, 0)
for i, [a, v] in enumerate(inarr):
    cum += v
    if (cum - a) > cummax[0]:
        cummax = (cum - a, a)
    maxes[i]=cummax
    cums[i+1]=cum

# print("cummax: {}, cums: {}".format(cummax, cums))
if cummax[0] == 0:
    print(0)
    exit(1)

resmax = 0
for i, [b, v] in enumerate(inarr):
    oasum, x = (0, 0) if i == 0 else maxes[i-1]
    obsum = cums[N] - cums[i] - (C-b)
    # print("len oa: {} len ob: {} oa sum: {} ob sum: {} score: {}".format(x, C-b, oasum, obsum, obsum + oasum - min(C-b, x)))
    resmax = max(resmax, obsum + oasum - min(C-b, x))
    # print(resmax)

# print(maxes[N-1])
resmax = max(resmax, maxes[N-1][0])
print(resmax)


### FIXED CODE ###

N,C=map(int, input().split())
inarr=[[int(i) for i in input().split()] for _ in range(N)]
maxes1=[(0, 0)]*N
maxes2=[(0, 0)]*N
cums=[0]*(N+1)
cum = 0
cummax1 = (0, 0)
cummax2 = (0, 0)
for i, [a, v] in enumerate(inarr):
    cum += v
    if (cum - a) > cummax1[0]:
        cummax1 = (cum - a, a)
    if (cum - 2*a) > cummax2[0]:
        cummax2 = (cum - 2*a, a)
    maxes1[i]=cummax1
    maxes2[i]=cummax2
    cums[i+1]=cum

# print("{}".format(maxes1))
resmax = 0
for i, [b, v] in enumerate(inarr):
    oasum1, x = (0, 0) if i == 0 else maxes1[i-1]
    oasum2, x = (0, 0) if i == 0 else maxes2[i-1]
    obsum = cums[N] - cums[i]
    resmax = max(resmax, obsum + oasum1 - 2*(C-b), obsum + oasum2 - (C-b))
    # print(resmax)

# print(maxes1[N-1])
print(max(resmax, maxes1[N-1][0], 0))
main():
    K = int(input())
    A, B = map(int, input().split())
    x = list(range(K, 1001, K))
    print('OK') if any([A <= i <= B for i in x]) else print('NG')

    return


if __name__=="__main__":
    main()


### FIXED CODE ###

def main():
    K = int(input())
    A, B = map(int, input().split())

    for i in range(A, B+1):
        if i % K == 0:
            print('OK')
            return
    print('NG')


if __name__=="__main__":
    main()
a,b=map(int,ijnput().split())
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')

### FIXED CODE ###

a,b=map(int,input().split())
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
import copy
h,w=map(int,input().split())
a=[list(map(lambda x:0 if x=="#" else 1,input())) for i in range(h)]
b=[[0 for i in range(w)] for j in range(h)]
count=0
while a!=b:
  z=copy.deepcopy(a)
  for i in range(h):
    for j in range(w):
      a[i][j]=z[i][j]*(z[i-1][j] if i!=0 else 1)*(z[i+1][j] if i!=h-1 else 1)*(z[i][j-1] if j!=0 else 1)*(z[i][j+1] if j!=h-1 else 1)
  count+=1
print(count)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
visited=[[-1]*w for _ in range(h)]
queue=deque()
for i in range(h):
  for j in range(w):
    if a[i][j]=='#':
      visited[i][j]=0
      queue.append([i,j])
while queue:
  y,x=queue.popleft()
  for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
    n_y,n_x=y+j,x+k
    if 0<=n_y<h and 0<=n_x<w and a[n_y][n_x]=='.' and visited[n_y][n_x]<0:
      visited[n_y][n_x]=visited[y][x]+1
      queue.append([n_y,n_x])
ans=0
for l in visited:
  ans=max([ans]+l)
print(ans)
white_num_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

N, K = map(int, input().split())
black_num_list = list(map(int, input().split()))

white_num_list = list(set(white_num_list).difference(set(black_num_list)))
num_combination = list(itertools.combinations_with_replacement(white_num_list, len(str(N))))

num_list = []
for num in num_combination:
    if num[0] == 0:
        continue
    num_list.append(int(''.join(map(str, num))))

num_list = sorted(num_list)

def price(N, num_list, white_num_list):
    for num in num_list:
        if num >= N:
            return num
    
    if 0 in white_num_list:
        white_num_list.remove(0)
    placeholder = str(min(white_num_list))
    return int(placeholder * (len(str(N)) + 1))
  
print(price(N, num_list, white_num_list))

### FIXED CODE ###

import itertools
 
white_num_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
N, K = map(int, input().split())
black_num_list = list(map(int, input().split()))
 
white_num_list = list(set(white_num_list).difference(set(black_num_list)))
num_combination = list(itertools.product(white_num_list, repeat = len(str(N))))
 
num_list = []
for num in num_combination:
    if num[0] == 0:
        continue
    num_list.append(int(''.join(map(str, num))))
    
num_list = sorted(num_list)
 
def price(N, num_list, white_num_list):
    for num in num_list:
        if num >= N:
            return num
    
    placeholder = str(min(white_num_list)) * (len(str(N)) + 1)
    if placeholder[0] == '0':
        white_num_list.remove(0)
        placeholder = str(min(white_num_list)) + placeholder[1:]
    return int(placeholder)
      
print(price(N, num_list, white_num_list))
a, b, c = input().split()
    
print("A", b[1], "C")


### FIXED CODE ###

a, b, c = input().split()
    
str = a[0] + b[0] + c[0]
print(str)
S = str(input())

front = int(S[:2])
back = int(S[2:4])

if front > 12 and back > 0 and back <= 12:
    print('YYMM')
elif front <=12 and front > 0 and back > 12:
    print('MMYY')
elif front == 0 or end == 0:
    print('NA')
else:
    print('AMBIGUOUS')

### FIXED CODE ###

S = str(input())

front = int(S[:2])
back = int(S[2:4])

if (front == 0 or front > 12) and back > 0 and back <= 12:
    print('YYMM')
elif front <= 12 and front > 0 and (back == 0 or back > 12):
    print('MMYY')
elif (front <= 12 and front > 0) and (back > 0 and back <= 12):
    print('AMBIGUOUS')
else:
    print('NA')
n=int(input())
a = [input() for i in range(n)]
b = sorted(list(set(a)))
d = {}
for i in b:
    t = a.count(i)
    d.setdefault(t,[])
    d[t].append(i)

for i in d[max(d.keys())]:
    print(i)


### FIXED CODE ###

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

if len(set(b)) == 2:
    print('Yes')
else:
    print('No')
a = list(input())
b = []
for i,j in enumerate(a):
    if j == str("0"):
        b += str("0")
    elif j == str("1"):
        b += str("1")
    else:
        del b[i-1]
print("".join(b))
        

### FIXED CODE ###

a = list(input())
b = []
for i,j in enumerate(a):
    if j == str("0"):
        b += str("0")
    elif j == str("1"):
        b += str("1")
    elif j == str("B"):
        if not b:
            pass
        else:
            del b[len(b)-1]
        
print("".join(b))
N = int(input())
P = list(map(int, input().split()))
CNT = 0
for i in range(N):
  if P[i] == i+1
    CNT += 1
print('YES' if  CNT <=  2 else 'NO')

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
CNT = 0
for i in range(N):
  if P[i] != i+1:
    CNT += 1
print('YES' if  CNT <=  2 else 'NO')
import sys

num1 = input()
num2 = input()
num3 = input()
num4 = input()

strTarget = "1974"

isValidation1 = num1 in strTarget

if isValidation1 :
    strTarget.replace(num1,"")
else:
    print("NO")
    sys.exit()

isValidation2 = num2 in strTarget
if isValidation2 :
    strTarget.replace(num2,"")
else:
    print("NO")
    sys.exit()

isValidation3 = num3 in strTarget
if isValidation3 :
    strTarget.replace(num3,"")
else:
    print("NO")
    sys.exit()

isValidation4 = num4 in strTarget
if isValidation4 :
    strTarget.replace(num4,"")
else:
    print("NO")
    sys.exit()

print("YES")


### FIXED CODE ###

import sys
#
# num = input()
#
# num1 = num[0]
# num2 = num[1]
# num3 = num[2]
# num4 = num[3]

num1, num2, num3, num4 = (int(i) for i in input().split())

num1 = str(num1)
num2 = str(num2)
num3 = str(num3)
num4 = str(num4)


strTarget = "1974"
isCheck1 = False
isCheck2 = False
isCheck3 = False
isCheck4 = False

isValidation1 = num1 in strTarget
if isValidation1 :
    strTarget = strTarget.replace(num1,"")
    isCheck1 = True

isValidation2 = num2 in strTarget
if isValidation2 :
    strTarget = strTarget.replace(num2,"")
    isCheck2 = True

isValidation3 = num3 in strTarget
if isValidation3 :
    strTarget = strTarget.replace(num3,"")
    isCheck3 = True

isValidation4 = num4 in strTarget
if isValidation4 :
    strTarget = strTarget.replace(num4,"")
    isCheck4 = True

if isCheck1 and isCheck2 and isCheck3 and isCheck4:
    print("YES")
else:
    print("NO")
s = input()
ls = len(s)
part_s = set( [s[i:j+1] for i in range(ls) for j in range(ls)  ])
part_s = [ i for i in part_s if set(list(i)) | set(["A","T","C","G"]) == set(["A","T","C","G"])]
print(max(map(len,part_s)))

### FIXED CODE ###


s = input()
ls = len(s)
part_s = set( [s[i:j+1] for i in range(ls) for j in range(ls)  ])
part_s = [ i for i in part_s if set(list(i)) | set(["A","T","C","G"]) == set(["A","T","C","G"])]
if part_s == []:
    print(0)
else:
    print(max(map(len,part_s)))
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
dp = []
if a:
  cantuse = a.pop(0)
dp.append(1)
if cantuse == 1:
  dp.append(0)
  cantuse = a.pop(0)
else:
  dp.append(1)

for i in range(N-1):
  if (i+2) == cantuse:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
dp = []
dp.append(1)
if a:
  cantuse = a.pop(0)
  if cantuse == 1:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(1)
else:
  cantuse = -1
  dp.append(1)

for i in range(N-1):
  if (i+2) == cantuse:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)
import fraction as math

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

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

l = a[0]
for num in a[1:]:
    l = lcm(num, l)

ans = 0
for num in a:
    ans += (l - 1) % num

print(ans)



### FIXED CODE ###

import fractions as math

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

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

l = a[0]
for num in a[1:]:
    l = lcm(num, l)

ans = 0
for num in a:
    ans += (l - 1) % num

print(ans)
import sys
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
    if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m = 1e9
	for i in range(x+1,mn(n,x+k+1)):
		t = ab(ar[x]-ar[i])+solve(n,k,ar,dp,i)
		m = t if t<m else m
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(n,k,ar,dp,0))

main()


### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
n = input()
print((n+1)/2)

### FIXED CODE ###

print((int(input())+1)//2)
S, T = input().split()
A, B = map(int, input().split)
U = input()
 
if S == U:
    print(A-1 , B)
else:
    print(A , B-1)

### FIXED CODE ###

S, T = input().split()
A, B = map(int,input().split())
U = input()
 
if S == U:
    print(A-1 , B)
else:
    print(A , B-1)
import functools
import math
n = int(input())
values = list(map(int, input().split()))
m = 1

for i in range(n):
    a = values[:]
    a.pop(i)
    gcd = functools.reduce(math.gcd, a)
    if m < gcd:
        m = gcd


print(m)


### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
m = 1
gf = []
gp = []


def gcd(x, y):
    if x < y:
        x += y
        y = x - y
        x -= y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


gf.append(v[0])
for i in range(n-1):
    gf.append(gcd(gf[i], v[i+1]))

gp.append(v[n-1])
for i in range(n-1):
    gp.append(gcd(gp[i], v[n-2-i]))

m = gp[n-2]

for i in range(n-1):
    b = gcd(gf[i], gp[n-3-i])
    if m < b:
        m = b
if m < gf[n-2]:
    m = gf[n-2]

print(m)
N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

for i in range(N):
    if V[i] <= C[i]:
        continue
    Max = Max + V[i] - C[i]
print(Max)

### FIXED CODE ###

A,B,T = map(int,input().split())
print(T//A*B)
def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


# def count_reachable(a):
#     # reachable = 0
#     # for s in a:
#     #     reachable += len(s) * (len(s) - 1) // 2
#     # return reachable
#     return sum(map(lambda x: len(x) * (len(x) - 1) // 2, a))


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ia = find_index_by_value(reachable_node, a)
        ib = find_index_by_value(reachable_node, b)
        if ia == -1 and ib == -1:
            reachable_node.append({a, b})
            reachable += 1
        elif ia == -1:
            reachable -= num_reachable(len(reachable_node[ib]))
            reachable_node[ib].add(a)
            reachable += num_reachable(len(reachable_node[ib]))
        elif ib == -1:
            reachable -= num_reachable(len(reachable_node[ia]))
            reachable_node[ia].add(b)
            reachable += num_reachable(len(reachable_node[ia]))
        else:
            if ia != ib:
                reachable -= num_reachable(len(reachable_node[ia]))
                reachable -= num_reachable(len(reachable_node[ib]))
                reachable_node[ia] |= reachable_node[ib]
                reachable_node.pop(ib)
                reachable += num_reachable(len(reachable_node[ia]))
        # count = not_reachable - count_reachable(reachable_node)
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())




### FIXED CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]


def find_group(x):
    c = []
    p = x
    while True:
        pp = group[p]
        if pp == p:
            break
        else:
            c.append(p)
            p = pp
    for i in c:
        group[i] = pp
    return pp

# find_group = lambda x: x if x == group[x] else find_group(group[x])

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())
dt = [for int(i) in input().split("/")]
if dt[0] >= 2019 and dt[1] >= 5:
    print("TBD")
else :
    print("Heisei")

### FIXED CODE ###

dt = [int(i) for i in input().split("/")]

if dt[0] >= 2019 and dt[1] >= 5:
    print("TBD")
else :
    print("Heisei")
n = int(input())
p = set(map(int, input().split()))
p = list(p)
p.sort()
if len(p) % 2 == 1 and n % 2 == 1:
    print(0)
else:
    p = list(p)
    cnt = p[len(p)//2] - p[len(p)//2 -1]
    print(cnt)

### FIXED CODE ###

s = str(input())
s1 = set(s)
s2 = list(s)
cnt = 0
if len(s1) != 2:
    print("No")
else:
    for i in range(1,len(s2)):
        if s[0] == s[i]:
            cnt += 1
    if cnt == 1:
        print("Yes")
    else:
        print("No")
N=int(input())
X=list(map(int, input().split()))
s=[]
for XP in range(min(X),max(X)):
    a=0
    for i in range(N):
        a+=(XP-X[i])**2
    s.append(a)
print(min(s))

### FIXED CODE ###

N=int(input())
X=list(map(int, input().split()))
s=[]
for i in range(min(X),max(X)+1):
    a=0
    for i2 in range(N):
        a+=(i-X[i2])**2
    s.append(a)
print(min(s))
ans=""
for i in input():
  if x=="B":t=t[:-1]
  else:t+=i
print(ans)

### FIXED CODE ###

t=""
for i in input():
  if i=="B":
    if len(t)!=0:
      t=t[:-1]
  else:t+=i
print(t)
N = int(input())
A = list(map(int, input().split()))

A.sort()

count = 0
for i in range(N):
    if A[i] == A[i+1]:
        count += 1
        break

if count == 0:
    print('YES')
else:
    print('NO')    

### FIXED CODE ###

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

A.sort()

count = 0
for i in range(N-1):
    if A[i] == A[i+1]:
        count += 1
        break

if count == 0:
    print('YES')
else:
    print('NO')
n = int(input())
lst = str(input()).split(' ')

p1 = [0]*(max([int(i) for i in lst])+1)
p2 = [0]*(max([int(i) for i in lst])+1)
for idx in range(n):
	if idx%2 == 0:
		p1[int(lst[idx])] += 1
	else:
		p2[int(lst[idx])] += 1

pp1 = p1.index(max(p1))
pp2 = p2.index(max(p2))
if pp1 == pp2:
	if max(p1) >= max(p2):
		pp1 = p1.index(max(p1))
		pp2 = p2.index(sorted(p2)[-2])
	elif max(p2) > max(p1):
		pp1 = p1.index(sorted(p1)[-2])
		pp2 = p2.index(max(p2))

cnt1 = 0
cnt2 = 0
for idx in range(n):
	if idx%2 == 0:
		if not lst[idx] == str(pp1):
			cnt1 += 1
	else:
		if not lst[idx] == str(pp2):
			cnt2 += 1

print(cnt1 + cnt2)

### FIXED CODE ###

n = str(input())
one_idx = []
nine_idx = []
for idx in range(len(n)):
	if n[idx]=='1':
		one_idx.append(idx)
	if n[idx]=='9':
		nine_idx.append(idx)

out = ''
for idx in range(len(n)):
	if idx in one_idx:
		out += '9'
	if idx in nine_idx:
		out += '1'
          
print(out)