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

s=input()
q=int(input())

cnt=0
left=""
right=""

for i in range(q):
  qq=[x for x in input().rstrip().split()]

  if qq[0]=="2":
    t=int(qq[0])
    f=int(qq[1])
    c=qq[2]
    
    if cnt%2==1 and f==1:
      s=s+c
    elif cnt%2==1 and f==2:
      s=c+s
    elif cnt%2==0 and f==2:
      s=s+c
    elif cnt%2==0 and f==1:
      s=c+s

  else:
    cnt+=1


if cnt%2==1:
  print(s[::-1])
else:
  print(s)

### FIXED CODE ###

s=input()
q=int(input())

cnt=0
left=""
right=""

for i in range(q):
  qq=[x for x in input().rstrip().split()]

  if qq[0]=="2":
    t=int(qq[0])
    f=int(qq[1])
    c=qq[2]
    
    if cnt%2==1 and f==1:
      right=right+c
    
    elif cnt%2==1 and f==2:

      left=c+left
    elif cnt%2==0 and f==2:
  
      right=right+c
    elif cnt%2==0 and f==1:

      left=c+left

  else:
    cnt+=1

s=left+s+right
if cnt%2==1:
  print(s[::-1])
else:
  print(s)
### BUGGY CODE ###

def uf_find(x):
  z = x
  while z != p[z]:
    z = p[z]
  p[x] = z
  return z

def uf_unite(x,y):
  global rand
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    if r[y]>r[x]:
      x,y = y,x
    if r[x]==r[y]:
      r[x]+= 1
    p[y] = x


N, M = map(int, input().split())
p = list(range(N))
r = [0]*N

rand = 0

for i in range(M):
  A, B = [int(j)-1 for j in input().split()]
  uf_unite(A,B)
  #print(p)
  
for i in range(N):
  p[i] = uf_find(i)


q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))


### FIXED CODE ###

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

par = list(range(N))
rank = [1]*N
size = [1]*N

def find(x):
  if par[x] == x:
    return x
  else:
    return find(par[x])
  
def unite(x,y):
  x = find(x)
  y = find(y)
  
  if x == y:
    return
  if rank[x]<rank[y]:
    par[x]=y
    size[y]+= size[x]
  else:
    par[y] = x
    size[x] += size[y]
    if rank[x]==rank[y]:
      rank[x]+=1
    
for i in range(M):
  a,b = [int(i)-1 for i in input().split()]
  unite(a,b)
  
print(max(size))
### BUGGY CODE ###

eneNum, spNum = map(int, input().split())
eneHp = map(int, input().split())
eneHpList = list(eneHp)

count = 0
for i in range(spNum):
    if len(eneHpList) > 0:
        maxEneHp = max(eneHpList)
        eneHpList.remove(maxEneHp)
count = sum(eneHpList)

print("{}".format(count))

### FIXED CODE ###

eneNum, spNum = map(int, input().split())
eneHp = map(int, input().split())
eneHpList = list(eneHp)

# TLE
#count = 0
#for i in range(spNum):
#    if len(eneHpList) > 0:
#        maxEneHp = max(eneHpList)
#        eneHpList.remove(maxEneHp)

# new method
eneHpList.sort()
eneHpList.reverse()
del eneHpList[0:min([spNum, len(eneHpList)])]
count = sum(eneHpList)

print("{}".format(count))
### BUGGY CODE ###

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

count = 0
for i in range(N):
    for j in range(N):
        if A[i] == A[j]:
            count = count + 1

if count == N:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

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

A.sort()
count = 0

for i in range(1, N):
    if A[i-1] == A[i]:
        count += 1
        break

