Harryxun/stf_run huggingface dataset:
H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = []
done = {}
for i in range(Q):
    L, R = tests[i]
    if (L, R) in done:
        scores.append(done[(L, R)])
    elif L == R:
        scores.append(0)
    else:
        x, y = stage[L]
        score = 0
        nowL = L.copy()
        while nowL < R:
            if (nowL, R) in done:
                score += done[(nowL, R)]
                break
            new_x, new_y = stage[nowL + D]
            score += abs(new_x - x) + abs(new_y - y)
            x = new_x
            y = new_y
            nowL += D
        scores.append(score)
        done[(L, R)] = score

for score in scores:
    print(score)



### FIXED CODE ###

import numpy as np

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = np.zeros([H * W + 1]).astype(np.int)
for i in range(H * W, 0, -1):
    if i + D > H * W:
        scores[i] = 0
    else:
        x, y = stage[i]
        ox, oy = stage[i + D]
        scores[i] = scores[i + D] + abs(x - ox) + abs(y - oy)

for i in range(Q):
    L, R = tests[i]
    print(scores[L] - scores[R])
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

inf = float('inf')
match = (inf, 2, 5, 5, 4, 5, 6, 3, 7, 6)
matnum = set([match[a] for a in A])
dp = [0]+[-inf]*N

for i in range(1, N+1):
    dp[i] = max([10*dp[i-match[a]] + a for a in A])

print(''.join(sorted(str(dp[-1]), reverse = True)))


### FIXED CODE ###

def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

inf = float('inf')
match = (inf, 2, 5, 5, 4, 5, 6, 3, 7, 6)
matnum = set([match[a] for a in A])
dp = [0]+[-inf]*N

for i in range(1, N+1):
    dp[i] = max([10*dp[max(-1,i-match[a])] + a for a in A])

print(''.join(sorted(str(dp[-1]), reverse = True)))
N = int(input())
a = list(map(int, input().split()))
c2=c4=0

for i in range(len(N)):
  if a[i]%4==0:
    c4+=1
  if a[i]%2==0:
    c2+=1

nodd=N-c2
c4=c4-c2

if nodd<c4:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
c2=c4=0

for i in range(N):
  if a[i]%4==0:
    c4+=1
  if a[i]%2==0:
    c2+=1

nodd=N-c2
c2=c2-c4
if c2>0:
  nodd+=1
if c4>=nodd-1:
  print("Yes")
else:
  print("No")
def check_other(tmp_i, cur_p, cur_q, cur_x, cur_y, tmp_count):
    for i in range(len(p)):
        if i in tmp_i:
            continue

        tmp_p = p[i][0] - cur_x
        tmp_q = p[i][1] - cur_y

        if tmp_p == cur_p and tmp_q == cur_q:
            tmp_i.append(i)

            tmp_count += 1
            tmp_count = check_other(tmp_i, cur_p, cur_q, p[i][0], p[i][1], tmp_count)


    return tmp_count





if __name__ == "__main__":
    #入力取得
    N = int(input())

    p = []


    for i in range(N):
        l = list(map(int, input().split()))
        p.append(l)

    min_cost = N

    results = []

    counts = []


    for i in range(len(p)):
        tmp_i = [i]
        tmp_count = 0
        if i == 0:
            continue

        tmp_p = p[i][0] - p[0][0]
        tmp_q = p[i][1] - p[0][1]



        tmp_count = check_other(tmp_i, tmp_p, tmp_q, p[i][0], p[i][1], tmp_count)


        counts.append(tmp_count)




tmp_max = max(counts)

if N == 2:
    result = 1
elif tmp_max == 0:
    result = N - 2
else:
    result = N - tmp_max - 1
#
print(result)


### FIXED CODE ###

n = int(input())
a = [tuple(map(int,input().split())) for i in range(n)]

m = dict()


ans = 0


for i in range(n):
    for j in range(n):
        if i !=j:
            x = a[i][0] - a[j][0]
            y = a[i][1] - a[j][1]

            p = (x,y)

            if p not in m:
                m[p] = 0

            m[p] += 1

            ans = max(m[p], ans)



