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

import collections
import sys

sys.setrecursionlimit(10 ** 6)

N = int(input())
colors = [int(x) - 1 for x in input().split()]
neighbors = collections.defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    neighbors[a - 1].append(b - 1)
    neighbors[b - 1].append(a - 1)

subtree_sizes = [0] * N


def calc_sizes(node, parent):
    size = 1
    for i in neighbors[node]:
        if i != parent:
            size += calc_sizes(i, node)
    subtree_sizes[node] = size
    return size


calc_sizes(0, -1)
components = {c: {0: N} for c in range(N)}
components[colors[0]] = {}
color_stack = {c: [0] for c in range(N)}
color_stack[colors[0]] = []


def calc_components(node, parent):
    color_stack_pushed = False
    if parent >= 0 and colors[parent] != colors[node]:
        color_parent = color_stack[colors[node]][-1]
        components[colors[node]][color_parent] -= subtree_sizes[node]
        components[colors[parent]][node] = subtree_sizes[node]
        color_stack[colors[parent]].append(node)
        color_stack_pushed = True
    for i in neighbors[node]:
        if i != parent:
            calc_components(i, node)
    if color_stack_pushed:
        color_stack[colors[parent]].pop()


calc_components(0, -1)


def count_paths(n):
    return n * (n + 1) // 2


total_paths = count_paths(subtree_sizes[0])
for c in range(N):
    print(total_paths - sum(count_paths(size) for size in components[c].values()))


### FIXED CODE ###

import collections
import sys

sys.setrecursionlimit(10 ** 6)

N = int(input())
colors = [int(x) - 1 for x in input().split()]
neighbors = collections.defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    neighbors[a - 1].append(b - 1)
    neighbors[b - 1].append(a - 1)

subtree_sizes = [0] * N


def calc_sizes(node, parent):
    sz = 1
    for i in neighbors[node]:
        if i != parent:
            sz += calc_sizes(i, node)
    subtree_sizes[node] = sz
    return sz


calc_sizes(0, -1)
components = {c: {0: N} for c in range(N)}
components[colors[0]] = {}
color_stack = {c: [0] for c in range(N)}
color_stack[colors[0]] = []


def calc_components(node, parent):
    color_stack_pushed = False
    if parent >= 0 and colors[parent] != colors[node]:
        color_parent = color_stack[colors[node]][-1]
        components[colors[node]][color_parent] -= subtree_sizes[node]
        components[colors[parent]][node] = subtree_sizes[node]
        color_stack[colors[parent]].append(node)
        color_stack_pushed = True
    for i in neighbors[node]:
        if i != parent:
            calc_components(i, node)
    if color_stack_pushed:
        color_stack[colors[parent]].pop()


calc_components(0, -1)


def count_paths(n):
    return n * (n + 1) // 2


total_paths = count_paths(subtree_sizes[0])
for c in range(N):
    print(total_paths - sum(count_paths(size) for size in components[c].values()))
### BUGGY CODE ###

import numpy as np

