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

import sys
input = sys.stdin.readline
import queue
sys.setrecursionlimit(1000000000)

N, Q = list(map(int, input().split()))
graph = [[] for i in range(N)]
# 最初にroot pointを定めて:
# graph構造に大して点を与える...
for i in range(N-1):
    a, b = list(map(int, input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

points = [0] * N
for _ in range(Q):
    p, x = list(map(int, input().split()))
    points[p-1] += x

visited = [False] * N
tot_points = [0] * N
tot_points[0] = points[0]

nodes = graph[0]
visited[0] = True


def dfs(old_node, node):
    if visited[node]:
        return
    tot_points[node] = tot_points[old_node] + points[node]
    visited[node] = True
    nodes = graph[node]
    for _node in nodes:
        dfs(node, _node)
for _node in nodes:
    dfs(0, _node)

for x in tot_points:
    print(x, end=" ")
    
    

### FIXED CODE ###

import sys
from queue import deque
input = sys.stdin.readline

def main():
    N, Q = list(map(int, input().split()))
    graph = [[] for i in range(N)]
    # 最初にroot pointを定めて:
    # graph構造に大して点を与える...
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    
    points = [0] * N
    for _ in range(Q):
        p, x = list(map(int, input().split()))
        points[p-1] += x
    
    visited = [False] * N
    
    nodes = deque([0])

    while nodes:
        node = nodes.pop()
        visited[node] = True
        for _node in graph[node]:
            if visited[_node]:
                continue
            points[_node] += points[node]
            nodes.append(_node)
    
    print(*points)
    
main()
### BUGGY CODE ###

n = input()
b = 1
a = list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    for i in range(len(a)):
        b *= int(a[i])
    if b > 10**18:
        print(-1)
    else:
        print(b)

### FIXED CODE ###

n = int(input())
b = 1
a = list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    for i in range(n):
        b *= a[i]
        if b > 10**18:
            print(-1)
            break
    if b <=10**18:
        print(b)
### BUGGY CODE ###

import numpy as np
n, d = list(map(int, input().split()))
a = list(map(int, input().split()))
Max = 0

for i in range(n-d+1):
  Sum = sum(a[i:i+d])
 
  if Sum >= Max:
    Max = Sum
    ans = a[i:i+d]    
  else:
    pass
  
ans = np.array(ans)
ans = ans*0.5 + 0.5
print(sum(ans))

### FIXED CODE ###

import numpy as np
n, d = list(map(int, input().split()))
a = list(map(int, input().split()))
Max = 0
Sum = 0
a = np.array(a)
a = a*0.5 + 0.5
ans = []

if d == 1:
  print(max(a))
elif n == d:
  print(sum(a))
else:
  for i in range(n-d+1):
    left = a[i]
    right = a[i+d-1]

    if i == 0:
      Sum = sum(a[i:i+d])
      Max = sum(a[i:i+d])
      ans = a[i:i+d]
    else:
      Sum = Sum + right - a[i-1]

      if Sum >= Max:
        Max = Sum
        ans = a[i:i+d]
      else:
        pass

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

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

INF = 10**10
lis = [INF]*N
lis[0] = 0
for i in range(1, N):
    H_i = H[i]
    for j in range(max(0, i-K), i):
        lis[i] = min(lis[j] + abs(H[j] - H_i), lis[i])
print(lis[N-1])

### FIXED CODE ###

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

INF = 10**9 + 1
L = [INF]*N
L[0] = 0
for i in range(1, N):
    minLi = L[i]
    H_i = H[i]
    for k in range(1, K+1):
        if i - k >= 0:
            minLi = min(minLi, L[i-k] + abs(H_i - H[i-k]))
    L[i] = minLi
print(L[N-1])
### BUGGY CODE ###

A,B,K=map(int, input().split())
count=0
for i in range(K):
    if A>0:
        A=A-1
    elif B>0:
        B=B-1
print(A,B)


### FIXED CODE ###

A,B,K=map(int, input().split())
count=0
if (A-K)<0:
    B=B+A-K
    A=0
    if B<0:
        B=0
else:
    A=A-K
print(A,B)
### BUGGY CODE ###

N = int(input())
min_num = 10**5
for i in range(1, N+1):
    if N % i == 0:
        min_num = min(max(len(str(i)), len(str(N//i))), min_num)
print(min_num)

### FIXED CODE ###

N = int(input())
min_num = 10**5
for i in range(1, 10**5+1):
    if N % i == 0:
        min_num = min(max(len(str(i)), len(str(N//i))), min_num)
print(min_num)
### BUGGY CODE ###

K,S = list(map(int,input().split()))
counter = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k ==S:
                counter +=1
print(counter)


### FIXED CODE ###

K,S = list(map(int,input().split()))
counter = 0
for i in range(K+1):
    for j in range(K+1):
            if 0<=S-i-j<=K:
                counter +=1
               # print(str(i)+' '+str(j)+ ' ' + str(S-i-j))
print(counter)
### BUGGY CODE ###

from operator import itemgetter
import sys


def read():
    return sys.stdin.readline().rstrip()


def add(arr, i, x):
    while i < len(arr):
        arr[i] += x
        i += i & -i


def range_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = iter(sorted([[i] + [int(j) for j in read().split()] for i in range(q)], key=itemgetter(2)))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            add(bit, li, -1)
        last[ci] = i + 1
        add(bit, i + 1, 1)
        while i + 1 == r:
            ans[k] = range_sum(bit, l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                break
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

from operator import itemgetter
import sys


class BIT:
    def __init__(self, size: int):
        self.size = size + 1
        self.array = [0] * self.size

    def add(self, i, x):
        if not i > 0:
            return
        while i < self.size:
            self.array[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.array[i]
            i -= i & -i
        return s


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) for i in read().split()]
    queries = [() for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries.sort(key=itemgetter(2))
    last = [0] * n
    bit = BIT(n)
    ans = [-1] * q
    cr = 0
    for i, l, r in queries:
        for ri in range(cr, r):
            ci = c[ri] - 1
            bit.add(last[ci], -1)
            last[ci] = ri + 1
            bit.add(last[ci], 1)
            cr = ri
        ans[i] = bit.sum(r) - bit.sum(l - 1)
    print(*ans, sep="\n")


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

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors


tmp = [0]*(N+1)
b = [0]*N
ball_num = 0
ball_box = []
for i in reversed(range(N)):
    if a[i] == 0:
        if (tmp[i+1]%2) == 0:
            continue
        else:
            ball_box.append(i+1)
            ball_num += 1
            val = make_divisors(i+1)
            for elms in val:
                tmp[elms] += 1
    elif a[i] == 1:
        if (tmp[i+1]%2) == 0:
            ball_box.append(i+1)
            ball_num += 1
            val = make_divisors(i+1)
            for elms in val:
                tmp[elms] += 1
        else:
            continue

print(ball_num)
if ball_num != 0:
    print(*ball_box)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
 
 
tmp = [0]*(N+1)
b = [0]*N
ball_num = 0
ball_box = []
for i in reversed(range(N)):
    if a[i] == 0:
        if (tmp[i+1]%2) == 0:
            continue
        else:
            ball_box.append(i+1)
            ball_num += 1
            val = make_divisors(i+1)
            for elms in val:
                tmp[elms] += 1
    elif a[i] == 1:
        if (tmp[i+1]%2) == 0:
            ball_box.append(i+1)
            ball_num += 1
            val = make_divisors(i+1)
            for elms in val:
                tmp[elms] += 1
        else:
            continue
 
print(ball_num)
if ball_num != 0:
    print(*ball_box)
### BUGGY CODE ###

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

max_digit = 0
for i in range(N):
    a[i] = bin(a[i])[2:][::-1]
    max_digit = max(max_digit, len(a[i]))
    
for i in range(N):
    l = '0'*(max_digit-len(a[i]))
    a[i] += l
    a[i] = a[i][::-1]

digits = [0]*max_digit    
for i in range(max_digit):
    for j in range(N):
        if a[j][i] == '1':
            digits[i] += 1
    digits[i] %= 2

ans = ['']*N
for i in range(N):
    num = a[i]
    for j in range(max_digit):
        ans[i] += str((int(num[j]) + digits[j]) % 2)
    ans[i] = str(int(ans[i],2))
        
ans = ' '.join(ans)

print(ans)

### FIXED CODE ###

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

max_digit = 0
for i in range(N):
    a[i] = bin(a[i])[2:][::-1]
    max_digit = max(max_digit, len(a[i]))
    
for i in range(N):
    l = '0'*(max_digit-len(a[i]))
    a[i] += l
    a[i] = a[i][::-1]

digits = [0]*max_digit    
for i in range(max_digit):
    for j in range(N):
        if a[j][i] == '1':
            digits[i] += 1
    digits[i] %= 2

ans = ['']*N
for i in range(N):
    num = a[i]
    for j in range(max_digit):
        ans[i] += str((int(num[j]) + digits[j]) % 2)
    ans[i] = str(int(ans[i],2))
        
ans = ' '.join(ans)

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

import fractions

N = int(input())

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

for j in range(N):

    A_co = A.copy()
    del A_co[j]

    now_gcd = A_co[0]
    
    for i in range(N-2):

        now_gcd = fractions.gcd(now_gcd , A_co[i+1])

    if ans <= now_gcd:
        ans = now_gcd

print (ans)

### FIXED CODE ###

import fractions

N = int(input())

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

L = [0] * N
R = [0] * N

now = A[0]
for i in range(N):

    if i >= 1:

        now = fractions.gcd(now,A[i-1])
        L[i] = now

A.reverse()

now = A[0]
for i in range(N):

    if i >= 1:

        now = fractions.gcd(now,A[i-1])
        R[i] = now

A.reverse()
R.reverse()

maxi = 0
for i in range(N):

    if L[i] == 0 or R[i] == 0:
        maxi = max(maxi,L[i],R[i])

    else:
        maxi = max(maxi, fractions.gcd(L[i],R[i]))

print (maxi)
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0

    while q:
        t, i, j, d = q.pop()

        ni, nj = i + dr[d][0], j + dr[d][1]
        if 0 <= ni < H and 0 <= nj < W:
            if C[ni][nj] != '@':
                timeninj = time[ni][nj]
                if timeninj[d] > t + 1:
                    q.append((t + 1, ni, nj, d))
                    timeninj[d] = t + 1

        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                if nt == t:
                    q.append((nt, i, j, nd))
                else:
                    q.appendleft((nt, i, j, nd))
                timeij[nd] = nt

    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)
### BUGGY CODE ###

a = input().split()
b = input().split()

exlist = []

for i in range(int(a[0])):
    sum = 0
    for j in range(int(b[i])+1):
        sum += j
    exlist.append(sum/int(b[i]))

ans = 0

for i in range(int(a[0])-int(a[1])+1):
    sum = 0
    for j in range(int(a[1])):
        sum += exlist[i+j]
    if ans < sum:
        ans = sum

print(ans)


### FIXED CODE ###

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

sum = 0
ans = 0

for i in range(a[0]):
    sum += (1 + b[i])/2
    if i > a[1]-1:
        sum -= (1 + b[i-a[1]])/2
    if ans < sum:
        ans = sum

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

n = int(input())
ans = n
s = []
for i in range(n):
    temp = input()
    if temp in s:
        ans -= 1
    else:
        s.append(temp)
print(ans)


### FIXED CODE ###

n = int(input())
ans = n
s = set()
for i in range(n):
    s.add(input())
print(len(s))
### BUGGY CODE ###

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

ans = 1
for i in range(a, b + 1):
    ans *= i

if ans > 0:
    print("Positive")
elif ans < 0:
    print("Negative")
elif ans == 0:
    print("Zero")
else:
    pass


### FIXED CODE ###

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

if a > 0 and b > 0:
    print("Positive")
elif a < 0 and b > 0:
    print("Zero")
else:
    if (b - a + 1) % 2 == 0:
        print("Positive")
    else:
        print("Negative")
### BUGGY CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
A = map(int, raw_input().split())

m_fact = {}
def fact(n):
    if n in m_fact:
        return m_fact[n]
    if n == 1:
        m_fact[n] = 1
        return 1
    m_fact[n] = fact(n - 1) * n
    return m_fact[n]

m_rev = {}
def rev_mod(n):
    if n in m_rev:
        return m_rev[n]
    p = MOD - 2
    ret = 1
    p_cur = n
    while p > 0:
        if p % 2:
            ret *= p_cur
            ret %= MOD
        p_cur *= p_cur
        p_cur %= MOD
        p /= 2
    m_rev[n] = ret
    return ret

S = [0] * (N + 2)
S2 = [0] * (N + 2)

for i in range(1, N):
    num = (fact(N) * rev_mod(i + 1)) % MOD
    S[0] += num
    S[0] %= MOD
    S[i] -= num
    S[i] %= MOD
    S[N] -= num
    S[N] %= MOD
    S[N - i] += num
    S[N - i] %= MOD

S[0] += fact(N)
S[0] %= MOD
S[N] -= fact(N)
S[N] %= MOD

for i in range(N):
    S[i + 1] += S[i]
    S[i + 1] %= MOD

for i in range(1, N - 1):
    num = (fact(N) * rev_mod(i + 1) * rev_mod(i + 2) * 2) % MOD
    wid = min(i, N - 1 - i)
    S2[1] += num
    S2[1] %= MOD
    S2[wid + 1] -= num
    S2[wid + 1] %= MOD
    S2[N - wid] -= num
    S2[N - wid] %= MOD

for i in range(N):
    S2[i + 1] += S2[i]
    S2[i + 1] %= MOD

for i in range(N):
    S2[i + 1] += S2[i]
    S2[i + 1] %= MOD

ans = 0
for i in range(N):
    ans += S[i] * A[i]
    ans += S2[i] * A[i]
    ans %= MOD

print ans

### FIXED CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
A = map(int, raw_input().split())

m_fact = {}
def fact(n):
    if n in m_fact:
        return m_fact[n]
    if n == 1:
        m_fact[n] = 1
        return 1
    m_fact[n] = (fact(n - 1) * n) % MOD
    return m_fact[n]

m_rev = {}
def rev_mod(n):
    if n in m_rev:
        return m_rev[n]
    p = MOD - 2
    ret = 1
    p_cur = n
    while p > 0:
        if p % 2:
            ret *= p_cur
            ret %= MOD
        p_cur *= p_cur
        p_cur %= MOD
        p /= 2
    m_rev[n] = ret
    return ret

S = [0] * (N + 2)
S2 = [0] * (N + 2)

for i in range(1, N):
    num = (fact(N) * rev_mod(i + 1)) % MOD
    S[0] += num
    S[0] %= MOD
    S[i] -= num
    S[i] %= MOD
    S[N] -= num
    S[N] %= MOD
    S[N - i] += num
    S[N - i] %= MOD

S[0] += fact(N)
S[0] %= MOD
S[N] -= fact(N)
S[N] %= MOD

for i in range(N):
    S[i + 1] += S[i]
    S[i + 1] %= MOD

for i in range(1, N - 1):
    num = (fact(N) * rev_mod(i + 1) * rev_mod(i + 2) * 2) % MOD
    wid = min(i, N - 1 - i)
    S2[1] += num
    S2[1] %= MOD
    S2[wid + 1] -= num
    S2[wid + 1] %= MOD
    S2[N - wid] -= num
    S2[N - wid] %= MOD

for i in range(N):
    S2[i + 1] += S2[i]
    S2[i + 1] %= MOD

for i in range(N):
    S2[i + 1] += S2[i]
    S2[i + 1] %= MOD

ans = 0
for i in range(N):
    ans += S[i] * A[i]
    ans += S2[i] * A[i]
    ans %= MOD

print ans
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
ans=0
for i in range(1,n):
    ans+=len(make_divisors(n-i))
print(ans)

### FIXED CODE ###

n = int(input())
ans=0
for i in range(1,n):
    ans+=int((n-1)/i)
print(ans)
### BUGGY CODE ###

from itertools import combinations
mod = 10**9+7

N = int(input())
li = list(map(int,input().split()))

ans = 0

for i,j in combinations(li,2):
    ans += (i*j)
    ans = ans%mod
print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
mod = 10**9+7

S = sum(li)
li2 = [x**2 for x in li]
S2 = sum(li2)

print((S**2-S2)//2%mod)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

n=int(input())
S=[]
for i in range(n):
    S.append(input())

a=0

for i in range(n):
    flag=1
    for j in range(n):
        for k in range(j):
            if S[(n+j-i)%n][k] != S[(n+k-i)%n][j]:
                flag=0
                break
    if flag == 1:
        a = a+1

print(a*n)

### FIXED CODE ###

# coding: utf-8
# Your code here!

n=int(input())
S=[]
for i in range(n):
    S.append(input())

a=0

for i in range(n):
    S=[S[-1]]+S[:-1]
#    print(S)
    flag=1
    for j in range(n):
        for k in range(j):
            if S[j][k] != S[k][j]:
                flag=0
                break
    if flag == 1:
        a = a+1

print(a*n)
### BUGGY CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
INF = float("inf")
import sys
sys.setrecursionlimit(10000)

a = []
@lru_cache(None)
def dfs(no, i):
    global a

    ans = abs(a[-1] - a[i])
    for j in range(i + 1, len(a) - 1):
        nex = dfs(1 - no, j + 1)
        # X
        if no % 2 == 0:
            ans = max(ans, nex)
        # Y
        else:
            ans = min(ans, nex)
    return ans


def solve2(N, Z, W):
    global a
    a = [Z, W] + a
    return dfs(0, 1)


def solve(N, Z, W):
    global a
    ans = abs(a[-1] - W)
    if len(a) > 1:
        ans = max(ans, abs(a[-2] - a[-1]))
    return ans


def main():
    global a
    N, Z, W = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve2(N, Z, W))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N, Z, W = map(int, input().split())
    a_list = list(map(int, input().split()))

    ans = 0
    ans = max(ans, abs(a_list[-1] - W))
    if N >= 2:
        ans = max(ans, abs(a_list[-2] - a_list[-1]))
    print(ans)


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

S=input()
Q=int(input())
lis=[]
for _ in range(Q):
    lis.append(input().split())
ans=S
cnt=0
for i in lis:
    if(i[0] == '1'):
        cnt+=1
    elif((cnt % 2 == 0 and i[1]=='1') or (cnt % 2 == 1 and i[1]=='2')):
        ans= i[2] + ans
    else:
        ans+=i[2]

print(ans[::-1]) if(cnt % 2 == 1) else print(ans)


### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
ans=deque(S)
cnt=0
for _ in range(Q):
    i=(input().split())
    if(int(i[0]) == 1):
        cnt= (cnt+1) % 2
    elif((cnt== 0 and i[1]=='1') or (cnt == 1 and i[1]=='2')):
        ans.appendleft(i[2])
    else:
        ans.append(i[2])
ans=''.join(ans)
print(ans[::-1]) if(cnt % 2 == 1) else print(ans)
### BUGGY CODE ###

from collections import deque
def main():
    H, W = list(map(int, input().split()))
    A = [['!'] * (W + 2)] + [['!', ] + list(input()) + ['!', ] for _ in range(H)] + [['!'] * (W + 2)]
    printl = lambda A:[print(''.join(a)) for a in A]
    INF = 100000
    ans = 0
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if A[h][w] == '#': continue
            stack = deque([[h, w], ])
            count = 0
            visited = [[0] * (W + 2) for _ in range(H + 2)]
            score = [[INF] * (W + 2) for _ in range(H + 2)]
            score[h][w] = 0
            f = False
            while stack:
                x, y = stack.popleft()
                if visited[x][y]:
                    continue
                else:
                    visited[x][y] = 1
                for dx, dy in dxy:
                    X, Y = x + dx, y + dy
                    if A[X][Y] == '#':
                        f = True
                        count = score[x][y] + 1
                        break
                    elif A[X][Y] == '.' and visited[X][Y] == 0:
                        stack.append([X, Y])
                        score[X][Y] = min(score[X][Y], score[x][y] + 1)
                if f:
                    break
            ans = max(ans, count)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    B = [(i, j) for i, a in enumerate(A) for j, b in enumerate(a) if b == '#']
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    stack = deque(B)
    colored = len(B)
    tot = h * w
    count = 0
    while colored < tot:
        next = deque([])
        while stack:
            y, x = stack.popleft()
            for dx, dy in dxy:
                X = x + dx
                Y = y + dy
                if X < 0 or X >= w or Y < 0 or Y >= h:
                    continue
                if A[Y][X] == '.':
                    next.append((Y, X))
                    A[Y][X] = '#'
        stack = next
        count += 1
        colored += len(next)
    print(count)

if __name__ == '__main__':
    main()