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

N = int(input())
a = list(map(int, input().split()))
for i in range(N):
    print(a.count(i + 1))



### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
li = [0] * N

for i in range(N-1):
    li[a[i]-1] = li[a[i]-1] + 1

for i in range(N):
    print(li[i])
### BUGGY CODE ###

n, w = map(int, input().split())
wv_array = [[int(x) for x in input().split()] for y in range(n)]

dp = [[0 for x in range(w + 1)] for y in range(n+1)]

index = 1
for ww, vv in wv_array:
    for capacity in range(1, w + 1):
        if ww <= capacity:
            dp[index][capacity] = max(dp[index - 1][capacity - ww] + vv, dp[index-1][capacity])
        else:
            dp[index][capacity] = dp[index - 1][capacity]
    index += 1
print(max(dp[n]))

### FIXED CODE ###

n, w = map(int, input().split())
wv_array = [[int(x) for x in input().split()] for y in range(n)]

dp = [[0 for x in range(w + 1)] for y in range(n+1)]

index = 1
for ww, vv in wv_array:
    for capacity in range(1, w + 1):
        if ww <= capacity:
            dp[index][capacity] = max(dp[index - 1][capacity - ww] + vv, dp[index-1][capacity])
        else:
            dp[index][capacity] = dp[index - 1][capacity]
    index += 1
print(max(dp[n]))
### BUGGY CODE ###

num,k,q = map(int,input().split())

arr = [k]*num


for i in range(q):
    a = int(input())
    arr = [i-1 for i in arr]
    arr[a-1] +=1


for i in range(len(arr)):
    if arr[i] > 0:
        print("Yes")
    else:
        print("No")
    

### FIXED CODE ###

num,k,q = map(int,input().split())

arr = [0]*num


for i in range(q):
    a = int(input())
    arr[a-1] +=1

arr = [i-(q-k) for i in arr]

