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

n=int(input())
a=list(map(int,input().split()))
a=[sum(a[:i])+a[i] for i in range(len(a))]
j=0
k=2
ans=10**9

for i in range(1,n-1):
    while abs(a[j]*2-a[i])>abs(a[j+1]*2-a[i]):
        j+=1
    while abs(a[k]*2-a[i]-a[n-1])>abs(a[k+1]*2-a[i]-a[n-1]):
        k+=1
    t=[a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k]]
    ans=min(ans,max(t)-min(t))
print(ans)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]

for i in range(n-1):
    a[i+1]+=a[i]

j=0
k=2
ans=10**9

for i in range(1,n-1):
    while abs(a[j]*2-a[i])>abs(a[j+1]*2-a[i]):
        j+=1
    while abs(a[k]*2-a[i]-a[n-1])>abs(a[k+1]*2-a[i]-a[n-1]):
        k+=1
    t=[a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k]]
    ans=min(ans,max(t)-min(t))
print(ans)
### BUGGY CODE ###

H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]   # (i,j) = A[i][j]
seen = [[False] * W for _ in range(H)] 
queue=[]

for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append((i,j,0))
            seen[i][j]=True

while queue:
    i,j,k=queue.pop(0)
    if i!=0   and seen[i-1][j] == False: 
        queue.append((i-1,j,k+1))
        seen[i-1][j]=True
    if i!=H-1 and seen[i+1][j] == False:
        queue.append((i+1,j,k+1))
        seen[i+1][j]=True
    if j!=0   and seen[i][j-1] == False:
        queue.append((i,j-1,k+1))
        seen[i][j-1]=True
    if j!=W-1 and seen[i][j+1] == False:
        queue.append((i,j+1,k+1))
        seen[i][j+1]=True

print(k)

### FIXED CODE ###

import numpy as np
import sys
# 距離K以内にxが居ない
# xからの距離を測る

buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
black = np.zeros((R+2,C+2),dtype=np.bool)
black[1:-1,1:] = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#').reshape(R,C+1)

INF = 10 ** 9
dist = np.zeros((R,C),dtype=np.int32)
dist[~black[1:-1,1:-1]] = INF

for n in range(1,R):
  np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(R-2,-1,-1):
  np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,C):
  np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(C-2,-1,-1):
  np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)
### BUGGY CODE ###

n = int(input())
moto = [int(i) for i in input().split()]
 
array=[0]*n
 
for i in reversed(range(1,n+1)):
  if sum(array[i-1::i])%2 != moto[i-1]:
    array[i-1] = 1
    
m = array.count(1)
ans = ""
for i in range(n):
  if array[i] == 1:
    ans = ans + str(i+1) + " "
print(m)
if ans != "":
  print(ans[:-1])

### FIXED CODE ###

n = int(input())
moto = [int(i) for i in input().split()]
 
array=[0]*n
 
for i in reversed(range(1,n+1)):
  if sum(array[i-1::i])%2 != moto[i-1]:
    array[i-1] = 1
    
m = sum(array)
print(m)
ans = ""
for i in range(n):
  if array[i] == 1:
    print(i+1, end=" ")
### BUGGY CODE ###

_, m = map(int, input().split())
l = []
w = a = 0
D = {}
for _ in range(m):
    n, j = input().split()
    if n not in D:
        D[n] = 0
    if n not in l:
        if j == "WA":
            D[n] += 1
        else:
            a += 1
            l += [n]
            w += D[n]
print(a, w)

### FIXED CODE ###

d = [0]*10**5

a = set()
w = 0

for t in open(0):
    p, s = t.split()
    p = int(p)
    if "AC" == s and p not in a:
        w += d[p]
        a.add(p)
    if "WA" == s:
        d[p] += 1

print(len(a), w)
### BUGGY CODE ###

N, Q = map(int, input().split())
s = str(input())
coms = [list(map(str, input().split())) for _ in range(Q)]


def ok_lower(A, index, coms):
    # シミュレーションを行う
    for com in coms:
        if com[0] == A[index]:
            if com[1] == 'R':
                index += 1
            elif com[1] == 'L':
                index -= 1
            if index == len(A):
                return True
            elif index == -1:
                return False
    return False


