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

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    visited = [False] * (H * W)
    q = deque([(start[0], start[1], 0)])
    max_d = 0
    while q:
        (i, j, d) = q.popleft()
        max_d = max(max_d, d)
        visited[i * W + j] = True
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                q.append((i + dy, j + dx, d + 1))
    return max_d

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([start])
    dist[start[0] * W + start[1]] = 0
    while q:
        (i, j) = q.popleft()
        d = dist[i * W + j]
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx))
    return max(x for x in dist if x < INF)

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)
### BUGGY CODE ###

N = int(input())
AA = list(map(int,input().split()))
AAwIdx = [[0]*2 for _ in range(N)]
for i in range(N):
    AAwIdx[i][0] = i
    AAwIdx[i][1] = AA[i]
AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
#print(AA_sorted)

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

ans_all = 0
Idx_i = 0
Idx_f = N-1
for i in range(0,N):
    for no in range(i+1):
        idxi = i-no
        idxf = Idx_f-no
        ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1]
        if ans>answer[i+1-no][no]:
            answer[i+1-no][no] = ans
        ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1]
        if ans>answer[i-no][no+1]:
            answer[i-no][no+1] = ans
for i in range(N,N+1):
    for no in range(i+1):
        if ans_all<answer[i-no][no]:
            ans_all = answer[i-no][no]
  
print(ans_all)

### FIXED CODE ###

def solve():
    INF = float('inf')
 
    def max2(x, y): return x if x >= y else y
 
    N = int(input())
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]
 
    As.sort(reverse=True)
 
    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))
 
    ans = 0
    for i in range(N+1):
        j = N-i
        ans = max2(ans, dp[i][j])
 
    print(ans)
 
 
solve()
### BUGGY CODE ###

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

max = max(a)
list = []
for b in range(max*-1,max):
  sum = 0
  for i, j in enumerate(a):
    i = i+1
    sum += abs(j - (b+i))
  list.append(sum)

print(min(list))

### FIXED CODE ###

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

b = []

for i in range(n):
  b.append(a[i]-(i+1))

# print(b)
b.sort()
# print(b)

min_b=b[n//2]
# print(min_b)

ans = 0
for i in range(n):
  ans+=abs(a[i]-(min_b+(i+1)))
  # print(ans)
print(ans)
### BUGGY CODE ###

import heapq

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

flg = 0
heap = []

for i in range(N):
	heapq.heappush(heap, [- A[i] * F[i], F[i]])
	
for i in range(K):
	score, tmp_F = heapq.heappop(heap)
	if score != 0:
		score += tmp_F
		heapq.heappush(heap, [score, tmp_F])
	else:
		flg = 1
		break
		
if flg:
	print(0)
else:
	ret = heapq.heappop(heap)
	print(-1 * ret[0])	

### FIXED CODE ###

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

A.sort()
F.sort(reverse = True)

ng = -1
ok = 10 ** 12

while ok - ng > 1:
	mid = (ok + ng) // 2
	ctr = 0
	for i in range(N):
		ctr += max(0, A[i] - mid // F[i])
	if ctr <= K:
		ok = mid
	else:
		ng = mid

print(ok)
### BUGGY CODE ###

S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]

print(dp[N][5] % MOD)


### FIXED CODE ###

S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 13] %= MOD
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + n) % 13] %= MOD


print(dp[N][5] % MOD)
### BUGGY CODE ###

while True:
    N,M = map(int,input().strip().split(" "))
    if [N,M] == [0,0]:
        break
    D = 0 #目的地までの総距離
    L = []
    for i in range(N):
        d,p = map(int,input().strip().split(" "))
        for j in range(d):
            L.append(p)
        D = D + d
    L.sort()
    S = 0 #Sが襲われる回数の期待値
    for k in range(D-M):
        S = S + L[k]
    print(S)


### FIXED CODE ###

