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

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,X,M = map(int,input().split())

    A = [-1 for i in range(M)]
    A[0] = X

    start = N
    end = N

    cnt = [0 for i in range(M)]

    for i in range(1,M):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i

    # print(A)

    # print(start,end)
    # print(A[start],temp)

    L = end - start + 1
    straight = [0 for i in range(start)]
    loop = [0 for i in range(L)]

    for i in range(start):
        straight[i] = straight[i-1] + A[i]

    if start != N:
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]

    # print(straight)
    # print(loop)

    res = 0

    if start != 0:
        if N >= start:
            res += straight[-1]
            N -= start
        else:
            res += straight[N-1]
            N = 0


    if start != N:
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8[:],i8[:],i8,i8,i8))
def SerchLoop(M,A,cnt,start,end,temp):
    for i in range(1,M+2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i
    return np.append(np.append(A,start),end)


def main():
    N,X,M = map(int,input().split())

    A = [-1 for i in range(M+2)]
    A[0] = X
    A = np.array(A)

    start = -1
    end = -1

    cnt = [0 for i in range(M)]
    cnt[X] = 0
    cnt = np.array(cnt)

    C = SerchLoop(M,A,cnt,start,end,0)
    A = C[:-2]
    start = C[-2]
    end = C[-1]

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(N):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()
### BUGGY CODE ###

H, N = map(int, input().split())
AB = [0] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

m = 10**4 + 100

dp = [float("INF")] * m

dp[0] = 0

for i in range(H):
    for x in AB:
        if i + x[0] <= H:
            dp[i + x[0]] = min(dp[i + x[0]], dp[i] + x[1])
        else:
            dp[H] = min(dp[H], dp[i] + x[1])

print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
AB = [0] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

m = 10**4 + 100

dp = [float("INF")] * m

dp[0] = 0

for i in range(H):
    for x in AB:
        if i + x[0] <= H:
            dp[i + x[0]] = min(dp[i + x[0]], dp[i] + x[1])
        else:
            dp[H] = min(dp[H], dp[i] + x[1])

print(dp[H])
### BUGGY CODE ###

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

# 文字数のカウント
cnt=dict()
for a in A:
  if a in cnt.keys():
    cnt[a]+=1
  else:
    cnt[a]=1
    
# 頻出数を探す
cnt_sort = sorted(cnt.items(), key=lambda x:x[1])
cnt_sort.reverse()

# 頻出数100つとその±1の数字を候補とする
candidates=set()
for i in range(min(100,len(cnt))):
  candidates.add(cnt_sort[i][0])
  candidates.add(cnt_sort[i][0]-1)
  candidates.add(cnt_sort[i][0]+1)

# 配列に渡された配列内に，±1で数xに出来る数がいくつあるか判定
def neigh(array, x):
  cnt = 0
  for a in array:
    if a == x:
      cnt+=1
    elif a-1 == x:
      cnt+=1
    elif a+1 == x:
      cnt+=1
  return cnt

res=[]
for c in candidates:
  res.append(neigh(A,c))
  
print(max(res))

### FIXED CODE ###

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

cnt=dict()
# a内の数とその±1をdict型の配列に入れながら個数をカウント
for a in A:
  cnt[a] = cnt.setdefault(a,0) + 1
  cnt[a-1] = cnt.setdefault(a-1,0) + 1
  cnt[a+1] = cnt.setdefault(a+1,0) + 1
  
  
# カウントした数字で昇順にソート  
cnt_sort = sorted(cnt.items(), key=lambda x:x[1])
cnt_sort.reverse()

print(cnt_sort[0][1])
### BUGGY CODE ###

def main():
    from itertools import accumulate

    n, k = map(int, input().split())
    A = list(map(int, input().split())) + [0]
    for _ in range(k):
        l = [0] * (n + 1)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = list(accumulate(l))
    print(*A[:-1])

main()

### FIXED CODE ###

import numpy as np
from numba import jit


@jit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


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

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, MOD = [int(i) for i in input().split()]
adj = [[] for _ in [0] * (n+1)]
dp = [[0, 0] for i in range(n+1)]
dp2 = [0] * (n+1)


def dfs1(node, pn):
    dp[node] = [1, 1]
    for i in adj[node]:
        if i == pn:
            continue
        dfs1(i, node)
        dp[node][0] = (dp[node][0] * (dp[i][0] + dp[i][1]))
        dp[node][1] = (dp[node][1] * dp[i][1])
    return



def dfs2(node, pn):
    dp2[node] = dp[node][0] % MOD

    for i in adj[node]:
        if i == pn:
            continue

        dp[node][0] = (dp[node][0] / (dp[i][0] + dp[i][1]));
        dp[node][1] = (dp[node][1] / dp[i][1]);
        dp[i][0] = (dp[i][0] * (dp[node][0] + dp[node][1]));
        dp[i][1] = (dp[i][1] * dp[node][1]);
        dfs2(i, node);
        dp[i][1] = (dp[i][1] / dp[node][1]);
        dp[i][0] = (dp[i][0] / (dp[node][0] + dp[node][1]));
        dp[node][0] = (dp[node][0] * (dp[i][0] + dp[i][1]));
        dp[node][1] = (dp[node][1] * dp[i][1]);
    return



for _ in range(n-1):
    x, y = [int(i) for i in input().split()]
    adj[x].append(y)
    adj[y].append(x)

dfs1(1, -1)
dfs2(1, -1)

for i in range(1, n+1):
    print(dp2[i])


### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n,MOD = [int(i) for i in input().split()]

to = [[] for _ in [0]*n]
for _ in range(n-1):
    x,y = [int(i)-1 for i in input().split()]
    to[x].append(y)
    to[y].append(x)


dp = [[0]*len(to_i) for to_i in to]
parent_index = [-9999]*n 
ans = [0]*n

def dfs(v, p):
    res = 1
    for i, vc in enumerate(to[v]):
        if vc == p:
            parent_index[v] = i
            continue
        dp[v][i] = dfs(vc, v)
        res *= dp[v][i]+1
        res %= MOD
    return res

def dfs2(v, res_p, p):
    deg = len(to[v])
    if p >= 0:
        dp[v][parent_index[v]] = res_p

    accl = [1]*(deg+1)
    accr = [1]*(deg+1)

    for i in range(1, deg+1):
        accl[i] = accl[i-1] * (dp[v][i-1] + 1) % MOD
        accr[-i-1] = accr[-i] * (dp[v][-i] + 1) % MOD

    ans[v] = accr[0]
    for i,vc in enumerate(to[v]):
        if vc == p: continue
        dfs2(vc, accl[i]*accr[i+1]%MOD, v)

dfs(0,-1)
#print(dp)
dfs2(0,0,-1)
#print(dp)
for i in ans:
    print(i)
### BUGGY CODE ###

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

while(True):
    if n % k == 0:
        n = 0
        break

    if k % n == 0:
        break

    new = abs(n-k)
    if new < n:
        n = new
        continue
    else:
        break

print(n)

### FIXED CODE ###

n, k = list(map(int, input().split()))
if n < k:
    print(min(n, k-n))
else:
    print(min(n%k, k-(n%k)))
### BUGGY CODE ###

from fractions import gcd

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

if len(set([i&-i for i in a])) != 1:
  print(0)
else:
  x = a[0]/2
  for i in range(1, len(a)):
      x = x*(a[i]/2//gcd(x,a[i]/2))

  print(int(((M//x)+1)//2))

### FIXED CODE ###

from fractions import gcd

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

if len(set([i&-i for i in a])) != 1:
  print(0)
else:
  x = a[0]//2
  for i in range(1, len(a)):
      x = x*(a[i]//2//gcd(x,a[i]//2))

  print(M//x-M//(2*x))
### BUGGY CODE ###

n = int(input())
x = input()
num = 0
count = 0
for i in range(n):
    if x[-(i+1)] == "1":
        num += 2**i
        count += 1

mod = [[0, 0] for _ in range(n)]
for i in range(n):
    mod[i][0] = 2**i%(count-1) if count!=1 else 0
    mod[i][1] = 2**i%(count+1)
mod1 = num%(count-1) if count!=1 else 0
mod2 = num%(count+1)

ans = [0]*n
for i in range(n):
    if x[-(i+1)] == "1":
        _num = num-2**i
        if _num == 0:
            continue
        _num = (mod1-mod[i][0])%(count-1)
    else:
        _num = num+2**i
        _num = (mod2+mod[i][1])%(count+1)
    ans[i] += 1
    _count = 0
    for c in bin(_num):
        if c == "1":
            _count += 1
    while True:
        if _num == 0:
            break
        _num %= _count
        _count = 0
        for c in bin(_num):
            if c == "1":
                _count += 1
        ans[i] += 1
for i in range(n):
    print(ans[-(i+1)])

### FIXED CODE ###

n = int(input())
x = input()
num = 0
count = 0
for i in range(n):
    if x[-(i+1)] == "1":
        num += 2**i
        count += 1

mod = [[0, 0] for _ in range(n)]
mod[0][0] = 1%(count-1) if count!=1 else 0
mod[0][1] = 1%(count+1)
for i in range(1, n):
    if mod[i-1][0] != 0:
        mod[i][0] = (mod[i-1][0]*2)%(count-1)
    if mod[i-1][1] != 0:
        mod[i][1] = (mod[i-1][1]*2)%(count+1)
mod1 = num%(count-1) if count!=1 else 0
mod2 = num%(count+1)

table = [0]*(2*10**5+10)
for i in range(2*10**5+10):
    _num = i
    while True:
        _count = 0
        for c in bin(_num):
            if c == "1":
                _count += 1
        if _num == 0:
            break
        _num %= _count
        table[i] += 1

ans = [0]*n
for i in range(n):
    if x[-(i+1)] == "1":
        _num = num-2**i
        if _num == 0:
            continue
        _num = (mod1-mod[i][0])%(count-1)
    else:
        _num = num+2**i
        _num = (mod2+mod[i][1])%(count+1)
    ans[i] = 1+table[_num]
for i in range(n):
    print(ans[-(i+1)])
### BUGGY CODE ###

n = int(input())
arr = sorted(list(map(int,input().split())))

count = 0

for a in range(n-2):
    for b in range(a+1,n-1):
        for c in range(b+1,n):
            if arr[a]<arr[b]+arr[c] and arr[b]<arr[c]+arr[a] and arr[c]<arr[a]+arr[b]:
                count +=1
            else:
                break

print(count)

### FIXED CODE ###


n = int(input())
arr = list(map(int,input().split()))
arr.sort()

count = 0

for a in range(n-2):
    k = a+2
    for j in range(a+1,n):
        while (k < n and arr[a] + arr[j] > arr[k]):
            k+=1
        
        if k>j:
            count += k-j-1
        
print(count)
### BUGGY CODE ###

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

N, W = map(int, readline().split())
tmp = map(int, read().split())
wv = tuple(zip(tmp, tmp))

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
    for w in range(W + 1):
        if wv[i][0] <= w:
            dp[i + 1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]

print(max(dp[-1]))

### FIXED CODE ###

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

N, W = map(int, readline().split())
wv = map(int, read().split())
dp = np.zeros(W + 1, np.int64)

for w, v in zip(wv, wv):
    np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])

print(dp.max())
### BUGGY CODE ###

from collections import deque

def a():
    H,W = map(int,input().split())
    S = ["" for _ in range(H)]
    for _ in range(H):
        S[_] = input()
    b = lambda n:S[n//W][n%W] == '.'
    u = map(lambda n:(n%W,n//W),filter(b,range(H*W)))

    def bfs(root):
        depth = [[-1]*W for _ in range(H)]
        q = deque()
        q.append((root,0))
        while q:
            r,d = q.popleft()
            x,y = r
            depth[y][x] = d
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                dx += x
                dy += y
                if 0 <= dx < W and 0 <= dy < H and depth[dy][dx] == -1 and S[dy][dx] == ".":
                    q.append(((dx,dy),d+1))
        return depth
    
    p = []
    for x in map(bfs,u):
        o = []
        for y in x:
            o.append(max(y))
        p.append(max(o))
    print(max(p))


a()





### FIXED CODE ###

from collections import deque

def a():
    H,W = map(int,input().split())
    S = ["" for _ in range(H)]
    for _ in range(H):
        S[_] = input()
    b = lambda n:S[n//W][n%W] == '.'
    v = list(filter(b,range(H*W)))
    u = list(map(lambda n:(n%W,n//W),v))

    le = len(v)

    def bfs(root):
        i = 0
        depth = [[-1]*W for _ in range(H)]
        in_que = [[0]*W for _ in range(H)]
        q = deque()
        q.append((root,0))
        xx,yy = root
        in_que[yy][xx] = 1
        while i < le:
            r,d = q.popleft()
            x,y = r
            depth[y][x] = d
            i += 1
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                dx += x
                dy += y
                if 0 <= dx < W and 0 <= dy < H and in_que[dy][dx] == 0 and S[dy][dx] == ".":
                    q.append(((dx,dy),d+1))
                    in_que[dy][dx] = 1
        return depth
    
    print(max([max([max(y) for y in x]) for x in map(bfs,u)]))

a()
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())

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

for i in range(M):
    B, C = map(int, input().split())
    A.extend([C]*B)

E = list(A)
E.sort(reverse = True)

print(sum(E[:N])) 

### FIXED CODE ###

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

A = sorted(list(map(int, input().split())), reverse=True)

B = []
for i in range(M):
    b, c = map(int, input().split())
    B.append([b, c])

B.sort(key=lambda x:(-x[1]))

cnt = 0
ans = 0
a = 0
b = 0
while True:
    if b <= M-1 and A[a] <= B[b][1]:
        n = min(B[b][0], N-cnt)
        ans += B[b][1]*n
        cnt += n
        if cnt == N:
            print(ans)
            break
        b += 1
    elif a <= N-1:
        cnt += 1
        ans += A[a]
        if cnt == N:
            print(ans)
            break
        a += 1
### BUGGY CODE ###

n=int(input())
a=[0]+[int(i) for i in input().split()]
m=0
ans=[]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
for i in range(n,0,-1):
    if a[i]%2==1:
        m+=1
        ans.append(i)
        l=make_divisors(i)
        for j in l:
            a[j]+=1
print(m)
if ans!=[]:
    for i in range(m):
        if i!=m-1:
            print(ans[i],end=" ")
        else:
            print(ans[i])


### FIXED CODE ###

n=int(input())
a=[0]+[int(i) for i in input().split()]
m=0
ans=[]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
for i in range(n,0,-1):
    if a[i]%2==1:
        m+=1
        ans.append(i)
        l=make_divisors(i)
        for j in l:
            a[j]+=1
print(m)
if ans!=[]:
    for i in range(m):
        if i!=m-1:
            print(ans[i],end=" ")
        else:
            print(ans[i])
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                ans+=1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z >= 0 and z <= k:
            cnt += 1

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

l = input()
length = len(l)

idx = 0
ones = 0

pattern = 3 ** len(l)

for s in l:
    idx += 1
    if s == "1":
        ones += 1
    else:
        pattern -= (2 ** (ones + 1)) * (3 ** (length - idx))

print(pattern % 1000000007)

### FIXED CODE ###

l = input()
length = len(l)

idx = 0
ones = 0

prime = 1000000007

pattern = pow(3, length, prime)

for s in l:
    idx += 1
    if s == "1":
        ones += 1
    else:
        pattern -= (pow(2, ones + 1, prime) * pow(3, length - idx, prime)) % prime

print(pattern % prime)
### BUGGY CODE ###

N = int(input())
A = sorted((map(int,input().split())))
B = [True]*N

for i in range(N):
    for j in range(i,N):
        if B[j] and j != i:
            if A[j]==A[i]:
                B[i] = False
                B[j] = False
            elif A[j]%A[i]==0:
                B[j] = False
ans = 0
for i in range(N):
    if B[i]:
        ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
A = sorted((map(int,input().split())))
a_Max = A[-1]
B = [0]*a_Max

for a in A:
    if B[a-1] == 0:
        B[a-1] = 1
        for j in range(2,a_Max+1):
            if a*j > a_Max:
                break
            B[a*j-1] = 2
    elif B[a-1] == 1:
        B[a-1] = 2
            
ans = 0
for b in B:
    if b == 1:
        ans += 1

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

N=int(input())
ans=0
for i in range(1,N+1):
    for j in range(i,N+1,i):
        ans+=j
print(ans)


### FIXED CODE ###

N=int(input())
#sum[k:1 to N]floor(N/K)
ans=0
j=1
while(j*(j*1)<=N):
    b=1+(N//j)
    a=1+(N//(j+1))
    tmp=((N//a)*((N//a)+1))//2
    tmpa=(a*(a-1))//2
    tmpb=(b*(b-1))//2
    ans+=(tmpb-tmpa)*tmp
    j+=1
for i in range(1,a):
    ans+=i*((N//i)*((N//i)+1))//2
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(int(i/2) for i in map(int, input().split()))
A.sort(reverse = True)
m = max(A)
A.remove(m)
cnt = 0
for i in range(m,M+1,2*m):
	semi = True
	for j in A:
		if i % j != 0 or (i // j) % 2 == 0:
			semi = False
	if semi:
		cnt += 1

print(cnt)

### FIXED CODE ###

N, M = map(int, input().split())
A = set(i//2 for i in map(int, input().split()))
B = []
for i in A:
	B = B + [0]
	while i % 2 == 0:
		i //= 2
		B[-1] += 1
if len(set(B)) == 1:
	m = max(A)
	A.remove(m)
	base = 0
	for i in range(m,M+1,2*m):
		semi = True
		for j in A:
			if i % j != 0 or (i // j) % 2 == 0:
				semi = False
				break
		if semi:
			base = i
			break
	if base == 0:
		print(0)
	else:
		print(((M // base) + 1)//2)
else:
	print(0)
### BUGGY CODE ###

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

for i in range(N):
  box.insert(i,A.index(i+1)+1)

print(' '.join(map(str, box)))

### FIXED CODE ###

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

a=[0]*N

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

print(" ".join(map(str,a)))
### BUGGY CODE ###

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))
Flg = "YES"

for i in range(M):
    if(T.count(T[i]) > D.count(T[i])):
        Flg = "NO"
        break
print(Flg)

### FIXED CODE ###

from collections import Counter
N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))
Flg = "YES"

c1 = Counter(D)
c2 = Counter(T)

for i, val in c2.items():
    if(c1[i] < val):
        Flg = "NO"
        break
print(Flg)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = []
for i in range(m):
    bc.append(list(map(int, input().split())))
bc.sort(key = lambda x: x[1], reverse = True)
a.sort(reverse = True)
sum_a = 0
count = 0
while count < n:
    if not bc:
        sum_a += sum(a)
        break
    if not a:
        amount = min(bc[0][0], n - count)
        sum_a += bc[0][1] * amount
        count += amount
        del bc[0]
    if a[0] >= bc[0][1]:
        sum_a += a[0]
        count += 1
        del a[0]
    else:
        amount = min(bc[0][0], n - count)
        sum_a += bc[0][1] * amount
        count += amount
        del bc[0]
        a = a[:len(a) - amount]
print(sum_a)

### FIXED CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = []
for i in range(m):
    bc.append(list(map(int, input().split())))
bc.sort(key = lambda x: x[1], reverse = True)
a.sort(reverse = True)
count = 0 
count2 = 0
a2 = [0]
for i in range(n):
    a2.append(a2[-1] + a[i])
a.reverse()
sum_a = 0
for i in range(m):
    num = bc[i][1]
    num2 = bc[i][0]
    temp = n - bisect.bisect_left(a, num)
    count += temp
    count2 += temp
    temp2 = min(num2, n - count2)
    sum_a += num * temp2
    count2 += temp2
    if count2 == n:
        break
    count -= temp
    count2 -= temp
count3 = n - (count2 - count)
sum_a += a2[count3]
print(sum_a)
### BUGGY CODE ###

N,P=map(int,input().split())
S=str(input())
count=0

listS=[i for i in S]


for start in range(N):
    for end in range(start,N):
        num=""
        for i in range(start,end+1):
            num=num+listS[i]       
        num=int(num)
        if num%P==0:
            count+=1
print(count)


### FIXED CODE ###

n, p = map(int, input().split())
 
s = list(input())
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        ten *= 10
        ten %= p
        d[i - 1] = (d[i] + a) % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        cnt[d[i]] += 1
    for  i in cnt:
        ans+=i*(i-1)/2

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

def main():
    s = input()
    q = int(input())
    r = s[::-1]
    for i in range(q):
        query = input().split()
        if query[0] == "1":
            s,r = r,s
        else:
            if query[1] == "1":
                s = query[2] + s
                r = r + query[2]
            if query[1] == "2":
                s = s + query[2]
                r = query[2] + r
    print(s)



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    q = int(input())
    left = ""
    right = ""
    hanten = False
    for i in range(q):
        query = input().split()
        if query[0] == "1":
            hanten = not hanten
        else:
            c = query[2]
            if query[1] == "1":
                if not hanten:
                    left += c
                else:
                    right += c
            else:
                if not hanten:
                    right += c
                else:
                    left += c
        #print(query)
        #print(s,left,right)
    left = left[::-1]
    answer = left + s + right

    if not hanten:
        print(answer)
    else:
        print(answer[::-1])


if __name__ == '__main__':
    main()