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

class DisjointSet:
    def __init__(self,size):
        self.rank=[0]*size
        self.p=[0]*size
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self,i):
        self.p[i]=i
        self.rank[i]=0
    
    def same(self,x,y):
        return self.findSet(x) == self.findSet(y)
    
    def unite(self, x,y):
        self.link(self.findSet(x), self.findSet(y))
    
    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y]+=1
     
    def findSet(self, x):
        if(x!=self.p[x]):
            self.p[x]=self.findSet(self.p[x])
        return self.p[x]

    def print(self):
        print(self.p)
        
def readinput():
    n,m=list(map(int,input().split()))
    p=list(map(int,input().split()))
    p.insert(0,0)
    pairs=[]
    for _ in range(m):
        pair=list(map(int,input().split()))
        pairs.append(pair)
    return n,m,p,pairs

def main(n,m,p,pairs):
    uft=DisjointSet(n+1)
    for x,y in pairs:
        if uft.same(x, y):
            pass
        else:
            uft.unite(x, y)

    #uft.print()

    #print(p)
    count=0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i==p[j]:
                #print(i,j)
                break
        if uft.same(i,j):
            #p[i],p[j] = p[j], p[i]
            count+=1
    
    return count

if __name__=='__main__':
    n,m,p,pairs=readinput()
    ans=main(n,m,p,pairs)
    print(ans)


### FIXED CODE ###

class DisjointSet:
    def __init__(self,size):
        self.rank=[0]*size
        self.p=[0]*size
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self,i):
        self.p[i]=i
        self.rank[i]=0
    
    def same(self,x,y):
        return self.findSet(x) == self.findSet(y)
    
    def unite(self, x,y):
        self.link(self.findSet(x), self.findSet(y))
    
    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y]+=1
     
    def findSet(self, x):
        if(x!=self.p[x]):
            self.p[x]=self.findSet(self.p[x])
        return self.p[x]

    def print(self):
        print(self.p)
        
def readinput():
    n,m=list(map(int,input().split()))
    p=list(map(int,input().split()))
    p.insert(0,0)
    pairs=[]
    for _ in range(m):
        pair=list(map(int,input().split()))
        pairs.append(pair)
    return n,m,p,pairs

def main(n,m,p,pairs):
    uft=DisjointSet(n+1)
    for x,y in pairs:
        if uft.same(x, y):
            pass
        else:
            uft.unite(x, y)

    #uft.print()

    #print(p)
    count=0
    for i in range(1,n+1):
        if uft.same(i,p[i]):
            #p[i],p[j] = p[j], p[i]
            count+=1
    
    return count

if __name__=='__main__':
    n,m,p,pairs=readinput()
    ans=main(n,m,p,pairs)
    print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = [[] for _ in range(n)]
M = iter(pqc)

#s = [set() for _ in range(n)]
s = set()
for p,q,c in zip(M,M,M):
    p -= 1
    q -= 1
    g[p].append((q,c))
    g[q].append((p,c))
    if p==0 or q==0: s.add(c)
    #s[p].add(c)
    #s[q].add(c)
    


from collections import deque
def bfs01(g,s):
    n = len(g)
    #checked = [0]*n
    #checked[0] = 1
    ans = INF = 1<<30
    mask = (1<<20)-1
    q = deque((ci,1) for ci in s)
    res = {ci:1 for ci in s}
    
    mmm = [INF]*n
    
    #print(res)
    while q:
        vl,dv = q.popleft()
        if res[vl] < dv: continue
        v,l = vl>>20, vl&mask
        for to,line in g[v]:
            tl = (to<<20)+line
            ndv = dv+(0 if l==line else 1)
            if tl not in res or res[tl] > ndv and mmm[to] >= ndv:
                mmm[to] = min(mmm[to],ndv)
                res[tl] = ndv
                if l==line: q.appendleft((tl,ndv))
                else: q.append((tl,ndv))
                
                #if to == n-1: ans = min(ans,ndv)
                
                #print(tl,ndv,(v,l,dv),l==line)
    ans = mmm[-1]                
        #print(q)
    if ans==INF: ans=-1
    return ans



