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

import sys
import bisect
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a,b,q = map(int,readline().split())

jinja = [-(2*10**10+10)]

for i in range(a):
    jinja.append(int(input()))

tera = [-(2*10**10+10)]

for i in range(b):
    tera.append(int(input()))

#add big number
jinja.append(2*10**10+10)
tera.append(2*10**10+10)

for query in range(q):
    x = int(input())
    j_r = bisect.bisect_left(jinja,x)
    j_l = jinja[j_r-1]
    t_r = bisect.bisect_left(tera,x)
    t_l = tera[t_r-1]
    j_r = jinja[j_r]
    t_r = tera[t_r]
    ans = min((x-j_l)*2+(t_r-x),(x-t_l)*2+(j_r-x),(x-j_l)+(t_r-x)*2,(x-t_l)+(j_r-x)*2)
    ans = min (ans,x - min(j_l,t_l), max(j_r,t_r)-x)
    print(ans)


### FIXED CODE ###

import sys
import bisect
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a,b,q = map(int,readline().split())

jinja = [-(10**10+10)]

for i in range(a):
    jinja.append(int(readline()))

tera = [-(10**10+10)]

for i in range(b):
    tera.append(int(readline()))

#add big number
jinja.append(2*10**10+10)
tera.append(2*10**10+10)

for query in range(q):
    x = int(readline())
    j_r = bisect.bisect_left(jinja,x)
    j_l = jinja[j_r-1]
    t_r = bisect.bisect_left(tera,x)
    t_l = tera[t_r-1]
    j_r = jinja[j_r]
    t_r = tera[t_r]
    ans = min((x-j_l)*2+(t_r-x),(x-t_l)*2+(j_r-x),(x-j_l)+(t_r-x)*2,(x-t_l)+(j_r-x)*2)
    ans = min (ans,x - min(j_l,t_l), max(j_r,t_r)-x)
    print(ans)
### BUGGY CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353


def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)
    F = np.zeros(N + 10, np.int64)
    F[0] = 1
    for n in range(1, N + 10):
        F[n] += F[n - 1]
        for k in range(K):
            l, r = L[k], R[k] + 1
            if n - l >= 0:
                F[n] += F[n - l]
            if n - r >= 0:
                F[n] -= F[n - r]
        F[n] %= MOD
    ans = F[N - 1] - F[N - 2]
    return ans % MOD


N, K = map(int, readline().split())
LR = np.array(read().split(), np.int64)

print(main(N, LR))


### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353


@njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)
    F = np.zeros(N + 10, np.int64)
    F[0] = 1
    for n in range(1, N + 10):
        F[n] += F[n - 1]
        for k in range(K):
            l, r = L[k], R[k] + 1
            if n - l >= 0:
                F[n] += F[n - l]
            if n - r >= 0:
                F[n] -= F[n - r]
        F[n] %= MOD
    ans = F[N - 1] - F[N - 2]
    return ans % MOD


N, K = map(int, readline().split())
LR = np.array(read().split(), np.int64)

print(main(N, LR))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 道の接続マップ
route2 = {}

# 接続している部屋のマップ
room_next = [[] for n in range(N)]

for a, b in zip(A, B):
    room_next[a - 1].append(b - 1)
    room_next[b - 1].append(a - 1)

# pprint(room_next)

# route2.update({(a - 1, b - 1): True})
# route2.update({(b - 1, a - 1): True})

# 探索する
room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

# 次に行く部屋
stack = [0]

while stack:
    now = stack.pop()
    for j in room_next[now]:
        # if (now, j) in route2.keys():
        if room_depth[j] is None or room_depth[j] > room_depth[now] + 1:
            room_depth[j] = room_depth[now] + 1
            room_sign[j] = now + 1
            stack.append(j)

print('Yes')
for s in room_sign[1:]:
    print(s)


### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

N=int(input())
S={i:input() for i in range(N)}
value=[]
max=0

for i in S.values():
	N=list(S.values()).count(i)
	if N>max or N==max:
		max=N
