Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def f_pond_skater():
    from fractions import Fraction
    from math import ceil
    from collections import deque
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    def is_inside(row, col):
        return (0 <= row < H) and (0 <= col < W)

    dp = [[[float('inf')] * 4 for j in range(W)] for i in range(H)]
    dr, dc = (0, -1, 0, 1), (-1, 0, 1, 0)  # '0123' と '左上右下' を対応
    queue = deque([(0, start_row, start_col, 0)])
    while queue:
        cost, row, col, direction = queue.pop()
        dp[row][col][direction] = cost

        # 1マス直進する
        nr, nc = row + dr[direction], col + dc[direction]
        if (is_inside(nr, nc) and Grid[nr][nc] == '.' and
                dp[nr][nc][direction] > cost + Fraction(1, K)):
            queue.appendleft((dp[row][col][direction] + Fraction(1, K), nr, nc, direction))

        # 向きを 90 度変える
        for i in (1, 3):
            if dp[row][col][(direction + i) % 4] > ceil(float(cost)):
                queue.appendleft((ceil(float(cost)), row, col, (direction + i) % 4))

    ans = min(dp[target_row][target_col][d] for d in range(4))
    return ceil(float(ans)) if ans != float('inf') else -1

print(f_pond_skater())

### FIXED CODE ###

def f_pond_skater():
    from heapq import heappush, heappop
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    heap = []
    dist = [[float('inf')] * W for _ in range(H)]
    dist[start_row][start_col] = 0

    diff = ((0, 1), (1, 0), (0, -1), (-1, 0))
    heappush(heap, (0, start_row, start_col))
    while heap:
        cost, row, col = heappop(heap)
        cost_next = cost + 1

        if row == target_row and col == target_col:
            return cost

        for dr, dc in diff:
            nr, nc = row, col
            for _ in range(K):
                nr += dr
                nc += dc
                if not (0 <= nr < H and 0 <= nc < W) or Grid[nr][nc] == '@':
                    break
                if dist[nr][nc] > cost_next:
                    dist[nr][nc] = cost_next
                    heappush(heap, (cost_next, nr, nc))
                elif dist[nr][nc] == cost_next:
                    continue
                else:
                    break
    return -1

