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

import sys


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def main():
    X, Y = map(int, input().split())
    C = 10**9 + 7

    if (X + Y) % 3 != 0:
        print(0)
        sys.exit()
    cnt = [0, 0]
    if Y / X >= 1:
        (i, j) = (1, 2)
        cnt[0] += 1
    else:
        (i, j) = (2, 1)
        cnt[1] += 1

    while (i, j) != (X, Y):
        if Y * i > X * j:
            i += 1
            j += 2
            cnt[0] += 1
        else:
            i += 2
            j += 1
            cnt[1] += 1

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()


### FIXED CODE ###

import sys


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def main():
    X, Y = map(int, input().split())
    C = 10**9 + 7

    if (X + Y) % 3 != 0:
        print(0)
        sys.exit()

    cnt = [0, 0]
    cnt[0] = (2 * X - Y) // 3
    cnt[1] = (-X + 2 * Y) // 3

    if cnt[0] < 0 or cnt[1] < 0:
        print(0)
        sys.exit()

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()
### BUGGY CODE ###

def longest_common_subsequence(S, T):
    LS = len(S); LT = len(T)
    dp = [[0] * (LT + 1) for _ in range(LS + 1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    return dp
    

def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i and j:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))


s,t=input(), input()
print(reconstruct_LCS(s, t, longest_common_subsequence(s, t)))


### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
ans = ''
while(dp[n][m]>0):
  if dp[n][m] == dp[n-1][m-1] +1 and dp[n][m] == dp[n-1][m] +1 and dp[n][m] == dp[n][m-1] +1:
    ans = ''.join([s[n-1],ans])
    n -= 1
    m -= 1
  elif dp[n-1][m] > dp[n][m-1]:
    n -= 1
  else:
    m -= 1
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
A = np.array(list(map(int,input().split())), dtype=np.int64)
print(min(abs(sum(A[0:i+1])-sum(A[i+1:n])) for i in range(n-1)))


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
Asum = sum(A)
Al = 0
ans = Asum
for a in A:
    Al += a
    Ar = Asum-Al
    ans = min(ans,abs(Ar-Al))
print(ans)
### BUGGY CODE ###



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

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)



### FIXED CODE ###


import sys
input = sys.stdin.readline

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

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

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

N = int(input())
gacha_list = []
output = 0

for i in range(N):
  input_line = input()
  gacha_list.append(input_line)

while len(gacha_list) > 0:
  result = gacha_list[0]
  result_count = gacha_list.count(result)
  for i in range(result_count):
    gacha_list.remove(result)
  output += 1
  
print(output)

### FIXED CODE ###

N = int(input())
gacha_list = set()

for i in range(N):
  input_line = input()
  if input_line not in gacha_list:
    gacha_list.add(input_line)
    
print(len(gacha_list))
### BUGGY CODE ###

a, b, c, d= map(int, input().split())
ans = 0