for j in S.values():
	M=list(S.values()).count(j)
	if N==M:
		value.append(j)
value=list(set(value))
value.sort()
[print(i) for i in value]

### FIXED CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline())
S = sys.stdin.read().split()
 
count = Counter(S)
max_num = max(count.values())

max_list = [i for i,j in count.items() if j==max_num]
 
max_list.sort()
print('\n'.join(max_list))
### BUGGY CODE ###

import collections

def cmb(n, r):
    if n - r < r: 
      r = n - r
    if r == 0: 
      return 1
    if r == 1: 
      return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result

def solve():
  n = int(input())
  a_list = list(map(int, input().split()))
  for i in range(1, n + 1):
    all = cmb(n - 1, 2)
    ans = 0
    ball_list = collections.Counter(a_list[0:i-1] + a_list[i:n])
    key_list = list(ball_list.keys())
    for i in key_list:
      if ball_list[i] > 1:
        ans += cmb(ball_list[i], 2)
    print(ans)
  return 0

if __name__ == "__main__":
  solve()

### FIXED CODE ###

import numpy as np
import functools
import math
import collections
import scipy
import fractions
import itertools

def solve():
  n = int(input())
  a = list(map(int, input().split()))
  c = collections.Counter(a)
  s = 0
  for i in list(c.values()):
    s += i*(i-1)//2
  for i in a:
    print(s-(c[i]-1))
  return 0
 
if __name__ == "__main__":
  solve()
### BUGGY CODE ###

import heapq

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

BC=[list(map(int,input().split())) for i in range(M)]
[A.extend([C]*B) for B,C in BC]
print(sum(heapq.nlargest(N, A)))


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    A= list(map(int,input().split()))
    A = sorted(A)

    BC=[list(map(int,input().split())) for i in range(M)]
    BC = sorted(BC, key=lambda x: x[1],reverse=True)
    index=0
    max_index=len(A)
    
    for B,C in BC:
        temp = [C]*B
        for t in temp:
            if max_index>index and  t>A[index]:
                A[index] = t
            else:
                return A
            index+=1
    return A
    
if __name__ == '__main__':
    A=main()
    print(sum(A))
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())
point = np.zeros(N, dtype='int') + K
for i in range(Q):
    x = int(input())
    point[x - 1] = point[x - 1] + 1
    point = point - 1
    
for i in range(N):
    if point[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
d = K - Q
point = [0]*N
for i in range(Q):
    point[int(input()) - 1] += 1
    
for i in range(N):
    if point[i] + d > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

K=int(input())
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            t=gcd(i,gcd(j,k))
            ans+=t
print(ans)


### FIXED CODE ###

K=int(input())
def gcd(a,b):
    res=0
    while b!=0:
        res=a%b
        a=b
        b=res
    return a

ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            t=gcd(i,gcd(j,k))
            ans+=t
print(ans)
### BUGGY CODE ###

import collections
 
# A = input()
# A = int(input())
# A = map(int, input().split())
# A = list(map(int, input().split()))
# A = [int(input()) for i in range(N)]
#
# c = collections.Counter()
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]
 
cl = collections.Counter(A)
for key in cl:
  BC.append((cl[key], key))
#BC = [(cl[key], key) for key in cl]
print
BC = sorted(BC, key=lambda x: -x[1])
 
c = 0
total = 0
for (n, key) in BC:
  if (c + n) < N:
    c += n
    total += key * n
  else:
    for i in range(n):
      if c < N:
        c += 1
        total += key

print(total)

### FIXED CODE ###

import collections
 
# A = input()
# A = int(input())
# A = map(int, input().split())
# A = list(map(int, input().split()))
# A = [int(input()) for i in range(N)]
#
# c = collections.Counter()
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]
 
cl = collections.Counter(A)
BC += [(cl[key], key) for key in cl]
BC = sorted(BC, key=lambda x: -x[1])
 