print(bfs01(g,s))


#print(res)




### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[]
score=1
for i in range(k):
    score*=a[i]
l.append(score)
m=k
d=0
multi=a[m]
div=a[d]
for i in range(k+1,n+1):
    score=(score*a[m])//a[d]
    l.append(score)
    m+=1
    d+=1
old=l[0]
for i in range(1,len(l)):
    if l[i]<=old:
        print("No")
    else:
        print("Yes")
    old=l[i]

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=k
d=0
for i in range(k+1,n+1):
    if a[m]<=a[d]:
        print("No")
    else:
        print("Yes")
    m+=1
    d+=1
### BUGGY CODE ###

import collections
import copy
n = int(input())
aa = list(map(int, input().split()))

def comb(n, k):
    return (n * (n - 1)) // 2
    

memo = {}
for i in range(len(aa)):
    if not aa[i] in memo:
        hu = copy.deepcopy(aa)
        del hu[i]
        a = collections.Counter(hu)
        summ = 0
        for j in a:
            summ += comb(a[j], 2)
        memo[aa[i]] = summ
    print(memo[aa[i]])


### FIXED CODE ###

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

sub = collections.Counter(a)
ans = 0
for i in sub:
    ans += sub[i] * (sub[i] - 1) // 2
for i in range(n):
    ad = sub[a[i]] * (sub[a[i]] - 1) // 2 - ((sub[a[i]] - 1) * (sub[a[i]] - 2) // 2)
    print(ans - ad)
### BUGGY CODE ###

import numpy as np

n = int(input())
s = '^' + input().strip() + '$'

dp = (np.zeros((n + 2, n + 2)) - np.identity(n + 2) * 9999999).astype(int)
longest = 0
for i in range(1, n + 2):
    for j in range(i + 1, n + 2):
        if s[i] == s[j]:
            dp[i, j] = dp[i - 1, j - 1] + 1
        else:
            val = dp[i - 1, j - 1]
            if j - i < val:
                val = j - i
            if val > longest:
                longest = val

print(longest)

### FIXED CODE ###

n = int(input())
s = '^' + input().strip() + '$'

dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
longest = 0
for i in range(1, n + 2):
    for j in range(i + 1, n + 2):
        if s[i] == s[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            val = dp[i - 1][j - 1]
            if j - i < val:
                val = j - i
            if val > longest:
                longest = val

print(longest)
### BUGGY CODE ###

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

### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            count += 1
print(count)
### BUGGY CODE ###

from math import gcd
n,m=map(int,input().split())
s=input()
t=input()
res=n*m//gcd(n,m)
for i in range(res):
  if i*n/res==int(i*n/res) and i*m/res==int(i*m/res):
    if s[i*n//res]!=t[i*m//res]:
      print('-1')
      exit()
print(res)

### FIXED CODE ###

from math import gcd
n,m=map(int,input().split())
s=input()
t=input()
res=n*m//gcd(n,m)
a=m//gcd(n,m)
b=n//gcd(n,m)
if n>=m:
  for i in range(m):
    if (i*b)%a==0:
      if s[(i*b)//a]!=t[i]:
        print(-1)
        exit()
else:
  for i in range(n):
    if (i*a)%b==0:
      if s[i]!=t[(i*a)//b]:
        print(-1)
        exit()
print(res)
### BUGGY CODE ###

K = int(input())
q = [i for i in range(1, 10)]
for _ in range(K):
  x = q.pop(0)
  r = x%10
  if r != 0: q.append(x*10 + r - 1)
  q.append(x*10 + r)
  if r != 9: q.append(x*10 + r + 1)
print(x)

### FIXED CODE ###

K = int(input())
Q = [i for i in range(1, 10)]
k = 0
for q in Q:
  if k >= K:
    break
  r = q%10
  if r != 0:
    Q.append(q*10 + r - 1)
    k += 1
  Q.append(q*10 + r)
  k += 1
  if r != 9:
    Q.append(q*10 + r + 1)
    k += 1
print(Q[K-1])
### BUGGY CODE ###

n,m = map(int,input().split())
a_n = list(map(int,input().split()))
b_and_c = []
for i in range(m):
    b_and_c.append(list(map(int,input().split())))

for i in range(m):
    a_n.sort()
    for j in range(b_and_c[i][0]):
        if a_n[j] < b_and_c[i][1]:
            a_n[j] = b_and_c[i][1]
        else:
            break

print(sum(a_n))

### FIXED CODE ###

n,m = map(int,input().split())
a_n = list(map(int,input().split()))
b_and_c = []
for i in range(m):
    b_and_c.append(list(map(int,input().split())))

a_n.sort()

b_and_c.sort(key = lambda x : x[1], reverse = True)
index = 0
for i in range(m):
    if index >= n:
        break
    elif a_n[index] >= b_and_c[i][1]:
        break
    for j in range(index, n):
        if a_n[j] < b_and_c[i][1]:
            for k in range(j, min(j + b_and_c[i][0], n)):
                if a_n[k] < b_and_c[i][1]:
                    a_n[k] = b_and_c[i][1]
                else:
                    break
            index = k + 1
            break

print(sum(a_n))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

for i in range(N):
  P[i] -= 1

ans = max(C)
S = set(range(N))
while S:
  scores = []
  x = min(S)
  while x in S:
    S.remove(x)
    scores.append(C[x])
    x = P[x]
  l = len(scores)
  if K <= l:
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = 0
      for k in range(K):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)
  else:
    t = sum(scores)
    t = t * (K // l - 1) if t > 0 else 0
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = t
      for k in range(l + (K%l)):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

for i in range(N):
  P[i] -= 1

ans = max(C)
S = set(range(N))
while S:
  scores = []
  x = S.pop()
  while True:
    scores.append(C[x])
    x = P[x]
    if x not in S:
      break
    S.remove(x)
  l = len(scores)
  if K <= l:
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = 0
      for k in range(K):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)
  else:
    t = sum(scores)
    if t < 0:
      t = 0
    q, r = divmod(K, l)
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = t * (q - 1)
      for k in range(l):
        ss += scores[(i+k)%l]
        ans = max(ans, ss + (t if k < r else 0))

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

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

P = list(map(int, input().split()))

if N == 0:
    print(X)
    exit()

# high
high = 0
tmp = 0
while not high:
    if (X + tmp) in P:
        tmp += 1
        continue
    high = X + tmp

low = 0
tmp = 0
while not low:
    if (X - tmp) in P:
        tmp += 1
        continue
    low = X - tmp

if abs(X - low) == abs(X - high):
    print(low)
elif abs(X - low) < abs(X - high):
    print(low)
else:
    print(high)


### FIXED CODE ###

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

P = list(map(int, input().split()))

if N == 0:
    print(X)
    exit()

diff = 0
high = low = None
while True:
    if X + diff not in P:
        high = X + diff
    if X - diff not in P:
        low = X - diff
    if high is None and low is None:
        diff += 1
        continue

    if high == low:
        print(low)
    elif low is None:
        print(high)
    else:
        print(low)
    break
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                if k<=6500:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                if k<=6500:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                if k<=6500:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###

import sys #追加
sys.setrecursionlimit(500*500) #追加
n,m=map(int,input().split())
edge = [[] for i in range(n*3)]
#edge[i] : iから出る道の[行先]の配列
for i in range(m):
    x,y = map(int,input().split())
    x-=1;y-=1
    x*=3;y*=3
    edge[x  ].append(y+1)
    edge[x+1].append(y+2)
    edge[x+2].append(y  )
    
def dfs(s,g,res):
  if s==g or s==g+1 or s==g+2:
    if res%3==0:
      return res//3
  
  if res>m*3:
    return float("inf")
  
  l=float("inf")
  for i in edge[s]:
    l=min(l,dfs(i,g,res+1))
  return l
s,t=map(int,input().split())
s-=1;t-=1
ans=dfs(s*3,t*3,0)
if ans==float("inf"):
  print(-1)
else:
  print(ans)


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
edge = [[] for i in range(n+1)]
#edge[i] : iから出る道の[行先]の配列
for _ in range(m):
    u, v = map(int, input().split())
    edge[u].append(v)
s,t = map(int, input().split())
queue = deque()
queue.append((s, 0))
visited = [[False] * 3 for _ in range(n+1)]
while queue:
    u, d = queue.popleft()
    if visited[u][d % 3]:
        continue
    visited[u][d % 3] = True
    if d % 3 == 0 and u == t:
        print(d // 3);exit()
    for v in edge[u]:
        queue.append((v, d+1))
print(-1)
### BUGGY CODE ###

import sys
#from collections import defaultdict
n, limit= map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

#各重さとi番目の荷物を入れ終わった状態のテーブルをつくる
d = {}
dp = [d.copy() for _ in range(n)]

#初期状態
for w in range(L[0][0], limit+1):
    dp[0][w] = L[0][1]
#print(dp)
for i in range(1, n):
    for w in range(1, limit+1):
        if dp[i-1].get(w-L[i][0]) and dp[i-1].get(w): #キーが存在するなら
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w])
        elif dp[i-1].get(w) and w==L[i][0]:
            dp[i][w] = max(L[i][1], dp[i-1][w])
        elif dp[i-1].get(w):
            dp[i][w] = dp[i-1][w]
        elif w==L[i][0]:
            dp[i][w] = L[1][1]
    #print(dp)  
print(max(dp[-1].values()))

### FIXED CODE ###

import sys
n, limit = map(int, sys.stdin.readline().split()) 
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [dict() for i in range(n)]
#print(dp)
dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], float('inf')))
    for v, w in dp[i-1].items():
        dp[i][v] = min(dp[i-1][v], dp[i].get(v, float('inf')))
        dp[i][L[i][1] + v] = min(L[i][0] + dp[i-1][v], dp[i-1].get(L[i][1] + v, float('inf'))) 
        
