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

import heapq

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

que=[(-B[i],i) for i in range(N)]
heapq.heapify(que)
count=0
while True:
    val,index=heapq.heappop(que)
    if val>0:
        break
    if index!=N-1:
        a,b,c=B[index-1],B[index],B[index+1]
        if a==A[index-1] and c==A[index+1]:
            if B[index]%(a+c)==A[index]%(a+c):
                count+=(B[index]-A[index])//(a+c)
                B[index]=A[index]
                heapq.heappush(que,(B[index],index))
            else:
                count=-1
                break
        else:
            if B[index]>a+c:
                count+=B[index]//(a+c)
                B[index]%=a+c
                heapq.heappush(que,(-B[index],index))
            else:
                heapq.heappush(que,(B[index],index))
    else:
        a,b,c=B[index-1],B[index],B[0]
        if a==A[index-1] and c==A[0]:
            if B[index]%(a+c)==A[index]%(a+c):
                count+=(B[index]-A[index])//(a+c)
                B[index]=A[index]
                heapq.heappush(que,(B[index],index))
            else:
                count=-1
                break
        else:
            if B[index]>a+c:
                count+=B[index]//(a+c)
                B[index]%=a+c
                heapq.heappush(que,(-B[index],index))
            else:
                heapq.heappush(que,(B[index],index))

if A==B:
    print(count)
else:
    print(-1)


### FIXED CODE ###

import heapq

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

que=[(-B[i],i) for i in range(N)]
heapq.heapify(que)
count=0
while que:
    val,index=heapq.heappop(que)
    if val>0:
        break
    if index!=N-1:
        a,b,c=B[index-1],B[index],B[index+1]
        if a==A[index-1] and c==A[index+1]:
            if B[index]%(a+c)==A[index]%(a+c):
                count+=(B[index]-A[index])//(a+c)
                B[index]=A[index]
            else:
                count=-1
                break
        else:
            if B[index]>a+c:
                count+=B[index]//(a+c)
                B[index]%=a+c
                heapq.heappush(que,(-B[index],index))
    else:
        a,b,c=B[index-1],B[index],B[0]
        if a==A[index-1] and c==A[0]:
            if B[index]%(a+c)==A[index]%(a+c):
                count+=(B[index]-A[index])//(a+c)
                B[index]=A[index]
            else:
                count=-1
                break
        else:
            if B[index]>a+c:
                count+=B[index]//(a+c)
                B[index]%=a+c
                heapq.heappush(que,(-B[index],index))

if A==B:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = [0 for i in range(n)]
ans = 0
cnt = 0
for i in range(n):
  l[i] = p[i]*(p[i]+1)/(2*p[i])
if n == k:
  for i in range(k):
    ans += l[i]
else:
  for i in range(n-k+1):
    cnt = sum(l[i:i+k])
    if cnt > ans:
      ans = cnt
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = [0 for i in range(n)]
ans = 0
cnt = 0
for i in range(n):
  l[i] = p[i]*(p[i]+1)/(2*p[i])
if n == k:
  ans = sum(l)
else:
  ans = sum(l[:k])
  cnt = ans
  for i in range(n-k):
    cnt = cnt - l[i] + l[i+k]
    if cnt > ans:
      ans = cnt
print(ans)
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline

priority_que = []
N, K = map(int, input().split())
A = sorted(map(int, input().strip().split()))
F = sorted(map(int, input().strip().split()))[::-1]
if sum(A) <= K:
    print(0)
    exit()
hpop = heapq.heappushpop
hpush = heapq.heappush


for i, a in enumerate(A):
    f = F[i]
    key = f*a
    while key >= 0:
        # print(key)
        if len(priority_que) > K:
            if key <= priority_que[0]:
                break
            hpop(priority_que, key)
        else:
            hpush(priority_que, key)
        key -= f

# print(priority_que)
print(heapq.heappop(priority_que))


### FIXED CODE ###

import sys
import heapq


def can_eat_with_score(key):
    now_K = K
    for i, now_score in enumerate(score):
        if key < now_score:
            now_K -= (now_score-key+F[i]-1) // F[i]
            if now_K < 0:
                return False
    return True


input = sys.stdin.readline

priority_que = []
N, K = map(int, input().split())
A = sorted(map(int, input().strip().split()))
F = sorted(map(int, input().strip().split()))[::-1]
score = [A[i]*F[i] for i in range(N)]
if sum(A) <= K:
    print("0")
    exit()


left = -1
right = max(score)
while right - left > 1:
    mid = (left+right) // 2
    can_eat = can_eat_with_score(mid)
    # print(mid, can_eat)
    if can_eat:
        right = mid
    else:
        left = mid
print(left+1)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 3*10^5

for i in range(N):
    n = 0

    n += S[:i].count("W")
    n += S[i+1:].count("E")

    if ans > n:
        ans = n