def update(A, N):
    B = [0] * N
    for i in range(0, N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if (r + 1 < N):
            B[r + 1] -= 1
    return np.cumsum(B)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(0, min(100, K)):
        A = update(A, N)
    print(" ".join([str(item) for item in A]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

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

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

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

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

N = int(input()) #社員数
joushi_no_bangou = [0] #上司の社員番号
ans = []
joushi_no_bangou += map(int,input().split())

#==--------------

for i in range(N):
    if i+1 not in joushi_no_bangou:
        print(0)
    else:
        print(joushi_no_bangou.count(i+1))

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
ct = [0] * N
     
for a in As: #ここがキモ．リスト「As」にはそれぞれの上司が入っていて，その中からaを取り出すので，a=上司になっている．これにより，ctの上司を正確に呼び出すことができる．
    ct[a-1] += 1
     
for c in ct:
    print(c)

#別解
#print(*c,sep='\n')
### BUGGY CODE ###

n,m = map(int, input().split())
ns = set(i+1 for i in range(n))
for i in range(m):
    l, r = map(int, input().split())
    ns &= set(j for j in range(l, r+1))
print(len(ns))

### FIXED CODE ###

n,m = map(int, input().split())
ns = set(i+1 for i in range(n))
l_min = 0
r_max = n
for i in range(m):
    l, r = map(int, input().split())
    l_min = max(l_min, l)
    r_max = min(r_max, r)
print(max(r_max - l_min+1, 0))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
result = 1
for i in a:
    result *= i
    if i == 0:
        break
if result > 10**18:
    print(-1)
else:
    print(result)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
result = 1
overflow = False
for i in a:
    result *= i
    if result > 1e18:
        result = 1
        overflow = True
if result != 0 and overflow:
    print(-1)
else:
    print(result)
### BUGGY CODE ###

n, m = map(int, input().split())

A = [0]*m
C = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    cs = list(map(int, input().split()))
    c = 0
    for c_ in cs:
        c += 1 << (c_-1)
    C[i] = c

dp = [float('inf')]*(1 << n)
dp[0] = 0
for i in range(1 << n):
    for j in range(m):
        c = C[j]
        dp[i|c] = min(dp[i|c], dp[i]+A[j])

if dp[-1] != float('inf'):
    print(dp[-1])
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

dp = [float('inf')]*(1<<n)
dp[0] = 0

for i in range(m):
  a, b = map(int, input().split())
  c = 0
  for j in list(map(int, input().split())):
    c += 1<<(j-1)
  
  for k in range(1<<n):
    dp[k|c] = min(dp[k|c], dp[k]+a)
    
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])
### BUGGY CODE ###

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

import numpy as np

N = int(readline())
A = np.array(read().split(), np.int8)

counter = np.bincount(A,minlength=4)
S = A.sum()

B = (counter[2]+counter[3])
C = counter[3]

dp = np.zeros((B+1,C+1),np.float64)

p2 = np.tile(np.arange(B+1)[:,None],(1,C+1))/N
p3 = np.tile(np.arange(C+1)[None,:],(B+1,1))/N
p_rest = 1-p2-p3

bc = np.arange(B+1)[:,None]*2+np.arange(C+1)[None,:]*3

for n in range(1,S+1):
    prev = dp
    one = n-bc
    p1 = np.maximum(0,one/N)
    dp = np.ones_like(prev)
    dp += p1*prev
    dp[1:] += p2[1:]*prev[:-1]
    dp[:-1,1:] += p3[:-1,1:]*prev[1:,:-1]
    dp /= (p1+p2+p3)

answer = dp[B-C,C]
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
N = int(input())

sushi = np.bincount(np.array(input().split(), dtype=np.int8),minlength=4)
total = (sushi * np.arange(4)).sum()

# a,b,c = 1個、2個、3個
# S = a + 2b + 3c：total スシ
# S の小さい方から求めていく
# S ごとには、b,c だけ持てば a が分かる

b = np.arange(N+1)[:,None]
c = np.arange(N+1)[None,:]
S_bc = 2 * b + 3 * c
dp = np.zeros((N+1,N+1))
for S in range(1,total+1):
    prev = dp
    a = S - S_bc
    dp = prev * a + N
    dp[1:] += prev[:-1] * b[1:]
    dp[:-1,1:] += prev[1:,:-1] * c[:,1:]
    dp /= (a+b+c)
    dp[a < 0] = 0

answer = dp[sushi[2],sushi[3]]
print(answer)
### BUGGY CODE ###

import itertools

def q49(n, k, h):
    a = []
    for i in itertools.combinations(h, k):
        mi = min(i)
        ma = max(i)
        a.append(ma - mi)
    return min(a)
            
N, K = [int(i) for i in input().split()]
h = []
for _ in range(N):
    h.append(int(input()))
print(q49(N, K, h))

### FIXED CODE ###

import itertools

def q49(n, k, h):
    h.sort()
    a = [h[i+k-1]-h[i] for i in range(n-k+1)]
    return min(a)
            
N, K = [int(i) for i in input().split()]
h = []
for _ in range(N):
    h.append(int(input()))
print(q49(N, K, h))
### BUGGY CODE ###

n, m = map(int, input().split())
ab = []

for i in range(m):
  a, b = map(int, input().split())
  if a == 1 or b == n:
    ab.append((a,b))

x = len(ab) # length ab
for i in range(x):
  for j in range(x):
    if ab[i][0] == ab[j][1]:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n, m = map(int, input().split())
a1 = []
bn = []

for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    a1.append(b)
  elif b == n:
    bn.append(a)
la = len(a1)
lb = len(bn)
sa = set(a1)
sb = set(bn)
if len(sa | sb) < la + lb:
  print('POSSIBLE')
  exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

n, m = map(int, input().split())
numlist = []
record = [0] * (n-1)
route = []
flag = 0
for i in range(m):
    temp = list(map(int, input().split()))
    if(temp[0] == 1):
        m -= 1
        record[temp[1] - 2] = 1
        flag += 1
        route.append(temp[1])
    elif(temp[1] == 1):
        m -= 1
        record[temp[0] - 2] = 1
        flag += 1
        route.append(temp[0])
    else:
        numlist += temp
newlist = []
while(flag < n-1):
    newroute = []
    for i in range(len(route)):
        for j in range(m):
            if(numlist[j * 2] == route[i]):
                m -= 1
                if(record[numlist[j * 2 + 1] - 2] == 0):
                    record[numlist[j * 2 + 1] - 2] = route[i]
                    flag += 1
                newroute.append(numlist[j * 2 + 1])
            elif(numlist[j * 2 + 1] == route[i]):
                m -= 1
                if(record[numlist[j * 2] - 2] == 0):
                    record[numlist[j * 2] - 2] = route[i]
                    flag += 1
                newroute.append(numlist[j * 2])
            else:
                newlist += numlist[j*2:j*2 + 2]
        numlist = newlist
        newlist = []
    route = newroute
print("Yes")
for i in record:
    print(i)

### FIXED CODE ###

import queue
n, m = map(int, input().split())
graph = [[] for i in range(n)]
depth = [-1] * n
route = []
result = [0] * (n - 1)
for i in range(m):
    temp = list(map(int, input().split()))
    graph[temp[0] - 1].append(temp[1] - 1)
    graph[temp[1] - 1].append(temp[0] - 1)
    route.append(temp)
q = queue.Queue()
q.put(0)
depth[0] = 0
for i in range(n-1):
    item = q.get()
    for j in graph[item]:
        if(depth[j] == -1):
            q.put(j)
            depth[j] = depth[item] + 1
print("Yes")
for i in route:
    if(i[0] == 1):
        result[i[1] - 2] = 1
    elif(i[1] == 1):
        result[i[0] - 2] = 1
    elif(depth[i[0] - 1] - depth[i[1] - 1] == 1):
        result[i[0] - 2] = i[1]
    elif(depth[i[1] - 1] - depth[i[0] - 1] == 1):
        result[i[1] - 2] = i[0]
for i in result:
    print(i)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2000)


