Harryxun/stf_run huggingface dataset:
import string


def count_changes(s, k, pool, prev=None):
    if k == 0:
        return 0, None, None
    t = s * k
    count = 0
    i = 0
    prev = prev or t[0]
    for cur in t[1:]:
        if cur == prev:
            count += 1
            prev = pool[i]
            i = (i + 1) % length
        else:
            prev = cur
    return count, i, prev


if __name__ == '__main__':
    s = input()
    k = int(input())
    pool = list(set(string.ascii_lowercase) - set(s))
    length = len(pool)
    if k <= 2:
        print(count_changes(s, k, pool)[0])
    else:
        base_count, i, prev = count_changes(s, 3, pool)
        d, rest = divmod(k, 3)
        print(base_count * d + count_changes(s, rest, pool, i, prev)[0])

### FIXED CODE ###

def count_changes(s, k, prev=None):
    count = 0
    for _ in range(k):
        for cur in s:
            if cur == prev:
                count += 1
                prev = None
            else:
                prev = cur
    return count, prev


if __name__ == '__main__':
    s = input()
    k = int(input())
    if len(set(s)) == 1:
      print((len(s) * k) // 2)
      exit()
    if k <= 10 ** 8:
        print(count_changes(s, k)[0])
    else:
        base_count, prev = count_changes(s, 3)
        d, rest = divmod(k, 3)
        res = base_count * d
        if rest:
            res += count_changes(s, rest, prev)[0]
        elif s[0] == prev:
            res += (d - 1)
        print(res)
number = input()
number_list = list(number)
A = int(number_list[0])
B = int(number_list[2])
K = int(number_list[4])

while K > 0:
    if A % 2 == 0:
        A = A
    else:
        A = A - 1
    A = A / 2
    B = B + A
    K = K - 1
    if K > 0:
        if B % 2 == 0:
            B = B
        else:
            B = B - 1
        B = B / 2
        A = A + B
        K = K - 1
print(str(int(A)) + ' ' + str(int(B)))

### FIXED CODE ###

number = input().strip().split(' ')
number_list = list(map(int,number))
A = number_list[0]
B = number_list[1]
K = number_list[2]

while K > 0:
    if A % 2 == 0:
        A = A
    else:
        A = A - 1
    A = A / 2
    B = B + A
    K = K - 1
    if K > 0:
        if B % 2 == 0:
            B = B
        else:
            B = B - 1
        B = B / 2
        A = A + B
        K = K - 1
print(str(int(A)) + ' ' + str(int(B)))
# https://atcoder.jp/contests/abc093/tasks/arc094_a
a, b, c = map(int, input().split())

nums = [a, b, c]
nums.sort()

ans = 0
if (nums[1] - nums[0]) % 2 == 1:
    # 小さい2つの差が奇数の場合、偶数になるように
    # 小さい2つの数字両方にならないように、1を足す。
    # ここでは、二番目に大きいのと、最大の数に1を足す。
    nums[1] += 1
    nums[2] += 1
    ans += 1
ans += (nums[1] - nums[0]) // 2　# 一番小さい数が、二番目に大きい数に追いつくようにする。それには2ずつ足すのが良い。
ans += (nums[2] - nums[1]) # 一番目も二番目も同じかずになったので、両方に１つづ足していき、最大の数と同じになる様にする。
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
# int(input()) # 入力が1つ
a, b, c = map(int, input().split()) # 入力が複数
nums = sorted([a, b, c])

ans = 0
if (nums[1] - nums[0]) % 2 != 0:
    nums[2] += 1
    nums[1] += 1
    ans += 1
ans += (nums[1] - nums[0]) // 2
ans += nums[2] - nums[1]
print(ans)
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


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

    print(algorithm(N, A))


def algorithm(N, A):
    gcdList = [0] * N
    for i in range(N):
        copy_A = A.copy()
        copy_A.pop(i)
        gcdList[i] = gcd_list(copy_A)

    return max(gcdList)

problem()

### FIXED CODE ###

from functools import reduce
import fractions


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

    print(algorithm(N, A))


def algorithm(N, A):
    if N == 0:
        return 0
    if N == 1:
        return A[0]
    if N == 2:
        return max(A[0],A[1])

    L_i = 0
    R_i = [0] * N
    R_i[N - 1] = A[N - 1]
    R_i[N-2] = fractions.gcd(A[N-1], A[N-2])
    
    for i in range(3,N):
        R_i[N - i] = fractions.gcd(R_i[N - i + 1], A[N - i])

    maxGCD = R_i[1]
    for i in range(1, N-1):
        L_i = fractions.gcd(L_i, A[i - 1])
        tmp = fractions.gcd(L_i, R_i[i+1])
        if tmp > maxGCD:
            maxGCD = tmp

    L_i = gcd_list(A[:N-1])
    if L_i > maxGCD:
        maxGCD = L_i
    return maxGCD

problem()
n = int(input())

import sympy
sympy.divisors(10**9)

def m(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return len(lower_divisors) + len(upper_divisors[::-1])

ans = 0
for i in range(1, n+1):
    ans += i * m(i)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    y = n // i
    ans += y * (y + 1) * i // 2
print(ans)
def gcd(x, y):
  r = 1
  for i in range(min(x, y)):
    if x % i == 0 and y % i == 0:
      r = i
  return r

x, y = map(int, re.split(' ', raw_input()))
print(gcd(x, y))

### FIXED CODE ###

import re

def gcd(x, y):
    if x == y:
        return x
    if x < y and y % x == 0:
        return x
    if x > y and x % y == 0:
        return y
    if x <= y:
        m = y % x
        return gcd(x, m)
    if x >= y:
        m = x % y
        return gcd(y, m)

    l = list(range(1, int(min(x, y) / 2) + 1))
    l.reverse()
    r = 1
    for i in l:
        if x % i == 0 and y % i == 0:
            return i
    return 1
 
x, y = map(int, re.split(' ', raw_input()))
print(gcd(x, y))
import math
print math
N, D = map(int, input().split())
l = [list(map(int, input().split())) for l in range(N)]

ans=0
x=3
for i,a in enumerate(l):
    if math.sqrt(a[0]**2 + a[1]**2)>D :
        ans+=1

### FIXED CODE ###

import math
N, D = map(int, input().split())
l = [list(map(int, input().split())) for l in range(N)]
 
ans=0
for i,a in enumerate(l):
    if math.sqrt(a[0]**2 + a[1]**2)<=D:
        ans+=1
print(ans)
a, b, c = map(int, input().split())

if ((c - (a - b)) >= 0):
    print(c - (a - b))
else print(0)

### FIXED CODE ###

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

if ((c - (a - b)) >= 0):
    print(c - (a - b))
else:
    print(0)
a=map(int,"1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51".split())
b=int(input())
print(a[b-1])

### FIXED CODE ###

a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
b=int(input())
print(a[b-1])
A, b = map(int, input().split())

print(max([
    A+B,
    A+A-1,
    B+B-1,
]))


### FIXED CODE ###

A, B = map(int, input().split())

print(max([
    A+B,
    A+A-1,
    B+B-1,
]))
s = input()
a = s[::2].count(0) + s[1::2].count(1)
b = s[::2].count(1) + s[1::2].count(0)
print(min(a, b))

### FIXED CODE ###

s = input()
a = s[::2].count('0') + s[1::2].count('1')
b = s[::2].count('1') + s[1::2].count('0')
print(min(a, b))
from collections import defaultdict, deque

n, m = [int(i) for i in raw_input().split()]

parents = defaultdict(list)

for _ in xrange(m):
    u, v = [int(i) for i in raw_input().split()]
    parents[v-1].append(u-1)

def get_f(parents, f, i):
    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], get_f(parents, f, v) + 1)

    return f[i]