print(ans)


### FIXED CODE ###

N = int(input())
S = input()

n = p = S[1:].count("E")

for i in range(0,N-1):
    if S[i+1] == "E":
        p -= 1
    if S[i] == "W":
        p += 1
    n = min(p, n)

print(n)
### BUGGY CODE ###

n = int(input())
left = 0
right = n - 1
print(left)
s_l = input()
s_r = 'Male' if s_l == 'Female' else 'Male'
p = 0
while True:
    p = (left + right) // 2
    print(p)
    status = input()
    if status == 'Vacant':
        exit()
    if p % 2 == 0:
        if status == first:
            left = p + 1
        else:
            right = p
    else:
        if status == second:
            left = p + 1
        else:
            right = p

### FIXED CODE ###

n = int(input())
left = 0
right = n - 1
print(left)
first = input()
second = 'Male' if first == 'Female' else 'Female'
p = 0
while True:
    p = (left + right) // 2
    print(p)
    status = input()
    if status == 'Vacant':
        break
    if p % 2 == 0:
        if status == first:
            left = p + 1
        else:
            right = p
    else:
        if status == second:
            left = p + 1
        else:
            right = p
### BUGGY CODE ###

n,k,q = [int(x) for x in input().split()]
li = []
for i in range(q):
    a = int(input())
    li.append(a)
score = [k]*n
for pe in li:
    for k in range(len(score)):
        score[k] = score[k] - 1
    score[pe-1] = score[pe-1]+1
result = []
for i in range(len(score)):
    if score[i]>0:
        print('Yes')
    else:
        print('No')
        


### FIXED CODE ###

n,k,q = [int(x) for x in input().split()]
li = []
for i in range(q):
    a = int(input())
    li.append(a)
score = [k] * (n + 1)
temp =[0]*(n+2)
for pe in li:
    temp[1] += (-1)
    temp[pe] -= (-1)
    temp[pe + 1] += (-1)
    temp[n + 1] -= (-1)

for i in range(1,n + 2):
    temp[i] += temp[i - 1]
#print(temp)
for i in range(1,n + 1):
    score[i] += temp[i]
    if(score[i] <= 0):
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n = int(input())
total = 0
for i in range(n-1):
    total += i+1
print(total)

### FIXED CODE ###