def ok_upper(A, index, coms):
    # シミュレーションを行う
    for com in coms:
        if com[0] == A[index]:
            if com[1] == 'R':
                index += 1
            elif com[1] == 'L':
                index -= 1
            if index == len(A):
                return False
            elif index == -1:
                return True
    return False


def lower_bound(A, coms):
    ng = -1
    ok = len(A)

    while(abs(ok-ng) > 1):
        mid = (ok + ng) // 2

        if ok_lower(A, mid, coms):
            ok = mid
        else:
            ng = mid
    return ok


def upper_bound(A, coms):
    ng = len(A)
    ok = -1

    while(abs(ok-ng) > 1):
        mid = (ok + ng) // 2

        if ok_upper(A, mid, coms):
            ok = mid
        else:
            ng = mid
    return ok


lower = lower_bound(s, coms)
upper = upper_bound(s, coms)
print(max(0, lower-upper-1))


### FIXED CODE ###

N, Q = map(int, input().split())
s = str(input())
coms = [list(map(str, input().split())) for _ in range(Q)]


def isOK(A, index, coms, c):
    # シミュレーションを行う
    for com in coms:
        if com[0] == A[index]:
            if com[1] == 'R':
                index += 1
                if index == len(A):
                    return c == 'R'
            elif com[1] == 'L':
                index -= 1
                if index == -1:
                    return c == 'L'
    return False


def lower_bound(A, coms):
    ng = -1
    ok = len(A)

    while(abs(ok-ng) > 1):
        mid = (ok + ng) // 2

        if isOK(A, mid, coms, 'R'):
            ok = mid
        else:
            ng = mid
    return ok


def upper_bound(A, coms):
    ng = len(A)
    ok = -1

    while(abs(ok-ng) > 1):
        mid = (ok + ng) // 2

        if isOK(A, mid, coms, 'L'):
            ok = mid
        else:
            ng = mid
    return ok


lower = lower_bound(s, coms)
upper = upper_bound(s, coms)
print(lower-upper-1)
### BUGGY CODE ###

#!/usr/bin/env python
import numpy as np
N = int(input())
X = np.array(list(map(int, input().split())))
idx = np.ones(N, dtype=bool)
for i in range(N):
    idx[i] = False
    print(int(np.median(X[idx])))
    idx[i] = True


### FIXED CODE ###

