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

import itertools,sys
def f0070(A,n,s):
  if n==1:
    if s in A: return 1
    else: return 0
  c=0
  for i in range(len(A)):
    b=s-A[i]*n
    if b<=0:break
    c+=f0070(A[:i]+A[i+1:],n-1,b)
  return c

for a in sys.stdin:
  c=0
  n,s=map(int,a.split())
  c=f0070(range(10),n,s)
  print c

### FIXED CODE ###

import sys
K=1024
N=331
R=range(K)
B=[1,2,4,8,16,32,64,128,256,512]
C=[0]*K
D=[[0 for i in range(N)]for j in R]

for i in R:
  s=format(i,'b')
  n=s.count('1')
  C[i]=n
  if n==1:D[i][B.index(i)]=1
  else:
    for j in range(len(s)):
      if s[-j-1]=='1':
        dp=n*j
        i2=i-B[j]
        for k in range(N-dp):
          D[i][k+dp]+=D[i2][k]
   
for a in sys.stdin:
  n,s=map(int,a.split())
  x=0
  if s<N:x=sum([D[i][s] for i in R if C[i]==n])
  print x
### BUGGY CODE ###

import sys
import  math
from heapq import *
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

    
N,M=nm()
INF=10**18
def bfs(start,edge):
    d=[INF]*(N+1)
    ans=[0]*(N+1)
    d[start]=0
    q=[(0,start)]
    while(len(q)!=0):
        ci,i=heappop(q)
        for j in edge[i]:
            if(d[j]>=d[i]+1):
                d[j]=d[i]+1
                heappush(q,(d[j],j))
                ans[j]=i

    return ans




edge=[[]for _ in range(N+1)]
for i in range(M):
    A,B=nm()
    edge[A].append(B)
    edge[B].append(A)

ans=bfs(1,edge)

for i in range(2,N+1):
    if(ans[i]==0):
        print('No')
        sys.exit(0)

print('Yes')
for i in range(2,N+1):
    print(ans[i])



### FIXED CODE ###

import sys
import  math
from heapq import *
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

    
N,M=nm()
INF=10**18
def bfs(start,edge):
    d=[INF]*(N+1)
    ans=[0]*(N+1)
    d[start]=0
    q=[(0,start)]
    while(len(q)!=0):
        ci,i=heappop(q)
        for j in edge[i]:
            if(d[j]>d[i]+1):
                d[j]=d[i]+1
                heappush(q,(d[j],j))
                ans[j]=i

    return ans




edge=[[]for _ in range(N+1)]
for i in range(M):
    A,B=nm()
    edge[A].append(B)
    edge[B].append(A)

ans=bfs(1,edge)


for i in range(2,N+1):
    if(ans[i]==0):
        print('No')
        sys.exit(0)

print('Yes')
for i in range(2,N+1):
    print(ans[i])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def chmax(a,b):
    if a>=b:
        return a
    return b
def chmin(a,b):
    if a<=b:
        return a
    return b
def main():
    N=int(input())
    a=list(map(int,input().split()))
    dp=[[0]*(N+2) for _ in range(N+2)]
    for len in range(1,N+1):
        for i in range(N+1-len):
            j=i+len
            if (N-len)%2==0:
                dp[i][j]=chmax(dp[i+1][j]+a[i],dp[i][j-1]+a[j-1])
            else:
                dp[i][j]=chmin(dp[i+1][j]-a[i],dp[i][j-1]-a[j-1])
    print(dp[0][N])
main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def chmax(a,b):
    if a>=b:
        return a
    return b
def chmin(a,b):
    if a<=b:
        return a
    return b
def main():
    N=int(input())
    a=list(map(int,input().split()))
    dp=[[0]*(N+2) for _ in range(N+2)]
    for len in range(1,N+1):
        for i in range(N+1-len):
            j=i+len
            if (N-len)%2==0:
                dp[i][j]=chmax(dp[i+1][j]+a[i],dp[i][j-1]+a[j-1])
            else:
                dp[i][j]=chmin(dp[i+1][j]-a[i],dp[i][j-1]-a[j-1])
    print(dp[0][N])
main()
### BUGGY CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]

toN = list(filter(lambda x: N in x, AB))
toN = [flatten for inner in toN for flatten in inner]
frm_first = list(filter(lambda x: 1 in x, AB))
frm_first = [flatten for inner in frm_first for flatten in inner]