c = 0
total = 0
for (n, key) in BC:
  if (c + n) < N:
    c += n
    total += key * n
  else:
    total += key * (N - c)
    break

print(total)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    answer = 0
    for i in range(N):
        p[i] = (1+p[i])/2
    sum_list = [sum(p[:i]) for i in range(N+1)]
    for i in range(N-K+1):
        answer = max(answer, sum_list[i+K]-sum_list[i])
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    answer = sum(p[0:K])
    r = answer
    for i in range(N-K):
        answer = answer - p[i] + p[i+K]
        r = max(r, answer)
    print((r+K)/2)


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

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

li = []
for i in range(N):
    li.append(A[i] + i)

li.sort()

cnt = 0
for j in range(N):
    cnt += li.count(j - A[j])

print(cnt)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

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

li = []
for i in range(N):
    li.append(A[i] + i)

li.sort()

cnt = 0
for j in range(N):
    target = j - A[j]
    cnt += bisect_right(li, target) - bisect_left(li, target)

print(cnt)
### BUGGY CODE ###

h, w, m = map(int, input().split())

h_bomb = [0 for _ in range(h)]
w_bomb = [0 for _ in range(w)]

bomb_xy = {}
for ij in range(m):
    y, x = map(int, input().split())
    h_bomb[y-1] += 1
    w_bomb[x-1] += 1
    bomb_xy[str(y-1)+str(x-1)] = 1

ans = 0
# print("ans:", ans)
for j in range(h):
    for i in range(w):
        if str(j)+str(i) in bomb_xy:
            temp_max = h_bomb[j] + w_bomb[i] - 1
        else:
            temp_max = h_bomb[j] + w_bomb[i]

        # print("temp:", temp_max)
        if temp_max > ans:
            ans = temp_max

print(ans)


### FIXED CODE ###

import sys

h, w, m = map(int, input().split())

h_bomb = [0 for _ in range(h)]
w_bomb = [0 for _ in range(w)]

bomb_xy = {}
for ij in range(m):
    y, x = map(int, input().split())
    h_bomb[y-1] += 1
    w_bomb[x-1] += 1
    bomb_xy[str(y-1)+str(x-1)] = 1

h_max = max(h_bomb)
h_max_index = [i for i, y in enumerate(h_bomb) if y == h_max]
w_max = max(w_bomb)
w_max_index = [j for j, x in enumerate(w_bomb) if x == w_max]

ans = 0
# print("ans:", ans)
for j in h_max_index:
    for i in w_max_index:
        if str(j)+str(i) in bomb_xy:
            ans = h_bomb[j] + w_bomb[i] - 1
        else:
            print(h_bomb[j] + w_bomb[i])
            sys.exit()

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

import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

INF = float('inf')
dist1 = [[INF]*N for i in range(N)]
dist2 = [[INF]*N for i in range(N)]
for a,b,c in ABC:
    if c > L: continue
    a,b = a-1,b-1
    dist1[a][b] = dist1[b][a] = c