#!/usr/bin/env python
import numpy as np
N = int(input())
X = np.array(list(map(int, input().split())))
idx = X.argsort()
low = idx[N//2-1]
high = idx[N//2]

res = np.zeros(N, dtype=int)
res[idx[:N//2]] = X[high]
res[idx[N//2:]] = X[low]

for i in range(N):
    print(res[i])
### BUGGY CODE ###

n = int(input())
paper = []
for i in range(n):
  tmp = input().rstrip()
  if tmp not in paper:
    paper.append(tmp)
  else:
    paper.pop(paper.index(tmp))
print(len(paper))

### FIXED CODE ###

n = int(input())
paper = set()
for i in range(n):
  tmp = input().rstrip()
  if tmp not in paper:
    paper.add(tmp)
  else:
    paper.remove(tmp)
print(len(paper))
### BUGGY CODE ###

n=int(input())
print(0)
la=input()
if la=='Vacant':
  exit()
print(n-1)
ra=input()
if ra=='Vacant':
  exit()
l=0
r=n-1
while true:
  m=(l+r)//2
  print(m)
  s=input()
  if s=='Vacant':
    exit()
  elif (s!=la and (m-l)%2==0) or (s==ra and (m-l)%2==1):
    r=m
    ra=s
  else:
    l=m
    la=s

### FIXED CODE ###

n=int(input())
def out(t):
  print(t,flush=True)
  s=input()
  if s=='Male':return 0
  elif s=='Female':return 1
  else:exit()
l=0
r=n
f=out(0)
while l+1!=r:
  m=(l+r)//2
  if (m+f)%2==out(m):l=m
  else:r=m
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

# Segment Tree
class SegmentTree:
    def __init__(self, N):
        self.size = 2 ** (N-1).bit_length()# 要素数を超える最小の2べき
        self.dat = [0] * (2*self.size)
    
    def update(self,i,x):# i番目の文字がxになる
        i += self.size
        self.dat[i] = 1 << ord(x)-ord('a')
        while i > 0:# 上まで更新していく
            i >>= 1
            self.dat[i] = self.dat[i*2] | self.dat[i*2+1]

    def fold(self, l, r):
        l += self.size
        r += self.size
        vl = 0
        vr = 0
        while l < r:
            if l & 1:
                vl |= self.dat[l]
                l += 1
            if r & 1:
                r -= 1
                vr |= self.dat[r]
            l >>= 1
            r >>= 1
        # print(bin(vl | vr))
        return bin(vl | vr).count('1')

def main():
    N = int(input())
    S = list(input())
    sg = SegmentTree(N)
    for i in range(N):
        sg.update(i,S[i])
    # print(sg.dat)
    
    Q = int(input())
    for _ in range(Q):
        Query = input().split()
        if Query[0] == '1':
            sg.update(int(Query[1])-1, Query[2])
            # print(sg.dat)
        else:
            res = sg.fold(int(Query[1])-1, int(Query[2]))
            print(res)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

# Segment Tree
class SegmentTree:
    def __init__(self, N):
        self.size = 2 ** (N-1).bit_length()# 要素数を超える最小の2べき
        self.dat = [0] * (2*self.size)
    
    def update(self,i,x):# i番目の文字がxになる
        i += self.size
        self.dat[i] = 1 << ord(x)-ord('a')
        while i > 0:# 上まで更新していく
            i >>= 1
            self.dat[i] = self.dat[i*2] | self.dat[i*2+1]

    def fold(self, l, r):
        l += self.size
        r += self.size
        vl = 0
        vr = 0
        while l < r:
            if l & 1:
                vl |= self.dat[l]
                l += 1
            if r & 1:
                r -= 1
                vr |= self.dat[r]
            l >>= 1
            r >>= 1
        # print(bin(vl | vr))
        return bin(vl | vr).count('1')

def main():
    N = int(input())
    S = list(input())
    sg = SegmentTree(N)
    for i in range(N):
        sg.update(i,S[i])
    
    Q = int(input())
    for _ in range(Q):
        Query = input().split()
        if Query[0] == '1':
            sg.update(int(Query[1])-1, Query[2])
        else:
            res = sg.fold(int(Query[1])-1, int(Query[2]))
            print(res)

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

from heapq import heappop, heappush, heapify
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)

q = [(-a[i]*f[i], -f[i]) for i in range(n)]
heapify(q)

for i in range(k):
    t, g = heappop(q)
    heappush(q, (t-g, g))

ans, _ = heappop(q)
print(-ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)

left, right = -1, a[-1] * f[0]

while right - left > 1:
    mid = (left + right) // 2
    ck = 0
    for i in range(n): ck += max(0, a[i] - mid // f[i])
    if ck <= k: right = mid
    else: left = mid

print(right)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
sum_r = sum(A)
# print(A[0::2])
# print(A[1::2])
sum_odd = sum(A[0::2])
sum_even = sum(A[1::2])

ans = ''
rolling_even = sum_even 
rolling_odd = sum_odd - A[0]
#print(sum_r,sum_even)
ans += str(sum_r - 2 * rolling_even) + ' ' + str(sum_r - 2 * rolling_odd)
for i in range(2,N):
    tmp = sum_r
    # for j in range(N//2):
    #     #print((i+1+j*2)%N)
    #     amount -= A[(i+1+j*2)%N]*2
    if i % 2 == 0:
        #print(i,rolling_odd, A[(i-2)%N], A[(i-1)%N])
        rolling_even += A[(i-2)%N] - A[(i-1)%N]
        tmp = sum_r - 2 * rolling_even
    else:
        rolling_odd += A[(i-2)%N] - A[(i-1)%N]
        tmp = sum_r - 2 * rolling_odd
    ans += ' ' + str(tmp)
print(ans)




### FIXED CODE ###

import sys
# input = sys.stdin.readline()
N = int(input())
A = list(map(int,input().split()))
sum_r = 0
# print(A[0::2])
# print(A[1::2])
sum_odd = 0
sum_even = 0
for i in range(N):
    a = A[i]
    sum_r += a
    if i % 2 == 0:
        sum_odd += a
    else:
        sum_even += a

ans = ''
rolling_even = sum_even 
rolling_odd = sum_odd - A[0]
#print(sum_r,sum_even)
X_i = sum(A) - 2 * sum(A[1::2])
sys.stdout.write(str(X_i))
for i in range(N-1):
    X_i_plus_1 = 2 * A[i] - X_i
    sys.stdout.write(' ' + str(X_i_plus_1))
    X_i = X_i_plus_1
# ans += str(sum_r - 2 * rolling_even) + ' ' + str(sum_r - 2 * rolling_odd)
# sys.stdout.write(ans + ' ')
# mepo = A[1]
# mope = A[0]
# for i in range(2,N):
#     tmp = sum_r

#     if i % 2 == 0:
#         # rolling_even += A[(i-2)%N] - A[(i-1)%N]
#         mepo = A[(i-1)]
#         rolling_even += mope - mepo
#         tmp = sum_r - 2 * rolling_even
#     else:
#         mope = A[(i-1)]
#         rolling_odd += mepo - mope
#         tmp = sum_r - 2 * rolling_odd
#     sys.stdout.write(' '+str(tmp))
#     ans += ' ' + str(tmp)
# sys.stdout.write('\n')
### BUGGY CODE ###

N, K, Q = list(map(int, input().split()))
A = [int(input()) for i in range(Q)]
scores = [K] * N
for n in range(N):
    scores[n] = scores[n] + A.count(n+1)
    if scores[n] > Q:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import collections
N, K, Q = list(map(int, input().split()))
A = [int(input()) for i in range(Q)]
cs = collections.Counter(A)
for n in range(N):
    if cs[n+1] > Q-K:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
income = [[] for _ in range(M+1)] # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        bisect.insort_left(income[a], b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
for rest_days in range(1, M+1):
    if income[rest_days]:
        ans += income[rest_days].pop(-1)
        if rest_days < M:
            income[rest_days+1] = sorted(income[rest_days+1] + income[rest_days])

print(ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
heapq.heapify(tmp)

for rest_days in range(1, M+1):
    for x in income[rest_days]:
        heapq.heappush(tmp, x)
    if tmp:
        ans += heapq.heappop(tmp)

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

# -*- coding: utf-8 -*-
import copy

[N, M] = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
BC = []
for m in range(M):
    BC.append([int(i) for i in input().split()])

# Aをソートする
A.sort()

# BCをCが大きい順にソートする
sorted_BC = sorted(BC, key=lambda x:(x[1]), reverse=True)

for m in range(M):
    [B, C] = sorted_BC[m]
    # もしAの最小値がCを超えていたらもうやる意味ないので終了
    if A[0] > C:
        break

    # 小さいほうからB枚のカードをCに変える
    # ただし変えるのは元の数字より大きい時だけ
    for i in range(B):
        if A[i] < C:
            A[i] = C
    A.sort()


print (sum(A))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import copy
from operator import itemgetter

[N, M] = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
BC = []
for m in range(M):
    BC.append([int(i) for i in input().split()])

# Aをソートする
A.sort()

# BCをCが大きい順にソートする
sorted_BC = sorted(BC, key=itemgetter(1, 0), reverse=True)

new_A = []
for [B, C] in sorted_BC:
    # もしAの最小値がCを超えていたらもうやる意味ないので終了
    if A[0] > C:
        break

    # 小さいほうからB枚のカードをCに変える
    # ただし変えるのは元の数字より大きい時だけ
    I = 0
    for i in range(B):
        I = i
        if len(A) <= i:
            I -=1
            break
        if A[i] > C:
            I -=1
            break
        new_A.append(C)
        #print(new_A)

    # 変えた分はリストから除外する
    #print(A)
    #print(I)
    del A[:I+1]
    if len(A) == 0:
        break

    #print(A)

if len(A) != 0:
    new_A.extend(A)

print (sum(new_A))
### BUGGY CODE ###

n, k = [int(e) for e in input().split()]
arr = [int(e) for e in input().split()]
dp = [0]*len(arr)
 
for i in range(1,len(arr)):
  dp[i] = min(dp[j] + abs(arr[i]-arr[j]) for j in range(max(i-k,0),i))
print(dp[-1])



### FIXED CODE ###

n, k = [int(e) for e in input().split()]
arr = [int(e) for e in input().split()]
dp = [0]*len(arr)
 
for i in range(1,len(arr)):
  dp[i] = min(dp[j] + abs(arr[i]-arr[j]) for j in range(max(i-k,0),i))
print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
x = set()
while i < m: 
    l = list(map(int, input().split()))
    l.append(i)
    x.add(l[0])
    lst.append(l)
    i+=1
xxx= sorted(list(x))
ll=sorted(lst)
j=1
for i in xxx:
    for k in ll:
        if i == k[0]:
            k[1]=i*1000000+j
            j+=1
        else:
            j=1
#ans
for ans in sorted(ll, key=lambda x:x[2]):
    print('{0:012d}'.format(ans[1]))



### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    lst.append(list(map(int, input().split())) + [i])
    i+=1
lst = sorted(lst)
j=0
i=1
for k in lst:
    if i != k[0]:
        i=k[0]
        j=1
        k[1]=i*1000000+j
    else:
        j+=1
        k[1]=i*1000000+j

#ans
for ans in sorted(lst, key=lambda x:x[2]):
    print('{0:012d}'.format(ans[1]))
### BUGGY CODE ###


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

# アレイ import numpy as np =np.array(list(map(float,input().split())))

# 文字列 =list(str(input()).split(" " or ","))

# 一文字＆連番(縦横可能) =map(int, open(0).read().split())

# 2-d list
lis=[[] for _ in range(M)]
for i in range(M):
    lis[i] = list(map(int,input().split()[0:]))

# Each list
N = int(input())
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
"""
import math
a,b,n=map(int,input().split())
kai=[]
for i in range(1,n+1):
    k=math.floor(a*i/b)-a*math.floor(i/b)
    kai.append(k)
print(max(kai))

### FIXED CODE ###

a, b, n = list(map(int, input().split()))
x = min(b - 1, n) # b-1がいいけど、上限 nの制約あり
ans = int(a * x / b)
print(ans)
### BUGGY CODE ###

import bisect
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))

d = [int(input()) for _ in range(q)]

event.sort()
now = []

tmp = 0
for i, (t, flg, x) in enumerate(event):
    if flg == 1:
        bisect.insort_left(now, x)
    else:
        idx = bisect.bisect_left(now, x)
        now.pop(idx)

    while tmp < q and i < len(event) - 1 and t <= d[tmp] < event[i+1][0]:
        if len(now) > 0:
            print(now[0])
        else:
            print(-1)
        tmp += 1

while tmp < q:
    print(-1)
    tmp += 1

### FIXED CODE ###

import heapq, sys
input = sys.stdin.readline
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))

for _ in range(q):
    d = int(input())
    event.append((d, 2, 0))

event.sort(key=lambda x: (x[0], x[1]))
now = []
memo = set()

tmp = 0

for i, (t, flg, x) in enumerate(event):
    if flg == -1:
        memo.remove(x)
    elif flg == 1:
        heapq.heappush(now, x)
        memo.add(x)
    else:
        while len(now) > 0 and now[0] not in memo:
            heapq.heappop(now)
        if len(now) > 0:
            print(now[0])
        else:
            print(-1)
### BUGGY CODE ###

# B
import sys
N, K = map(int, input().split())
h = list(map(int, input().split()))

cost = [0]*N

cost[0] = 0
for i in range(1,N):
    cost_tmp = []
    for j in range(0,min(K,i)):
        cost_tmp.append(abs(h[i - (1+j)] - h[i]) + cost[i - (1+j)])
    cost[i] = min(cost_tmp)

print(cost[-1])

    

### FIXED CODE ###

# B(TLE) 2104ms

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
cost = np.zeros(N, dtype="int32")

cost[0] = 0
for i in range(1,N):
    start = 0 if i < K else i-K
    cost[i] = np.min(cost[start:i] + np.abs(h[i]-h[start:i]))

print(cost[-1])
### BUGGY CODE ###

N = int(input())
count = 0
flag = False
for i in range(1, N + 1):
    
    for j in range(1, N // 2):
        for l in range(1, N // 2):
            for r in range(1, N // 2):
                if j ** 2 + l ** 2 + r ** 2 + j * l + j * r + l * r == i:
                    if j == l == r:
                        flag = True
                        count = 1
                        break
                    else:
                        flag = True
                        count = 3
                        break
            if flag:
                break
        if flag:
            break            
    print(count)
    count = 0
    flag = False

### FIXED CODE ###

# # import math
N = int(input())
# # count = 0
# # flag = False
# # # n = int(math.sqrt(N))
n = 105

# # for i in range(1, N + 1):
    
# #     for j in range(1, n):
# #         for l in range(1, n):
# #             for r in range(1, n):
# #                 if j + l + r > N // 2:
# #                     continue
# #                 if j ** 2 + l ** 2 + r ** 2 + j * l + j * r + l * r == i:
# #                     if j == l == r:
# #                         flag = True
# #                         count = 1
# #                         break
# #                     else:
# #                         flag = True
# #                         count = 3
# #                         break
# #             if flag:
# #                 break
# #         if flag:
# #             break            
# #     print(count)
# #     count = 0
# #     flag = False
ans = [0] * 10050
for j in range(1, n):
    for l in range(1, n):
        for r in range(1, n):
            value = j * j  + l * l + r * r + j * l + j * r + l * r
            if value < 10050:
                ans[value] += 1

for i in range(N):
    print(ans[i + 1])
# n = int(input())
# ans = [0 for _ in range(10050)]
# for i in range(1,105):
#     for j in range(1,105):
#         for k in range(1,105):
#             v = i*i+j*j+k*k+i*j+j*k+k*i;
#             if v<10050:
#                 ans[v]+=1   
# for i in range(n):
#     print(ans[i+1])
### BUGGY CODE ###

sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx,sy,0)]
for i in range(n):
    data.append(tuple(map(int,input().split())))
data.append((gx,gy,0))
for i in range(n+2):
    for j in range(i,n+2):
        if i==j:
            g[i].append((0,j))
            g[j].append((0,i))
            continue
        tmp=max(0,((data[i][0]-data[j][0])*(data[i][0]-data[j][0])+(data[i][1]-data[j][1])*(data[i][1]-data[j][1]))**0.5-data[i][2]-data[j][2])
        g[i].append((tmp,j))
        g[j].append((tmp,i))

def dijkstra(g,st,ed):
    from heapq import heappush, heappop, heapify
    inf=10**12
    dist=[inf for i in range(len(g))]
    dist[st]=0
    que = []
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if dist[v]<c:
            continue
        for i in range(len(g[v])):
            if g[v][i][0]+c<dist[g[v][i][1]]:
                dist[g[v][i][1]]=g[v][i][0]+c
                heappush(que,(g[v][i][0]+c,g[v][i][1]))
    return dist[ed]

print(dijkstra(g,0,n+1))

### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

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

for _ in range(q):
    query = input().split()
    if len(query) == 1:
        s = s[::-1]
    else:
        if query[1] == "1":
            s = query[2] + s
        else:
            s = s + query[2]
print(s)

### FIXED CODE ###

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

pres = []
posts = []
mode = 0
for _ in range(q):
    query = input().split()
#     print(s, query, mode, pres, posts)
    if len(query) == 1:
        mode = 1 - mode
    else:
        if mode == 0:
            if query[1] == "1":
                pres.append(query[2])
            else:
                posts.append(query[2])
        else:
            if query[1] == "1":
                posts.append(query[2])
            else:
                pres.append(query[2])
s = "".join(pres[::-1]) + s + "".join(posts)
if mode == 1:
    s = s[::-1]
print(s)