ans = 0
for v, w in dp[-1].items():
    if w <=limit:
        if ans < v:
            ans = v
#print(dp)
print(ans)
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            if i*j+k==n:
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n):
    ans+=(n-1)//i
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
data = list(map(int, input().split()))
rui = [1]
for i in range(n):
    rui.append( rui[-1] * data[i] )

for i in range(n-k):
    if data[i:i+k][0] < data[i+1:i+k+1][-1]:
        print("Yes")
        # print( data[i:i+k] )
        # print( data[i+1:i+k+1] )
    else:
        print("No")


### FIXED CODE ###

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

for i in range(n-k):
    # if data[i:i+k][0] < data[i+1:i+k+1][-1]:
    # print("-----------------")
    # print( data[i:i+k] )
    # print( data[i+1:i+k+1] )

    # print( data[i] )
    # print( data[k+i] )
    # print("-----------------")

    if data[i] < data[k+i]:
        print("Yes")
        # print( data[i:i+k] )
        # print( data[i+1:i+k+1] )
    else:
        print("No")
### BUGGY CODE ###

#ABC073C

n=int(raw_input())
l=[]
for i in xrange(n):
 l.append(int(raw_input()))
s=set(l)
ls=list(set(s))
cnt=0
for i in xrange(len(ls)):
 if l.count(ls[i])%2:
  cnt+=1
print cnt


### FIXED CODE ###

