Harryxun/stf_run huggingface dataset:
N, Q = map(int, input().split())
L, R = [None] * N, [None] * N

S = input()

for i in range(Q):
    L[i], R[i] = map(int, input().split())


counts = [0] * N
count_tmp = 0

for i in range(1, N):
    if S[i-1] == 'A' and S[i] == 'C':
        count_tmp += 1
    counts[i] = count_tmp

# print(counts)

for i in range(Q):
    print(counts[R[i] - 1] - counts[L[i] - 1])

### FIXED CODE ###

N, Q = map(int, input().split())
L, R = [None] * Q, [None] * Q

S = input()

for i in range(Q):
    L[i], R[i] = map(int, input().split())

counts = [0] * N
count_tmp = 0

for i in range(1, N):
    if S[i-1] == 'A' and S[i] == 'C':
        count_tmp += 1
    counts[i] = count_tmp

# print(counts)

for i in range(Q):
    print(counts[R[i] - 1] - counts[L[i] - 1])
k,x=[int(i) for i in input().split()]

left=max(−1000000,x-k+1)
right=min(x+k-1,1000000)
for i in range(left,right+1):
    print(i,end=' ')
print()


### FIXED CODE ###

k,x=[int(i) for i in input().split()]

left=max(-1000000,x-k+1)
right=min(x+k-1,1000000)
for i in range(left,right+1):
    print(i,end=' ')
print()
S = input()
T = input()
pareil = True
for i in range(0,len(S)):
	if S[i] != T[i]:
    	pareil = False
if pareil:
	print('Yes')
else:
	print('No')

### FIXED CODE ###

S = input()
T = input()

pareil = True
for i in range(0, len(S)):
    if S[i] != T[i]:
        pareil = False
if pareil:
    print('Yes')
else:
    print('No')
N=int(input())
if N = 10**5:
  print("90909")
elif N >= 10**4:
  resid=N-10**4+1
  print(str(9+900+resid))
elif N >= 10**3:
  print("990")
elif N >= 10**2:
  resid=N-10**2+1
  print(str(9+resid))
elif N >= 10:
  print("9")
else:
  print(str(N))

### FIXED CODE ###

N=int(input())
if N == 10**5:
  print("90909")
elif N >= 10**4:
  resid=N-10**4+1
  print(str(9+900+resid))
elif N >= 10**3:
  print("909")
elif N >= 10**2:
  resid=N-10**2+1
  print(str(9+resid))
elif N >= 10:
  print("9")
else:
  print(str(N))
S = list(input())
list = []
temp = ""
for i in range(len(S)):
    if S[i] == 'A' or S[i] == 'T' or S[i] == 'G' or S[i] == 'C':
        temp += S[i]
    else:
        list.append(temp)
        temp = ""
#print(list)
ans = []
for i in range(len(list)):
    ans.append(len(list[i]))
#print(ans)
print(max(ans))

### FIXED CODE ###

S = list(input())
#print(S)
list = []
temp = ""
for i in range(len(S)):
    if S[i] == 'A' or S[i] == 'T' or S[i] == 'G' or S[i] == 'C':
        temp += S[i]
        list.append(temp)
    else:
        list.append(temp)
        temp = ""
#print(list)
ans = []
for i in range(len(list)):
    ans.append(len(list[i]))
#print(ans)
print(max(ans))
n = int(input())
C = [c for c in input()]
Red = []
White = []
len_Red = 0
len_White = 0
for i in range(n):
    if C[i] == 'R':
        Red.append(i)
        len_Red += 1
    else:
        White.append(i)
        len_White += 1


ans = 0
cnt = 0
w = 0
r = len_Red - 1
while True:
    if w < len_White:
        cnt = White[w]
        w += 1
    else:
        print(ans)
        exit()
    if cnt < Red[r]:
        C[cnt], C[r] = C[r], C[cnt]
        ans += 1
        r -= 1
    else:
        print(ans)
        exit()

### FIXED CODE ###

n = int(input())
C = [c for c in input()]
Red = []
White = []
len_Red = 0
len_White = 0
for i in range(n):
    if C[i] == 'R':
        Red.append(i)
        len_Red += 1
    else:
        White.append(i)
        len_White += 1

ans = 0
cnt = 0
w = 0
r = len_Red - 1
while True:
    if w < len_White:
        cnt = White[w]
        w += 1
    else:
        print(ans)
        exit()
    if r >= 0 and cnt < Red[r]:
        C[cnt], C[r] = C[r], C[cnt]
        ans += 1
        r -= 1
    else:
        print(ans)
        exit()
