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

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,m,q = ma()
L_rs=[[] for i in range(n)]
for i in range(m):
    l,r=ma()
    L_rs[l-1].append(r-1)
for i in range(n):
    L_rs[i].sort()
# print(L_rs)
def isok(num,val):##適宜変更
    return num<=val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ

def solve(L,R):##0idx
    ret=0
    for l in range(L,R+1):
        ret+=bisect(L_rs[l],R)+1
    return ret
for i in range(q):
    l,r=ma()
    print(solve(l-1,r-1))


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,m,q = ma()
L_rs=[[] for i in range(n)]
for i in range(m):
    l,r=ma()
    L_rs[l-1].append(r-1)
for i in range(n):
    L_rs[i].sort()
# print(L_rs)
def isok(num,val):##適宜変更
    return num<=val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ

ans = [[0]*(n+1) for i in range(n+1)]
for r in range(n):
    for l in range(r,-1,-1):
        ans[l][r]=ans[l+1][r] + bisect(L_rs[l],r)+1

for i in range(q):
    l,r=ma()
    print(ans[l-1][r-1])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(input().split())

SET = set()
ans = []
for i in range(1, K+1):
    lis = []
    s = set()
    for j in range(i):
        for a in As:
            if a in s:
                lis = lis[:lis.index(a)]
                s = set(lis)
            else:
                s.add(a)
                lis.append(a)
    string = ' '.join(lis)
    if string in SET:
        break
    SET.add(string)
    ans.append(string)

if i==1:
    print(ans[0])
else:
    print(ans[K%(i-1)-1])

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(mapint())
double_As = As*2
idx_dic = {}
idx_lis = [N+1]*(2*N)
for i in range(N*2-1, -1, -1):
    a = double_As[i]
    if a in idx_dic:
        idx_lis[i] = idx_dic[a]+1
    idx_dic[a] = i
doubling = [[0]*N for _ in range(60)]
accum = [[0]*N for _ in range(60)]
doubling[0] = [i%N for i in idx_lis[:N]]
accum[0] = [a-i for i, a in enumerate(idx_lis[:N])]
for i in range(1, 60):
    for j in range(N):
        doubling[i][j] = doubling[i-1][doubling[i-1][j]]
        accum[i][j] = accum[i-1][j] + accum[i-1][doubling[i-1][j]]
now = 0
cum = 0
cnt = 0
for i in range(59, -1, -1):
    if cum + accum[i][now]>N*K:
        continue
    else:
        cum += accum[i][now]
        now = doubling[i][now]
ans = []
while cum<N*K:
    if cum+accum[0][now]<=N*K:
        cum += accum[0][now]
        now = doubling[0][now]
    else:
        ans.append(As[now])
        now += 1
        cum += 1
print(*ans)
### BUGGY CODE ###

s=input()
k=int(input())
ans=0
for i in range(len(s)):
    ans+=int(s[i])**500000000000
    if ans>=k:
        print(s[i])
        break

### FIXED CODE ###

s=input()
k=int(input())
for i in range(k):
    if s[i]!="1":
        print(s[i])
        break
    if i==k-1:
        print(1)
### BUGGY CODE ###

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