for v in frm_first:
    if v in toN:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]

toN = list(filter(lambda x: N in x, AB))
toN = set([flatten for inner in toN for flatten in inner])
frm_first = list(filter(lambda x: 1 in x, AB))
frm_first = set([flatten for inner in frm_first for flatten in inner])

if toN & frm_first:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

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

l.sort(reverse=True)
#print(l)

ans = 0
for i in range(n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    for k in range(j+1, n):
      c = l[k]
      if a<b+c:
        #print(a, b, c)
        ans += 1
      else:
        break

print(ans)


### FIXED CODE ###

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

l.sort(reverse=True)
m = sorted(l)
#print(l)
# print(m)

import bisect

ans = 0
for i in range(n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    x = a-b
    ind = bisect.bisect_right(m,x)
    #print(a, b, j, ind)
    if n-1-j-ind >= 0:
      ans += n-1-j-ind

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

n=int(input())
slist=[]
for i in range(n):
    slist.append(''.join(sorted(input())))
dup = [s for s in set(slist) if slist.count(s) > 1]
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
res=0
for s in dup:
    res += combinations_count(slist.count(s),2)
print(res)

### FIXED CODE ###

n=int(input())
sdict={}
cnt=0
for i in range(n):
    s=''.join(sorted(input()))
    if s in sdict:
        sdict[s] += 1
        cnt += sdict[s] - 1
    else:
        sdict[s] = 1
print(cnt)
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
a=sorted([(j,i) for i,j in enumerate(a)])[::-1]
dp=[[-1]*(n+1) for _ in range(n+1)]
dp[0][0]=0
for m,(a_k,k) in enumerate(a):
  for i in range(m+1):
    j=m-i
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a_k*abs(k-i))
    dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a_k*abs(k-((n-1)-j)))
ans=0
for i in range(n+1):
  ans=max(ans,dp[i][n-i])
print(ans)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
a=sorted([(j,i) for i,j in enumerate(a)])[::-1]
dp=[[-1]*(n+1) for _ in range(n+1)]
dp[0][0]=0
for m,(a_k,k) in enumerate(a):
  for i in range(m+1):
    j=m-i
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a_k*abs(k-i))
    dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a_k*abs(k-((n-1)-j)))
ans=0
for i in range(n+1):
  ans=max(ans,dp[i][n-i])
print(ans)
### BUGGY CODE ###

N = int(input())
A = sorted([int(_) for _ in input().split()])


def comb(n, r):
    res = 1
    for i in range(n - r + 1, n + 1):
        res *= i
    for i in range(1, r):
        res //= i
    return res


x = A.pop()
N -= 1
for i in range(N):
    if A[i] > x // 2:
        break
if comb(x, A[i]) > comb(x, A[i - 1]):
    y = A[i]
else:
    y = A[i - 1]
print(x, y)


### FIXED CODE ###

N = int(input())
A = sorted([int(_) for _ in input().split()])


def comb(n, r):
    res = 1
    for i in range(n - r + 1, n + 1):
        res *= i
    for i in range(1, r):
        res //= i
    return res


x = A.pop()
N -= 1
for i in range(N):
    if A[i] > x // 2:
        break
if abs(A[i] - x / 2) < abs(A[i - 1] - x / 2):
    print(x, A[i])
else:
    print(x, A[i - 1])
### BUGGY CODE ###

line = input().rstrip().split(' ')
n = int(line[0])
a = int(line[1])
b = int(line[2])

i = 0
ans = 0
while i <= n:
    if i + a <= n:
        ans += a
    else:
        t = n - i
        ans += t
    i += a + b

print(ans)

### FIXED CODE ###

line = input().rstrip().split(' ')
n = int(line[0])
a = int(line[1])
b = int(line[2])

i = 0
ans = 0

t = int(n / (a + b))
ans = t * a

if n > (a + b) * t:
    t2 = n - (a + b) * t
    if t2 > a:
        ans += a
    else:
        ans += n - (a + b) * t

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

from collections import Counter
def main():
    S = input()
    N = len(S)
    result = 0
    work = [0] * (N + 1)
    temp = 0
    for i in range(N):
        temp += int(S[N - i - 1]) * 10**i
        work[i] = temp % 2019
    for v in Counter(work).values(): result += v*(v-1)//2
    print(result)
main()

### FIXED CODE ###