n = int(input())
total = 0
print(n*(n-1)//2)
### BUGGY CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, X, M = list(map(int, _in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    A = X
    for i in range(N):
        ans += A
        A = pow(A, 2, M)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, X, M = list(map(int, _in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    A = X
    head_list = []
    head = set()
    repeat = set()
    for i in range(N):
        if A in head:
            ind = head_list.index(A)
            repeat = head_list[ind:]
            head = head_list[:ind]
            break
        else:
            head.add(A)
            head_list.append(A)
            A = pow(A, 2, M)

    if len(repeat) == 0:
        ans = sum(head)
    else:
        repeat_time = (N - len(head)) // len(repeat)
        tail_len = N - len(head) - repeat_time * len(repeat)
        ans = sum(head) + sum(repeat) * repeat_time + sum(repeat[:tail_len])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


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

n=int(input())
a=list(map(int,input().split()))
ans=[i for i in range(n)]
for i in range(n):
    ans[i]=a.index(i+1)+1
print(*ans)

### FIXED CODE ###

n=int(input())
num=[i+1 for i in range(n)]
L=list(map(int,input().split()))
ans=[0 for _ in range(n)]
for j in range(n):
    ans[L[j]-1]=num[j]
print(*ans)
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
MOD = 998244353


lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr += (list(range(l, r + 1)))

lr.sort()


@lru_cache(maxsize=None)
def rec(n):
    if n == 1:
        return 1
    else:
        ans = 0
        for k in lr:
            if n - k >= 1:
                ans += rec(n - k)
                ans %= MOD
    return ans


print(rec(n))

### FIXED CODE ###

def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


n, k = map(int, input().split())
MOD = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)
### BUGGY CODE ###

n = int(input())

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

sigma = 0
for i in range(len(a)-1):
  start = a[i]
  after = sum(a[i+1:])
  sigma = sigma + start * after
  if sigma >= (10**9 + 7):
    sigma = sigma % (10**9+7)

print(sigma)


### FIXED CODE ###

n = int(input())

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

sigma = 0
after = sum(a[0:])
for i in range(len(a)-1):
  start = a[i]
  after = after - a[i]
  sigma = sigma + start * after
  if sigma >= (10**9 + 7):
    sigma = sigma % (10**9+7)

print(sigma)
### BUGGY CODE ###

a,b,n = map(int, input().split())
max = 0
for x in range(0,min(b,n+1)):
    M = int(a*x/b) - a*int(x/b)
    if max < M:
        max = M

print(max)

### FIXED CODE ###

a,b,n = map(int, input().split())
m = min(n,b-1)
print(int(a*m/b)-a*int(m/b))
### BUGGY CODE ###

n = int(input())
tt = list(map(int,input().split()))
    
ss = 1

for i in tt:
    p = []
    p.append(int(ss))
    p.append(int(i))
    q = list(sorted(p))
    while q[1] % q[0] != 0:
        r = [q[1] % q[0] , q[0]]
        s = list(sorted(r))
        q[0] = int(s[0])
        q[1] = int(s[1])

        
    ss = int(ss * i) // q[0]
num = ss
kouho = 0
for num in range(1,num + 1):
    onesum = 0
    for onenum in tt:
        onesum += num % onenum
    if kouho < onesum:
        kouho = onesum
print(kouho)


### FIXED CODE ###

n = int(input())
tt = list(map(int,input().split()))
    
ss = 1

for i in tt:
    p = []
    p.append(int(ss))
    p.append(int(i))
    q = list(sorted(p))
    while q[1] % q[0] != 0:
        r = [q[1] % q[0] , q[0]]
        s = list(sorted(r))
        q[0] = int(s[0])
        q[1] = int(s[1])

        
    ss = int(ss * i) // q[0]
num = ss
kouho = 0

for onenum in tt:
    kouho += (num-1) % onenum

print(kouho)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    def point(x):
        use = a[:x]+a[x+K:]
        borf = a[x:x+K]
        score = 0
        for num in use:
            if num > 0:
                score += num
        if sum(borf) > 0:
            score += sum(borf)
        return(score)
        
    ans = 0
    for i in range(N-K+1):
        ans = max(ans,point(i))
        
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    
    cum = [0]
    pluscum = [0]
    
    for i in range(N):
        cum.append(cum[-1]+a[i])
        if a[i] > 0:
            pluscum.append(pluscum[-1]+a[i])
        else:
            pluscum.append(pluscum[-1])

    ans = -(10**15)
    for i in range(N-K+1):
        ret = pluscum[i]+(pluscum[-1]-pluscum[i+K])+max((cum[i+K]-cum[i]),0)
        ans = max(ans,ret)
    
    print(ans)

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

from functools import reduce
q = 1000003
N = int(input())
queries = [list(map(int, input().split())) for _ in range(N)]
for x, d, n in queries:
    prod = 1
    ans = reduce(lambda prod, next: prod * next % q, [x + i*d for i in range(n)], prod)
    print(ans)


### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools
 
setrecursionlimit(10**7)
 
def input():
  return stdin.readline().strip()
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
MOD = 10**6 + 3
 
fact = [1] * MOD
for i in range(1, MOD):
  fact[i] = (fact[i-1] * i) % MOD
invfact = [0] * MOD; invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(MOD-2, -1, -1):
  invfact[i] = invfact[i+1] * (i+1) % MOD
# print(invfact[:10])
 
def inv(n):
  return pow(n, MOD-2, MOD)
 
def solve(x, d, n):
  if x == 0:
    return 0
  if d == 0:
    return pow(x, n, MOD)
  k = x * inv(d) % MOD
  if n + k - 1 >= MOD:
    return 0
  return fact[n + k - 1] * invfact[k-1] % MOD * pow(d, n, MOD) % MOD
 
Q = read()
for _ in range(Q):
  x, d, n = reads()
  ans = solve(x, d, n)
  print(ans)
### BUGGY CODE ###

import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = Q.index(c)
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.append(i)
        I.sort()
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.insert(j, i)
    print(ans)


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

class DoublyLinkedKist:
    DLlist = []

    def command(self, cmd):
        if cmd[0] == 'insert':
            self.DLlist[:0] = [cmd[1]]
        elif cmd[0] == 'delete':
            if cmd[1] in self.DLlist:
                self.DLlist.remove(cmd[1])
        elif cmd[0] == 'deleteFirst':
            self.DLlist.pop(0)
        elif cmd[0] == 'deleteLast':
            self.DLlist.pop()

if __name__ == '__main__':
    DL = DoublyLinkedKist()
    for i in range(int(input())):
        DL.command(input().split())
    print(*DL.DLlist)

### FIXED CODE ###

from collections import deque
class DoublyLinkedKist:
    DLlist = deque()

    def command(self, cmd):
        if cmd[0] == 'insert':
            self.DLlist.appendleft(cmd[1])
        elif cmd[0] == 'delete':
            if cmd[1] in self.DLlist:
                self.DLlist.remove(cmd[1])
        elif cmd[0] == 'deleteFirst':
            self.DLlist.popleft()
        elif cmd[0] == 'deleteLast':
            self.DLlist.pop()

if __name__ == '__main__':
    DL = DoublyLinkedKist()
    for i in range(int(input())):
        DL.command(input().split())
    print(*DL.DLlist)
### BUGGY CODE ###

n, k = map(int,input().split())
s = input()
ans = 0
for i in range(n-1):
  if s[i] == s[i+1]:
    ans += 1
while True:
  for i in range(k):
    if ans < n-2:
      ans += 2
    if ans == n-2:
      ans += 1
    else:
      break
print(ans)

### FIXED CODE ###

n, k = map(int,input().split())
s = input()
ans = 0
for i in range(n-1):
  if s[i] == s[i+1]:
    ans += 1
for i in range(k):
  if ans < n-2:
    ans += 2
  elif ans == n-2:
    ans += 1
  else:
    pass
print(ans)
### BUGGY CODE ###

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

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
skip = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)
    




    
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q

import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)
### BUGGY CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
w=[(i1,l1) for i1 in range(n) for l1 in range(n-i1,1,-1)]
v=[(i2,l2) for i2 in range(n) for l2 in range(n-i2,1,-1)]
#print(w)
#print(v)
ans=(10**18)*5
for w_sub in w:
    for v_sub in v:
        i1,l1=w_sub
        i2,l2=v_sub
        x_sub1=x[i1][0]
        x_sub2=x[i1+l1-1][0]
        y_sub1=y[i2][0]
        y_sub2=y[i2+l2-1][0]
        z=[0]*n
        for i in range(n):
            if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                z[i]=1
        if sum(z)>=k:
            ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