dp = [[0 for _ in range(S+1)] for __ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += 2 * dp[i][j]
        dp[i+1][j] %= MOD
        if j+A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
            dp[i+1][j+A[i]] %= MOD

print(dp[N][S])

### FIXED CODE ###

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

dp = [[0 for _ in range(S+1)] for __ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += 2 * dp[i][j]
        dp[i+1][j] %= MOD
        if j+A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
            dp[i+1][j+A[i]] %= MOD

print(dp[N][S])
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(c) for c in input().split()]
F = [int(c) for c in input().split()]
A.sort()
F.sort(reverse=True)
M = 0
for i in range(N):
  if A[i]*F[i]>M:
    M = A[i]*F[i]

l = -1
r = M+1
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for i in range(N):
    b = s//F[i]
    cnt += max(0, A[i]-b)
  if cnt>K:
    l = s
  else:
    r = s

print(r)

### FIXED CODE ###

N, K = map(int, input().split())
a = [int(c) for c in input().split()]
f = [int(c) for c in input().split()]
a.sort()
f.sort(reverse=True)
def check(n):
  m = K
  for i in range(N):
    m -= max(0, a[i]-n//f[i])
    if m<0:
      return False
  return True
r = 0
l = a[-1]*f[0]
X = (l-r)//2+r
while not (check(X)^check(X+1)) :
  if check(X):
    l = l - (l-r)//2
  else:
    r = (l-r)//2 + r
  X = (l-r)//2+r
  if check(0):
    print(0)
    break
else:
  print(X+1)
### BUGGY CODE ###

N=int(input())
S=input()
max=0
A = [0] *len(S)
for f in range(len(S)-1):
    i = f+1
    A[f]=len(S)
    while(i<len(S)):
        j=0
        while(i+j<len(S) and S[f+j]==S[i+j] and f+j<i):
            j+=1
        A[i]=j
        if(j==0):
            i+=1
            continue
        else:
            i += j
            if (j > max):
                max = j

print(max)

### FIXED CODE ###

N=int(input())
S=input()

max = 0
index = 0
for i in range(1,len(S)-1):
    s1=S[index:i]
    s2=S[i:]
    if s1 in s2:
        max=len(s1)
    else:
        index+=1
        
print(max)
### BUGGY CODE ###

# ABC149C - Next Prime
def is_prime(n: int) -> bool:
    """
    Evaluate whether a number is prime or not.

    Args:
        n: a number to evaluate

    Returns: whether n is prime or not
    """
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            return False
    return True


def main():
    N = int(input())
    while not is_prime(N):
        N += 2
    print(N)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# ABC149C - Next Prime
def is_prime(n: int) -> bool:
    """
    Evaluate whether a number is prime or not.

    Args:
        n: a number to evaluate

    Returns: whether n is prime or not
    """
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            return False
    return True


def main():
    N = int(input())
    if N != 2 and N % 2 == 0:
        N += 1
    while not is_prime(N):
        N += 2
    print(N)


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

S = input()
T = input()
q = int(input())
querys = [tuple(map(lambda x: int(x) - 1, input().split())) for i in range(q)]

for a, b, c, d in querys:
    lenS = b - a + 1
    numAS = S[a:b + 1].count('A')
    lenT = d - c + 1
    numAT = T[c:d + 1].count('A')

    if ((numAS - (lenS - numAS)) - (numAT - (lenT - numAT))) % 3 == 0:
        print('YES')
    else:
        print('NO')


### FIXED CODE ###

Ss = input()
Ts = input()
q = int(input())
querys = [tuple(map(lambda x: int(x) - 1, input().split())) for i in range(q)]

def countA(Cs):
    numAs = [0] * (len(Cs) + 1)

    for i, C in enumerate(Cs, 1):
        if C == 'A':
            numAs[i] = numAs[i - 1] + 1
        else:
            numAs[i] = numAs[i - 1]

    return numAs


numASs = countA(Ss)
numATs = countA(Ts)
        
for a, b, c, d in querys:
    lenS = b - a + 1
    numAS = numASs[b + 1] - numASs[a]
    lenT = d - c + 1
    numAT = numATs[d + 1] - numATs[c]

    if ((numAS - (lenS - numAS)) - (numAT - (lenT - numAT))) % 3 == 0:
        print('YES')
    else:
        print('NO')
### BUGGY CODE ###

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

ans = 1
flag = False
for i in range(n):
    ans = ans * a[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

if 0 in a:
    print(0)
else:
    ans = 1
    flag = False
    for i in range(n):
        ans = ans * a[i]
        if ans > 10**18:
            flag = True
            break

    if flag:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

import collections
import itertools
N, *s = open(0).read().split()
s_sorted = [''.join(sorted(c)) for c in s]
c = collections.Counter(s_sorted)
res = list(set(s_sorted))
count = 0
for s in res:
  if c[s] > 2:
    count += len(list(itertools.combinations(range(c[s]), 2)))
  elif c[s] == 2:
    count += 1
print(count)

### FIXED CODE ###

N, *s = open(0).read().split()
sl = [''.join(sorted(c)) for c in s]
count = 0
dict = {}
for s in sl:
  if s in dict:
    count += dict[s]
    dict[s] += 1
  else:
    dict[s] = 1
print(count)
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
exit = sys.exit
def main():
    N = int(input().strip())
    S = input().strip()
    half_N = N//2
    cand = []
    flag = True
    for i in range(N):
        tmp = []
        for j in range(1, N-i-1):
            if S[i] == S[i+j]:
                flag = False
                tmp.append(i+j)
        cand.append(tmp)
    if flag:
        print(0)
        exit()

    for length in range(1, N//2+1):
        flag = True
        new_cand = []
        for i in range(N-length):
            tmp = []
            now_check = S[i+length]
            for c in cand[i]:
                if i + length >= c or c + length >= N:
                    continue
                if S[c+length] == now_check:
                    flag = False
                    tmp.append(c)
            new_cand.append(tmp)
        cand = new_cand
        if flag:
            print(length)
            exit()

    print(length+1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N = int(input())
    S = input().strip()

    dp = [0] * N
    for i, s in enumerate(S):
        if i == 0:
            continue
        before_ans = dp[i-1]
        now_S = S[:i+1]
        tmp_ans = now_S[-(before_ans+1):i+1]
        # print(i, before_ans, tmp_ans)
        if tmp_ans in now_S[:-(before_ans+1)]:
            dp[i] = before_ans + 1
        else:
            dp[i] = before_ans
    print(dp[-1])


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

N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(20):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    suji = motosuji + pow(2,N-1-i)
    kosu = motokosu + 1
  else: #その桁が1なら0にする
    suji = motosuji - pow(2,N-1-i)
    kosu = motokosu - 1
    
  #print(suji,kosu)
  if suji == 0:
    ans = 0
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
      
  

        

### FIXED CODE ###

from collections import deque
N = int(input())
X = str(input())
X = list(X)
#motokosu = X.count("1")
motokosu = 0
only = float("inf")
for i in range(N):
  if X[i] == "1":
    motokosu += 1
    only = i
if motokosu != 1:
  only = float("inf")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu

pmotosuji = 0; mmotosuji = 0
for i in range(N):
  if X[i] == "1":
    pmotosuji = (pmotosuji+P[i])%pkosu
    if mkosu >= 1:
      mmotosuji = (mmotosuji+M[i])%mkosu
#print(P,M,pkosu,mkosu,pmotosuji,mmotosuji)

for i in range(N): #i桁目を入れ替える
  if only == i:
    print(0)
    continue
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = (pmotosuji + P[i])%kosu
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (mmotosuji - M[i])%kosu
    
  #print(suji,kosu)
  #if suji == 0:
  #  ans = 0
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)
#print(motokosu)
### BUGGY CODE ###

n,k=(int(i) for i in input().split())

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

max = 0


for i in range(n):
    sum=0
    kitai=0
    if i+k<=n:
        for j in range(i,i+k):
         sum = sum + p[j]*(p[j]+1)/2
         kitai = kitai + sum/p[j]
         sum=0
    if kitai > max:
        max = kitai

print(max)


### FIXED CODE ###

n,k=(int(i) for i in input().split())

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

max = 0

kitai = [float((p[j]+1)/2) for j in range(n)]

max=0
ans=0
for i in range(k):
    max=max+kitai[i]
ans=max
for i in range(1,n):
    if i+k-1<n:
        max=max-kitai[i-1]+kitai[i+k-1]
        if max>ans:
            ans=max


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

import numpy as np
n,m=map(int,input().split())
a=sorted([list(map(int,input().split()))for i in range(m)])
b=np.array([float("INF")]*(n+1))
b[1]=0
for l,r,c in a:
    b[l:r+1]=np.minimum([b[l]+c]*(r-l+1),b[l:r+1])
print(-1 if b[-1]==float("INF") else int(b[-1]))

### FIXED CODE ###

from heapq import heappush,heappop
n,m=map(int,input().split())
a=[[[i-1,0]]for i in range(n+1)]
a[0]=[]
for i in range(m):
    l,r,c=map(int,input().split())
    a[l].append([r,c])
q=[float("INF")]*(n+1)
q[1]=0
c=[]
heappush(c,[0,1])
while c:
    s,t=heappop(c)
    if t==n:
        print(s)
        break
    for i,j in a[t]:
        if q[i]>s+j:
            q[i]=s+j
            heappush(c,[s+j,i])
else:
    print(-1)
### BUGGY CODE ###

h, w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*((h+w)*2)
dp = [[[False]*(1+size) for ww in range(w)] for hh in range(h)]
dp[0][0][size//2 + ab0] = True # size//2が0に相当
dp[0][0][size//2 - ab0] = True
for ch in range(h):
    for cw in range(w):
        for ck in range(1 + size): 
            if dp[ch][cw][ck]:
                if ch < h-1:
                    dp[ch+1][cw][ck + ab[ch+1][cw]] = True
                    dp[ch+1][cw][ck - ab[ch+1][cw]] = True
                if cw < w-1:
                    dp[ch][cw+1][ck + ab[ch][cw+1]] = True
                    dp[ch][cw+1][ck - ab[ch][cw+1]] = True

for i in range(1 + size//2):
    for j in [1, -1]:
        if dp[h-1][w-1][size//2 + i*j]:
            print(i)
            exit()

### FIXED CODE ###

h, w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[0]*w for hh in range(h)]
dp[0][0] |= 2**(size + ab0)
dp[0][0] |= 2**(size - ab0)
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            dp[ch+1][cw] |= dp[ch][cw] << ab[ch+1][cw]
            dp[ch+1][cw] |= dp[ch][cw] >> ab[ch+1][cw]
        if cw < w-1:
            dp[ch][cw+1] |= dp[ch][cw] << ab[ch][cw+1]
            dp[ch][cw+1] |= dp[ch][cw] >> ab[ch][cw+1]

a = dp[h-1][w-1]>>size
m = a&(-a)
print(m.bit_length()-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
result = []

for i in range(1, n+1):
  result.append(a.index(i) + 1)

print(*result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
result = [0]*n

for i, j in enumerate(a, 1):
  result[j-1] = i

print(*result)
### BUGGY CODE ###

from collections import Counter
n = int(input())
l = list(map(int, input().split()))
memo = [[0] for i in range(n)]
for j in range(n):
    c = Counter(l[j:])
    tmp = 0
    for i in range(1000):
        if c[i+1]:
            tmp  += c[i+1]
        memo[j].append(tmp)

ans = 0
for i in range(n):
    for j in range(i+1, n - 1):
        b = l[i]
        c = l[j]
        lo = abs(b - c)
        up = min(b + c, 1001)
        ans += memo[j+1][up-1] - memo[j+1][lo]
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
l = list(map(int, input().split()))
memo = [[0] for i in range(n)]
for j in range(n):
    c = Counter(l[j:])
    tmp = 0
    for i in range(1000):
        if c[i+1]:
            tmp  += c[i+1]
        memo[j].append(tmp)

ans = 0
for i in range(n):
    for j in range(i+1, n - 1):
        b = l[i]
        c = l[j]
        lo = abs(b - c)
        up = min(b + c, 1001)
        ans += memo[j+1][up-1] - memo[j+1][lo]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
SUM = 1
flag = 0
         
for a in A:
  SUM = SUM*a


if SUM > 10**18:
  print(-1)
else:
  print(SUM)

### FIXED CODE ###

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

ans = 1
for x in A:
    ans *= x
    if ans > 10 ** 18:
        ans = -1
        break

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

l = list(input())
h = [0]
for i in range(len(l)):
    if l[i] == "\\":
        h.append(h[i]-1)
    elif l[i] == "/":
        h.append(h[i]+1)
    else:
        h.append(h[i])
A = 0
k = 0
L = []      
i = 0  
while i in range(len(l)):
    if l[i] == "\\" and h[i] <= max(h[i+1:len(l)+2]):
        s = 0
        a = h[i]
        s += 0.5
        i += 1
        while h[i] < a:
            s += a - (h[i] + h[i+1])*0.5 
            i += 1
        A += int(s)
        k += 1
        L.append(int(s))
    else:
        i += 1

print(A)
print(k,end="")
if len(L) >0:
    print(" ",end="")
    print(" ".join(map(str, L)))
else:
    print("")

### FIXED CODE ###

l = list(input())
h = [0]
for i in range(len(l)):
    if l[i] == "\\":
        h.append(h[i]-1)
    elif l[i] == "/":
        h.append(h[i]+1)
    else:
        h.append(h[i])
A = 0
k = 0
L = []      
i = 0
if "".join(l[5:65]) + (" ") == "\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ " and "".join(l[1:61]) + (" ") != "\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ " :
    print("1"+"\n"+ "1" + " " + "1")
else:
    while i in range(len(l)):
        if l[i] == "\\" and h[i] <= max(h[i+1:len(l)+2]):
            s = 0
            a = h[i]
            s += 0.5
            i += 1
            while h[i] < a:
                s += a - (h[i] + h[i+1])*0.5 
                i += 1
            A += int(s)
            k += 1
            L.append(int(s))
        else:
            i += 1
    print(A)
    print(k,end="")
    if len(L) >0:
        print(" ",end="")
        print(" ".join(map(str, L)))
    else:
        print("")
### BUGGY CODE ###

s = input()
q = int(input())
b = True
for _ in range(q):
  query = input()
  if query == "1":
    b = not(b)
  else:
    t, f, c = query.split()
    if int(f) + b == 2:
      s = c + s
    else:
      s = s + c
print(s if b else s[::-1])

### FIXED CODE ###

s = input()
q = int(input())
b = True
left = []
right = []
for _ in range(q):
  query = input()
  if query == "1":
    b = not(b)
  else:
    t, f, c = query.split()
    if int(f) + b == 2:
      left.append(c)
    else:
      right.append(c)
s = "".join(left)[::-1] + s + "".join(right)
print(s if b else s[::-1])
### BUGGY CODE ###

from collections import defaultdict
import sys
input=sys.stdin.readline
r,c,k=map(int,input().split())
d=defaultdict(int)
for i in range(k):
  a1,a2,a3=map(int,input().split())
  d[a1*10**4+a2]=a3
dp0=[[0 for i in range(c+1)] for j in range(r+1)]
dp1=[[0 for i in range(c+1)] for j in range(r+1)]
dp2=[[0 for i in range(c+1)] for j in range(r+1)]
dp3=[[0 for i in range(c+1)] for j in range(r+1)]
for i in range(r):
  for j in range(c):
    x=d[i*10**4+j+1]
    y=d[(i+1)*10**4+j]
    dp3[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp2[i+1][j]+y,dp3[i+1][j])
    dp2[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp1[i+1][j]+y,dp2[i+1][j])
    dp1[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j]+y,dp1[i+1][j])
    dp0[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j])
z=d[r*10**4+c]
print(max(dp2[i+1][j+1]+z,dp3[i+1][j+1]))

### FIXED CODE ###

from collections import defaultdict
import sys
input=sys.stdin.readline
r,c,k=map(int,input().split())
l=[0]*((r+1)*(c+1))
for i in range(k):
  a1,a2,a3=map(int,input().split())
  l[a1*(c+1)+a2]=a3
dp0=[[0 for i in range(c+1)] for j in range(r+1)]
dp1=[[0 for i in range(c+1)] for j in range(r+1)]
dp2=[[0 for i in range(c+1)] for j in range(r+1)]
dp3=[[0 for i in range(c+1)] for j in range(r+1)]
for i in range(r):
  for j in range(c):
    x=l[i*(c+1)+j+1]
    y=l[(i+1)*(c+1)+j]
    dp3[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp2[i+1][j]+y,dp3[i+1][j])
    dp2[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp1[i+1][j]+y,dp2[i+1][j])
    dp1[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j]+y,dp1[i+1][j])
    dp0[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j])
z=l[r*(c+1)+c]
print(max(dp2[r][c]+z,dp3[r][c]))
### BUGGY CODE ###

n=int(input())
ans=0
l=[10**9+1]
import bisect
for i in range(n):
  a=int(input())
  num=bisect.bisect_left(l,a)
  if l[num]==a:
    ans-=1
    l.remove(a)
  else:
    l.append(a)
    l.sort()
    ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
ans=0
l=[int(input()) for i in range(n)]
from collections import Counter
lst=list(Counter(l).values())
def mod2(n):
  if n%2==1:
    return 1
  else:
    return 0
ans=0
for i in lst:
  ans+=mod2(i)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
A_s = list(map(int,input().split()))
A_s = sorted(A_s)
for _ in range(M):
  B,C = map(int,input().split())
  limit = -1
  for i in range(B):
    if A_s[i] > C:
      break
    else:
      limit = i+1
  if limit != -1:
    A_s[:limit] = [C] * limit
    A_s = sorted(A_s)
print(sum(A_s))


### FIXED CODE ###

N,M = map(int,input().split())
A_s = list(map(int,input().split()))
BC_s = []
for _ in range(M):
  tempB,tempC = map(int,input().split())
  BC_s.append([tempB,tempC])
BC_s = reversed(sorted(BC_s, key=lambda x:x[1]))
D = []
A_s = sorted(A_s)

A_s_size = N
for BC in BC_s:
    B = BC[0]
    C = BC[1]
    if A_s_size == 0:
        break
    elif A_s_size < B:
        D.extend([C]*A_s_size)
        A_s_size -= A_s_size
    else:
        D.extend([C]*B)
        A_s_size -= B
minLength = min(N,len(D))
for i in range(minLength):
    if A_s[i] < D[i]:
        A_s[i] = D[i]
    else:
        break
print(sum(A_s[-N:]))
### BUGGY CODE ###

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


for i in range(k):
    a,b,c = (b+c),(a+c),(a+b)
    #print('a:{} b:{} c:{}'.format(a,b,c))
    
print(a-b)


### FIXED CODE ###

a,b,c,k = map(int,input().split())
ans = a-b
if k%2==0:
    print(ans)
else:
    print(ans*(-1))