def longest_path(parents, n):
    f = [-1 for _ in xrange(n)]

    for i in xrange(n):
        get_f(parents, f, i)

    return max(f)

print longest_path(parents, n)

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n, m = [int(i) for i in raw_input().split()]
parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)
while True:
  count = int(raw_input())
  if count == 0: break
  previous_cube = [1, 2, 3, 4, 5, 6]
  operation = {'North':[1, 5, 2, 3, 0, 4], 'East':[3, 1, 0, 5, 4, 2], 'West': [2, 1, 5, 0, 4, 3], 'South':[4, 0, 2, 3, 5, 1], 'Right':[0, 2, 4, 1, 3, 5], 'Left':[0, 3, 1, 4, 2, 5]}
  sum = 1
  for i in xrange(count):
    new_cube = []
    for e in xrange(5):
      new_cube.append(previous_cube[operation[raw_input().strip()][e]])
    sum += new_cube[0]
    previous_cube = new_cube
  print sum

### FIXED CODE ###

while 1:
  n = input()
  if n == 0:  break
  d = range(1, 7)
  ans = 1
  for i in range(n):
    c = raw_input()[0]
    if c == 'N': S = [1,5,2,3,0,4]
    elif c == "S": S = [4,0,2,3,5,1]
    elif c == "E": S = [3,1,0,5,4,2]
    elif c == "W": S = [2,1,5,0,4,3]
    elif c == "R": S = [0,2,4,1,3,5]
    elif c == "L": S = [0,3,1,4,2,5]
    d = [d[s] for s in S]
    ans += d[0]
  print ans