for i in range(d + 1):
    for j in range(d + 1):
        for k in range(d + 1):
            sum = a * i + b * j + c * k
            if sum == d:
                ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range((N//R)+1):
    for g in range((N//G)+1):
        if r*R + g*G <= N and (N - r*R - g*G) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

k, s=map(int, input().split())
count=0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        count+=1
print(count)

### FIXED CODE ###

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

W, H = map(int, raw_input().split())
p = sorted([(i, int(raw_input())) for i in xrange(W)], key=lambda x:-x[1])
q = sorted([(i, int(raw_input())) for i in xrange(H)], key=lambda x:-x[1])

class UnionFind(object):
    def __init__(self, n):
        self.uf = [-1 for _ in xrange(n)]

    def union(self, x, y):
        x = self.find(x[0] + x[1]*(W+1))
        y = self.find(y[0] + y[1]*(W+1))
        if x == y:
            return False
        if self.uf[x] >= self.uf[y]:
            self.uf[y] += self.uf[x]
            self.uf[x] = y
        else:
            self.uf[x] += self.uf[y]
            self.uf[y] = x
        return True

    def find(self, x):
        leaves = []
        while self.uf[x] >= 0:
            leaves.append(x)
            x = self.uf[x]
        for lf in leaves:
            self.uf[lf] = x
        return x

uf = UnionFind((W+1)*(H+1))
ans = 0
while len(p) > 0 or len(q) > 0:
    if len(q) == 0 or (len(p) > 0 and p[-1][1] <= q[-1][1]):
        i, cost = p.pop()
        for j in xrange(H+1):
            if uf.union((i, j), (i+1, j)):
                ans += cost
    else:
        j, cost = q.pop()
        for i in xrange(W+1):
            if uf.union((i, j), (i, j+1)):
                ans += cost
print ans


### FIXED CODE ###

W, H = map(int, raw_input().split())
p = sorted([(i, int(raw_input())) for i in xrange(W)], key=lambda x:-x[1])
q = sorted([(i, int(raw_input())) for i in xrange(H)], key=lambda x:-x[1])
ans = 0
pe, qe, ae = 0, 0, (W+1)*(H+1)-1
while len(p)> 0 or len(q) > 0:
    if len(q) == 0 or (len(p) > 0 and p[-1][1] <= q[-1][1]):
        i, cost = p.pop()
        pe += 1
        ans += cost*(H+1-qe)
    else:
        j, cost = q.pop()
        qe += 1
        ans += cost*(W+1-pe)

print ans
### BUGGY CODE ###

from itertools import product, takewhile
# count = 0


def iter_break():
    yield True
    raise StopIteration


def main():
    N, Y = (int(x) for x in input().split(" "))
    y10 = 10000
    y5 = 5000
    y1 = 1000
    max_y10 = Y // y10
    max_y5 = Y // y5
    max_y1 = Y // y1
    if (max_y10) > N:
        max_y10 = N
    if (max_y5) > N:
        max_y5 = N
    if (max_y1) > N:
        max_y1 = N
    # guess = [(x, y, z) for (x, y, z) in
    #          if x+y+z == N]
    # result = list((n_y10, n_y5, n_y1) for n_y10, n_y5,
    #               n_y1 in guess if n_y10 * y10 + n_y5 * y5 + n_y1 * y1 == Y & iter_break())
    for (n_y10, n_y5, n_y1) in product(
        range(max_y10, -1, -1),
        range(max_y5, -1, -1),
            range(max_y1, -1, -1)):
        if (n_y10 + n_y5 + n_y1 != N) or (n_y10 * y10 + n_y5 * y5 + n_y1 * y1 != Y):
            continue
        print(n_y10, n_y5, n_y1)
        exit()
    print(-1, -1, -1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import product, takewhile
# count = 0


def iter_break():
    yield True
    raise StopIteration


def main():
    N, Y = (int(x) for x in input().split(" "))
    Y = Y//1000
    y10 = 10
    y5 = 5
    y1 = 1
    max_y10 = Y // y10
    max_y5 = Y // y5
    max_y1 = Y // y1
    if (max_y10) > N:
        max_y10 = N
    if (max_y5) > N:
        max_y5 = N
    # if (max_y1) > N:
    #     max_y1 = N
    for (n_y10, n_y5) in product(
        range(max_y10, -1, -1),
            range(max_y5, -1, -1)):
        n_y1 = N-n_y10-n_y5
        if n_y1 < 0 or (n_y10 * y10 + n_y5 * y5 + n_y1 * y1 != Y):
            continue
        print(n_y10, n_y5, n_y1)
        exit()
    print(-1, -1, -1)


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

N,W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]

def dp(f,w):
    global F
    if w < 0:
        return -10**9
    if f == 0:
        if w < F[0][0]:
            return 0
        else:
            return F[0][1]
    return max(dp(f-1,w),dp(f-1,w-F[f][0])+F[f][1])

print(dp(N-1,W))

### FIXED CODE ###

N,W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]

DP = []
for w,v in F:
    if DP == []:
        DP = [0]*w+[v]*(W-w+1)
    else:
        dp = DP[::]
        for w2 in range(w,W+1):
            dp[w2] = max(DP[w2-w] + v, DP[w2])
        DP = dp
    #print(DP)
print(DP[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())
p = [int(x) for x in input().split()]

x = []
oklist = [0]

for i in range(1,n):
    res = "ok"
    for j in range(i):
        #print(j,i,p[j],p[i])
        if p[j] < p[i]:
            res = "ng"
    if res == "ok":
        oklist.append(i)

#print(oklist)
print(len(oklist))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())
p = [int(x) for x in input().split()]

ok = 1
minp = [p[0]]

for i in range(1,n):
    if p[i] < minp[i-1]:
        minp.append(p[i])
        ok = ok + 1
    else:
        minp.append(minp[i-1])

print(ok)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

for q in LOO:
  print(ans[q])
  
  
  
  

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

p = []
for q in LOO:
  p.append(ans[q])
  
print(*p, sep="\n")
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
MOD = 10**9+7
for elem in a:
    g *= elem//fractions.gcd(g,elem)
res = sum((g//elem for elem in a))
print(res%MOD)


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)
### BUGGY CODE ###

n=int(input())
s=input()
a0=[]
for i in range(n):
    left=s[:i:].count("W")
    right=s[i+1:].count("E")
    a0.append(left+right)
a=sorted(a0)
print(a[0])


### FIXED CODE ###

n=int(input())
s=input()
w=[0]*n
e=[0]*n
for i in range(n):
    if s[i]=="W":
        if i==0:
           w[i]+=1
        else:
            w[i]+=w[i-1]+1
            e[i]+=e[i-1]
    else:
        if i==0:
            e[i]+=1
        else:
            e[i]+=e[i-1]+1
            w[i]+=w[i-1]
min=9999999
for i in range(n):
    if i==0:
        num=e[n-1]-e[i]

    else:
        num=w[i-1]+e[n-1]-e[i]
    if min>num:
        min=num
print(min)
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        for i in range(0, p+1):
            if p % (2**(i+1)) != 0:
                ans *= 2**(i//n)
                p //= 2**i
                break
        for i in range(3, p+1, 2):
            if i**n > p:
                break
            for j in range(0, p+1):
                if p % (i**(j+1)) != 0:
                    ans *= i**(j//n)
                    p //= i**j
                    break
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

def lcm(x, y):
   """This function takes two
   integers and returns the L.C.M."""

   # choose the greater number
   if x > y:
       greater = x
   else:
       greater = y

   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm
a,b = list(map(int,input().split()))
print(lcm(a,b))



### FIXED CODE ###

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

def lcm(a,b): 
    return (a*b) / gcd(a,b) 
a,b = list(map(int,input().split()))
print(int(lcm(a,b)))
### BUGGY CODE ###

from math import factorial
import bisect
import sys
n = int(input())
A = sorted(list(map(int,input().split())))
           
max1 = A[-1]
half = A[-1]//2

point = bisect.bisect_left(A, half)

if A[point] == A[-1]:
  print(A[-1],A[-2])
  sys.exit()

a1 = factorial(max1) / factorial(A[point]) / factorial(max1 - A[point])
a2 = factorial(max1) / factorial(A[point+1]) / factorial(max1 - A[point+1])
if a1>=a2:
  print(max1,A[point])
else:
  print(max1,A[point+1])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
m = max(a)
a = sorted(a)
 
ans = 0
 
for i in a:
    if abs(m/2-i) < abs(m/2-ans):
        ans = i
 
print(m, ans)
### BUGGY CODE ###

from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [[[0,0,0]for _ in range(S+1)]for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0] ;dp[i+1][j][0] %= mod
            dp[i+1][j][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j][0]+dp[i][j][1]+dp[i][j][2];dp[i+1][j][2]%= mod
            if j+a[i] <= S:
                dp[i+1][j+a[i]][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][1] %= mod
                dp[i+1][j+a[i]][2] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][2] %= mod
    print(int(dp[N][S][2]))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [0]*(S+1)
    ans = 0
    for A in a:
        dp[0] += 1
        for i in reversed(range(A,S+1)):
            dp[i] += dp[i-A]    
            dp[i] %= mod
        ans += dp[S]
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
N = int(input())
a = input()

def combination(n: int, r: int) -> int:
    comb = 1
    for i in range(r):
        comb *= n-i
    comb //= math.factorial(r)
    return comb

def is_ans_odd(a: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(a):
        x = int(c)
        co = combination(len(a)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
a = input()

def is_combination_odd(n, r):
    _n = n
    _r = r
    is_odd = True
    while _n > 0 and _r > 0:
        if _n % 0b10 < _r % 0b10:
            is_odd = False
            break
        _n >>= 1
        _r >>= 1
    #print('n: %d, r: %d, is_odd: %d' % (n, r, is_odd))
    return is_odd
    
def is_ans_odd(num_str: str) -> bool:
    is_odd = False
    for i, c in enumerate(num_str):
        is_c_odd = int(c) % 2
        is_odd ^= is_combination_odd(len(num_str)-1, i) & is_c_odd
    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

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

def flpl(): return [float(i) for i in input().split()]
def inpl(): return [int(i) for i in input().split()]
import numpy as np
xs, ys, xt, yt = flpl()
rs,rt = 0, 0
N = int(input())
xyr = [(xs, ys, rs),(xt, yt,rt)] + [inpl() for _ in range(N)]
X, Y, R = np.array(xyr).T
edge = np.zeros((N+2,N+2))
edge 
for i in range(N+2):
    for j in range(i+1):
        edge[i][j] = edge[j][i] = max(0, \
            ((X[i]-X[j])**2 + (Y[i]-Y[j])**2)**(1/2) - (R[i]+R[j]))
        inf = float('inf')
dist = np.array([inf for _ in range(N+2)])
dist[0] = 0 
import heapq

decided = [False for _ in range(N+2)]
Q = []
heapq.heappush(Q,(0,0))
while Q:
    k = heapq.heappop(Q)
    k = k[1]
    if decided[k]:
        continue
    decided[k] = True
    for j in range(N+2):
        if decided[j]:
            continue
        if dist[k] + edge[k][j] < dist[j]:
            dist[j] = dist[k] + edge[k][j] 
            heapq.heappush(Q,(dist[j],j)) 
    if decided[1]:
        break
print(dist[1])

### FIXED CODE ###

def flpl(): return [float(i) for i in input().split()]
def inpl(): return [int(i) for i in input().split()]
import heapq
def dijkstra(vnum, vs):
    dist = [float('inf') for _ in range(vnum)]
    dist[vs] = 0 
    remain = set(range(vnum))
    Q = []
    heapq.heappush(Q,(0,vs))
    while Q:
        c, vn = heapq.heappop(Q)
        if vn not in remain :
            continue
        remain.remove(vn)
        for j in remain:
            evnj = edge(vn, j)
            if dist[vn] + evnj < dist[j]:
                dist[j] = dist[vn] + evnj 
                heapq.heappush(Q,(dist[j],j)) 
        if not remain:
            break
    return dist
def edge(s, t):
    return max(((X[s] - X[t])**2 + (Y[s] - Y[t])**2)**(1/2) -(R[s]+R[t]), 0)

xs, ys, xt, yt = flpl()
N = int(input())
xyr = [(xs, ys, 0),(xt, yt, 0)] + [inpl() for _ in range(N)]
X, Y, R = list(map(list, zip(*xyr)))
D = dijkstra(N+2, 0)
print(D[1])
### BUGGY CODE ###

mst_l = [chr(i) for i in range(97,97+26)]

n = int(input())
l = [input() for _ in range(n)]
l = ["".join(map(str, [x.count(a) for a in mst_l])) for x in l]
result = 0
for i in range(n-1):
    result += len([x for x in l[i+1:] if x == l[i]])
print(result)

### FIXED CODE ###

from math import factorial
from collections import Counter
 
def conb(n):
    if n <= 1:
        return 0
    else:
        return factorial(n) // factorial(n-2) // factorial(2) 

n = int(input())
S = [''.join(sorted(list(input()))) for i in range(n)]

print(int(sum([conb(i) for i in Counter(S).values()])))
### BUGGY CODE ###


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

def rev(s):
    return "".join(list(reversed(s)))



for i in range(q):
    inp = input().split()
    if inp[0] == "1":
        s = s[::-1]
    elif inp[1] == "1":
        s = inp[2] + s
    else:
        s = s + inp[2]


print(s)


### FIXED CODE ###

from collections import deque

#inp = list(map(lambda x: int(x), input().split()))
#n,k = map(lambda x: int(x), input().split())
#p_n = list(map(lambda x:int(x),input().split()))


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


cnt = 0
for i in range(q):
    inp = input().split()
    if inp[0] == "1":
        cnt += 1
    else:
        if inp[1] == "1":
            if cnt % 2 == 0:
                s.appendleft(inp[2])
            else:
                s.append(inp[2])
        else:
            if cnt % 2 == 0:
                s.append(inp[2])
            else:
                s.appendleft(inp[2])

ans = list(s)

if cnt % 2 == 1:
    ans = ans[::-1]

print(''.join(ans))