print(f_pond_skater())
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
a = counter[1]
b = counter[2]
c = counter[3]
"""
dp[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[-1] * (310) for _ in range(310)] for _ in range(310)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    res = 0
    if i > 0:
        res += rec(i-1,j,k) * i
    if j > 0:
        res += rec(i+1,j-1,k) * j
    if k > 0:
        res += rec(i,j+1,k-1) * k
    res += N
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            rec(i, j, k)
print(dp[a][b][c])


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
a = A.count(1)
b = A.count(2)
c = A.count(3)
"""
dp[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

# 先にiについて更新することで、dp[i""+1""][j-1][k]を可能にしている。
# 先にjについて更新することで、dp[i][j""+1""][k-1]を可能にしている。
for k in range(c + 1):
    for j in range(b + c + 1 - k): # ２貫の皿の数の最大値 - 3枚の皿の数
        for i in range(a + b + c + 1 - k - j):
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = N * 1.0
            if i > 0:
                tmp += i * dp[i-1][j][k]
            if j > 0:
                tmp += j * dp[i+1][j-1][k]
            if k > 0:
                tmp += k * dp[i][j+1][k-1]
            dp[i][j][k] = tmp / (i + j + k)
print(dp[i][j][k])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    num=a[i]
    a[i]=0
    print(max(a))
    a[i] = num
    

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_1 = max(a)
a_2 = sorted(a)[-2]
for i in a:
    if i != a_1: print(a_1)
    else: print(a_2)
### BUGGY CODE ###

N=int(input())
ans=[0]*N
if N>=6:
    ans[5]=1
for i in range(1,N+1):
    for x in range(1,N+1):
        if x**2>i:
            break
        for y in range(1,N+1):
            if x**2+y**2>i:
                break
            for z in range(1,N+1):
                if x**2+y**2+z**2>i:
                    break
                if x**2+y**2+z**2+x*y+y*z+z*x==i and i!=6:
                    ans[i-1]=3
for i in ans:
    print(i)

### FIXED CODE ###

from itertools import permutations
N=int(input())
ans=[0]*(10**6)
for x in range(1,N+1):
    if x**2>N:
        break
    for y in range(1,N+1):
        if x**2+y**2>N:
            break
        for z in range(1,N+1):
            if x**2+y**2+z**2>N:
                break
            else:
                kari=[x,y,z]
                #print(kari)
                if x**2+y**2+z**2+x*y+y*z+z*x<=10**5:
                    ans[x**2+y**2+z**2+x*y+y*z+z*x-1]+=1
                    
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import sys
import os
from collections import deque


def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

N,M = LI()
AB = [LI() for _ in range(M)]

if M==0:
    print(1)
    exit()

# 無向グラフ
G = []
for _ in [0]*N:
    G.append([False]*N)

for r in AB:
    f = r[0]-1
    t = r[1]-1
    G[f][t] = True
    G[t][f] = True

used = [False] * N

ss = []
for i in range(N):
    if used[i]==True:
            continue
    s = set()
    que = deque([])
    que.append(i)
    while que:
        p = que.popleft() 
        if used[p]==True:
            continue
        used[p]=True   
        s.add(p)
        for i, x in enumerate(G[p]):
            if x == True:
                if used[i]==True:
                    continue
                que.append(i)
    ss.append(len(s))


    # for i, x in enumerate(G[i]):
    #     if x == True:
    #         if used[i]==True:
    #             continue
    #         for j,y in enumerate(x):
    #             if used[j]==True:
    #                 continue
    #             if x == True and used[i]==False:
    #                 s.add(i)


    # l = [i for i, x in enumerate(G[i]) if x == True and used[i]==False]
    # for j in l:
    #     used[j]=True
    #     s.add(j)
    #     for i,x in enumerate(G[i]):
    #         if x == True and used[i]==False:
    #             s.add(i)

print(max(ss))

### FIXED CODE ###

import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N,M = LI()
AB = [LI() for _ in range(M)]

ans = 0

par = [0]*N
# rank = [0]*N

def init(n):
    for i in range(n):
        # 親のID or 属する頂点の数
        par[i]=-1
        # rank[i] = 0

# rootを返す
def find(x):
    # 根
    if par[x] < 0:
        return x
    # 節の親
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    if (x==y):
        return
    if (par[x] > par[y]):
        x,y = y,x
    # rootの頂点数を結合
    par[x] += par[y]
    # yの親をxに
    par[y] = x
    return

    # if (rank[x]<rank[y]):
    #     par[x]=y
    # else:
    #     par[y]=x
    #     if rank[x] == rank[y]:
    #         rank[x] += 1

def same(x,y):
    return find(x)==find(y)

def size(x):
    return -par[find(x)]

init(N)

for r in AB:
    f = r[0]-1
    t = r[1]-1
    unite(f,t)
    # print(par)

for i in range(N):
    # print(size(i))
    ans = max(ans,size(i))

print(ans)
### BUGGY CODE ###

def input_int():
    return(int(input()))

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

def input_int_map():
    return(map(int,input().split()))

def run():
    num_count = input_int()
    nums = []
    for _ in range(num_count):
        nums.append(input_int())

    num_history = [1]

    current_num = 1
    while True:
        current_num = nums[current_num - 1]

        if current_num in num_history:
            print(-1)
            return

        if current_num == 2:
            print(len(num_history))
            return

        num_history.append(current_num)

run()


### FIXED CODE ###

def input_int():
    return(int(input()))

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

def input_int_map():
    return(map(int,input().split()))

def run():
    num_count = input_int()
    nums = []
    for _ in range(num_count):
        nums.append(input_int())

    num_count = 1

    current_num = 1
    while True:
        current_num = nums[current_num - 1]

        if num_count >= len(nums):
            print(-1)
            return

        if current_num == 2:
            print(num_count)
            return
        num_count += 1

run()
### BUGGY CODE ###

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

ls = list(map(int, input().split()))
ans = []

for i in range(2**N):
  num = 0
  s = 0
  for j in range(N):
    if ((i >> j) & 1):
      if num < K:
        s += ls[j]
        num += 1
  if num == K:
    ans.append(s)

print(min(ans))

### FIXED CODE ###

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

ls = list(map(int, input().split()))
ans = 0

ls2 = sorted(ls)

for i in range(K):
  ans += ls2[i]

print(ans)
### BUGGY CODE ###

from sys import stdin
import numpy as np


def main():
    x = int(input())
    a = 1
    while True:
        b = - pow(x - a ** 5, 1/5)
        if b == int(b):
            print(a, int(b))
            break

if __name__ == '__main__':
    main()


### FIXED CODE ###



def main():
    x = int(input())
    for a in range(-120, 120):
        for b in range(-120, 120):
            if a ** 5 - b ** 5 == x:
                print(a, b)
                break
        else:
            continue
        break


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# youtubeバージョン
import sys
from heapq import *
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    dis=[]
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        ds.append(d)
        dis.append([d, i])
    ds.sort()
    dis.sort()

    for x, s, t in xst:
        i=bisect_left(ds,s)
        nd=len(ds)
        while i<nd:
            if ds[i]<t:
                ai=dis[i][1]
                ans[ai]=x
                del ds[i]
                del dis[i]
                nd-=1
            else:
                break

    print("\n".join(map(str,ans)))


n, q = map(int, input().split())
f(n, q)


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

n = int(input())

s = input().split(" ")

ans = 0
for i in range(n):
  for j in range(int(i)+1,n):
    
    ans += int(s[i])*int(s[j])
    
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())