def dfs(now):
    if now == x:
        print(1)
        exit()
    elif now > x:
        return False
    for i in range(6):
        if (dfs(now + 100 + i)):
            pass


x = int(input())
if x >= 2100:
    print(1)
else:
    dfs(0)
    print(0)


### FIXED CODE ###

x = int(input())
if x >= 2100:
    print(1)
else:
    for i in range(1, 21):
        x -= 100
        if x < 0:
            break
        if x in range(0, i * 5 + 1):
            print(1)
            exit()
    print(0)
### BUGGY CODE ###

# C
N = int(input())
D = sorted(list(map(int, input().split())))
center = len(D)//2
cnt = 0
for k in range(min(D), max(D)+1):
    for i in range(len(D)):
        if D[i] >= k:
            break
    if center == i:
        cnt += 1
print(cnt)


### FIXED CODE ###

# C
import math
N = int(input())
D = sorted(list(map(int, input().split())))
print(D[math.ceil((N)/2)] - D[math.ceil((N)/2)-1])
### BUGGY CODE ###

n = int(input())
s_list = []
anagrams = []
ans = 0

for i in range(n):
    s = list(input())
    s = sorted(s)
    s_list.append(s)

for i in range(n):
    for j in range(i+1,n):
#        print(s_list[i],s_list[j])
        if s_list[i] == s_list[j]:
            ans = ans + 1
#        print(i,j)

print(ans)


### FIXED CODE ###

n = int(input())
dict = {}
ans = 0

for i in range(n):
    s = ''
    list = sorted(input())
    for j in list:
        s += j
    if i != 0 and s in dict.keys():
        ans += dict[s]
        dict[s] += 1
    else:
        dict[s] = 1

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


INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def query2(s,f,c,ct):
    if ct%2==1:
        s=s[::-1]
    
    if f=='1':
        s=c+s
    else:
        s=s+c
    
    return s
    