for i in range(N):
    dist1[i][i] = 0
    dist2[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist1[i][j] = min(dist1[i][j], dist1[i][k] + dist1[k][j])
for i in range(N):
    for j in range(N):
        if i==j: continue
        if dist1[i][j] <= L:
            dist2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist2[i][j] = min(dist2[i][j], dist2[i][k] + dist2[k][j])

ans = []
for s,t in ST:
    d = dist2[s-1][t-1]
    if d == INF:
        ans.append(-1)
    else:
        ans.append(d-1)
print(*ans, sep='\n')

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

INF = float('inf')
dist1 = [[INF]*N for i in range(N)]
dist2 = [[INF]*N for i in range(N)]
for a,b,c in ABC:
    if c > L: continue
    a,b = a-1,b-1
    dist1[a][b] = dist1[b][a] = c
for i in range(N):
    dist1[i][i] = 0
    dist2[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist1[i][k] + dist1[k][j]
            if dist1[i][j] <= d: continue
            dist1[i][j] = d
for i in range(N):
    for j in range(N):
        if i==j: continue
        if dist1[i][j] <= L:
            dist2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist2[i][k] + dist2[k][j]
            if dist2[i][j] <= d: continue
            dist2[i][j] = d
ans = []
for s,t in ST:
    d = dist2[s-1][t-1]
    if d == INF:
        ans.append(-1)
    else:
        ans.append(d-1)
print(*ans, sep='\n')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

INF = float("INF")


def run(cost, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                cost[i][j] = min(
                    cost[i][j],
                    cost[i][k] + cost[k][j])
    return cost


if __name__ == '__main__':
    N, M, L = map(int, input().split())

    cost = [[INF] * N for _ in range(N)]
    for i in range(N):
        cost[i][i] = 0

    for _ in range(M):
        v1, v2, w = map(int, input().split())
        v1, v2 = v1-1, v2-1
        cost[v1][v2] = w
        cost[v2][v1] = w
    cost = run(cost, N)

    for i in range(N):
        for j in range(N):
            if cost[i][j] == 0:
                pass
            elif cost[i][j] <= L:
                cost[i][j] = 1
            else:
                cost[i][j] = INF
    cost = run(cost, N)

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        ans = cost[s-1][t-1]
        if ans == INF:
            print(-1)
        else:
            print(ans - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def solve():
    N, K = map(int, input().split())
    AB = [sorted([int(i) for i in input().split()]) for _ in range(N - 1)]
    AB.sort()
    p = 1
    pattern = 1
    print(dfs(AB, 1, 0, 0, 1, K, 0) % (10 ** 9 + 7))


def dfs(hen, cho, kai, ko, tag, K, oya):
    tag *= K - (ko - 1 if ko > 0 else 0) - (2 if kai >= 2 else kai)
    next_ko = []
    for h in hen:
        if cho in h and not (oya in h):
            x = h[0] if h[1] == cho else h[1]
            next_ko.append(x)
    # print(cho, ko, kai, next_ko, tag)
    # print(K - (ko - 1 if ko > 0 else 0))
    # print((2 if kai >= 2 else kai))
    # input()
    # print(cho, next_ko)
    # input()
    for i in range(len(next_ko)):
        tag = dfs(hen, next_ko[i], kai + 1, i + 1, tag, K, cho)
    return tag


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def solve():
    N, K = map(int, input().split())
    AB = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)

    # AB = [sorted([int(i) for i in input().split()]) for _ in range(N - 1)]
    # AB.sort()
    print(dfs(AB, 1, 0, 0, 1, K, 0) % (10 ** 9 + 7))


def dfs(hen, cho, kai, ko, tag, K, oya):
    tag *= K - (ko - 1 if ko > 0 else 0) - (2 if kai >= 2 else kai)
    next_ko = hen[cho].copy()
    if oya != 0:
        next_ko.remove(oya)
    for i in range(len(next_ko)):
        tag = dfs(hen, next_ko[i], kai + 1, i + 1, tag, K, cho)
    return tag % (10 ** 9 + 7)


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

n = int(input())
l = list(map(int, input().split()))

ans = round(n*(n-1)*(n-2)/6)
b=0

l.sort()

for i in range(n):
    for j in range(i+1,n):
        b = l[i] + l[j]
        for k in range(j+1,n):
            if b>l[k]:
                continue
            else:
                ans-=n-k
                break

if ans<0:
    ans=0

print(ans)

### FIXED CODE ###

import bisect
n = int(input())
li = list(map(int, input().split()))

li.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        ans += bisect.bisect_left(li, li[i]+li[j]) - j - 1

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

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
for zzz in range(Q):
    x=int(input())
    value=2*10**10
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if 0<= s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                if 0<= t < B:
                    value=min(max(x,S[s])-min(x,S[s]) + max(S[s],T[t])-min(S[s],T[t]),value)
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if 0<= t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                if 0<= s < A:
                    value=min(max(x,T[t])-min(x,T[t]) + max(S[s],T[t])-min(S[s],T[t]),value)

    print(value)


### FIXED CODE ###

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
X=[int(input()) for i in range(Q)]
value1=2*(10**10)
for x in X:
    value=value1
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if -1< s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                a=0
                if -1< t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if -1< t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                a=0
                if -1< s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a

    print(value)
### BUGGY CODE ###

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

rev = False
for _ in range(q):
    query = input().split()

    if query[0] == '1' and not(rev):
        rev = True
    elif query[0] == '1' and rev:
        rev = False

    elif query[0] == '2' and query[1] == '1' and not(rev):
        s = query[2] + s
    elif query[0] == '2' and query[1] == '1' and rev:
        s += query[2]

    elif query[0] == '2' and query[1] == '2' and not(rev):
        s += query[2]
    elif query[0] == '2' and query[1] == '2' and rev:
        s = query[2]+s

if rev:
    s=s[::-1]

print(s)


### FIXED CODE ###

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

sl = ['']*(q*2+2)
sl[q] = s
m = q-1
u = q+1
rev = False
for _ in range(q):
    query = input().split()

    if query[0] == '1' and not(rev):
        rev = True
    elif query[0] == '1' and rev:
        rev = False

    elif query[0] == '2' and query[1] == '1' and not(rev):
        sl[m] = query[2]
        m -= 1

    elif query[0] == '2' and query[1] == '1' and rev:
        sl[u] = query[2]
        u += 1

    elif query[0] == '2' and query[1] == '2' and not(rev):
        sl[u] = query[2]
        u += 1

    elif query[0] == '2' and query[1] == '2' and rev:
        sl[m] = query[2]
        m -= 1

if rev:
    sl[q] = s[::-1]
    sl.reverse()
    print(''.join(sl))
else:
    print(''.join(sl))
### BUGGY CODE ###

n, play = map(int, input().split())
card = list(map(int, input().split()))
card.sort()
for i in range(play):
  n, c = map(int, input().split())
  for i in range(n):
    step = 0
    if card[step] < c:
      card[step] = c
      card.sort()
    else:
      step += 1
print(sum(card))
        

### FIXED CODE ###

n, play = map(int, input().split())
card = list(map(int, input().split()))
card.sort()
# カードのリスト化を全操作済み
bc = [list(map(int, input().split())) for _ in range(play)]
bc.sort(key=lambda x:x[1], reverse=True)

arr = []
sum_b = 0
for b, c in bc:
  arr += [c]*b
  sum_b += b
  if sum_b >= n:
    break
# 最初のカードを連結
arr += card    
arr.sort(reverse=True)
# カード枚数分合計
print(sum(arr[:n]))
### BUGGY CODE ###

def main():
    from itertools import accumulate

    n, k = map(int, input().split())
    *a, = map(int, input().split())

    acc = (0,) + tuple(accumulate((a)))

    bits = [0] * 40

    seg_idx = 0
    for r in range(1, n + 1):
        for l in range(r):
            b = acc[r] - acc[l]
            for j in range(40):
                if (b >> j) & 1:
                    bits[j] |= (1 << seg_idx)
            seg_idx += 1

    ret = 0
    t = (1 << seg_idx) - 1
    for j in range(39, -1, -1):
        s = t & bits[j]
        if bin(s).count('1') >= k:
            ret |= (1 << j)
            t = s
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import log, ceil

n, k = map(int, input().split())
a = tuple(map(int, input().split()))

A_MAX = 10 ** 9
MAX_BIT_LENGTH = ceil(log(A_MAX * n, 2))

cs = [0]
t = 0
for aa in a:
    t += aa
    cs.append(t)

ps = []
for r in range(1, n + 1):
    for l in range(r):
        ps.append(cs[r] - cs[l])

ans = 0
for b in range(MAX_BIT_LENGTH)[::-1]:
    cnt = 0
    t = ans + (1 << b)
    for p in ps:
        if p & t == t:
            cnt += 1
            if cnt == k:
                ans = t
                break

print(ans)