a = int(input())
b = int(input())
print(a*b, 2*(a+b), end='')

### FIXED CODE ###

(a,b) = list(map(int, input().split()))
print ("%d %d" % (a * b, a * 2 + b * 2))
import sys
N, D = map(int, input().split())
ans = 0
for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    if x ** + y** <= D**:
        ans += 1
print(ans)

### FIXED CODE ###

import sys
N, D = map(int, input().split())
ans = 0
for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    if x **2 + y**2 <= D**2:
        ans += 1
print(ans)
a=input()
n = 0
print(int((a-1)/2))

  
  

### FIXED CODE ###

a=int(input())

print(int((a-1)/2))
n = int(input())

t_score = 0
h_score = 0


for i in range(n):
 t, h = input().split()
 if ord(t[0]) > ord(h[0]):
  t_score += 3
 elif ord(t[0]) < ord(h[0]):
  h_score += 3
 elif ord(t[0]) == ord(h[0])
  t_score += 1
  h_score += 1

print("{0} {1}".format(t_score, h_score))

### FIXED CODE ###

n = int(input())

t_score = 0
h_score = 0


for i in range(n):
 t, h = input().split()
 if t == h:
  t_score += 1
  h_score += 1
  continue
 if len(t) >= len(h):
  for j in range(len(h)):
   if ord(t[j]) > ord(h[j]):
    t_score += 3
    break
   elif ord(t[j]) < ord(h[j]):
    h_score += 3
    break
  else:
   t_score += 3
 elif len(t) < len(h):
   for j in range(len(t)):
    if ord(t[j]) > ord(h[j]):
     t_score += 3
     break
    elif ord(t[j]) < ord(h[j]):
     h_score += 3
     break
   else:
    h_score += 3

   
print("{0} {1}".format(t_score, h_score))
number = int(input())

num_eight_divisors = 0

numbers = list(range(9, number + 1, 2))

for i in range(9, number + 1, 2):
    divisors = [1, i]

    for j in range(2, i):
        q, mod = divmod(i, j)

        if mod == 0:
            divisors.append(j, q)

    if len(set(divisors)):
        num_eight_divisors = num_eight_divisors + 1

print(num_eight_divisors)


### FIXED CODE ###

number = int(input())

num_eight_divisors = 0

numbers = list(range(9, number + 1, 2))

for i in range(9, number + 1, 2):
    divisors = [1, i]

    for j in range(2, i):
        q, mod = divmod(i, j)

        if mod == 0:
            divisors.append(j)
            divisors.append(q)

    if len(set(divisors)) == 8:
        num_eight_divisors = num_eight_divisors + 1

print(num_eight_divisors)
import sys
input = sys.stdin.readline

S = list(input().strip())
P = [list(v) for v in ["dream", "dreamer", "erase", "eraser"]]

def dfs(n):
    if len(S[n:]) == 0:
        return True
    
    for v in P:
        if S[n:n+len(v)] == v:
            if dfs(n + len(v)):
                return True
    
    return False

if dfs(0):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

import sys
input = sys.stdin.readline

S = list(reversed(input().strip()))
P = [list(reversed(v)) for v in ["dream", "dreamer", "erase", "eraser"]]

n = 0
while n < len(S):
    if S[n:n+5] == P[0] or S[n:n+5] == P[2]:
        n += 5
    elif S[n:n+7] == P[1]:
        n += 7
    elif S[n:n+6] == P[3]:
        n += 6
    else:
        print("NO")
        exit()
        