while True:
    N,M = map(int,input().strip().split(" "))
    if [N,M] == [0,0]:
        break
    L = []
    S = 0
    for i in range(N):
        l = list(map(int,input().strip().split(" ")))
        l.reverse()
        L.append(l)
        S = S + l[0]*l[1]
    L.sort()
    for j in range(0,N):
        t = N-j-1
        if M >= L[t][1]:
            S = S - L[t][0]*L[t][1]
            M = M - L[t][1]
        elif 0 < M:
            S = S - L[t][0]*M
            M = M - L[t][1]
    print(S)
### BUGGY CODE ###

N=int(input())
NUM=[i for i in range(1,N+1)]
H=list(map(int, input().split()))
L_NUM=[x+y for (x,y) in zip(NUM,H)]
R_NUM=[x-y for (x,y) in zip(NUM,H)]

ANS=0
for i in L_NUM:
    ANS+=R_NUM.count(i)
print(ANS)

### FIXED CODE ###

import collections
N=int(input())
NUM=[i for i in range(1,N+1)]
H=list(map(int, input().split()))
L_NUM=[x+y for (x,y) in zip(NUM,H)]
R_NUM=[x-y for (x,y) in zip(NUM,H)]

L_dict=collections.Counter(L_NUM)
R_dict=collections.Counter(R_NUM)

ANS=0
for i in L_dict.keys():
    cnt=L_dict[i]*R_dict[i]
    ANS+=cnt
print(ANS)
### BUGGY CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline

def main():
    n,c = map(int,input().split())
    x1,v1 = [0],[0]
    x2,v2 = [],[]
    for _ in range(n):
        a,b = map(int, input().split())
        x1.append(a)
        x2 = [c-a] + x2
        v1.append(b)
        v2 = [b] + v2
    x2 = [0] + x2
    v2 = [0] + v2

    v1, v2 = list(accumulate(v1)), list(accumulate(v2))

    f = [v2[i] - x2[i] for i in range(n+1)]
    f2 = [v2[i] - 2*x2[i] for i in range(n+1)]
    g1 = list(accumulate(f, max))
    g2 = list(accumulate(f2, max))
    val = max(v1[n]-x1[n] + g2[0], v1[n]-2*x1[n] + g1[0])
    for i in range(1,n+1):
        val = max(val, v1[n-i]-x1[n-i] + g2[i], v1[n-i]-2*x1[n-i] + g1[i])

    print(val)

if __name__=='__main__': main()

### FIXED CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline

def main():
    n,c = map(int,input().split())
    x1,v1 = [0],[0]
    for _ in range(n):
        a,b = map(int, input().split())
        x1.append(a)
        v1.append(b)
    x2 = [0]
    v2 = [0]
    for i in range(n,0,-1):
        x2.append(c-x1[i])
        v2.append(v1[i])

    v1, v2 = list(accumulate(v1)), list(accumulate(v2))
    g1,g2 = [v2[0]-x2[0]],[v2[0]-2*x2[0]]
    for i in range(1,n+1):
        f = v2[i] - x2[i]
        f2 = v2[i] - 2*x2[i]
        g1.append(max(g1[i-1],f))
        g2.append(max(g2[i-1],f2))
    val = max(v1[n]-x1[n] + g2[0], v1[n]-2*x1[n] + g1[0])
    for i in range(1,n+1):
        val = max(val, v1[n-i]-x1[n-i] + g2[i], v1[n-i]-2*x1[n-i] + g1[i])

    print(val)

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

N=int(input())
a=0
b=0
x=0
for i in range(N+1):
  a=i**0.5
  b=int(a)
  if(i==b*b):
   x=i
print(x)

### FIXED CODE ###

import math
N=int(input())
n=math.sqrt(N)
m=math.floor(n)
print(m*m)
### BUGGY CODE ###

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

comon = c.most_common()
ans = 0
for i in comon:
  if i[1] != 1:
  	ans += (i[1]*(i[1]-1)//2)
  
for i in a:
  if (ans-int(a.count(i))) < 0:
    print(0)
  else:
    co = a.count(i)
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))


      

### FIXED CODE ###