def do():
    S=STR()
    q=INT()
    ct=0
    for i in range(q):
        qt=LISTS()
        if qt[0]=='1':
            ct+=1
        else:
            S=query2(S,qt[1],qt[2],ct)
            ct=0
    
    if ct%2==1:
        S=S[::-1]
    
    print(S)
    
if __name__ == '__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    q=INT()
    l=''
    r=''
    ct=0
    for i in range(q):
        fc=LISTS()
        if fc[0]=="1":
            ct+=1
        else:
            if fc[1]=="1":
                if ct%2==0:
                    l=fc[2]+l
                else:
                    r=r+fc[2]
            else:
                if ct%2==1:
                    l=fc[2]+l
                else:
                    r=r+fc[2]
    
    sums=l+s+r
    if ct%2==1:
        ans=""
        for i in range(len(sums)-1,-1,-1):
            ans=ans+sums[i]
    else:
        ans=sums
    
    print(ans)
                
if __name__ == '__main__':
    do()
### BUGGY CODE ###

def get_input_line():
    return list(map(int, input().split()))
n, k = get_input_line()
p_list = get_input_line()

def calc_dice_score(p):
    return 0.5*(p+1)

def calc_score(score_list):
    return sum(score_list)

dice_scores = [0.5*(p+1) for p in p_list]

score_list = []

for i in range(n- k + 1):
    score_list.append(sum(dice_scores[i:i+k]))
print(max(score_list))

### FIXED CODE ###

import collections

def get_input_line():
    return list(map(int, input().split()))
n, k = get_input_line()
p_list = get_input_line()

def calc_dice_score(p):
    return 0.5*(p+1)

def calc_score(score_list):
    return sum(score_list)

dice_scores = [0] * n

max_score = 0
tmp_score = 0

for i in range(k):
    dice_scores[i] = 0.5*(p_list[i]+1)
    tmp_score += dice_scores[i]

max_score = tmp_score
for i in range(1, n- k + 1):
    dice_scores[i+k-1] = 0.5*(p_list[i+k-1]+1)
    tmp_score -= dice_scores[i-1]
    tmp_score += dice_scores[i+k-1]
    max_score = max(max_score, tmp_score)
print(max_score)
### BUGGY CODE ###

N = int(input())
k = list(map(int, input().split()))
d = {}
for i in range(N):
    if k[i] in d:
        d[k[i]] += 1
    else:
        d[k[i]] = 1

for i in range(N):
    res = 0

    for key in d:
        if d[key]>1:
            if key == k[i]:
                res += (d[key]-1)*(d[key]-2)/2
            else:
                res += d[key]*(d[key]-1)/2
    print(int(res))

### FIXED CODE ###

N = int(input())
k = list(map(int, input().split()))
d = {}
dd = {}
for i in range(N):
    a = k[i]
    if a in d:
        d[a] += 1
    else:
        d[a] = 1
tot = 0
for key in d:
    a = d[key]
    dd[key] = int(a*(a-1)/2)
    tot += dd[key]
for i in range(N):
    print(tot - d[k[i]]+1)
### BUGGY CODE ###

N,K = map(int,input().split())
pls = list(map(int,input().split()))
ans = 0
for i in range(N-K+1):
    sum1 = sum(pls[i:i+K])/2 + 0.5*K   
    ans = max(ans,sum1) 
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
pls = list(map(int,input().split()))
ans = sum(pls[:K])/2 + 0.5*K
sum1 = ans
for i in range(1,N-K+1):
    sum1 += -pls[i-1]/2+pls[i+K-1]/2
    ans = max(ans,sum1) 
print(ans)
### BUGGY CODE ###

inpvals = []
lopvals = []
outvals = []

max_loop = int(input())
idx_loop = 0
while idx_loop < max_loop :
  inpvals.append(input())
  idx_loop = idx_loop+1

max_cnt = 0
lopvals = set(inpvals)
for inpval in lopvals :
  cnt = inpvals.count(inpval)

  if max_cnt <= cnt :
    if max_cnt != cnt :
      outvals = []
    max_cnt = cnt
    outvals.append(inpval)

outvals.sort()
    
for outval in outvals :
  print(outval)

### FIXED CODE ###

from collections import defaultdict
from collections import OrderedDict

N = int(input())

words = dict()
wordsFromValue = defaultdict(list)

for idx in range(N) :
  word = str(input())
  
  if word in words :
    words[word] += 1
  else :
    words[word] = 1
  