for i in range(len(arr)):
    if arr[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/python
import sys
from scipy.sparse import*
g=[]
n=int(sys.stdin.readline())
for _ in xrange(n-1):
	a,b=map(int,sys.stdin.readline().split())
	g.append((a-1,b-1,1))
z=[-1]*n
for _ in xrange(int(sys.stdin.readline())):
	a,b=map(int,sys.stdin.readline().split())
	g.append((n,a-1,b))
	z[a-1]=b
a,b,c=zip(*g)
a=map(int,csgraph.dijkstra(coo_matrix((c,(a,b)),[n+1]*2),0,n))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		exit()
for e in g:
	if e[0]<e[1] and abs(a[e[0]]-a[e[1]])!=1:
		print('No')
		exit()
print('Yes')
print("\n".join(map(str,a[:n])))

### FIXED CODE ###

#!/usr/bin/python
def shortestPath(g,s,dist,prev):
	n = len(g)-1
	Q=[]
	heapq.heappush(Q,(0,-2,s))
	while Q:
		e = heapq.heappop(Q)
		if prev[e[2]]!=-1: continue
		prev[e[2]] = e[1]
		for f in g[e[2]]:
			if dist[f[2]] > e[0] + f[0]:
				dist[f[2]] = e[0] + f[0]
				heapq.heappush(Q,(e[0]+f[0],f[1],f[2]))

import sys,heapq
#if sys.version_info[0]>=3:raw_input=input

n=int(raw_input())
g=[[] for _ in range(n+1)]
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g[a-1]+=[(1,a-1,b-1)]
	g[b-1]+=[(1,b-1,a-1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g[n]+=[(b,n,a-1)]
	z[a-1]=b
a=[1e9]*n+[0]
shortestPath(g,n,a,[-1]*(n+1))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for _ in g:
	for e in _:
		if e[1]<e[2] and abs(a[e[1]]-a[e[2]])!=1:
			print('No')
			sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))
### BUGGY CODE ###

num = input()

count = 0
year = 2019

for i in range(len(num)):
  for j in range(i, len(num)):
    if int(num[i:j+1]) % year == 0:
      count += 1
print(count)

### FIXED CODE ###

def main():
    S = input()[::-1]
    ans = 0
    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        ans += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 % 2019
    print(ans)

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

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

ans = 0

for i in range(min(d), max(d)+1):
    d_list = [x for x in d if i <= x]

    if len(d_list) == N // 2:
        ans += 1
print(ans)


### FIXED CODE ###

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

print(d[N//2]-d[N//2-1])
### BUGGY CODE ###

N = int(input().strip())

X = {}
Y = {}

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = set()
  X[x].add(y)
  if y not in Y: Y[y] = set()
  Y[y].add(x)

count = 0
for x, y_set in X.items():
  if len(y_set) < 2:
    continue

  for y in y_set:
    x_set = Y[y]
    if len(x_set) < 2:
      continue

    for _x in x_set:
      if x == _x:
        continue

      _y_set =  X[_x]
      for _y in y_set:
        if _y not in _y_set:
          _y_set.add(_y)
          count += 1

print(count)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input().strip())

X = {}
Y = {}
G = (X, Y)

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = []
  if y not in Y: Y[y] = []
  X[x].append(y)
  Y[y].append(x)


def dfs_visit(visited, u, i):
  if u in visited[i]: return
  visited[i].add(u)
  for v in G[i][u]:
    dfs_visit(visited, v, (i + 1) % 2)


count = 0
i = 0
while len(X) > 0:
  visited = (set(), set())
  x = X.__iter__().__next__()
  dfs_visit(visited, x, 0)

  for x in visited[0]:
    count += len(visited[1]) - len(X.pop(x))

print(count)
### BUGGY CODE ###

_ = input()
nums = [int(x) for x in input().split(" ")]
res = 0
sums = [sum(nums[i:]) for i in range(1, len(nums))]
for i, ni in enumerate(nums[:-1]):
    res += ni*sums[i]
    res %= 10**9 + 7
print(res)

### FIXED CODE ###

_ = input()
nums = [int(x) for x in input().split(" ")]
res = 0
sums = []
for n in nums[1:][::-1]:
    if sums:
        sums.append(sums[-1]+n)
    else:
        sums.append(n)
sums.reverse()
#print(sums)
for i, ni in enumerate(nums[:-1]):
    res += ni*sums[i]
    res %= 10**9 + 7
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
hlist = tuple(map(int,input().split()))
dp = [float('inf')]*n
dp[0] = 0
dp[1] = abs(hlist[1]-hlist[0])
for i in range(2,n):
  for j in range(max(0,i-k),i):
      dp[i] = min(dp[i], dp[j] + abs(hlist[i]-hlist[j]))
print(dp[n-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [10**9]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i-j >= 0:
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

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

k,q=map(int,readline().split())
D=list(map(int,readline().split()))
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=list(map(lambda x:x%m,D))
    SD=[0]+tmpD
    n-=1
    for i in range(1,k):
        SD[i+1]+=SD[i]
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=tmpD.count(0)*(n//k)
    count+=tmpD[:n%k].count(0)
    ans=n-x//m-count
    print(ans)

### FIXED CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k,q=map(int,readline().split())
D=np.array(readline().split(),dtype=np.int64)
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=D%m
    SD=np.hstack((np.zeros(1,dtype=np.int64), tmpD))#結合
    SD=np.cumsum(SD)
    n-=1
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=(k-np.count_nonzero(tmpD))*(n//k)
    count+=n%k-np.count_nonzero(tmpD[:n%k])
    ans=n-x//m-count
    print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())
mini = 2019
for i in range(L,R+1):
  for j in range(L,R+1):
    if (i*j)%2019 < mini and i != j:
      mini = (i*j) % 2019
print(mini)

### FIXED CODE ###

L,R = map(int,input().split())
ans = set()
mini = 2019
if (R-L) >= 2019:
  print(0)
else:  
  for i in range(L,R+1):
    ans.add(i%2019)
  
  for i in ans:
    for j in ans:
      if (i*j)%2019 < mini and i != j:
        mini = (i*j)%2019
  print(mini)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
    flg = False
    for j in range(n):
        if i==j:
            continue
        if a[i] % a[j] == 0:
            flg=True
    cnt += 0 if flg else 1
print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
dp = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    e = x * 2
    while e <= 10 ** 6:
        dp[e] = False
        e += x
ret = 0
for x in a:
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)
### BUGGY CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=1
if n%2==1 and collections.Counter(a)[0]==1:
    for i in range(2,n,2):
        if collections.Counter(a)[i]!=2:
            print(0)
            break
        else:
            ans=ans*2%(10**9+7)
    else:
        print(ans%(10**9+7))
elif n%2==0:
    for i in range(1,n,2):
        if collections.Counter(a)[i]!=2:
            print(0)
            break
        else:
            ans=ans*2%(10**9+7)
    else:
        print(ans%(10**9+7))
else:
    print(0)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
if n%2==1:
    b=[i for i in range(2,n,2)]
    b=b*2
    b.sort()
    #print(a,b)
    b=[0]+b
    if a==b:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
elif n%2==0:
    b=[i for i in range(1,n,2)]
    b=b*2
    b.sort()
    if a==b:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
### BUGGY CODE ###

from copy import deepcopy


def gen_2017_like(limit):
    p = [1 for _ in range(limit+1)]
    p[0] = p[1] = 0

    # prime?
    for i in range(2, len(p)):
        if not p[i]: continue
        else:
           for j in range(i*2, limit+1, i):
               p[j] = 0

    a = deepcopy(p)

    # like 2017?
    for i in range(len(a)):
        target = int((i+1)/2)
        if p[i] and p[target]:
            continue
        else:
            a[i] = 0
    return a



N = int(input())
R = []
L = []

for i in range(N):
    l, r = map(int, input().split())
    R.append(r)
    L.append(l)

limit = max(R)
sum_list = gen_2017_like(limit)

for l, r in zip(L, R):
    ans = sum(sum_list[l:r+1])
    print(ans)

### FIXED CODE ###

from copy import deepcopy


def gen_2017_like(limit):
    p = [1 for _ in range(limit+1)]
    p[0] = p[1] = 0

    # prime?
    for i in range(2, len(p)):
        if not p[i]: continue
        else:
           for j in range(i*2, limit+1, i):
               p[j] = 0

    a = deepcopy(p)

    # like 2017?
    for i in range(len(a)):
        target = int((i+1)/2)
        if p[i] and p[target]:
            continue
        else:
            a[i] = 0
    return a



N = int(input())
R = []
L = []

for i in range(N):
    l, r = map(int, input().split())
    R.append(r)
    L.append(l)

limit = max(R)
sum_list = gen_2017_like(limit)
S = [0]*len(sum_list)
for i, e in enumerate(sum_list[1:]):
    S[i+1] = S[i] + e

for l, r in zip(L, R):
    ans = S[r] - S[l-1]
    print(ans)
### BUGGY CODE ###

import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))

    
dist = [INF] * (3001 * n)
dist[min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * 3001 + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v * 3001 + tmp + cc] > dist[v * 3001 + tmp] + dd:
                dist[v * 3001 + tmp + cc] = dist[v * 3001 + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * 3001 + g] + time < dist[nxt_v * 3001 + g - cost]:
                dist[nxt_v * 3001 + g - cost] = dist[v * 3001 + g] + time
                heapq.heappush(q, (dist[nxt_v * 3001 + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * 3001:(i + 1) * 3001]))


### FIXED CODE ###

import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * (MAX_ + 1):(i + 1) * (MAX_ + 1)]))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
import itertools
count = 0
check = tuple([int(abs((N-i+1)- i)) for i in range(1,N+1)])
for p in itertools.permutations(A):
    if p == check:
        count += 1