s = input().split(" ")

sumup = 0
for i in s:
  sumup += int(i) 

ans = 0
for i in s:
  r = int(i)
  
  sumup -= r
  
  ans += r*sumup
    
print(ans%(10**9+7))
### BUGGY CODE ###

def cmb(n, r, p):
	if (r < 0) or (n < r):
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % p


p = 10 ** 9 + 7
N = 10 ** 7  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
	fact.append((fact[-1] * i) % p)
	inv.append((-inv[p % i] * (p // i)) % p)
	factinv.append((factinv[-1] * inv[-1]) % p)


n,a,b=map(int,input().split())
ans=((2**n-1)%(10**9+7)-cmb(n,a,p)-cmb(n,b,p))
print(int(ans))


### FIXED CODE ###

mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)
### BUGGY CODE ###

def main():
    """"ここに今までのコード"""
    N, K = map(int, input().split())
    dice_list = list(map(int, input().split()))
    expected_values = [sum(range(1, i + 1)) / i for i in dice_list]
    acc = [0 for i in range(N+1)]
    for i in range(1, N+1):
        n = dice_list[i-1]
        acc[i] = acc[i-1] + sum(range(1, n + 1)) / n 
    
    max_sum = -1

    for i in range(N - K + 1):
        s = acc[i + K] - acc[i]
        if s > max_sum:
            max_sum = s
    
    print(max_sum)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
    N, K = map(int, input().split())
    dice_list = list(map(int, input().split()))
    max, s = 0, 0

    for i in range(K):
        s += (dice_list[i] + 1) / 2
    
    max = s

    for i in range(N-K):
        s -= (dice_list[i] + 1) / 2
        s += (dice_list[i+K] + 1) / 2
        if s > max:
            max = s
    
    print(max)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

L,R = map(int, input().split())
Smin=2019
for x in range(L,R):
    for y in range(x+1,R+1):
        S=x*y%2019
        if Smin>S:
            Smin=S
print(Smin)



### FIXED CODE ###

L,R = map(int, input().split())
Smin=2019
Lo=L%2019
Ro=R-(L-Lo)
if Ro>=2019:
    Smin=0
if Ro<2019:
    for x in range(Lo,Ro):
        for y in range(x+1,Ro+1):
            Sa=x*y
            S=Sa%2019
            if Smin>S:
                Smin=S
print(Smin)
### BUGGY CODE ###

N, M = map(int, input().split())  # 品物の数、割引券の枚数
A = list(map(int, input().split()))  # 品物の値段
for _ in range(M):
    A[A.index(max(A))] = max(A) // 2
print(str(sum(A)))

### FIXED CODE ###

N, M = map(int, input().split())  # 品物の数、割引券の枚数
A = list(map(int, input().split()))  # 品物の値段
A.sort(reverse=True)
i = 0
for _ in range(M):
    A[i] = A[i] // 2
    if i <= N - 2 and A[i] < A[i + 1] and A[0] < A[i+1]:
        i += 1
    else:
        A.sort(reverse=True)
        i = 0
print(str(sum(A)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import numpy as np
# from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
N = H*W
ind = [0]*N
d = {}

A = []
for _ in range(H):
    row = list(map(int,readline().split()))
    A += row
    
for i in range(1,N+1):
    ind = A.index(i)
    x = ind // W
    y = ind % W
    d[i] = (x+1,y+1)
# print(d)

data = [[] for i in range(D)]
ac_data = []
for i in range(1,D+1):
    n = 1
    while i + D*n <= N: 
        x,y = d[i+D*(n-1)]
        nx,ny = d[i+D*n]
        power = abs(x-nx) + abs(y-ny)
        data[i%D].append(power)
        n += 1
# print(data)      
for row in data:
    row = [0] +row
    # ac_row = list(accumulate(row))
    ac_row = np.cumsum(row)
    ac_data.append(ac_row)

# print(ac_data)
Q = int(readline())
for i in range(Q):
    L,R = map(int,readline().split())
    k = L % D
    l = L // D 
    m = (R-L) // D
    if k == 0:
        print(ac_data[k][l-1+m]-ac_data[k][l-1])
    else:
        print(ac_data[k][l+m]-ac_data[k][l])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
X = [(0,0) for _ in range(H*W)]
Y = [0 for _ in range(H*W)]

for i in range(H):
    A = [int(x)-1 for x in readline().split()]
    for j in range(W):
        X[A[j]] = (i,j)

for i in range(0,H*W-D):
    Y[i+D] = Y[i] + abs(X[i+D][0] - X[i][0]) + abs(X[i+D][1] - X[i][1])

Q = int(readline())
for _ in range(Q):
    L,R = map(int,readline().split())
    print(Y[R-1]-Y[L-1])
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
ans,point = 0,0
for i in range(1,N+1):
    amari = i/B-i//B
    point = math.floor(A*amari)
    ans = max(ans,point)
print(ans)

### FIXED CODE ###

import math
A,B,N = map(int,input().split())
looked = min(B-1,N)
ans = (A*looked)//B - A*(looked//B)
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
red_buf = {}
def combinations_count(n, r):
    global red_buf
    r = min(r, n - r)
    numer = 0
    denom = 0
    if (n, n-r, -1) in red_buf:
        numer = red_buf[(n, n-r, -1)]
    else:
        numer = reduce(mul, range(n, n - r, -1), 1)
        red_buf[n, n-r, -1] = numer
    if (1, r+1) in red_buf:
        denom = red_buf[(1, r+1)]
    else:
        denom = reduce(mul, range(1, r + 1), 1)
        red_buf[(1, r+1)] = denom
    return numer // denom

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

ans = 0
if k == 1:
    print(0)
else:
    for i in range(1, n+1):
        if i >= k:
            ans += a_list[i-1] * combinations_count(i-1, k-1)
        if n-i >= k-1:
            ans -= a_list[i-1] * combinations_count(n-i, k-1)
    ans %= 1000000007
    print(ans)


### FIXED CODE ###

MOD = 1000000007
# 二項係数
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD

com = COM(100000, MOD)
n, k = map(int, input().split())
a_list = sorted(list(map(int, input().split())))

ans = 0
if k == 1:
    print(0)
else:
    for i in range(1, n+1):
        if i >= k:
            ans += a_list[i-1] * com.calc_COM(i-1, k-1)
        if n-i >= k-1:
            ans -= a_list[i-1] * com.calc_COM(n-i, k-1)
    ans %= MOD
    print(ans)
### BUGGY CODE ###

cnt = int(input())
lst = [int(input()) for i in range(cnt)]

for i, j in enumerate(lst):
    lst.remove(j)
    print(max(lst))
    lst.insert(i, j)



### FIXED CODE ###

cnt = int(input())
lst = [int(input()) for i in range(cnt)]
lst2 = sorted(lst)
for i in lst:
  if i == lst2[-1]:
    print(lst2[-2])
  else:
    print(lst2[-1])
### BUGGY CODE ###

import copy
n,k,*A = map(int,open(0).read().split())

A_1 = copy.deepcopy(A)
A_2 = copy.deepcopy(A)
for _ in range(k):
    A_1_1 = copy.deepcopy(A)
    if _ == 0:A = [0] * n
    for i,d in enumerate(A_1):
        if d >= max(n-i,i):continue
        for j in range(i-d,i+d+1):
            if 0<=j<n:
                if _ != 0 and i-A_2[i]<=j<=i+A_2[i]:continue
                A[j] += 1
    A_2 = copy.deepcopy(A_1); A_1 = copy.deepcopy(A)
    up = True
    for i,c in enumerate(A):
        if c < max(n-i,i+1):
            up = False          
    if up:
        break
print(*A)


### FIXED CODE ###

import copy
n,k,*A = map(int,open(0).read().split())
for _ in range(min(50,k)):
    B = [0] * (n+1)
    for i,d in enumerate(A):
        start = max(0,i-d)
        B[start] += 1
        end = min(n,i+d+1)
        B[end] -= 1
    light = 0 
    for i,b in enumerate(B[:n]):
        light += b
        A[i] = light

print(*A)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z > s:break
      if x+y+z == s:ans+=1
        
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
  for y in range(k+1):
    z=s-x-y
    ans += 1 if z>=0 and z<=k else 0
print(ans)
### BUGGY CODE ###

from collections import deque

s = input()
q = int(input())

d = deque(list(s))
for _ in range(q):
    qi = input()
    if len(qi) == 1:
        # query 1
        d.reverse()
    else:
        # query 2
        _, f, c = qi.split()
        if f == '1':
            d.appendleft(c)
        else:
            d.append(c)

ans = ''.join(list(d))
print(ans)


### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
is_reverse = False

d = deque(list(s))
for _ in range(q):
    qi = input()
    if len(qi) == 1:
        # query 1
        is_reverse = not is_reverse
    else:
        # query 2
        _, f, c = qi.split()
        f1 = f == '1'
        if f1 == is_reverse:
            d.append(c)
        else:
            d.appendleft(c)

d = list(d)
if is_reverse:
    d = d[::-1]
ans = ''.join(d)
print(ans)
### BUGGY CODE ###

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()
ans = 1
a_array = na()
for a in a_array:
    ans = ans * a
    if ans == 0:
        break
    if ans > 10 ** 18:
        ans = -1

print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()
ans = 1
a_array = na()
overflow = 0
for a in a_array:
    if a == 0:
        ans = 0
        break
    if not overflow:
        ans = ans * a
        if ans > 10 ** 18:
            overflow = 1
            ans = -1

print(ans)
### BUGGY CODE ###

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

n=[0]*(N+2) #i回目ワープ後にいる場所
n[0]=1
 
for i in range(1,N+1):
  if A[n[i-1]-1] in n:
    a=n.index(A[n[i-1]-1]) #ループの開始点
    le=i-a #ループする長さ
    n[i]=A[n[i-1]-1]
    break
  n[i]=A[n[i-1]-1] #i回目ワープ後にいる場所

 

if a>=K:
  print(n[K])
elif a<K:
  k_remain=(K-a)%le
 
  print(n[a:i][k_remain])

### FIXED CODE ###

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

n=[-1]*(N+2)
n[1]=0
i=0 #カウンター
place_now=1 #いる場所

while True:
  
  i+=1 #何回飛んだか
  place_now=A[place_now-1] #飛んだ時の場所
  
  
  if n[place_now] != -1:
    a=n[place_now] #ループの開始点
    loop=i-a #ループする長さ
    break
  
  n[place_now]=i #その場所につくのに何回飛んだか
  
if a>=K:
  print(n.index(K))
elif a<K:
  k_remain=(K-a)%loop+a
  print(n.index(k_remain))
### BUGGY CODE ###

x, y = map(int, input().split())
n = min(x, y)

for i in range(1, n+1):
    if x%i==0 and y%i==0:
        gcd = i

print(gcd)

### FIXED CODE ###

x, y = map(int, input().split())
a = max(x, y)
b = min(x, y)

while a%b != 0:
    temp = a
    a = b
    b = temp%b

print(b)