for key, value in sorted(words.items()) :
  wordsFromValue[value].append(key)
  

for val in wordsFromValue[max(wordsFromValue)] : 
  print(val)
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
import numpy as np
 
def main():
    H,W,K = map(int,input().split())
    a = [input() for _ in range(H)]
    
    x = np.zeros((H,W+1),dtype=int)
    for i in range(H):
        for j in range(W):
            if a[i][j] == "1":
                x[i][j+1] = 1
            else:
                x[i][j+1] = 0

    ans = 10**5
    for i in range(1<<H-1):
        use = np.zeros((H,W+1),dtype=int)
        u,now,count = 0,0,0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                count += 1
                bl = x[u:j+1,:]
                bl = np.sum(bl,axis=0)
                u = j+1
                use[now] = bl
                now += 1
        bl = np.sum(x[u:,:],axis=0)
        use[now] = bl
        r,vol = 1,np.zeros((H,1),dtype=int)
        while r<=W:
            vol += use[:,r].reshape(-1,1)
            if np.max(vol)>K:
                count += 1
                vol = np.zeros((H,1),dtype=int)
                vol += use[:,r].reshape(-1,1)
            r += 1
        ans = min(ans,count)
        
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = S = [list(map(int, list(input()))) for _ in range(H)]
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
arr = [r, g, b]
arr.sort()
ans = 0
tmp = 0
for i in range(n // arr[2] + 1):
    for j in range(n // arr[1] + 1):
        tmp = arr[2] * i + arr[1] * j
        if tmp == n:
            ans += 1
        if n - tmp > 0 and (n - tmp) % arr[0] == 0:
            ans += 1

print(ans)


### FIXED CODE ###

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

R, G, B, N = map(int, input().split())
ans = 0
r=0
while r*R <= N:
    g=0
    while r*R + g*G <= N:
        if (N - r*R - g*G) % B == 0:
            ans += 1
        g += 1
    r += 1
print(ans)


### FIXED CODE ###

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

from collections import defaultdict

S = input()

d = defaultdict(int)

d[0] += 1

for i in range(len(S)):
    mod = int(S[i:]) % 2019
    d[mod] += 1

ans = 0
for i in d.values():
    if i > 1:
        ans += i * (i - 1) / 2

print(int(ans))


### FIXED CODE ###

from collections import defaultdict

S = input()

d = defaultdict(int)

d[0] += 1

mod = 0
R = 1
for i in range(len(S)):
    mod = (mod + R * int(S[len(S) - i - 1])) % 2019
    R = R * 10 % 2019
    d[mod] += 1
ans = 0
for i in d.values():
    if i > 1:
        ans += i * (i - 1) / 2

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

import sys


input = sys.stdin.readline

N, Q = map(int, input().split())
S = input()
qlist = [(int(n)-1 for n in input().split()) for _ in range(Q)]
for l, r in qlist:
    count = 0
    while l < r:
        if S[l]+S[l+1] == "AC":
            count += 1
        if S[r-1]+S[r] == "AC":
            count += 1
        l += 1
        r -= 1
    print(count)

### FIXED CODE ###

import sys


input = sys.stdin.readline

N, Q = map(int, input().split())
S = list(input())
anum = [0]*N
for i in range(1, N):
    if S[i-1] == "A" and S[i] == "C":
        S[i-1] = "a"
        anum[i] += 1
    anum[i] += anum[i-1]
qnum = [map(int, input().split()) for _ in range(Q)]
for l, r in qnum:
    print(anum[r-1]-anum[l-1])
### BUGGY CODE ###

q = int(input())
a = []

for i in range(q):
    ops= list(map(int,input().split()))
    if ops[0] == 0:
        if ops[1] == 0:
            a.insert(0,ops[2])
        else:
            a.append(ops[2])
    elif ops[0] == 1:
        print(a[ops[1]])
    else:
        if ops[1] == 0:
            a.pop(0)
        else:
            a.pop(-1)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 14:53:50 2018
ITP21B
@author: maezawa
"""

from collections import deque

d = deque()

n = int(input())

for i in range(n):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if c[1] == 0:
            d.appendleft(c[2])
        else:
            d.append(c[2])
    elif c[0] == 1:
        print(d[c[1]])
    else:
        if c[1] == 0:
            d.popleft()
        else:
            d.pop()