print(n-ans)
MAX_N = 10**5+1
DP = [None] * (MAX_N + 1)  # 計算結果を保存する配列
DP[0] = 0  # 定義より
DP[1] = 1  # 定義より

def fib(n):
    # フィボナッチ数を2からnまで順に求めていく
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    return DP[n]

MOD = 10**9 + 7

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

ans = fib(a[0])
for i in range(M-1):
    ans *= fib(a[i+1] - a[i] - 1)
    ans %= MOD
ans *= fib(N - a[M-1])
ans %= MOD

print(ans)


### FIXED CODE ###

from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		z[i][j] += X[i][k] * Y[k][j]
	return z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0
tmp = []

for i in range(len(a)):
	if a[i] - a[i - 1] == 1:
		print(0)
		exit()

for k in a:
	tmp.append(fib(k - start) % INF)
	start = k + 1

for j in tmp:
	ans *= j
	ans %= INF

ans *= fib(N - start + 1)
print(ans % INF)
print(int(input()**2>>2)

### FIXED CODE ###

n=int(input())
if n % 2 == 0:
  temp = int(n/2)
  print(temp ** 2)
else:
  temp = n//2
  print(temp*(temp+1))
s = input()
ans =[]
for i in range(len(s)):
    if s[i] == '0':
        ans.append('0')
    elif s[i] == '1':
        ans.append('1')
    elif s[i] == 'B':
        ans.pop(-1)
print(''.join(ans))

### FIXED CODE ###

s = input()
ans =[]
for i in range(len(s)):
    if s[i] == '0':
        ans.append('0')
    elif s[i] == '1':
        ans.append('1')
    elif len(ans) != 0:
        ans.pop(-1)
print(''.join(ans))
def main():
    input()
    l = list(input().split())
    ans = []
    for i in range(len(l)):
        ans.append(l[0][i])
        ans.append(l[1][i])
    print(''.join(ans))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    input()
    l = list(input().split())
    ans = []
    for i in range(len(l[0])):
        ans.append(l[0][i])
        ans.append(l[1][i])
    print(''.join(ans))

if __name__ == '__main__':
    main()
N = input()
s1 = N[1:len(N)]
s2 = N[0:len(N) - 1]
isOk = True
for i in range(1, len(N)):
    if s1[i] != s1[i - 1]:
        break
        isOk = False
    else:
        continue

if isOk:
    print('Yes')

isOk = True
for i in range(1, len(N)):
    if s2[i] != s2[i - 1]:
        break
    else:
        continue

if isOk:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = input()
s1 = N[1:len(N)]
s2 = N[0:len(N) - 1]
isOk = True
for i in range(1, len(N)-1):
    if s1[i] != s1[i - 1]:
        isOk = False
        break
    else:
        continue

if isOk:
    print('Yes')
    exit(0)

isOk = True
for i in range(1, len(N)-1):
    if s2[i] != s2[i - 1]:
        isOk = False
        break
    else:
        continue

if isOk:
    print('Yes')
else:
    print('No')
n, k = map(int, input().split())
alst = list(map(int, input().split()))

if k == 0:
    print(max(alst))
    exit()

l = 0
r = max(alst)

while r != l:
    pos = (r + l) // 2
    cnt = 0
    for a in alst:
        cnt += (a - 1) // pos
    if cnt <= k:
        r = pos
    else:
        l = pos + 1
print(r)

### FIXED CODE ###

n, k = map(int, input().split())
alst = list(map(int, input().split()))

if k == 0:
    print(max(alst))
    exit()

l = 1
r = max(alst)

while r != l:
    pos = (r + l) // 2
    cnt = 0
    for a in alst:
        cnt += (a - 1) // pos
    if cnt <= k:
        r = pos
    else:
        l = pos + 1
print(r)
s = input()
ans = ""
for i in s
  if i == "B":
    if len(ans) > 0:
      ans = ans[:-1]
    else:
      ans = ans
  else:
    ans = ans + i
print(ans)

### FIXED CODE ###

s = input()
ans = ""
for i in s:
  if i == "B":
    if len(ans) > 0:
      ans = ans[:-1]
  else:
    ans = ans + i
print(ans)
a, b, c = map(int, input().split())
print('Yes' if a<=c<=b else 'No')

### FIXED CODE ###

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

print('YES' if a[-1]==b[0] and b[-1]==c[0] else 'NO')
import sys
k = int(input())

remainders = set()
remainder = 7 % k
remainders.add(remainder)

counter = 1
while True:
    counter += 1
    remainder = remainder * 10 % k
    if remainder in remainders:
        print('-1')
        sys.exit()
    remainders.add(remainder)
    print(remainders)
    if sum(remainders) % k == 0:
        print(counter)
        sys.exit()

### FIXED CODE ###

import sys

k = int(input())
n = 7
counter = 1
remainders = set()

while True:
    remainder = n % k
    if remainder == 0:
        print(counter)
        sys.exit()
    if remainder in remainders:
        print(-1)
        sys.exit()
    remainders.add(remainder)
    
    n = remainder * 10 + 7
    counter += 1
def f(N):
    res = 0
    while N//10 >= 1:
        res += N % 10
        N = N // 10
    return res


if __name__ == '__main__':
    N = int(input())

    if N % f(N) == 0:
        print('Yes')
    else:
        print('No')



### FIXED CODE ###

if __name__ == '__main__':
    N = input()

    fn = 0
    for i in range(len(N)):
        fn += int(N[i])

    if int(N) % fn == 0:
        print('Yes')
    else:
        print('No')
#l = map(str, raw_input().split())

A=l[0]
B=l[1]

if A=='H' and B=='H':
    print('H')

elif A=='H'and B=='D':
    print('D')

elif A=='D' and B=='H':
    print('D')
else:
    print('H')



### FIXED CODE ###

l = input().split()
A=l[0]
B=l[1]

if A=='H' and B=='H':
    print('H')

elif A=='H'and B=='D':
    print('D')

elif A=='D' and B=='H':
    print('D')
else:
    print('H')
I = input()
I = I.split(" ")
N = I[0]
K = I[1]
Q = I[2]

A = [0]*Q

for i in range(Q):
	A[i] = int(input())

point = [0]*N

for i in range(Q):
	point[A[i]-1] = point[A[i]-1] + 1

for i in range(Q):
	if point[i] > 0:
		print("yes")
	else:
		print("no")

### FIXED CODE ###

str = input()

if str == "Sunny":
	print("Cloudy")
elif str == "Rainy":
	print("Sunny")
else:
	print("Rainy")
K = int(input())
if(K%2==0):
    print(-1)
    exit()
check=list(str(K))
if(check[-1]=='5'):
    print(-1)
    exit()
else:
    seven=7
    if(int(''.join(['7']*(K-1)))%K==0):
        print(K-1)
        exit()
    while True:
        if(seven%K==0):
            print(len(str(seven)))
            break
        else:
            seven=seven*10+7



### FIXED CODE ###

k = int(input())
if(k%2==0 or k%5==0):
    print(-1)
    exit()
else:
    i=1
    seven=7%k
    while seven!=0:
        seven = (seven*10+7)%k
        i+=1
    print(i)
from collections import deque


def Fibonacci(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==1: 
        return 1
    # Second Fibonacci number is 1 
    elif n==2: 
        return 2
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2) 
        

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

A = deque()

for _ in range(M):
    A.append(int(input()))

pos = 0
diff = []
la = None

for a in A:
    if la and a - la == 1:
        print(0)
        exit()
    d = (a) - pos
    diff.append(d)
    pos = a
    la = a

# 最後の階段
diff.append(N - pos)
diff = list(filter(lambda x: False if x <= 0 else True, diff))
F = [Fibonacci(d) for d in diff]

_sum = 1
for f in F:
    _sum *= f

print(_sum // 1000000007)

### FIXED CODE ###

n, m = map(int, input().split())

broken = [0 for _ in range(n+1)]
for i in range(m):
    a = int(input())
    broken[a] = True

    
mod = 1000000007
dp = [0 for _ in range(n+2)]

dp[n] = 1
for i in range(n-1, -1, -1):
    if(broken[i]):
        dp[i] = 0
        continue

    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])