def main():
    S = input()
    work, temp = [0] * 2019, 0
    work[0] = 1
    a = 1
    for s in S[::-1]:
        temp += int(s) * a
        work[temp%2019] += 1
        a *= 10
        a %= 2019
    print(sum([w*(w-1)//2 for w in work]))
main()
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections
    import sys
    input = sys.stdin.readline

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    w_goto = []
    for i in range(5):
        for j in range(5):
            if [i, j] in next_y_x:
                pass
            else:
                w_goto.append([-2 + i, -2 + j])
    w_goto.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.appendleft([ny, nx, temp[2]])
                    fp[ny][nx] = w_num
        
        for dy, dx in w_goto:
            nwy = temp[0] + dy
            nwx = temp[1] + dx
            nw = w_num +1

            if 0 <= nwy <= H-1 and 0 <= nwx <= W-1:
                if grid[nwy][nwx] == '.' and fp[nwy][nwx] > w_num:
                    que.append([nwy, nwx, nw])
                    fp[nwy][nwx] = nw


    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9

    bit = [0 for _ in range(60)] 

    last = A[N-1]
    for j in range(60):
        bit[j] = last % 2
        last //= 2
    
    ans = 0
    for i in reversed(range(N-1)):
        total = N - 1 - i
        num = A[i]
        for j in range(60):
            if num % 2 == 1:
                ans += (total - bit[j]) * pow(2, j, mod)
                ans %= mod
            else:
                ans += bit[j] * pow(2, j, mod)
                ans %= mod
            bit[j] += (num % 2)
            num //=2
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9

    bit = dict()
    pow_list = dict()
    for j in range(60): 
        bit[j] = 0
        pow_list[j] = pow(2, j, mod)

    first = A[0]
    for j in range(60):
        bit[j] = first % 2
        first //= 2
    
    ans = 0
    for i in range(1, N):
        num = A[i]
        for j in range(60):
            if num % 2 == 1:
                ans += (i - bit[j]) * pow_list[j]
                ans %= mod
            else:
                ans += bit[j] * pow_list[j]
                ans %= mod
            bit[j] += (num % 2)
            num //=2
            
    print(ans)

    return 0

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

n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
while len(ab) != 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0][1]
    ab.sort()
    while ab[0][0] < end:
        ab.pop(0)
        if len(ab) == 0:
            break
    count += 1
print(int(count))


### FIXED CODE ###

n, m = map(int, input().split())
l = []
for i in range(m):
    a, b = map(int, input().split())
    l.append((b, a))
l.sort()
answer = 0
last = 0
for b, a in l:
    if a >= last:
        answer += 1
        last = b
print(answer)
### BUGGY CODE ###

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

bomb = [[False for i in range(w)] for j in range(h)]
cnth = [0 for i in range(h)]
cntw = [0 for i in range(w)]
for i in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  cnth[x] += 1
  cntw[y] += 1
  bomb[x][y] = True
maxh = max(cnth)
maxw = max(cntw)

xx = []
yy = []
for i in range(h):
  if maxh == cnth[i]:
    xx.append(i)
for i in range(w):
  if maxw == cntw[i]:
    yy.append(i)


ans = maxh + maxw -1
for i in xx:
  for j in yy:
    if not bomb[i][j]:
      ans += 1
      print (ans)
      exit()
print (ans)


### FIXED CODE ###

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

bomb = []
cnth = [0 for i in range(h)]
cntw = [0 for i in range(w)]
bomh = [set() for i in range(h)]
bomw = [set() for i in range(w)]
for i in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  cnth[x] += 1
  cntw[y] += 1
  bomh[x].add(y)
  bomw[y].add(x)
  bomb.append([x,y])
maxh = max(cnth)
maxw = max(cntw)
ans = maxh + maxw - 1

xx = []
yy = []
for i in range(h):
  if maxh == cnth[i]:
    xx.append(i)
for i in range(w):
  if maxw == cntw[i]:
    yy.append(i)

for i in xx:
  for j in yy:
    if j not in bomh[i]:
      print (ans+1)
      exit()
print (ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
p,q=0,1
for i in range(1,n+1):
    p,q=q,(p+q)*(not i in a)
print(q%(10**9+7))


### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
p,q=0,1
for i in range(1,n+1):
    p,q=q,(p+q)*(not i in a)
print(q%(10**9+7))
### BUGGY CODE ###

n = int(input())
x = input()

val = 0
rui = 1
mod = 0

nagasa = 2*10**5+1
#nagasa = 5
d_li = [0]*(nagasa)

for i in range(1,nagasa):
    t_v = i
    t_m = bin(t_v).count("1")
    ans = 0
    while t_v != 0:
        if d_li[t_v] != 0:
            ans += d_li[t_v]
            break
        ans += 1
        t_v %= t_m
        t_m = bin(t_v).count("1")
    d_li[i] = ans

#print(d_li)
#exit()

for i in range(n):
    val += int(x[n-1-i])*rui
    rui *= 2
    if int(x[n-1-i]) == 1:
        mod += 1

rui = 1
ans_li = []
    
for i in range(n):
    t_v = val
    t_m = mod
    if int(x[n-1-i]) == 1:
        t_v -= rui
        t_m -= 1
    else:
        t_v += rui
        t_m += 1
    rui *= 2
    ans = 0
    #while t_v != 0:
    if t_v != 0:
        t_v %= t_m
        ans += 1
    
    ans += d_li[t_v]
    #t_m = bin(t_v).count("1")
    ans_li.append(ans)
    #print(ans_li)

#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])


### FIXED CODE ###

def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    #nagasa = 5
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            #t_m = bin(t_v).count("1")
        d_li[i] = ans
    
    #print(d_li)
    #exit()
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    #print(val)
    #exit()
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    
    t_v_p = val % (mod+1)
    if mod == 1:
        t_v_m = 0
    else:
        t_v_m = val % (mod-1)
        
    for i in range(n):
        ans = 0
        #t_v = val
        #t_m = mod
        if int(x[i]) == 1:
            if mod == 1:
                t_v = 0
            else:
                t_v = t_v_m
                t_v -= pow(2,(n-1-i),mod-1)
                #t_v -= rui % (mod-1)
                t_v %= (mod-1)
                ans += 1
                #t_m -= 1
        else:
            t_v = t_v_p
            t_v += pow(2,(n-1-i),mod+1)
            #print(t_v,rui)
            #t_v += rui % (mod+1)
            t_v %= (mod+1)
            ans += 1
            #t_m += 1
        rui //= 2
        #print(t_v,mod)
        #while t_v != 0:
        """
        if t_v != 0:
            if int(x[i]) == 1:
                if mod == 1:
                    t_v = 0
                else:
                    t_v %= mod-1
            else:
                t_v %= mod + 1
            #t_v %= t_m
            ans += 1
        """
        ans += d_li[t_v]
        #t_m = bin(t_v).count("1")
        #ans_li.append(ans)
        print(ans)
        #print(ans_li)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""
### BUGGY CODE ###

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

for i in range(N):
    flg = 0
    j  = 0
    while(flg == 0 and j < i):
        if i != j:
            if S[j] == S[i]:
                S[j] = ''
                ans = ans - 1
                flg = 1
        j = j+1
print(ans)

### FIXED CODE ###

N = int(input())
S = []
ans = N
S = [input() for i in range(N)]
#for i in range(N):
#    S.append(input())
S.sort()
for i in range(N-1):
    if S[i] == S[i+1]:
        ans = ans - 1
print(ans)
### BUGGY CODE ###

def f(n):
    if n<2:
        return 0
    lim1 = int((n-2)**0.5-1)+1
    lim2 = int((-2+(4-12*(1-n))**0.5)/6)+1
    lim3 = int(n/6)+1
    
    result=set()
    for x in range(1,lim3):
        for y in range(1,lim2):
            for z in range(1,lim1):
                if x**2+y**2+z**2+x*y+y*z+z*x==n:
                    tmp=set([x,y,z])
                    if tmp not in result:
                        result.add(tuple(tmp))
    
    count=0
    for s in result:
        if len(s)==1:count+=1
        elif len(s)==2:count+=3
        else: count+=6
    return count

for i in range(1,int(input())+1):
    print(f(i))

### FIXED CODE ###

import numpy as np


def calc(n):
    #     lim = int((n - 2) ** 0.5 - 1) + 1
    lim = 130

    result = np.zeros(n + 1, dtype=int)
    for x in range(1, lim):
        for y in range(1, lim):
            if x > y:
                continue
            for z in range(1, lim):
                if y > z:
                    continue
                index = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
                if index > n:
                    continue
                s = set([x, y, z])
                if len(s) == 1:
                    result[index] += 1
                elif len(s) == 2:
                    result[index] += 3
                else:
                    result[index] += 6

    return result[1:]


for i in calc(int(input())):
    print(i)
### BUGGY CODE ###

from collections import defaultdict
import itertools

def main():
    node_num, edge_num, visit_num = map(int, input().split())
    visit_place = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    hashi_set = defaultdict(set)
    kyori_data = [defaultdict(int) for i in range(node_num + 1)]
    for i in range(edge_num):
        a, b, c = data[i]
        hashi_set[a].add(b)
        hashi_set[b].add(a)
        kyori_data[a][b] = c
        kyori_data[b][a] = c

    saitan_data = [[-1 for i in range(node_num + 1)] for j in range(node_num + 1)]


    for i in range(1, node_num + 1):
        saitan_data[i][i] = 0
        done_data = set()
        done_data.add(i)
        for j in range(1, i):
            saitan_data[i][j] = saitan_data[j][i]
            done_data.add(j)

        while len(done_data) < node_num:
            node_add = -1
            kyori_add = 10 ** 10
            for now_ele in done_data:
                for next_ele in hashi_set[now_ele]:
                    if saitan_data[i][next_ele] != -1:
                        continue
                    kyori = saitan_data[i][now_ele] + kyori_data[now_ele][next_ele]
                    if kyori < kyori_add:
                        kyori_add = kyori
                        node_add = next_ele
            done_data.add(node_add)
            saitan_data[i][node_add] = kyori_add

    # for i in range(node_num + 1):
    #     print(saitan_data[i])

    ans = 10 ** 10
    for ikikata in list(itertools.permutations(visit_place, visit_num)):
        kari = 0
        for i in range(visit_num - 1):
            kari += saitan_data[ikikata[i]][ikikata[i + 1]]
        if kari < ans:
            ans = kari
    print(ans)





if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import itertools

def main():
    node_num, edge_num, visit_num = map(int, input().split())
    visit_place = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    hashi_set = defaultdict(set)
    kyori_data = [defaultdict(int) for i in range(node_num + 1)]

    saitan_data = [[10 ** 10 for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        hashi_set[a].add(b)
        hashi_set[b].add(a)
        kyori_data[a][b] = c
        kyori_data[b][a] = c
        saitan_data[a][b] = c
        saitan_data[b][a] = c


    for k in range(1, node_num + 1):
        for i in range(1, node_num + 1):
            for j in range(1, node_num + 1):
                if i == j:
                    saitan_data[i][j] = 0
                    continue
                saitan_data[i][j] = min(saitan_data[i][j], saitan_data[i][k] + saitan_data[k][j])

    ans = 10 ** 10
    for ikikata in list(itertools.permutations(visit_place, visit_num)):
        kari = 0
        for i in range(visit_num - 1):
            kari += saitan_data[ikikata[i]][ikikata[i + 1]]
        if kari < ans:
            ans = kari
    print(ans)





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

import sys
input=sys.stdin.readline
s=input().rstrip()
q=int(input())
rev=0
for _ in range(q):
	qw=input().split()
	if qw[0]=="1":
		rev+=1
	else:
		f=qw[1]
		c=qw[2]
		if f=="1":
			if rev%2==0:
				s=c+s
			else:
				s+=c
		else:
			if rev%2==0:
				s+=c
			else:
				s=c+s
if rev%2==0:
	print(s)
else:
	print(s[::-1])

### FIXED CODE ###

alph="abcdefghijklmnopqrstuvwxyz"
from collections import deque
import sys
input=sys.stdin.readline
moji=deque([])
s=input().rstrip()
for i in range(len(s)):
	for j in range(26):
		if s[i]==alph[j]:
			moji.append(j)
			break
q=int(input())
rev=0
for _ in range(q):
	qw=input().split()
	if qw[0]=="1":
		rev+=1
	else:
		f=qw[1]
		c=qw[2]
		for j in range(26):
			if c==alph[j]:
				x=j
				break
		if f=="1":
			if rev%2==0:
				moji.appendleft(x)
			else:
				moji.append(x)
		else:
			if rev%2==0:
				moji.append(x)
			else:
				moji.appendleft(x)
ans=""
r=[]
for i in range(len(moji)):
	r.append(moji.popleft())
for i in range(len(r)):
	ans+=alph[r[i]]
if rev%2==0:
	print(ans)
else:
	print(ans[::-1])