#ABC073C
import sys

n=int(raw_input())
dic={}
for i in xrange(n):
 a=int(raw_input())
 if a in dic:
  dic[a]^=1
 else:
  dic[a]=1

res=0
for i in dic:
 if dic[i]==1:
  res+=1
print res
### BUGGY CODE ###

n = int(input())
a = input().split()

flag = True
if n % 2 == 0:
    for i in range(int(n/2)):
        if a.count(str(i*2 + 1)) == 2:
            pass
        else:
            flag = False
            break
    ans = 2**(n/2) % (1e9 + 7)

else:  # n % 2 == 1
    if a.count('0') == 1:
        for i in range(int((n - 1) / 2)):
            if a.count(str((i + 1) * 2)) == 2:
                pass
            else:
                flag = False
                break
    else:
        flag = False

    ans = 2**((n-1)/2) % (1e9 + 7)

if flag:
    print(int(ans))
else:
    print(0)


### FIXED CODE ###


from collections import Counter

n = int(input())
a = list(map(int, input().split()))
m = n // 2
ca = Counter(a)

if n % 2 == 1 and ca[0] == 1 and all(ca[(i+1)*2] == 2 for i in range(m)):
    ans = (2 ** m) % (10 ** 9 + 7)
    print(ans)
elif n % 2 == 0 and all(ca[i*2 + 1] == 2 for i in range(m)):
    ans = (2 ** m) % (10 ** 9 + 7)
    print(ans)
else:
    print(0)
### BUGGY CODE ###

from collections import Counter
from itertools import combinations

N = int(input())
S = [Counter(input()) for _ in range(N)]
ans = 0
for s1, s2 in combinations(S, 2):
  if s1 == s2:
    ans +=1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S={}
for _ in range(N):
  s = ''.join(sorted(input().rstrip()))
  if s in S:
    S[s] += 1
  else:
    S[s] = 1

ans=0
for s in S.values():
  ans += s*(s-1)//2
  
print(ans)
### BUGGY CODE ###

import bisect
n, k = map(int, input().split())
minus = []
zero = 0
plus = []
lm = 0
lp = 0
for i in map(int, input().split()):
  if i < 0:
    minus.append(-i)
    lm += 1
  elif i == 0:
    zero += 1
  else:
    plus.append(i)
    lp += 1

minus.sort()
plus.sort()

def test(x):
  count = 0
  if x < 0:
    x = -x
    for i in minus:
      count += lp - bisect.bisect_left(plus, -(-x//i))
    return count >= k
  
  if x == 0:
    count = lm*lp
    return count + zero*(n-zero) + zero*(zero-1)//2 >= k
  
  count = lm*lp + zero*(n-zero) + zero*(zero-1)//2
  for i in range(lm-1):
    t = minus[i]
    count += bisect.bisect_right(minus[i+1:], x//t)
  for i in range(lp-1):
    t = plus[i]
    count += bisect.bisect_right(plus[i+1:], x//t)
  return count >= k

ng = -(10**18)
ok = 10**18
while ok-ng > 1:
  mid = (ok+ng)//2
  if test(mid):
    ok = mid
  else:
    ng = mid
print(ok)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    for _ in range(q):
        query = input()
        if query[0] == '1':
            s = s[::-1]
        else:
            if query[2] == '1':
                s = query[-1] + s
            else:
                s += query[-1]

    print(s)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    q = int(input())

    rule = 0
    pre, suf = '', ''
    for _ in range(q):
        query = input()
        if query[0] == '1':
            rule += 1
        else:
            if rule % 2 == 0:
                if query[2] == '1':
                    pre = query[4] + pre
                else:
                    suf += query[4]
            else:
                if query[2] == '1':
                    suf += query[4]
                else:
                    pre = query[4] + pre

    s = pre + s + suf
    print(s if rule % 2 == 0 else s[::-1])


if __name__ == '__main__':
    main()