W, H, x, y, r = map(int, raw_input().split))
 
if (0 <= x-r) and (x+r <= W) and (0 <= y-r) and (y+r <= H):
 print 'Yes'
else:
 print 'No'

### FIXED CODE ###

W, H, x, y, r = map(int, raw_input().split())
 
if r <= x and x + r <= W and r <= y and y + r <= H:
 print 'Yes'
else:
 print 'No'
from decimal import *
a,b=map(int,input().split())
kotae=Decimal(a)*Decimal(b)
kotae=kotae%1
print(kotae)

### FIXED CODE ###

from decimal import *
a,b=map(Decimal,input().split())
kotae=Decimal(a)*Decimal(b)
print(int(kotae))
from itertools import combinations
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
data = [0]*4001
i = 1
while i**2<=4001:
    data[i**2]=1
    i += 1
res = 0
for a, b in combinations(X,2):
    temp = 0
    for x, y in zip(a, b):
        temp += (x-y)**2
    if data[temp]:
        res += 1
print(res)

### FIXED CODE ###

from itertools import combinations
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
data = [0]*16002
i = 1
while i**2<=16001:
    data[i**2]=1
    i += 1
res = 0
for a, b in combinations(X,2):
    temp = 0
    for x, y in zip(a, b):
        temp += (x-y)**2
    if data[temp]:
        res += 1
print(res)
a, b = map(int, input.split())
print(a * b, a * 2 + b * 2)




### FIXED CODE ###

a, b = map(int, input().split())
print(a * b, a * 2 + b * 2)
import sys
input=sys.stdin.readline
from itertools import combinations as cmb
n=int(input())
s=set(input())
combiset=set(cmb(s,3))
print(len(combiset))

### FIXED CODE ###

m,d=map(int,input().split(" "))
mm,dd=map(int,input().split(" "))
if m==mm:print(0)
else:print(1)
s = input()
t = input()

y = s[::-1]
for i,x in enumerate(y):
    print(i,y[i])
    if x == "?":
        cont += 1
        if cont == len(t):
            break
        elif (cont == len(t)-1)&(y[i+1] == t[0]):
            break
    else:
        cont = 0
            
if cont == 0:
    print("UNRESTORABLE")
else:
    print((s[:len(s)-i-1]+t+s[len(s)-i+len(t):]).replace("?","a"))

### FIXED CODE ###

s = input()
t = input()

flg = 0
y = s[::-1]
z = t[::-1]
result = []
for j,x in enumerate(range(0,len(y))):
    result = []
    for i,k in enumerate(y[x:x+len(t)]):
        if (k == z[i])|(k=="?"):
            result.append(True)
    if all(result)&(len(result)==len(t)):
        flg = 1
        break
if flg == 1:
    print((s[:len(s)-j-len(t)]+t+s[len(s)-j:]).replace("?","a"))
else:
    print("UNRESTORABLE")
n, a, b, k = map(int, input().split())

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def mod_inv(a, mod):
    return (pow(a,mod-2,mod))

def mod_combination(n, k, mod):
    return (fact[n]*mod_inv(fact[k], mod)*mod_inv(fact[n-k], mod)) % mod

g = gcd(k, gcd(a, b))
a //= g
b //= g
k //= g

mod = 998244353
fact = [1] + [0] * n
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod
if a < b:
    tmp = a
    a = b
    b = tmp