import collections
n = int(input())
a = list(map(str,input().split()))
ls = [i for i in range(2*10**5)]
c = collections.Counter(a)
comon = c.most_common()
ans = 0

for i in comon:
    if i != 1:
      ls[int(i[0])] = i[1]
      ans += (i[1]*(i[1]-1)//2)

for i in a:
    co = ls[int(i)]
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))
### BUGGY CODE ###

N, M, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
arui = [0] * (N + 1)
brui = [0] * (M + 1)
for i in range(N):
    arui[i + 1] = a[i] + arui[i]
for i in range(M):
    brui[i + 1] = b[i] + brui[i]

ans = 0
for i in range(N + 1):
    if arui[i] > K:
        break
    bcnt = M
    while brui[bcnt] + arui[i] > K:
        bcnt -= 1
    ans = max(ans, i + bcnt)

print(ans)

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

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

N=int(input())
li=[input() for i in range(N)]

B=[int(li.count(li[i])) for i in range(N)]

M=max(B)
C=[]
for i in range(N):
    if li.count(li[i])==M and not li[i] in C:
        C.append(li[i])
    else:
        pass

C.sort()

L=len(C)

for k in range(L):
    print(C[k])


### FIXED CODE ###

N=int(input())
li=[]
import collections

for i in range(N):
    S=input()
    li.append(S)

li.sort()

c=collections.Counter(li)
cl=c.values()
m=max(cl)
keys=[k for k,v in c.items() if v==m]
keys.sort()

for j in range(len(keys)):
    print(keys[j])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
while len(A) > 1:
    min_A = min(A)
    A = A-min_A
    A = A[A>0]
    A = np.append(A,[min_A])
    answer = min_A
    if answer == 1:
        break
print(min_A)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
while len(A) > 1:
    min_A = min(A)
    A = A%min_A
    A = A[A>0]
    A = np.append(A,[min_A])
    answer = min_A
    if answer == 1:
        break
print(min_A)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = input()
pc = X.count('1')


if pc == 0:
    print(*[1]*N, sep='\n')
    exit()
elif pc == 1:
    if int(X, 2) == 1:
        for i in range(N-1):
            print(2)
        print(0)
        exit()
    else:
        for i in range(N):
            if i == N-1:
                print(2)
            elif X[i] == '0':
                print(1)
            else:
                print(0)
        exit()

mod_plus_1, mod_minus_1 = 0, 0
for i in range(N):
    mod_plus_1 = (mod_plus_1*2+int(X[i])) % (pc+1)
    mod_minus_1 = (mod_minus_1*2+int(X[i])) % (pc-1)