lmnk=(2*N//K)
ans=0
for h in range(1,lmnk+1):
    a=h*K//2
    if 1<=a<=N:
        for i in range(1,(N+a)//K+1):
            b=i*K-a
            if 1<=b<=N:
                for j in range(1,(N+b)//K+1):
                    c=j*K-b
                    if 1<=c<=N:
                        if (a+b)%K==0 and (b+c)%K==0 and (c+a)%K==0:
                            ans+=1
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
if K%2==1:
    print((N//K)**3)
else:
    print((N//K)**3+(2*N//K-N//K)**3)
### BUGGY CODE ###

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

for i in range(Q):
  BC = list(map(int, input().split()))
  B_i = BC[0]
  C_i = BC[1]
  for j in range(len(A)):
    if A[j] == B_i:
      A[j] = C_i
  A = sorted(A)
  print(sum(A))
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
dic = dict()
 
for i in A:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
 
ans = sum(A)
 
for i in range(Q):
    b, c = list(map(int, input().split()))
    x = 0
    if b in dic:
        x = dic.pop(b)
        if c in dic:    
            dic[c] += x
        else:
            dic[c] = x
    ans += x * (c-b)
    print(ans)
### BUGGY CODE ###

#D
s = input()
q = int(input())
query = []
for _ in range(q):
    t = list(map(str,input().split()))
    if t[0] == '1':
        s = s[::-1]
    else:
        if t[1] == "1":
            s = t[2] + s
        else:
            s = s + t[2]
            
print(s)

### FIXED CODE ###

#D
#import sys
#input = sys.stdin.readline
from collections import deque
s = deque(input())
q = int(input())
#flg:反転してるときtrue,してないときFalse
flg = False

for _ in range(q):
    t = tuple(map(str,input().split()))
    if t[0] == '1':
        if flg:
            flg = False
        else:
            flg = True
    else:
        if t[1] == "1" and flg == False:
            s.appendleft(t[2])
        elif t[1] == "1" and flg == True:
            s.append(t[2])
        elif t[1] == "2" and flg == False:
            s.append(t[2])
        else:
            s.appendleft(t[2])
 
    
if flg:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

def resolve():
    import heapq
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)
    while True:
        mini = a[0]
        for i in range(1, len(a)):
            a[i] %= mini
            if sum(a[1:]) == 0:
                print(a[0])
                exit()
        
        a =[i for i in a if i!= 0]
        a = sorted(a)
resolve()

### FIXED CODE ###

def resolve():
    import heapq
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)
    while True:
        mini = a[0]
        others = a[1:]
        others = [x % mini for x in others]
        if sum (others) == 0:
            print(a[0])
            exit()
        a = [mini] + others
        a =[i for i in a if i!= 0]
        a = sorted(a)
resolve()
### BUGGY CODE ###

K, N = map(int,input().split())
A = list(map(int, input().split()))
l = 0
L = []
for i in range(N-1):
  l = A[i+1] - A[i]
  L.append(l)
L.append(K-A[N-1]+A[0])
Ans = []
for j in range(len(L)):
  l = sum(L) - L[j]
  Ans.append(l)
print(min(Ans))


### FIXED CODE ###

K, N = map(int,input().split())
A = list(map(int, input().split()))
l = 0
L = []
for i in range(N-1):
  l = A[i+1] - A[i]
  L.append(l)
L.append(K-A[N-1]+A[0])
print(sum(L)-max(L))