n,p=map(int,input().split())

d={}
x=p
for i in range(2,p):
  while x%i==0:
    if i in d:
      d[i]+=1
    else:
      d[i]=1
    x//=i
  if i*i>=p:
    break

ans=1
for k,v in d:
  for i in range(v//n):
    ans*=k

print(ans)

### FIXED CODE ###

n,p=map(int,input().split())

d={}
x=p
for i in range(2,p):
  while x%i==0:
    if i in d:
      d[i]+=1
    else:
      d[i]=1
    x//=i
  if i*i>=p:
    break
if x>1:
  d[x]=1

ans=1
for k,v in d.items():
  for i in range(v//n):
    ans*=k

print(ans)
a, b = map(int, input().split())
p = a + b
m = max(a - b)
d = a * b
print(max(p, m, d))

### FIXED CODE ###

a, b = map(int, input().split())
p = a + b
m = a - b
d = a * b
print(max(p, m, d))
K,X=list(map(int,input().split()))
min = max(X - (K -1),−1000000)
max = min (X + (K-1),1000000)
for i in range(min,max+1):
    ans.append(i)
print(' '.join(ans))

### FIXED CODE ###

K,X=list(map(int,input().split()))
Min = max(X - (K -1),-1000000)
Max = min(X + (K-1),1000000)
ans = []
for i in range(Min,Max+1):
    ans.append(i)
ans = map(str,ans)
ans = ' '.join(ans)
print(ans)
import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array(([list(map(int,list(input()))) for _ in range(H)])).T

if sum(sum(s) for s in S)<=K:
    print(0)
else:
    answer = (H-1) * (W-1)
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.array([0]*len(M))
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [sum(s[i] for i in m) for m in M]
                if any(d > K for d in D):
                    ans = answer + 1
                    break

        answer = min(answer,ans)

    print(answer

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
x = input()

if x == 3 or x == 5 or x == 7:
  print("YES")
else:
  print("NO)

### FIXED CODE ###

x = int(input())

if x == 3 or x == 5 or x == 7:
  print("YES")
else:
  print("NO")
from collections import Counter, deque

(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

freqA = Counter(A)
freqB = Counter(B)
for k in freqA.keys() & freqB.keys():
    if freqA[k] + freqB[k] > N:
        print("No")
        exit()

rotate = 0
for i in range(N):
    while A[(i + rotate) % N] == B[i]:
        rotate += 1
for i in range(N):
    while A[(i + rotate) % N] == B[i]:
        rotate += 1
for i in range(N):
    while A[(i + rotate) % N] == B[i]:
        rotate += 1
B = deque(B)
B.rotate(rotate)

for a, b in zip(A, B):
    if a == b:
        assert False
print("Yes")
print(" ".join(map(str, B)))



### FIXED CODE ###

from collections import Counter, deque

(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

freqA = Counter(A)
freqB = Counter(B)
for k in freqA.keys() & freqB.keys():
    if freqA[k] + freqB[k] > N:
        print("No")
        exit()

B = deque(B)
while True:
    rotate = 0
    for i in range(N):
        while A[(i + rotate) % N] == B[i]:
            rotate += 1
    bad = False
    B.rotate(rotate)
    for a, b in zip(A, B):
        if a == b:
            bad = True
    if not bad:
        break

print("Yes")
print(" ".join(map(str, B)))
h,w = map(int, input().split())
sl = []
for _ in range(h):
    row = list(input())
    sl.append(row)


dp = [ [10000]*w for _ in range(h) ]
dp[0][0] = 0

for h_i in range(h):
    for w_i in range(w):
        if h_i+1 < w:
            if sl[h_i][w_i] == '.' and sl[h_i+1][w_i] == '#':
                dp[h_i+1][w_i] = min( dp[h_i+1][w_i], dp[h_i][w_i]+1 )
            else:
                dp[h_i+1][w_i] = min( dp[h_i+1][w_i], dp[h_i][w_i] )

        if w_i+1 < h:
            if sl[h_i][w_i] == '.' and sl[h_i][w_i+1] == '#':
                dp[h_i][w_i+1] = min( dp[h_i][w_i+1], dp[h_i][w_i]+1 )
            else:
                dp[h_i][w_i+1] = min( dp[h_i][w_i+1], dp[h_i][w_i] )


ans = dp[h-1][w-1]
if sl[0][0] == '#': ans += 1
print(ans)


### FIXED CODE ###

h,w = map(int, input().split())
sl = []
for _ in range(h):
    row = list(input())
    sl.append(row)


dp = [ [10000]*w for _ in range(h) ]
dp[0][0] = 0

for h_i in range(h):
    for w_i in range(w):
        if h_i+1 < h:
            if sl[h_i][w_i] == '.' and sl[h_i+1][w_i] == '#':
                dp[h_i+1][w_i] = min( dp[h_i+1][w_i], dp[h_i][w_i]+1 )
            else:
                dp[h_i+1][w_i] = min( dp[h_i+1][w_i], dp[h_i][w_i] )

        if w_i+1 < w:
            if sl[h_i][w_i] == '.' and sl[h_i][w_i+1] == '#':
                dp[h_i][w_i+1] = min( dp[h_i][w_i+1], dp[h_i][w_i]+1 )
            else:
                dp[h_i][w_i+1] = min( dp[h_i][w_i+1], dp[h_i][w_i] )


ans = dp[h-1][w-1]
if sl[0][0] == '#': ans += 1
print(ans)
import math

N = int(input())
a = list(map(int, input().split()))
ans = 0
num = 0
for i in range(1, len(a)):
	num *= a[i-1] * a[i] // math.gcd(a[i-1],a[i])
num -= 1
for i in range(len(a)):
	ans += num % a[i]
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0
for x in a:
	ans += x - 1
print(ans)
s=str(input())
s=list(s)
q=int(input())
sb=[0]*q
sa=[0]*q
sbi=0
sai=0
ta=0
for i in range(q):
  temp=str(input())
  temp=list(temp)
  if temp[0]=="1":
    ta=ta+1
  else:
    if (temp[2]=="1" and ta%2==0) or (temp[2]=="2" and ta%2!=0):
      sb[sbi]=temp[4]
      sbi=sbi+1
    else:
      sa[sai]=temp[4]
      sai=sai+1
lsb=sb.index(0)
lsa=sa.index(0)
sa.reverse()
ans=sb[0:lsb]+s+sa[len(sa)-lsa:len(sa)]
if ta%2!=0:
  ans.reverse()
print("".join(ans))

### FIXED CODE ###

s=str(input())
s=list(s)
q=int(input())
sb=[0]*(q+1)
sa=[0]*(q+1)
sbi=0
sai=0
ta=0
for i in range(q):
  temp=str(input())
  temp=list(temp)
  if temp[0]=="1":
    ta=ta+1
  else:
    if (temp[2]=="1" and ta%2==0) or (temp[2]=="2" and ta%2!=0):
      sb[sbi]=temp[4]
      sbi=sbi+1
    else:
      sa[sai]=temp[4]
      sai=sai+1
lsb=sb.index(0)
lsa=sa.index(0)
sb.reverse()
ans=sb[len(sb)-lsb:len(sb)]+s+sa[0:lsa]
if ta%2!=0:
  ans.reverse()
print("".join(ans))
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(input())
K = int(input())
leng = len(S)
if len(set(S))==1:
    print(S*K//2)
    exit()
if S[0]!=S[-1] or K==1:
    last = S[0]
    cnt = 0
    for s in S[1:]:
        if s==last:
            cnt += 1
            last = '.'
        else:
            last = s
    print(cnt*K)
else:
    S += ['.']
    cnt = 1
    lis = []
    last = S[0]
    for s in S[1:]:
        if s==last:
            cnt += 1
        else:
            lis.append(cnt)
            last = s
            cnt = 1
    first = lis.pop(0)
    end = lis.pop()
    others = sum([i//2 for i in lis])
    ans = first//2 + others*K + (first+end)//2*(K-1)+end//2
    print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(input())
K = int(input())
leng = len(S)
if len(set(S))==1:
    print(K*leng//2)
    exit()
if S[0]!=S[-1] or K==1:
    last = S[0]
    cnt = 0
    for s in S[1:]:
        if s==last:
            cnt += 1
            last = '.'
        else:
            last = s
    print(cnt*K)
else:
    S += ['.']
    cnt = 1
    lis = []
    last = S[0]
    for s in S[1:]:
        if s==last:
            cnt += 1
        else:
            lis.append(cnt)
            last = s
            cnt = 1
    first = lis.pop(0)
    end = lis.pop()
    others = sum([i//2 for i in lis])
    ans = first//2 + others*K + (first+end)//2*(K-1)+end//2
    print(ans)
s = str(input())
n = len(s)
cnt = 0
if n%2==0:
  for i in range((n-3)/2):
    if s[i]!=s[n-i-1]:
      cnt += 1
else:
  for i in range(n/2-1):
    if s[i]!=s[n-i-1]:
      cnt += 1
print(cnt)

### FIXED CODE ###

s = str(input())
n = len(s)
cnt = 0
if n%2==0:
  for i in range(int(n/2)):
    if s[i]!=s[n-i-1]:
      cnt += 1
else:
  for i in range(int((n-1)/2)):
    if s[i]!=s[n-i-1]:
      cnt += 1
print(cnt)
b=input()
if b=='A':
    print('T')
elif b=='T':
    prtnt('A')
elif b=='C':
    print('G')
else:
    print('C')
    

### FIXED CODE ###

b=input()
if b=='A':
    print('T')
elif b=='T':
    print('A')
elif b=='C':
    print('G')
else:
    print('C')
A,B,C,K = map(int,input().split())
a,b,c = 0
for i in range(K):
  a = B + C
  b = A + C
  c = A + B
  A = a
  B = b
  C = c
if (abs(A - B) < 10**18):
  print("Unfair")
else:
  print(str(A - B))

### FIXED CODE ###

A,B,C,K = map(int,input().split())
if(K == 0):
  ans = A - B
elif(K % 2 == 1):
  ans = B - A
else:
  ans = A - B
if(ans > 10 ** 18):
  print("Unfair")
else:
  print(str(ans))
# coding: utf-8
# Your code here!
n=int(input())
a=[int(x) for x in input().split()]
from collections import defaultdict
import math
d=defaultdict(int)
num_n=[]
num_n_1=[]
for ai in a:
    for i in range(1,int(math.sqrt(ai))+1):
        if ai%i==0:
            d[i]+=1
            d[ai//i]+=1
for key in d.keys():
    if d[key]==n:
        num_n.append(key)
    elif d[key]==n-1:
        num_n_1.append(key)
anses=[]
if num_n_1:
    anses.append(max(num_n_1))
if num_n:
    anses.append(max(num_n))
print(max(anses))

### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
anses=set()
for i in [0,1]:
    for j in range(1, int(a[i]**0.5)+1):
        if a[i] % j == 0:
            anses.add(j)
            if j != a[i] // j:
                anses.add(a[i] // j)
anses=sorted(anses,reverse=True)
for ans in anses:
    solvenum=0
    for j in a:
        if j%ans==0:
            solvenum+=1
    if solvenum==n or solvenum==n-1:
        print(ans)
        break
S = input()
T = input()
m, n = len(S), len(T)
DP = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(1, m+1):
    for j in range(1, n+1):
        if S[i-1] == T[j-1]:
            DP[i][j] = DP[i-1][j-1] + 1
        else:
            DP[i][j] = max(DP[i][j-1], DP[i-1][j])
X = ''
i, j = m, n
while len(X) < DP[m][n]:
    if DP[i][j] == DP[i-1][j-1]+1:
        i -= 1
        j -= 1
        l += 1
        X = S[i-1]+X
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    elif DP[i][j] == DP[i][j-1]:
        j -= 1
print(X)


### FIXED CODE ###

S = input()
T = input()
m, n = len(S), len(T)
C = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if S[i] == T[j]:
            C[i+1][j+1] = C[i][j] + 1
        else:
            C[i+1][j+1] = max(C[i][j+1], C[i+1][j])
l = C[m][n]
X = ''
while l:
    if S[m-1] == T[n-1]:
        X = S[m-1]+X
        m -= 1
        n -= 1
        l -= 1
    elif C[m][n] == C[m-1][n]:
        m -= 1
    else:
        n -= 1
print(X)