print(count)

### FIXED CODE ###

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

import itertools
count = 0
check = [int(abs((N-i+1)- i)) for i in range(1,N+1)]
flag = sorted(A) == sorted(check)
if flag:
    print(2 ** (N//2) % (10 ** 9 + 7))
else:
    print(0)
### BUGGY CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[]
while (j<N-1):
  if (x[j]=="A") and (x[j+1]=="C"):
    s.append(1)
    s.append(0)
    j+=1
  else:s.append(0)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][0]-1:a[i][1]-1]
  print(sum(p))





### FIXED CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[0]
t=0
while (j<N-1):
  if (x[j]=="A") and (x[j+1]=="C"):
    t+=1
    s.append(t)
  else:s.append(t)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][1]-1]-s[a[i][0]-1]
  print(p)
### BUGGY CODE ###

A,B,C = map(int,input().split())

counter = 0

while A != B or B != C or A != C:
    if max([A,B,C])-min([A,B,C]) > 1:
        if A < B and A < C:
            A += 2
        elif B < A and B < C:
            B += 2
        else:
            C += 2
        counter += 1
    else:
        if A < C and B < C:
            A += 1
            B += 1
        elif A < B and C < B:
            A += 1
            C += 1
        else:
            B += 1
            C += 1
        counter += 1