if count == 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    HP,n = map(int,input().split())
    s = [tuple(map(int,input().split())) for i in range(n)]

    #dp[damage] := モンスターにdamageを与える最小コスト
    dp = [float('inf')]*(HP+1) #0~HP
    dp[0] = 0
    for hp in range(HP):
        for damage, cost in s:
            next_idx = min(hp+damage, HP)
            dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
    print(dp[-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

HP,n = map(int,input().split())
s = [tuple(map(int,input().split())) for i in range(n)]

#dp[damage] := モンスターにdamageを与える最小コスト
dp = [float('inf')]*(HP+1) #0~HP
dp[0] = 0
for damage, cost in s:
    for hp in range(HP):
        next_idx = min(hp+damage, HP)
        dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
print(dp[-1])
### BUGGY CODE ###

n=int(input())
P=[float(i) for i in input().split()]
Ans=[[0]*(n+1) for _ in range(n+1)]
Ans[0][0]=1
for i in range(1,n+1):
  for j in range(i+1):
    if j==0:
      Ans[i][j]=Ans[i-1][j]*(1-P[i-1])
    else:
      Ans[i][j]=Ans[i-1][j]*(1-P[i-1])+Ans[i-1][j-1]*P[i-1]
ans=0
for i in range(n//2+1):
  ans+=Ans[n][i]
print(1-ans)

### FIXED CODE ###

n=int(input())
P=[float(i) for i in input().split()]
Ans=[[0]*(n+1) for _ in range(n+1)]
Ans[0][0]=1
for i in range(1,n+1):
  for j in range(i+1):
    if j==0:
      Ans[i][j]=Ans[i-1][j]*(1-P[i-1])
    else:
      Ans[i][j]=Ans[i-1][j]*(1-P[i-1])+Ans[i-1][j-1]*P[i-1]
ans=0
for i in range(n//2+1):
  ans+=Ans[n][i]
print(1-ans)
### BUGGY CODE ###

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

m = [[0]*n for _ in range(n)]
dp = [-1]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1

que.append(0)
dp[0] = 0

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1:
      if dp[i] != -1 :continue
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]


### FIXED CODE ###

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

m = [[] for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  m[a].append(b)
  m[b].append(a)
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in m[c]:
    if dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]
### BUGGY CODE ###

#XORはビットごとに独立しているので各ビットで0*1の演算回数を数える
n=int(input())
A=list(map(int,input().split()))
B=[0]*62 #1の個数カウント
mod=10**9+7

for i in range(n):
    a=bin(A[i])
    for j in range(len(a)-2):
        if a[-j-1]=="1":
            B[-j-1]+=1

ans=0
cnt=1 #2の累乗管理
for b in range(len(B)):
    prd=B[-b-1]*(n-B[-b-1])
    ans+=prd*cnt%mod
    cnt*=2
    ans%=mod
    cnt%=mod
print(ans)

### FIXED CODE ###

#XORはビットごとに独立しているので各ビットで0*1の演算回数を数える
n=int(input())
A=list(map(int,input().split()))
B=[0]*62 #1の個数カウント
mod=10**9+7

for i in range(n):
    a=bin(A[i])
    for j in range(len(a)-2):
        if a[-j-1]=="1":
            B[-j-1]+=1

ans=0
cnt=1 #2の累乗管理
for b in range(len(B)):
    prd=B[-b-1]*(n-B[-b-1])
    ans+=prd*cnt%mod
    cnt*=2
    ans%=mod
    cnt%=mod
print(ans)
### BUGGY CODE ###

# coding cell (SUBMIT ONLY THIS CELL)

N = int(input())

counter = []
num = []

for i in range(N):
    temp = input()
    if temp in counter:
        num[counter.index(temp)] += 1
    else:
        counter.append(temp)
        num.append(1)

m = max(num)

joined = []
for i in range(len(num)):
    joined.append([-1 * num[i], counter[i]])

joined.sort()

for i in range(len(num)):
    if joined[i][0] == -1 * m:
        print(joined[i][1])
    else:
        break

### FIXED CODE ###

# coding cell (SUBMIT ONLY THIS CELL)

N = int(input())

counter = {}

for i in range(N):
    temp = input()
    if temp not in counter:
        counter.update({temp : 1})
    else:
        counter.update({temp : counter[temp] + 1})

m = max(counter.values())
        
ans = []    

for a,b in counter.items():
    if b == m:
        ans.append(a)
    
ans.sort()

for i in ans:
    print(i)
### BUGGY CODE ###

import math
import collections

def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
A=list(map(int, input().split()))
l=[]
    
c = collections.Counter(A)
#print(c)
for i in range(N):
    x=0
    for k,v in c.items():
        if A[i]==k:
            if v>=3:
                a=combi(v-1,2)
                x+=a
        else:
            if v>=2:
                a=combi(v,2)
                x+=a
    l.append(x)
#print(l)
[print(i) for i in l]
            

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
C=Counter(a)
#print(C)
total=0
for k,v in C.items():
    if v>=2:
        total+=v*(v-1)//2
#print(total)
for i in range(n):
    V=C[a[i]]
    ans=total-(V*(V-1))//2+((V-1)*(V-2))//2
    print(ans)
### BUGGY CODE ###

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

count = 0
I = [0]*N
J = [0]*N
for i in range(N):
  I[i] = i+A[i]
  J[i] = i-A[i]
for j in range(N):
  count += J.count(I[j])

print(count)

### FIXED CODE ###

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

ans = 0
B = [0]*N
C = [0]*N

for i in range(N):
  b = i+A[i]
  c = i-A[i]
  if 0 < b < N:
    B[b] += 1
  if 0 < c < N:
    C[c] += 1

for i in range(N):
  ans += B[i]*C[i]

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

n=10**5+2
#n=100
p=[0]*n
ac=[0]*n
def prime_list(x):
    for i in range(2,x+1):
        flg=True
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                flg=False
        if flg==True:
            p[i]=1

def elato(x):
    pr=list(range(2,x+1))
    for i in pr:
        for j in pr:
            if j!=i and j%i==0:
                pr.remove(j)
    return pr
            
for i in elato(n):
    p[i]=1
#print(p)
pre=0
for i in range(n):
    if p[i]==1 and p[int((i+1)/2)]==1 and i%2==1:
        k=1
    else:
        k=0
    pre+=k
    ac[i]=pre

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(ac[r]-ac[l-1])

### FIXED CODE ###

n=10**5+2
#n=100
p=[0]*n
ac=[0]*n
def prime_list(x):
    for i in range(2,x+1):
        flg=True
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                flg=False
        if flg==True:
            p[i]=1

prime_list(n)
#print(p)
pre=0
for i in range(n):
    if p[i]==1 and p[int((i+1)/2)]==1 and i%2==1:
        k=1
    else:
        k=0
    pre+=k
    ac[i]=pre

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(ac[r]-ac[l-1])
### BUGGY CODE ###

n = int(input())
data = [int(x) for x in input().split()]

total = 0
for i in range(n):
    if min(data[:(i+1)]) == data[i]:
        total += 1

print(total)

### FIXED CODE ###

n = int(input())
data = [int(x) for x in input().split()]

min_num = data[0]
ans = 0
for i in range(n):
    if min_num >= data[i]:
        ans += 1
        min_num = data[i]

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

N,C = map(int,input().split())
T = [[0 for j in range(C)] for i in range(10**5+1)]

for _ in range(N):
    s,t,c = map(int,input().split())
    T[s][c-1] += 1
    T[t][c-1] -= 1
for i in range(10**5):
    for j in range(C):
        T[i+1][j] += T[i][j]

ans = 0
for i in range(10**5):
    a = 0
    for j in range(C):
        if T[i][j] or T[i+1][j]:
            a += 1
    ans = max(ans,a)
print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
T = [[0 for i in range(10**5+1)] for j in range(30)]

for i in range(N):
    s,t,c = map(int,input().split())
    T[c-1][s] += 1
    T[c-1][t] -= 1
for i in range(C):
    for j in range(10**5):
        T[i][j+1] += T[i][j]

for i in range(C):
    for j in range(10**5):
        if T[i][-j-1] == 0 and T[i][-j-2] == 1:
            T[i][-j-1] = 1
ans = 0
for i in range(10**5+1):
    ans = max(ans,sum(T[j][i] for j in range(C)))
print(ans)
### BUGGY CODE ###

import sys
N, M = map(int,input().split())
D = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,input().split())
  D[a-1].append(b)
  D[b-1].append(a)

if [] in D:
  print("No")
  sys.exit()
else:
  print("Yes")

ans = [0 for i in range(N)]

near_next = [1]

while 0 in ans[1:]:
  near = near_next
  near_next = []
  for i in near:
    for j in D[i-1]:
      if ans[j-1]==0:
        ans[j-1] = i
        if j not in near_next:
          near_next.append(j)
  
for i in ans[1:]:
  print(i)

### FIXED CODE ###

import queue
N, M = map(int,input().split())
D = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,input().split())
  D[a-1].append(b)
  D[b-1].append(a)

print("Yes")

dist = [0 for i in range(N)]
prev = [0 for i in range(N)]
prev[0] == 1

q = queue.Queue()
q.put(1)

while not q.empty():
  t = q.get()
  for i in D[t-1]:
    if prev[i-1] == 0:
      prev[i-1] = t
      q.put(i)

for i in prev[1:]:
  print(i)
### BUGGY CODE ###

S = list(input())
L = len(S)
M = 13
MOD = 10**9 + 7
dp = [[0]*M for _ in range(L+1)]
dp[0][0]=1
for i in range(L):
    if S[i] == "?":
        for j in range(M):
            for k in range(10):
                s = k*pow(10, L-1-i, 13)
                dp[i+1][(j+s)%13] += dp[i][j]
                dp[i + 1][(j + s) % 13] %= MOD
    else:
        s = int(S[i])
        s *= pow(10, L - 1 - i, 13)
        for j in range(M):
            dp[i+1][(j+s)%13] += dp[i][j]
            dp[i + 1][(j + s) % 13] %= MOD

print(dp[L][5])

### FIXED CODE ###

S = list(input())
L = len(S)
M = 13
MOD = 10**9 + 7
dp = [[0]*M for _ in range(L+1)]
dp[0][0]=1
for i in range(L):
    p = pow(10, L-1-i, 13)
    if S[i] == "?":
        for j in range(M):
            for k in range(10):
                s = k*p
                dp[i+1][(j+s)%13] += dp[i][j]
                dp[i + 1][(j + s) % 13] %= MOD
    else:
        s = int(S[i])
        s *= p
        for j in range(M):
            dp[i+1][(j+s)%13] += dp[i][j]
            dp[i + 1][(j + s) % 13] %= MOD

print(dp[L][5])
### BUGGY CODE ###

import numpy as np

N, K, Q = map(int, input().split()) 
score = np.array([0]*N)

def change_score(N ,A, score):
    score = score - np.array([1]*N)
    score[A-1] = score[A-1] + 1
    return score

for i in range(Q):
    A = int(input())
    score = change_score(N, A, score)
    #print(score)
    f_score = score

for i in f_score:
    if i + K> 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import numpy as np

N, K, Q = map(int, input().split()) 
score = np.array([0]*N)

def change_score(N ,A, score):
    #score = score - np.array([1]*N)
    score[A-1] = score[A-1] + 1
    return score

for i in range(Q):
    A = int(input())
    score = change_score(N, A, score)
    #print(score)
    f_score = score

for i in f_score:
    if i + K - Q > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC67 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
g = [[] for _ in range(n)]
w = [[float('inf')]*n for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    w[a-1][b-1] = 1
    w[b-1][a-1] = 1

def dijkstra(s,n,w):
    dist = [float('inf')]*n
    used = [False]*n
    dist[s] = 0
    while 1:
        v = -1
        for i in range(n):
            if not used[i] and v == -1:
                v = i
            elif not used[i] and dist[i] < dist[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            dist[j] = min(dist[j],dist[v] + w[v][j])
    return dist

white,black = 0,0
d1 = dijkstra(0,n,w)
d2 = dijkstra(n-1,n,w)
for i in range(n):
    if d1[i] <= d2[i]:
        black += 1
    else:
        white += 1
if black > white:
    print('Fennec')
else:
    print('Snuke')


### FIXED CODE ###

#!/usr/bin/env python3
#ABC67 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

que = deque()
que.append((0,0))
c1 = [False]*n
dist1 = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist1[v] = min(dist1[v],d)
    if not c1[v]:
        c1[v] = True
        for u in g[v]:
            que.append((d+1,u))
que = deque()
que.append((0,n-1))
c2 = [False]*n
dist2 = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist2[v] = min(dist2[v],d)
    if not c2[v]:
        c2[v] = True
        for u in g[v]:
            que.append((d+1,u))

w,b = 0,0
for i in range(n):
    if dist1[i] <= dist2[i]:
        b += 1
    else:
        w += 1
if w < b:
    print('Fennec')
else:
    print('Snuke')
### BUGGY CODE ###

from  collections import deque
N,M,K=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visit_list=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
for i in range(K):
    c,d=CD[i]
    graph_cd[c].append(d)
    graph_cd[d].append(c)

for j in range(1,N+1):
    stack=deque([j])
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.popleft()
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
    visit_list[j]=visited
for i in range(1,N+1):
    user[i]=visit_list[i].count(1)-len(graph_ab[i])
for i,value in enumerate(graph_cd):
    for j in value:
        if visit_list[i][j]==1:
            user[j]-=1
#     for i in range(j,N+1):
#         if visited[i]==1 and (i not in graph_ab[j]) and (i not in graph_cd[j]):
#             user[j]+=1
#             user[i]+=1
del user[0]
print(*user)

### FIXED CODE ###

from  collections import deque,Counter
N,M,K=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visited=[0 for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
time=0
for j in range(1,N+1):
    if visited[j]==0:
        stack=deque([j])
        time+=1
        visited[j]=time
        while stack:
            x=stack.popleft()
            for i in graph_ab[x]:
                if visited[i]==0:
                    visited[i]=time
                    stack.append(i)
#     visit_list[j]=visited
counter=Counter(visited) 
for i in range(K):
    c,d=CD[i]
    if visited[c]==visited[d]:
        graph_cd[c].append(d)
        graph_cd[d].append(c)

for i in range(1,N+1):
    user[i]=counter[visited[i]]-len(graph_ab[i])-len(graph_cd[i])-1

del user[0]
print(*user)
### BUGGY CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
m=10**10
for i in a:
    dis=abs(i-x)
    if m>dis:
        m=dis
while True:
    j=1
    for i in a:
        num=abs(i-x)
        if num%m!=0:
            j=0
    if j:
        break
    else:
        m-=1
print(m)

### FIXED CODE ###

from fractions import gcd
n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=abs(a[0]-x)
for i in range(1,n):
    ans=gcd(ans,abs(a[i]-x))
print(ans)
### BUGGY CODE ###

n,p = map(int,input().split())
s = list(map(int,list(input())))
ans = 0

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sp = [0]*n
  sp[n-1] = s[n-1]%p
  for i in range(1,n):
    sp[n-i-1] = (sp[n-i]+s[n-i-1]*(10**i%p))%p
  cj = sp.count(0)
  ans += int(cj*(cj+1)/2)
  for j in range(1,p):
      cj = sp.count(j)
      ans += int(cj * (cj-1)/2)
print(ans)

### FIXED CODE ###

n,p = map(int,input().split())
s = list(map(int,list(input())))
ans = 0
cnt = [0]*p
cnt[0] = 1

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sum = 0
  for i in range(n):
    sum = (sum+s[n-i-1]*pow(10,i,p))%p
    cnt[sum] += 1
  for j in range(p):
    cj = cnt[j]
    ans += cj * (cj-1)//2
print(ans)
### BUGGY CODE ###

from collections import deque
N = int(input())
dic = {}
for i in range(N):
  a = [int(i) for i in input().split()]
  dic[i+1] = deque(a[:])
count = 0
while True:
  nokori = 0
  flag = True
  log = [-1]*N
  for k in dic.keys():
    k = int(k)
    if dic[k]==deque([]):
      nokori += 1
      continue
    p2 = dic[k][0]
#    print(k,p2)
    if dic[p2]==deque([]):
      print(-1)
      break
    if dic[p2][0]==k and log[k-1]==-1 and log[p2-1]==-1:
      a = dic[k].popleft()
      b = dic[p2].popleft()
#      print('%', a,b)
      log[k-1] = 1
      log[p2-1] = 1
      flag = False
      
  if nokori == N:
    print(count)
    break
  count += 1
  if flag:
    print(-1)
    break
    

### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

N = int(input())
A = list(enumerate(list(map(int, input().split()))))
count = 0
B = sorted(A,key=lambda x:x[1])
h = [x[1] for x in B]
mem = [i+1 for i in range(N-1)]
Min = h[0] + h[1]
Max = h[-1] + h[-2]
for i in range(2,N):
    if Min > i:
        continue
    elif Max < i:
        break
    else:
        for j in range(N-1):
            c = h[j]
            if c >= i:
                break
            else:
                d = i - c
                for k in range(mem[j],N):
                    if h[k] == d:
                        if abs(B[j][0]-B[k][0]) == i:
                            count += 1
                    elif h[k] > d:
                        mem[j] = k
                        break
print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
b = Counter([x[0]+x[1]+1 for x in A])
c = Counter([x[0]-x[1]+1 for x in A])
count = 0
for x in b.items():
    count += x[1] * c[x[0]]
print(count)
### BUGGY CODE ###

n,a,b= map(int,input().split())
sh = sorted([int(input()) for i in range(n)],reverse=True)
sumh = sum(sh)
def nibu(t):
    rt=0
    for i in range(n):
        temp = -1*(-1*max(0,sh[i]-t*b)//(a-b))
        if temp>0:rt+=-1*(-1*max(0,sh[i]-t*b)//(a-b))
        else:break
    return True if t>=rt else False

l,r=0,-1*(-1*sumh//b)
while r-l!=1:
    m = (l+r)//2
    if nibu(m):r=m
    else:l=m

print(r)

### FIXED CODE ###

n,a,b= map(int,input().split())
sh = sorted([int(input()) for i in range(n)],reverse=True)
sumh = sum(sh)
def nibu(t):
    rt=0
    for i in range(n):
        temp = -1*(-1*max(0,sh[i]-t*b)//(a-b))
        if temp>0:rt+=-1*(-1*max(0,sh[i]-t*b)//(a-b))
        else:break
        if rt>t:return False
    return True if t>=rt else False
l=max(sh)//a
r=max(sh)//b+1
while r-l!=1:
    m = (l+r)//2
    if nibu(m):r=m
    else:l=m
print(r)