def f(x):
    if x == 0:
        return 0
    else:
        return f(x % bin(x).count('1'))+1


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1 + 2**(N-1-i) % (pc+1)
        x %= (pc+1)
    else:
        x = mod_minus_1 - 2**(N-1-i) % (pc-1)
        x %= (pc-1)

    if x == 0:
        print(1)
    else:
        print(f(x)+1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = input()
pc = X.count('1')


if pc == 0:
    print(*[1]*N, sep='\n')
    exit()
elif pc == 1:
    if int(X, 2) == 1:
        for i in range(N-1):
            print(2)
        print(0)
        exit()
    else:
        for i in range(N):
            if i == N-1:
                print(2)
            elif X[i] == '0':
                print(1)
            else:
                print(0)
        exit()

mod_plus_1, mod_minus_1 = 0, 0
for i in range(N):
    mod_plus_1 = (mod_plus_1*2+int(X[i])) % (pc+1)
    mod_minus_1 = (mod_minus_1*2+int(X[i])) % (pc-1)


def f(x):
    if x == 0:
        return 0
    else:
        return f(x % bin(x).count('1'))+1


mods_p1, mods_m1 = [1 % (pc+1)], [1 % (pc-1)]
for i in range(N-1):
    mods_p1.append(mods_p1[-1]*2 % (pc+1))
    mods_m1.append(mods_m1[-1]*2 % (pc-1))
mods_p1 = mods_p1[::-1]
mods_m1 = mods_m1[::-1]


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1 + mods_p1[i]
        x %= (pc+1)
    else:
        x = mod_minus_1 - mods_m1[i]
        x %= (pc-1)

    if x == 0:
        print(1)
    else:
        print(f(x)+1)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

MOD = 10**9 + 7
U = 2 ** 20

N = int(input())
A = [int(x) for x in input().split()]
C = np.zeros(N,dtype = np.int64) # cumsum

cum = 0
for i,a in enumerate(A):
  cum ^= a
  C[i] = cum

arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1

zero_update = np.zeros(U,dtype=np.int64) #0が出てきて更新した回数
zero_cnt = 0

for i in range(N):
  c = C[i]
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b

answer = 0
final = C[-1]
if final != 0:
  answer = arr[final,0]
else:
  answer = arr[:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = [1] * U
arr_1 = [0] * U
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr_0[c]
  b = arr_1[c]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr_0[c] = a
  arr_1[c] = b
 
answer = 0
if c != 0:
  answer = arr_0[c]
else:
  answer = sum(arr_1[1:])
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
def left(i):
    if i < 1:
        return 0
    return gcd(left(i-1), A[i-1])
def right(i):
    if i+1 > n-1:
        return 0
    return gcd(right(i+1), A[i+1])
ans = 0
for i in range(n):
    ans = max(ans, gcd(left(i), right(i)))
print(ans)

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
L = [0]*n
R = [0]*n
for i in range(n-1):
    R [i+1] = gcd(R[i], A[i])
    L[i+1] = gcd(L[i], A[-i-1])
print(max(gcd(R[i], L[-i-1]) for i in range(n)))
### BUGGY CODE ###

def lcs(x, y):
    lx = len(x)
    ly = len(y)
    pcsl = [[0 for j in range(ly + 1)] for i in range(lx + 1)]
    for i in range(lx):
        for j in range(ly):
            if x[i] == y[j]:
                pcsl[i][j] = pcsl[i - 1][j - 1] + 1
            else:
                pcsl[i][j] = max(pcsl[i - 1][j], pcsl[i][j - 1])
    print(pcsl[i][j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs(ax, ay)

### FIXED CODE ###

def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print(len(indices) - 1)


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def judge(k: int, h: list, a:int, b:int):
    h = [max(0, hi - k*b) for hi in h]
    cnt = 0
    for hi in h:
        cnt += -(-hi//(a-b))

    return True if cnt <= k else False

def binary_search(h, a, b):
    low = 0
    high = 10**18

    while high - low > 1:
        mid = (high+low) // 2
        if judge(mid, h, a, b):
            high = mid
        else:
            low = mid

    return high

n, a, b = li()
h = [ni() for _ in range(n)]

print(binary_search(h, a, b))


### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def judge(k: int, h: list, a:int, b:int):
    h = [max(0, hi - k*b) for hi in h]
    cnt = 0
    for hi in h:
        cnt += -(-hi//(a-b))

    return True if cnt <= k else False

def binary_search(h, a, b):
    low = 0
    high = 10**18

    while high - low > 1:
        mid = (high+low) // 2
        if judge(mid, h, a, b):
            high = mid
        else:
            low = mid

    return high

n, a, b = li()
h = [ni() for _ in range(n)]

print(binary_search(h, a, b))
### BUGGY CODE ###

n = int(input())
for i in range(1, n+1):
    a = 0
    for x in range(1, 100):
        for y in range(x, int((10000-x**2)**(1/2))):
            for z in range(y, int((10000-x**2-y**2)**(1/2))):
                if x**2+y**2+z**2+x*y+y*z+z*x == i:
                    if x == y and y == z and z == y:
                        a += 1
                    elif x ==y or y == z or z == y:
                        a += 3
                    else:
                        a += 6
    print(a)

### FIXED CODE ###

n = int(input())
a = [0]*n
s = int(n**(1/2))+1
for i in range(1, s):
    for j in range(1, s):
        for k in range(1, s):
            b = i*i+j*j+k*k+i*j+j*k+k*i-1
            if b < n:
                a[b] += 1
for i in range(n):
    print(a[i])
### BUGGY CODE ###

n = int( input() )
strs = []
for i in range( n ):
	strs.append( ''.join( sorted( list( input() ) ) ) )

count = 0
strs = sorted( strs )
for i in range( n ) :
	bFound = False
	for j in range( i+1, n ) :
		if strs[i] == strs[j] :
			count += 1
			bFound = True
		elif bFound == True :
			break
		else:
			pass

print( count )


### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

#=-------------------------------------  
n = int( input() )

dict = {}
for i in range( n ):
	sorted_input = "".join( sorted( list( input() ) ) )
	if dict.get( sorted_input ) == None:
		dict[ sorted_input ] = 1
	else :
		dict[ sorted_input ] += 1

count = 0
for eachValue in dict.values():
	if eachValue == 1 : continue
	count += cmb( eachValue, 2 )
print( count )
### BUGGY CODE ###

s=input()
k=int(input())

lis=[]
for i in range(len(s)):
    for j in range(i,len(s)):
        if s[i:j+1] not in lis:
            lis.append(s[i:j+1])
            lis.sort()
            if len(s)==6:
                del lis[5]


print(lis[k-1])

### FIXED CODE ###

s=input()
k=int(input())

lis=[]
for i in range(len(s)):
    lis.append(s[i:i+5])
    lis.sort()

l=[]
for i in lis[:5]:
    for j in range(5):
        l.append(i[:j+1])

l=set(l)
l=list(l)

l.sort()

print(l[k-1])
### BUGGY CODE ###

import math
n, m = map(int, input().split())
p = []
pre = 0

def pattern_count(a,b):
    if a == 0 or b == 0:
        return 1
    else:
        return math.factorial(a+b)//(math.factorial(a)*math.factorial(b))

def count(a):
    ret = 0
    for i in range(a//2 + 1):
        ret += pattern_count(i, a-i*2)
    if ret == 0:
        return 1
    else:
        return ret

fault = False
for _ in range(m):
    a = int(input())
    if a == pre:
        fault = True
        break
    p.append(count(a-pre-1))
    pre = a+1

if fault:
    print(0)
else:
    p.append(count(n-pre))

    ans = 1
    for a in p:
        ans *= a

    print(ans % 1000000007)

### FIXED CODE ###

n, m = map(int, input().split())

hole_count = 0
pattern = [0,1]

if m != 0:
    a = int(input())
    hole_count += 1
else:
    a = n+1
    
for i in range(n):
    index = i + 1
    if index == a:
        pattern.append(0)
        if hole_count < m:
            a = int(input())
            hole_count += 1
    else:
        pattern.append(pattern[-1] + pattern[-2])

print(pattern[-1] % 1000000007)
### BUGGY CODE ###

N, K = map(int, input().split())
P = [(int(i)+1)/2 for i in input().split()]

wa_temp = 0
wa_max = 0.0
for i in range(N-K+1):
    wa_temp = sum(P[i:i+K])
    if wa_max < wa_temp:
        wa_max = wa_temp
print(wa_max)


### FIXED CODE ###

N, K = map(int, input().split())
P = [(int(i)+1)/2 for i in input().split()]

wa_temp = sum(P[0:K])
max_wa = wa_temp

for i in range(N-K):
    wa_temp = wa_temp - P[i] + P[i+K]
    if wa_temp > max_wa:
        max_wa = wa_temp
print(max_wa)
### BUGGY CODE ###

S = input()
Q = int(input())

flag = True
for _ in range(Q):
    query = input()
    if query[0] == '1':
        flag = not flag
    else:
        _, f, c = query.split()
        if (f == '1' and flag) or (f == '2' and not flag):
            S = c + S
        else:
            S = S + c
if not flag:
    S = S[::-1]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)