print("YES")
from math import factorial
import sys
input = sys.stdin.readline
def ncr(n,r):
 if n <= 1:
  return 0
 else:
  return  factorial(n) / factorial(r) / factorial(n - r)

n= int(input())
a = list(int(i) for i in input().split())
s = [0]
for i in range(n):
  s.append(s[i]+a[i])
s = sorted(s,reverse =True)
ans = 0
tmp = 1
for i in range(n):
  if s[i] == s[i+1]:
   tmp += 1
  else:
   ans += ncr(tmp,2)
   tmp = 1
ans += ncr(tmp,2)
print(int(ans))


### FIXED CODE ###

from math import factorial
import sys
input = sys.stdin.readline
def ncr(n):
 if n <= 1:
  return 0
 elif n == 2:
  return 1
 else:
  return  (factorial(n) // 2) // factorial(n - 2)

n= int(input())
a = list(int(i) for i in input().split())
s = [0]
for i in range(n):
  s.append(s[i]+a[i])
s = sorted(s,reverse =True)
ans = 0
tmp = 1
for i in range(len(s)-1):
  if s[i] == s[i+1]:
   tmp += 1
  else:
   ans += ncr(tmp)
   tmp = 1
ans += ncr(tmp)
print(ans)
import sys
import itertoolsy
N,D = map(int,input().split())
array = [ list(map(int,input().split())) for x in range(N) ]

if not ( 2 <= N <= 10 and 1 <= D <= 10 ): sys.exit()
for I in array:
    if not ( -20 <= min(I) and max(I) <= 20 ): sys.exit()

count = 0
for I in list(itertools.combinations(array,2)):
    tmp_distance = 0
    for J in range(D):
        tmp_distance += abs(I[0][J] - I[1][J]) ** 2
    distance = tmp_distance ** 0.5 
    if distance.is_integer(): count += 1

print(count)

### FIXED CODE ###

import sys
import itertools
N,D = map(int,input().split())
array = [ list(map(int,input().split())) for x in range(N) ]

if not ( 2 <= N <= 10 and 1 <= D <= 10 ): sys.exit()
for I in array:
    if not ( -20 <= min(I) and max(I) <= 20 ): sys.exit()

count = 0
for I in list(itertools.combinations(array,2)):
    tmp_distance = 0
    for J in range(D):
        tmp_distance += abs(I[0][J] - I[1][J]) ** 2
    distance = tmp_distance ** 0.5 
    if distance.is_integer(): count += 1

print(count)
a,b,c=map(int,input().stlip())
if a+b+c<=21:
	print('win')
  else:
  	print('bust')

### FIXED CODE ###

A = sum(list(map(int, input().split())))
 
print("bust") if A >= 22 else print("win")
import itertools
S=input()
T=input()

n=len(T)
Thatena=[[T[j] if (i>>j)&1 else "?" for j in range(n)] for i in range(2**n)] #Tのうち0文字以上を?に置き換えたものの集合
#print(Thatena)
#print(len(Thatena))
anslist=[S.find("".join(t)) for t in Thatena if S.find("".join(t))!=-1]

#print(anslist[0],anslist[0]+len(T))
ans=S[:anslist[0]]+T+S[anslist[0]+len(T):]
print("".join([c if c!="?" else "a" for c in ans]))

### FIXED CODE ###

import re
S = input().replace('?', '.')
T = input()
for i in range(len(S)-len(T), -1, -1):
    if re.match(S[i:i+len(T)], T):
        S = S.replace('.', 'a')
        print(S[:i]+T+S[i+len(T):])
        exit()
print('UNRESTORABLE')
n,m=map(int,input().split())
li=[]
city_counter = [1] * (m+1)
ans=[]

for i in range(m):
    p,y=map(int,input().split())
    li.append((p,y,i))

li.sort(key=lambda x:x[1])

for i in range(len(li)):
    tmp = str(li[i][0]).zfill(6) + str(city_counter[li[i][0]]).zfill(6)
    ans.append((tmp,li[i][2]))
    city_counter[li[i][0]] += 1

ans.sort(key=lambda x:x[1])

for i in range(len(ans)):
    print(ans[i][0])


### FIXED CODE ###

n,m=map(int,input().split())
dic=[]
ans=[]
number=[1] * (10**5+2)

for i in range(m):
    p,y=map(int,input().split())
    dic.append((p,y,i))

dic.sort(key=lambda x:x[1])

for i in range(m):
    tmp=str(dic[i][0]).zfill(6)+str(number[dic[i][0]]).zfill(6)
    number[dic[i][0]]+=1
    ans.append((tmp,dic[i][2]))

ans.sort(key=lambda x:x[1])

for i in range(m):
    print(ans[i][0])
n=int(x[0])
a=int(x[1])
b=int(x[2])
v=input().split()
x=0
while x<n:
    v[x]=int(v[x])
    x+=1
v.sort()
ave=0
for i in range(a):
    ave+=v[-i-1]
print(ave/a)
up=1
down=1
ans=0
x=v[-a:].count(v[-a])
y=v.count(v[-a])
if v[-1]!=v[-a]:
    
    for i in range(2,y+1):
        up*=i
    for i in range(2,x):
        down*=i
    for i  in range(2, y-x+1):
        down*=i
    print(up//down)
else:
    i=a
    while v[-i]==v[-1] and i!=b:
        for i in range(2,y+1):
            up*=i
        for i in range(2,i+1):
            down*=i
        for i  in range(2, y-i+1):
            down*=i
        ans+=(up//down)
        i+=1
    print(ans)

### FIXED CODE ###

import decimal
def ncr(x,y):
	ans=1
	q=x-y
	while x>y:
		ans*=x
		x=x-1
	
	while q>1:
		ans=ans/q
		q=q-1
	
	return ans

x=input().split()
n=int(x[0])
a=int(x[1])
b=int(x[2])
v=[0]*n
x = input().split()
ind=0
M={1:0}
M2={1:0}
for i in x:
	v[ind]=int(i)
	if int(i) in M:
		M[v[ind]]+=1
	else:
		M[v[ind]]=1
	ind+=1
v.sort(reverse=True)

cnt=0
ind=0
m=0
while cnt<a:
	cnt+=1
	m=decimal.Decimal((cnt-1)*m+v[ind])/decimal.Decimal(cnt)
	if v[ind] in M2:
		M2[v[ind]]+=1
	else:
		M2[v[ind]]=1
	ind+=1
while cnt<b:
	if (cnt*m+v[ind])/(cnt+1)<m:
		break
	else:
		cnt+=1;
		if v[ind] in M2:
			M2[v[ind]]+=1
		else:
			M2[v[ind]]=1
		ind+=1
print(m)
maxw=cnt;
ways=0;
for i in range(int(cnt),a-1,-1):
	if v[ind-1] not in M2:
			M2[v[ind]]=0
	if v[ind-1] not in M:
			M[v[ind-1]]=0
	#print(M[v[ind-1]],M2[v[ind-1]])
	ways+=ncr(M[v[ind-1]],M2[v[ind-1]])
	
	M2[v[ind-1]]-=1

print(round(ways))
x=int(input())
if x<100:
  print(0)
  exit()
DP=[False]*(x+1)
for i in range(x+1):
  coin=list(range(100,106,1))
  if i in coin:
    DP[i]=True
    continue
  DP[i]=True if any(DP[i-m] for m in coin) else False
print(1 if DP[x]==True else 0)

### FIXED CODE ###

x=int(input())
if x<100:
  print(0)
  exit()
elif 100<=x<=105:
  print(1)
  exit()
else:
  DP=[False]*(x+1)
  for i in range(x+1):
    coin=list(range(100,106,1))
    if i in coin:
      DP[i]=True
      continue
    DP[i]=True if any(DP[i-m] for m in coin) else False
  print(1 if DP[x]==True else 0)
n,x,m=map(int,raw_input().split()) 
v=[x] 
t={x:1} 
ok=1
while True: 
    y=(x*x)%m 
    if y==0: 
        print sum(v);ok=0;break
    if y in t: 
        break 
    else: 
        t[y]=1 
        v.append(y) 
        x=y 
g=n%(len(v)) 
ans=0
for i in range(len(v)): 
    if i>g: 
        ans+=((n/len(v))*(v[i]) )
        
    else: 
        ans+=((n/len(v)+1)*v[i]) 
       
if ok:
    print ans


### FIXED CODE ###

a=raw_input()
if a[-1]=='s':
    print (a+"es")
else: 
    print (a+"s")
# -*- coding: utf-8 -*-
from bisect import bisect_right

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

P = primes(10**6)

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

check = [0]*(10**6)
flag = 0
for a in A:
    temp = 0
    for i in range(bisect_right(P, int(a**0.5+10))):
        if a%P[i] == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 1
            temp = 1
    if temp:
        check[a] == 1
    if flag:
        break

if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")
    
    
    
    
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n = 10**6
minfac = list(range(n+1))
for i in range(2, int(n**0.5) + 1):
    if minfac[i] < i:
        continue
    for j in range(i, n + 1, i):
        if minfac[j] > i:
            minfac[j] = i

"""nの素因数の種類を求める"""
def osa_k(n):
    temp = set()
    while n > 1:
        temp.add(minfac[n])
        n = n//minfac[n]
    return temp


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

check = [0]*(10**6)
flag = 0
for a in A:
    for i in osa_k(a):
        if check[i]:
            flag = 1
        else:
            check[i] = 1
    if flag:
        break
        
if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")
N, M = map(int, input().split())
H = list(map(int, input().split()))
a = []
[a.append(i) for i in range(1,N+1)]
for i in range(M):
  ai, bi = map(int, input().split())
  if ai < bi:
    a.remove(ai)
  else:
    a.remove(bi)
print(len(a))    
  

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
a = [True] * N
for i in range(M):
  ai, bi = map(int, input().split())
  if H[ai-1] <= H[bi-1] :
    a[ai-1] = False
  if H[ai-1] >= H[bi-1]:
    a[bi-1] = False
print(sum(a))
import sys,math
sys.setrecursionlimit(10**5)

n,k=map(int,input().split())
m=10**9+7
to=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1, input().split())
  to[a].append(b)
  to[b].append(a)


def nPk(_n,_k):
  if _k<=0: return 1;
  a=math.factorial(_n)
  b=math.factorial(_n-_k)
  return a*pow(b,m-2,m)


def dfs(_v, p=-1):
  global ans
  for u in to[_v]:
    if u==p: continue
    dfs(u, _v)
  p=len(to[_v])
  ans*=nPk(k,p+1) if _v==0 else nPk(k-2,p-1)
  ans%=m
    
    
ans=1
chk=[False]*n
dfs(0)
  
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

n,k=map(int,input().split())
m=10**9+7
to=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1, input().split())
  to[a].append(b)
  to[b].append(a)
frac=[1]*(10**5+1)
for i in range(1,10**5+1):
  frac[i]=frac[i-1]*i
  frac[i]%=m


def nPk(_n,_k):
  if _n<0 or _k<0 or _n-_k<0: return 0;
  a=frac[_n]
  b=frac[_n-_k]
  return (a*pow(b,m-2,m))%m


def dfs(_v, _u=-1):
  global ans
  for u in to[_v]:
    if u==_u: continue
    dfs(u, _v)
  p=len(to[_v])
  ans*=nPk(k,p+1) if _v==0 else nPk(k-2,p-1)
  ans%=m
    
    
ans=1
chk=[False]*n
dfs(0)
  
print(ans)
N=input(N)

x=int(N**0.5)
print(x**2)

### FIXED CODE ###

N=int(input())

x=int(N**0.5)
print(x**2)
n = int(input())
vlist = list(map(int, input().split(" ")))

head = vlist[::2]
foll = vlist[1::2]

import collections
ch = collections.Counter(head).most_common()
cf = collections.Counter(foll).most_common()

h_ = ch[0]
f_ = cf[0]

if h_[0] == f_[0]:
    if h_[1] > f_[1]:
        if len(cf) != 1:
            f_ = cf[1]
        else:
            f_ = (-1.1, 0)
    else:
        if len(ch) != 1:
            h_ = ch[1]
        else:
            h_ = (-1.1, 0)
elif h_[1] == f_[1]:
    if h_[0] == vlist[0]:
        f_ = (-1.1, 0)
    else:
        h_ = (-1.1, 0)

count = 0
for i in range(len(vlist)):
    if i % 2 == 0 and vlist[i] != h_[0]:
        count += 1
    if i % 2 == 1 and vlist[i] != f_[0]:
        count += 1

print(count)

### FIXED CODE ###

intput_ = list(input())
output = ""
for s_ in intput_:
  if s_ == '1':
    output += "9"
  elif s_ == '9':
    output += "1"
  else:
    output += s_

print(output)