ans = 0
for x in range(max(-int(-(k-b*n)//a),0), k//a+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        ans += mod_combination(n, x, mod) * mod_combination(n, y, mod)
        ans %= mod
    
print(ans)

### FIXED CODE ###

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

mod = 998244353
fact = [1] + [0] * n
inv_fact = [0] * (n+1)
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod

for i in range(n+1):
    inv_fact[i] = pow(fact[i],mod-2,mod)
    
def cb(n, k, mod):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % mod

ans = 0
for x in range(n+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        if y >= 0:
            if x > n or y > n:
                pass
            else:
                ans += cb(n, x, mod) * cb(n, y, mod)
                ans %= mod
    
print(ans)
n,m,d=map(int,input().split())
da=[0 for i in range(n)]
print((n-2)*180)

### FIXED CODE ###

n=int(input())
print((n-2)*180)
n = int(input())
a = list(map(int, input().split()))

if len(set(a)) == 1:
    print(a[0])
else:
    a.sort()
    for i in range(1, 10 ^ 9+1):
        count = i
        for i in range(1, len(a)):
            x = a[i] + count
            for j in range(i):
                x = x % a[i-1-j]
        if x == 0:
            break

    print(count)


### FIXED CODE ###

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


def gcd(a, b):
    if a <= b:
        if b % a == 0:
            return a
        else:
            return(gcd(b % a, a))
    else:
        if a % b == 0:
            return b
        else:
            return(gcd(a % b, b))


ans = gcd(a[0], a[1])

for i in range(2, len(a)):
    ans = gcd(ans, a[i])

print(ans)
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list()
a=0
b=0
for i in range(N+M):
  if a+1<=N and b+1<=M and A[a]<B[b]:
    C.append(A[a])
    a+=1
  elif a+1<=N and b+1<=M and A[a]>B[b]:
    C.append(B[b])
    b+=1
  elif  a+1<=N and b+1<=M and A[a]==B[b]:
    if a+2==N:
      C.append(B[b])
      b+=1
    elif b+2==N:
      C.append(A[a])
      a+=1
    elif A[a+1]<B[b+1]:
      C.append(A[a])
      a+=1
    else:
      C.append(B[b])
      b+=1
  elif a==N:
    C.append(B[b])
    b+=1
  elif b==M:
    C.append(A[a])
    a+=1
import numpy as np
L=np.array(C).cumsum()
print(len(L[L <= K]))

### FIXED CODE ###

N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
c=0
k=M
import numpy as np
A=np.array(A).cumsum()
B=np.array(B).cumsum()
for i in range(N):
  d=K-A[i]
  if d<0:
    for j in reversed(range(M)):
      if K-B[j]>=0:
        if c<j+1:
          c=j+1
        break
    break
  else:
    for j in reversed(range(k)):
      if d>=B[j]:
        if c<i+j+2:
          c=i+j+2
        k=j+1
        break
    if d<B[0]:
      if c<i+1:
        c=i+1
      k=0
for j in reversed(range(M)):
  if K-B[j]>=0:
    if c<j+1:
      c=j+1
print(c)
S = list(input())

a = 'abcdefghijklmnopqrstuvwxyz'
if len(S) != 26:
    for i in range(26):
        if not a[i] in S:
            print (*S, sep = '', end = '')
            print (a[i])
            exit()

for i in range(25, 0, -1):
    if ord(S[i]) < ord(S[i - 1]):
        continue
    else:
        break
# print (i)
if i == 1:
    print (-1)
    print (A)
    exit()

tmp_n = ord('z')
for j in S[i:]:
    if ord(j) > ord(S[i - 1]):
        tmp_n = min(tmp_n, ord(j))

print (*S[:i - 1], sep = '', end = '')
print (chr(tmp_n))

### FIXED CODE ###

S = list(input())

a = 'abcdefghijklmnopqrstuvwxyz'
if len(S) != 26:
    for i in range(26):
        if not a[i] in S:
            print (*S, sep = '', end = '')
            print (a[i])
            exit()

for i in range(25, -1, -1):
    if i == -1:
        break
    if ord(S[i]) < ord(S[i - 1]):
        continue
    else:
        break
# print (i)
if i == 0:
    print (-1)
    exit()

tmp_n = ord('z')
for j in S[i:]:
    if ord(j) > ord(S[i - 1]):
        tmp_n = min(tmp_n, ord(j))

print (*S[:i - 1], sep = '', end = '')
print (chr(tmp_n))
import numpy as np
from itertools import combinations_with_replacement

N,M,X = map(int,input().split())
CA = []
for i in range(N):
  CA.append(list(map(int,input().split())))

OK = True
CA = np.array(CA)
sums = np.sum(CA,axis=0)
for i in range(1,M+1):
  if sums[i] < X:
    OK = False
    break

if OK == False:
  print(-1)
else:
  As = []
  for A in combinations_with_replacement(range(0, N),N):
    As.append(tuple(set(A)))
  print(As)
  As = list(map(list, set(As)))
  min_ = sums[0]
  for i in hoge:
    mini_CA = []
    for j in i:
      mini_CA.append(CA[j])
    mini_CA = np.array(mini_CA)
    OK2 = True
    sums = np.sum(mini_CA,axis=0)
    for k in range(1,M+1):
      if sums[k] < X:
        OK2 = False
        break
    if OK2 == True and sums[0] < min_:
      min_ = sums[0]
  print(min_)


### FIXED CODE ###

import numpy as np
from itertools import combinations_with_replacement

N,M,X = map(int,input().split())
CA = []
for i in range(N):
  CA.append(list(map(int,input().split())))

OK = True
CA = np.array(CA)
sums = np.sum(CA,axis=0)
for i in range(1,M+1):
  if sums[i] < X:
    OK = False
    break

if OK == False:
  print(-1)
else:
  # As = []
  # for A in combinations_with_replacement(range(0, N), r=M):
  #   As.append(tuple(set(A)))
  # As = list(map(list, set(As)))
  min_ = sums[0]
  hoge = []
  kouho = list(range(1,N+1))
  for i in combinations_with_replacement(kouho, N):
    hoge.append(list(set(i)))
  hoge = list(map(list, set(map(tuple, hoge))))
  for i in hoge:
    mini_CA = []
    for j in i:
      mini_CA.append(CA[j-1])
    mini_CA = np.array(mini_CA)
    OK2 = True
    sums = np.sum(mini_CA,axis=0)
    for k in range(1,M+1):
      if sums[k] < X:
        OK2 = False
        break
    if OK2 == True and sums[0] < min_:
      min_ = sums[0]
  print(min_)
import math
r = int(input)
print(math.pi*r*2)

### FIXED CODE ###

import math
r = int(input())
print(math.pi*r*2)
f = lambda: map(int,input().split())
h,w = f()
a = [list(f()) for _ in range(h)]
for i in range(h):
    if i%2 == 0:
        a[i].reverse()

for i in range(h):
    for j in range(w):
        if i == w-1 and j == h-1:
            break
        if i&1:
            if a[i][j]&1:
                if j == w-1:
                    print(i+1,w,i+2,w)
                    a[i+1][0] += 1
                else:
                    print(i+1,j+1,i+1,j+2)
                    a[i][j+1] += 1
        else:
            if a[i][j] & 1:
                if j == w - 1:
                    print(i + 1, 1, i + 2, 1)
                    a[i+1][0] += 1
                else:
                    print(i+1, w-j, i+1, w-j-1)
                    a[i][j+1] += 1


### FIXED CODE ###

f = lambda: map(int,input().split())
h,w = f()
a = [list(f()) for _ in range(h)]
for i in range(h):
    if i%2 == 0:
        a[i].reverse()

count = 0
ans = []

for i in range(h):
    for j in range(w):
        if i == h-1 and j == w-1:
            break
        if i&1:
            if a[i][j]&1:
                count += 1
                if j == w-1:
                    ans.append([i+1,w,i+2,w])
                    a[i+1][0] += 1
                else:
                    ans.append([i+1,j+1,i+1,j+2])
                    a[i][j+1] += 1
        else:
            if a[i][j] & 1:
                count += 1
                if j == w - 1:
                    ans.append([i + 1, 1, i + 2, 1])
                    a[i+1][0] += 1
                else:
                    ans.append([i+1, w-j, i+1, w-j-1])
                    a[i][j+1] += 1
print(count)
for i in range(count):
    print(*ans[i])
import functools
from math import gcd
n,x =map(int,input().split())
lis = list(map(int,input().split()))
for i in range(n):
lis[i] = abs(lis[i]-x)
print(functools.reduce(gcd,lis))

### FIXED CODE ###

from functools import reduce
from fractions import gcd
N,X=map(int,input().split())
x=[abs(X-int(i)) for i in input().split()]
print(reduce(gcd,x))
a = int(input())
b = int(input())
if 0 < a < 10 & 0 < b < 10:
  print(a * b)
else:
  print -1

### FIXED CODE ###

a, b = map(int, input().split())
if a < 10 and b < 10:
  print(a*b)
else:
  print(-1)
n = int(input())
h = list(map(int,input().split()))
submax = 0

for i in range(n-1):
  for j in range(i+1,n):
    if h[i] - h[j] >= 2:
      submax = 1
      break
  if submax == 1:
    break

if submax == 1:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

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

if nokori < 0:
  print(0)
else:
  print(nokori)
n = int(input())
if n%10=7:
  print('Yes')
else:
  n=n//10
  if n%10=7:
    print('Yes')
  else if n//10=7:
    print('Yes')
  else:
    print('No')



### FIXED CODE ###

n = int(input())
if n%10==7:
  print('Yes')
else:
  n=n//10
  if n%10==7:
    print('Yes')
  elif n//10==7:
    print('Yes')
  else:
    print('No')
import math
n = int(input())
counter = False
#for n in range (0,100):
  for i in range (math.ceil((n+1) / 4) ):
    for j in range (math.ceil((n+1) / 7) ):
      #print(n, i,j)
      if i*4 + j*7 == n:
        counter = True
  if counter == True:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

import math
n = int(input())
counter = False
#for n in range (0,100):
for i in range (math.ceil((n+1) / 4) ):
  for j in range (math.ceil((n+1) / 7) ):
    #print(n, i,j)
    if i*4 + j*7 == n:
      counter = True
if counter == True:
  print("Yes")
else:
  print("No")
n = int(input())
strs, strt = [s for s in range(n)]
new = ''
for i in range(0, n)
	new += strs[i]
  	new += strt[i]
print (new)

### FIXED CODE ###

n = int(input())
s,t = input().split()
new = ''
for i in range(n):
  new += s[i]
  new += t[i]
print (new)
n = int(input())
h_list = list(map(lambda x: int(x), input().split()))

max_move = 0
current_move = 0
s = 0
t = 1
continue_flag = True


while continue_flag:
    if h_list[s] >= h_list[t]:
        current_move += 1
        s += 1
        t += 1
    else:
        max_move = max([max_move, current_move])
        s += 1
        t += 1
        
    if t == n-1 or s == n-2:
        max_move = max([max_move, current_move])
        continue_flag = False
        
print(max_move)

### FIXED CODE ###

n = int(input())
h_list = list(map(lambda x: int(x), input().split()))

max_move = 0
current_move = 0
s = 0
t = 1
continue_flag = True

if n == 1:
    print(0)
else:
    while continue_flag:
        if h_list[s] >= h_list[t]:
            current_move += 1
            s += 1
            t += 1
        else:
            max_move = max([max_move, current_move])
            current_move = 0
            s += 1
            t += 1

        if t == n:
            max_move = max([max_move, current_move])
            continue_flag = False

    print(max_move)
letters = input()
if letters[2] == letters[3] && letters[4] == letters[5] :
    print('Yes')

else :
    print('No')

### FIXED CODE ###

letters = input()
if letters[2] == letters[3] and letters[4] == letters[5] :
    print('Yes')

else :
    print('No')
#i = int(input())
#s = input()
i = 13
s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
en = ['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 = [(en[(en.index(k)+i)%26]) for k in s]
print(''.join(s_list)

### FIXED CODE ###

i= int(input())
s = input()
en = ['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 = [(en[(en.index(k)+i)%26]) for k in s]
print(''.join(s_list))
a, b = map(int input().split())

def convert_num(a):
    if a == 1:
        a = 14
    return a

a = convert_num(a)
b = convert_num(b)
if a > b:
    print('Alice')
elif a == b:
    print('Draw')
else:
    print('Bob')
    

### FIXED CODE ###

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

def convert_num(a):
    if a == 1:
        a = 14
    return a

a = convert_num(a)
b = convert_num(b)
if a > b:
    print('Alice')
elif a == b:
    print('Draw')
else:
    print('Bob')
n = int(input())
hs = [int(elem) for elem in input().split()]

if n == 1:
  print("Yes")
else:
  flag = 0
  for i, h in enumerate(hs):
    if i == 0:
      pass
    else:
      if hs[i-1] == h + 1:
        hs[i-1] -= 1
      elif hs[i-1] > h + 1:
        flag = 1
        break
      else:
        pass
  
if flag == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = int(input())
h = [int(elem) for elem in input().split()]

flg = 0
max = 0
if n > 1 :
  for i in range(n):
    if h[i] > max:
      max = h[i]
    elif h[i] < max-1 :
      flg = 1
      break
 
if flg == 1 :
  print('No')
else:
  print('Yes')
N = int(input())
a = 0
for i in range(1,N+1) :
  if i%2 = 1 :
    a += 1
print(a/N)
  




### FIXED CODE ###

N = int(input())
a = 0
for i in range(1,N+1) :
  if i%2 == 1 :
    a += 1
print(a/N)
x=int(input())
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
li=[]
def f(n):
  c=0
  while x%n==0:
    x //= n
    c+=1
  return c
ans=0
for p in prime:
  ans = max(ans,f(p))
print(ans)

### FIXED CODE ###

x=int(input())
li=[]
for i in range(32):
  for j in range(2,6):
    if pow(i,j)<=x:
      li.append(pow(i,j))
print(max(li))
r,g=map(int,input().split())
print(g*2-r)

### FIXED CODE ###

r=int(input())
g=int(input())
print(g*2-r)
N = input()
for i in range(len(N)):
  if N[i] == "1":
    N[i] = "9"
  else:
    N[i] = "1"
print(N)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = list(input())[: -1]
for i in range(len(n)):
  if n[i] == "1":
    n[i] = "9"
  elif n[i] == "9":
    n[i] = "1"
print("".join(n))
def main(N, M):
    n = 1
    for _ in range(M):
        n *= 2

    print n * ((N - M) * 100 + M * 1900)

### FIXED CODE ###

N, M = map(int, input().split())

n = 1
for _ in range(M):
    n *= 2

print(n * ((N - M) * 100 + M * 1900))
list = [int(input().splir\t(''))for i in range(3)]

for i in range(3):
    if list[i] == 1:
        print(9, end="")
    elif list[i] == 9:
        print(9, end="")

print()


### FIXED CODE ###

nyu = input()
list(nyu)

for i in nyu:
    if i == "1":
        print("9", end="")
    elif  i == "9":
        print("1", end="")
print()
x = input()

for i in x:

        if x == 0:
        break

print("Case " +i+ ": " + x)

### FIXED CODE ###

print(*sorted(input().split(" ")))
while(1):
  count = input()
  if count == 0: break
  previous_cube = [1, 2, 3, 4, 5, 6]
  operation{'North':[2, 6, 3, 4, 1, 5], 'East':[4, 2, 1, 6, 5, 3], 'West': [3, 2, 6, 1, 5, 4], 'South':[5, 1, 3, 4, 6, 2], 'Right':[1, 3, 5, 2, 4, 6], 'Left[1, 4, 2, 5, 3, 6]}
  sum = 1
  for i in xrange(count):
    new_cube = []
    for i in xrange(6):
      new_cube.append(previous_cube[operation[raw_input()][e]])
    sum += new_cube[0]
    previous_cube = new_ccube
  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
import math
 
stri = input()
ary = stri.split()
n = int(ary[0])
k = int(ary[1])
 
ans1 = 1 * (n-k +1 )
ansi = ans1
print(ansi)
 
for i in range(2,k+1):
    ansi = ansi * (k- i + 1) / ( i - 1 ) *  (n-k - i + 2) / i 
    print(int(ansi % 1000000007))

### FIXED CODE ###

import math
 
stri = input()
ary = stri.split()
n = int(ary[0])
k = int(ary[1])
 
ans1 = 1 * (n-k +1 )
ansi = 0
ansi = int(ans1)
print(ansi)
for i in range(2,k+1):
    ansi = ansi * (k- i + 1) // int( i - 1 ) *  (n-k - i + 2) // int(i) 
    type(ansi)
    print(int(ansi % int(1000000007)))
def splitintinput():
    return map(int,input().split())

H,N = splitintinput()
dp = [[0] * (H+1) for i in range(N)]
A,B = splitintinput()
for j in range(1, H+1):
    dp[0][j] = B * int((j+A-1)/A)

for i in range(1,N):
    A,B = splitintinput()
    for j in range(1, A+1):
        dp[i][j] = min(dp[i-1][j], B)
    for j in range(A+1, H+1):
        dp[i][j] = min(dp[i-1][j], dp[i][j-A] + B)

print(dp[N-1][H])

### FIXED CODE ###

H,N =map(int,input().split()) 
dp = [[0] * (10001) for i in range(1001)]
A,B = map(int,input().split()) 
for j in range(1, H+1):
    dp[0][j] = B * int((j+A-1)/A)

for i in range(1,N):
    A,B = map(int,input().split())
    for j in range(1, A+1):
        dp[i][j] = min(dp[i-1][j], B)
    for j in range(A+1, H+1):
        dp[i][j] = min(dp[i-1][j], dp[i][j-A] + B)

print(dp[N-1][H])
n, k = map(int, input().split())
h = []
for i in range(n):
  h.append(int(input()))

h.sort()
  
ans = []
for i in range(n-k+1):
  ans.append(h[i+k]-h[i])
  
print(min(h))
  





### FIXED CODE ###

n, k = map(int, input().split())
h = []
for i in range(n):
  h.append(int(input()))

h.sort()
  
ans = []
for i in range(n-k+1):
  ans.append(h[i+k-1]-h[i])
  
print(min(ans))