print(counter)


### FIXED CODE ###

A,B,C = map(int,input().split())
 
counter = 0
 
while not A == B == C:
    A,B,C = sorted([A,B,C])
    if C - A > 1:
        A += 2
        counter += 1
    else:
        A += 1
        B += 1
        counter += 1
        
print(counter)
### BUGGY CODE ###

import sys
from collections import defaultdict
from bisect import insort

n, m = map(int, input().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    sub = d[i]
    if len(sub) > 0:
        for j in range(len(sub)):
            insort(resList, sub[j])
    if len(resList) > 0:
        res += resList.pop()

print(res)


### FIXED CODE ###

import sys
from heapq import heappush,heappop

n, m = map(int, sys.stdin.readline().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    if len(d[i]) > 0:
        for j in d[i]:
            heappush(resList, -j)
    if len(resList) > 0:
        res += (-1) * resList[0]
        heappop(resList)

print(res)
### BUGGY CODE ###

n = int(input())
a = list()
for x in range(n):
    a.append(int(input()))

for x in range(n):
    tmp = a.pop(x)
    print(max(a))
    a.insert(x, tmp)


### FIXED CODE ###

n = int(input())
a = list()
for x in range(n):
    a.append(int(input()))

copy_a = sorted(a, reverse=True)

A_Max = copy_a[0]
A_Second = copy_a[1]

for x in range(n):
    if a[x] == A_Max:
        print(A_Second)
    else:
        print(A_Max)
### BUGGY CODE ###

def lu(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    n = lu(n - 1) + lu(n - 2)
    return n


print(lu(int(input())))

### FIXED CODE ###

def lu(n):
    a, b = 2, 1
    for i in range(n):
        a, b = b, a + b
    return a
print(lu(int(input())))
### BUGGY CODE ###

#coding:utf-8

def inpl(): return list(map(int, input().split()))

n,m = inpl()
A = inpl()

B = []
tmp = 0
for a in A:
    tmp += a
    B.append(tmp)

ans = 0

for i in range(n):
    if B[i] % m == 0: ans += 1

for i in range(1,n):
    for j in range(0,i):
        if (B[i] - B[j]) % m == 0: ans += 1

print(ans)

### FIXED CODE ###

# coding:utf-8


def inpl(): return list(map(int, input().split()))


N, M = inpl()
A = inpl()

S = [0]
for i in range(N):
    S.append((S[-1] + A[i]) % M)
del S[0]

D = dict()
D[0] = 0
for i in range(N):
    if S[i] in D:
        D[S[i]] += 1
    else:
        D[S[i]] = 1

ans = 0
for num in D:
    tmp = D[num]
    # cmb(x, 2)を計算
    ans += tmp * (tmp - 1) // 2

# l, rが等しく（1箱で）分配できるパターンを最後に足す
ans += D[0]
print(ans)
### BUGGY CODE ###

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

sum = 0
for i in range(N):
	for j in range(N-i):
		if S[j+i] != S[i]:
			for k in range(N-(j+i)):
				if S[k+j+i] != S[i] and S[k+j+i] != S[j+i] and (j+i)-i != (k+j+i)-(j+i):
					sum += 1
print(sum)


### FIXED CODE ###

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

R = 0
G = 0
B = 0

for i in range(N):
	if S[i] == 'R':
		R += 1
	elif S[i] == 'G':
		G += 1
	else:
		B += 1
ans = R*G*B
for i in range(N-2):
	for j in range(i+1, N-1):
		k = j+(j-i)
		if k >= N:
			break
		if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
			ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())

A_list = list(map(int, input().split(' ')))
A_len = len(A_list)

result = 0
for i in range(A_len):
    tmp = 0
    for j in range(i, A_len):
        tmp += A_list[j]
        if tmp == 0:
            result += 1

print(result)

### FIXED CODE ###

import math

def calc_combination(n):
    combination = math.factorial(n) / (math.factorial(2) * math.factorial(n - 2))

    return combination


N = int(input())

list_A = list(map(int, input().split(' ')))

tmp_sum = 0
sum_map = {}
for A in list_A:
    tmp_sum += A
    sum_map[tmp_sum] = sum_map.get(tmp_sum, 0) + 1

result = sum_map.get(0, 0)
for value in sum_map.values():
    if value >= 2:
        result += calc_combination(value)

print(int(result))
### BUGGY CODE ###

from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
dp = [[[-1] * 2 for _ in range(n)] for _ in range(n + 1)]

def dfs(u, pu=-1):
    # if pu != -1 and dp[pu][u][0] != -1:
    #    return dp[pu][u]
    w = b = 1
    for v in to[u]:
        if v == pu: continue
        if dp[u][v][0] == -1: dfs(v, u)
        vb, vw = dp[u][v]
        b += b * vb
        w += vb + vw - 1
        b, w = b % m, w % m
    dp[pu][u] = [b, w]
    return

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    for u in range(n):
        dfs(u)
        print(dp[-1][u][0])

main()


### FIXED CODE ###

from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
# dp[u][v] uを根としたときのサブツリーvの値
dp = {}

def dfs(u=0, pu=-1):
    res = 1
    for v in to[u]:
        if v == pu: continue
        res *= dfs(v, u) + 1
        res %= m
    if pu != -1: dp[(pu,u)] = res
    return res

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    # bfsでdfsとは逆向きのdpを完成させる
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        # 累積積のための配列
        ll = [0] * tn
        rr = [0] * tn
        # uのサブツリーの値+1を入れる
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dp[(u,v)] + 1
        # 左右から累積積を作る
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        # 配列の最初or最後のために最後に1を追加
        ll += [1]
        rr += [1]
        # uの子vを根とみたときのサブツリーuの値を求める
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[(v,u)] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    # p2D(dp)
    # 各頂点について答えを出す
    for u in range(n):
        ans = 1
        for v in to[u]:
            ans = (ans * (dp[(u,v)] + 1)) % m
        print(ans)

main()
### BUGGY CODE ###

s = input()
q = int(input())
hanten = True
for i in range(q):
    l = input().split()
    if l[0] == "1":
        hanten = not hanten
    else:
        if l[1] == "1":
            if hanten == True:
                s = l[2] + s
            else:
                s = s + l[2]
        else:
            if hanten == True:
                s = s + l[2]
            else:
                s = l[2] + s

if hanten == False:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

s = input()
q = int(input())
hanten = True
atm = ""
kts = ""
for i in range(q):
    l = input().split()
    if l[0] == "1":
        hanten = not hanten
    else:
        if l[1] == "1":
            if hanten:
                atm = l[2] + atm
            else:
                kts = kts + l[2]
        else:
            if hanten:
                kts = kts + l[2]
            else:
                atm = l[2] + atm

ans = atm + s + kts
if hanten == False:
    print(ans[::-1])
else:
    print(ans)