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

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

r = 0
g = 0
b = 0
cnt_S = []
for i, s in enumerate(S):
    if s == 'R':
        r += 1
    elif s == 'G':
        g += 1
    else:
        b += 1
    cnt_S.append([r, g, b])

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] == 'R':
            if S[j] == 'G':
                ans += cnt_S[-1][2] - cnt_S[j][2]
                if 2 * j - i < N and S[j + j - i] == 'B':
                    ans -= 1
            if S[j] == 'B':
                ans += cnt_S[-1][1] - cnt_S[j][1]
                if 2 * j - i < N and S[j + j - i] == 'G':
                    ans -= 1
        elif S[i] == 'G':
            if S[j] == 'R':
                ans += cnt_S[-1][2] - cnt_S[j][2]
                if 2 * j - i < N and S[j + j - i] == 'B':
                    ans -= 1
            if S[j] == 'B':
                ans += cnt_S[-1][0] - cnt_S[j][0]
                if 2 * j - i < N and S[j + j - i] == 'R':
                    ans -= 1
        else:
            if S[j] == 'R':
                ans += cnt_S[-1][1] - cnt_S[j][1]
                if 2 * j - i < N and S[j + j - i] == 'G':
                    ans -= 1
            if S[j] == 'G':
                ans += cnt_S[-1][0] - cnt_S[j][0]
                if 2 * j - i < N and S[j + j - i] == 'R':
                    ans -= 1
print(ans)





### FIXED CODE ###

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

r = 0
g = 0
b = 0
cnt_S = []
for i, s in enumerate(S):
    if s == 'R':
        r += 1
    elif s == 'G':
        g += 1
    else:
        b += 1
    cnt_S.append([r, g, b])

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

N = int(input())

def main():
    a = [int(input()) for _ in range(N)]
    visited = []
    idx = 0
    ans = 0
    while True:
        n = a[idx] - 1
        ans += 1
        if n == 1:
            break
        if visited.count(n):
            ans = -1
            break
        visited.append(n)
        idx = n 
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())

def main():
    a = [[int(input()), False] for _ in range(N)]
    idx = 0
    ans = 0
    while True:
        idx = a[idx][0] - 1
        ans += 1
        if idx == 1:
            break
        if a[idx][1]:
            ans = -1
            break
        a[idx][1] = True
    print(ans)

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

def main():
	n,m = map(int,input().split())
	a = list(map(int,input().split()))
	maxl = [sum(a[0:m])]
	i = 1
	while i + m <= len(a):
		maxl.append(max(sum(a[i:i+m]),maxl[-1]))
		i += 1
	ans = 0
	for i in range(m):
		for t in range(1,a[maxl.index(max(maxl))+i]+1):
			ans += t * (1/(a[maxl.index(max(maxl))+i]))
	print(ans)
	
 
if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	n,m = map(int,input().split())
	a = list(map(int,input().split()))
	wa = [0,(1/2 * a[0] * (a[0] +1))/a[0]]
	for i in range(1,n):
		wa.append(wa[i] + (1/2 * a[i] * (a[i]+1))/a[i])
	ans = wa[m-1]
	for i in range(m,len(wa)):
		ans = max(wa[i]-wa[i-m],ans)
	print(ans)
	
 
if __name__ == '__main__':
	main()
### BUGGY CODE ###

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

em = 0
exp = []
for i in range(n-k+1):
  temp = sum(p[i:i+k])
  if em <= temp:
    em = temp
    exp = p[i:i+k]

    
print(sum([(pi + 1) / 2 for pi in exp]))

### FIXED CODE ###

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

rsum = [(p[0] + 1) / 2]
for i in range(1, n):
  rsum.append((p[i] + 1) / 2 + rsum[i-1])
  
result = 0
if (n == k):
  result = rsum[-1]

else:
  for i in range(n-k):
    if result < rsum[i+k] - rsum[i]:
      result = rsum[i+k] - rsum[i]

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

n=int(input())
xl=sorted([[int(i) for i in input().split()] for _ in range(n)],key=lambda x:x[0])
i=1
while(i<len(xl)):
    if xl[i-1][0]-xl[i-1][1]<xl[i][0]<xl[i-1][0]+xl[i-1][1]:
        xl.remove(xl[i])
    i+=1

print(len(xl))

### FIXED CODE ###

n=int(input())
X=[]
for i in range(n):
    x,l=[int(_) for _ in input().split()]
    X+=[(x-l,x+l)]
X.sort(key=lambda x:x[0])
ans=n
tmp=X[0][1]
for i in range(1,n):
    if tmp>X[i][0]:
        ans-=1
        tmp=min(tmp,X[i][1])
    else:
        tmp=X[i][1]
print(ans)
### BUGGY CODE ###

import heapq

X,Y,Z,K = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
Bn = list(map(int,input().split(' ')))
Cn = list(map(int,input().split(' ')))
output = []

for a in An:
    for b in Bn:
        for c in Cn:
            heapq.heappush(output,(a+b+c)*(-1))

for _ in range(K):
    print(heapq.heappop(output) * (-1))


### FIXED CODE ###

import heapq
 
X,Y,Z,K = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
Bn = list(map(int,input().split(' ')))
Cn = list(map(int,input().split(' ')))
output = []
ABn = [0] * (X*Y)
count = 0
for a in An:
    for b in Bn:
        ABn[count] = a + b
        count += 1
ABn.sort(reverse=True)
ABn = ABn[0:K]

for ab in ABn:
    for c in Cn:
        heapq.heappush(output,(ab+c)*(-1))
 
for _ in range(K):
    print(heapq.heappop(output) * (-1))
### BUGGY CODE ###

import numpy as np

now_max = -1
prev_max = 100000000
left_max = -1
right_max = -1
right_max_index = 0

N = int(input())
A_list = [int(input()) for _ in range(N)]
np_A_list = np.array(A_list)
for i, A in enumerate(A_list):
    # 右端
    if i == len(A_list) - 1:
        print(left_max)
        break
    if right_max_index == i:
        slc = np_A_list[i + 1:]
        right_max = slc.max()
        right_max_index = slc.argmax() + i + 1

    if left_max > right_max:
        now_max = left_max
        print(left_max)
    else:
        now_max = right_max
        print(right_max)
    
    if prev_max < now_max:
        left_max = right_max = now_max
        right_max_index = 10000000
    
    prev_max = now_max
    if left_max < A:
        left_max = A


### FIXED CODE ###

import numpy as np

now_max = -1
prev_max = 100000000
left_max = -1
right_max = -1
right_max_index = 0

N = int(input())
A_list = [int(input()) for _ in range(N)]
np_A_list = np.array(A_list)
for i, A in enumerate(A_list):
    # 右端
    if i == len(A_list) - 1:
        print(left_max)
        break
    if right_max_index == i:
        slc = np_A_list[i + 1:]
        right_max = slc.max()
        right_max_index = len(np_A_list) - 1 - slc[::-1].argmax()

    if left_max > right_max:
        now_max = left_max
        print(left_max)
    else:
        now_max = right_max
        print(right_max)
    
    if prev_max < now_max:
        left_max = right_max = now_max
        right_max_index = 10000000
    
    prev_max = now_max
    if left_max < A:
        left_max = A
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

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

dp = [1 for _ in range(n)]
def dfs1(x, p):
	for c in adj[x]:
		if c == p:
			continue
		dfs1(c, x)
		dp[x] *= dp[c]+1
		dp[x] %= m
	return

dfs1(0, -1)
ans = [0 for _ in range(n)]
ans[0] = dp[0]
def dfs2(x, p):
	l = len(adj[x])
	cuml = [1 for _ in range(l+2)]
	cumr = [1 for _ in range(l+2)]
	for i in range(l):
		cuml[i+1] = (cuml[i] * (dp[adj[x][i]] + 1)) % m
	for i in range(l-1, -1, -1):
		cumr[i+1] = (cumr[i+2] * (dp[adj[x][i]] + 1)) % m
	pres_x = dp[x]
	for i, c in enumerate(adj[x]):
		if c == p:
			continue
		pres_c = dp[c]
		dp[x] = (cuml[i] * cumr[i+2]) % m
		dp[c] *= dp[x] + 1
		dp[c] %= m
		ans[c] = dp[c]
		dfs2(c, x)
		dp[x] = pres_x
		dp[c] = pres_c
	return

dfs2(0, -1)
print(*ans, sep="\n")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

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

dp = [1 for _ in range(n)]
def dfs1(x, p):
	for c in adj[x]:
		if c == p:
			continue
		dfs1(c, x)
		dp[x] *= dp[c]+1
		dp[x] %= m
	return

dfs1(0, -1)
ans = [0 for _ in range(n)]
ans[0] = dp[0]
def dfs2(x, p):
	l = len(adj[x])
	cuml = [1 for _ in range(l+2)]
	cumr = [1 for _ in range(l+2)]
	for i in range(l):
		cuml[i+1] = (cuml[i] * (dp[adj[x][i]] + 1)) % m
	for i in range(l-1, -1, -1):
		cumr[i+1] = (cumr[i+2] * (dp[adj[x][i]] + 1)) % m
	pres_x = dp[x]
	for i, c in enumerate(adj[x]):
		if c == p:
			continue
		pres_c = dp[c]
		dp[x] = (cuml[i] * cumr[i+2]) % m
		dp[c] *= dp[x] + 1
		dp[c] %= m
		ans[c] = dp[c]
		dfs2(c, x)
		dp[x] = pres_x
		dp[c] = pres_c
	return

dfs2(0, -1)
print(*ans, sep="\n")
### BUGGY CODE ###

def gcd(a, b):
    return gcd(b, a%b) if b != 0 else a

def Main(N):
    ans = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                ans += gcd(gcd(i,j), k)
    return ans
    

def main():
    N = int(input())
    print(Main(N))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def gcd(a, b):
    return gcd(b, a%b) if b != 0 else a

def Main(N):
    ans = 0
    memo2 = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            if memo2[i][j] == 0:
                memo2[i][j] = gcd(i,j)
            for k in range(1, N+1):
                M = memo2[i][j]
                if memo2[M][k] == 0:
                    memo2[M][k] = gcd(M, k)
                ans += memo2[M][k]
    return ans
    

def main():
    N = int(input())
    print(Main(N))

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

n,q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

I = [i+1 for i in range(n) if i+2 < n and s[i:i+2] == "AC"]

for l,r in lr:
  cnt = 0
  for i in I:
    if l<=i<=r and l<=i+1<=r: cnt += 1
  print(cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

ans = [0] * N
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        ans[i+1] += (ans[i] + 1)
    else:
        ans[i+1] = ans[i]

for _ in range(Q):
    l, r = map(int, input().split())
    print(ans[r-1] - ans[l-1])
### BUGGY CODE ###

import collections
n,k=list(map(int,input().split()))
l_n=[(v+1)%k for v in range(n)]
c = collections.Counter(l_n)
m = len(c)
ret=0
for i in range(0,m):
    for j in range(0,m):
        if (i+j)%k==0:
            for r in range(0,m):
                if (i+r)%k ==0 and (r+j)%k==0:
                    ret+=c[i]*c[j]*c[r]
print(ret)
            
    


### FIXED CODE ###

n, k = map(int, input().split())
print(sum([1 if v % k == 0 else 0 for v in range(1, n+1)])**3 +
      sum([1 if v % k == k/2 else 0 for v in range(1, n+1)])**3)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
c=0
for i in range(-(-n//r)+1):
  for j in range(-(-n//g)+1):
    x=n-(i*r+j*g)
    if x>=0 and x%b==0:
      c+=1
print(c)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
c=0
for i in range(-(-n//r)+1):
  for j in range(-(-n//g)+1):
    x=n-(i*r+j*g)
    if x<0:
      break
    elif x%b==0:
      c+=1
print(c)
### BUGGY CODE ###

import heapq
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for i in range(n)]
# 必要な日数の照準にソートする
jobs.sort()
# 次に選ぶバイト候補の保存場所
money = []
ans = 0

# より制約の強い、最終リミットに近い日に行うバイトの割当てから攻めていく
for limit in range(1, m + 1):
    for a, b in jobs:
        # limit日までに報酬のもらえるアルバイトを抽出
        if a == limit:
            # 次に選ぶバイト候補に追加
            heapq.heappush(money, -b)
        elif a > limit:
            break
    # 要素数が空の場合のエラー処理
    if money != []:
        ans += heapq.heappop(money) * (-1)

print(ans)


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for i in range(n)]
# 必要な日数の照準にソートする
jobs.sort()
# 次に選ぶバイト候補の保存場所
money = []
ans = 0

i = 0
# より制約の強い、最終リミットに近い日に行うバイトの割当てから攻めていく
for limit in range(1, m + 1):
    # limit日までに報酬のもらえるアルバイトを抽出
    while i < n and jobs[i][0] <= limit:
        a = jobs[i][0]
        b = jobs[i][1]
        # 次に選ぶバイト候補に追加
        heapq.heappush(money, -b)
        i += 1
    # 要素数が空の場合のエラー処理
    if money != []:
        ans -= heapq.heappop(money)

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

# ボールAとボールBをN個の箱に入れる
# A,Bを1つずつ同じ箱に入れることがあってもよい。
# まずAをN個の箱に1つずつ入れる
# その上で、BをN個の箱に1つずつ入れる（すでにAが入っているかどうか、区別する必要がない）
# AとBの個数の組み合わせを列挙し、そのすべてについて(N C (Aの個数)) * (N C (Bの個数))を計算した和が答え

import sys
readline = sys.stdin.readline

N,A,B,K = map(int,readline().split())

DIV = 998244353
n = (10 ** 6) * 2 # PyPyじゃないと通らない。 * 5が限界くらい
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

# AとBを足してKになる組み合わせを探索する
ans = 0
for a in range(N + 1):
  rest = K - a * A
  if rest < 0:
    break # a * Aの時点で負の数。これ以上の探索も不要。
  if rest % B != 0:
    continue # 組み合わせを作れない
  b = rest // B
  if b > N:
    continue # 箱に入れられない
  # この時点で、Aがa個とBがb個で作れることが確定する
  # (N C (Aの個数)) * (N C (Bの個数))
  ans += (nCr(N, a, DIV) * nCr(N, b, DIV)) % DIV
  ans %= DIV
  
print(ans)


### FIXED CODE ###

# ボールAとボールBをN個の箱に入れる
# A,Bを1つずつ同じ箱に入れることがあってもよい。
# まずAをN個の箱に1つずつ入れる
# その上で、BをN個の箱に1つずつ入れる（すでにAが入っているかどうか、区別する必要がない）
# AとBの個数の組み合わせを列挙し、そのすべてについて(N C (Aの個数)) * (N C (Bの個数))を計算した和が答え

import sys
readline = sys.stdin.readline

N,A,B,K = map(int,readline().split())

DIV = 998244353
n = (10 ** 6) * 2 # PyPyじゃないと通らない。 * 5が限界くらい
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

# AとBを足してKになる組み合わせを探索する
ans = 0
for a in range(N + 1):
  b = K - a * A
  if b < 0:
    break # a * Aの時点で負の数。これ以上の探索も不要。
  if b % B != 0:
    continue # 組み合わせを作れない
  if (b // B) > N:
    continue # 箱に入れられない
  # この時点で、Aがa個とBがb個で作れることが確定する
  # (N C (Aの個数)) * (N C (Bの個数))
  ans += (nCr(N, a, DIV) * nCr(N, b // B, DIV)) % DIV
  ans %= DIV
  
print(ans)
### BUGGY CODE ###

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

def func(a,b):
    for i in range(21):
        if (a>>i)&(b >>i): #AND回路
            return False
    return True



ans = 0

for i in range(n-1):
    host = lst1[i]
    for j in range(i+1,n):
        if not func(host,lst1[j]):
            break
        host = host^lst1[j]
        ans += 1

ans += n

print(ans)

### FIXED CODE ###

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

def func(a,b):
    for i in range(21):
        if (a>>i)&(b>>i): #AND回路
            return False
    return True

def add_point(length):
    res = 0
    for i in range(1,length):
        res += i
    return res

a,b,count,ans = 0,1,0,0
host = lst1[0]
#尺取法
while True:
    if b >= n and a >= n:
        break
    while  b<n and func(host,lst1[b]):
        host = host^lst1[b]
        b += 1
    host = host^lst1[a] #使わなくなる部分を引く
    if b -a > 1:
        ans += b-a-1
    a += 1

ans += n
print(ans)
### BUGGY CODE ###

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


c = 0
a = 0

t = [0]*(n+1)

temp = []


for i in range(m):
    s = input().split()
    x = s[0]
    y = s[1]
    if y == 'AC' and x not in temp:
        a += 1
        c += t[int(x)]
        temp += [x]
    elif y == 'WA':
        t[int(x)] += 1

print(a, c)


### FIXED CODE ###

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

a = [0] * (n+1)
b = [0] * (n+1)

c = 0

for i in [0]*(m):

    s = input().split()

    if a[int(s[0])] == 0:
        if s[1] == "AC":
            a[int(s[0])] = 1
            c += b[int(s[0])]
        else:
            b[int(s[0])] += 1

print(sum(a), c)
### BUGGY CODE ###

n = int(input())
d_li = list(map(int,input().split()))
d_li.sort()
m = int(input())
t_li = list(map(int,input().split()))
t_li.sort()
for t in t_li:
    if t in d_li:
        d_li.remove(t)
    else:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

import bisect
n = int(input())
d_li = list(map(int,input().split()))
m = int(input())
t_li = list(map(int,input().split()))

import collections
d_cnt = collections.Counter(d_li)
t_cnt = collections.Counter(t_li)
#print(d_cnt,t_cnt)

for t in t_cnt.items():
    #print(d_cnt,d_cnt[t[0]],t[1])
    if d_cnt[t[0]] < t[1]:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.readline

    n = int(input())
    items = [tuple(map(int, input().split())) for _ in range(n)]

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1
        items_sub = [items[v]]
        while v > 0:
            v = (v - 1) // 2
            items_sub.append(items[v])

        m = len(items_sub)
        dp = [0] * (l + 1)
        for bit in range(1 << (m // 2)):
            s_val = s_w = 0
            for i, (val, w) in enumerate(items_sub[:m // 2]):
                if (bit >> i) & 1:
                    s_val += val
                    s_w += w
                    if s_w > l:
                        break
            if s_w <= l:
                dp[s_w] = max(dp[s_w], s_val)
        for i in range(l):
            dp[i + 1] = max(dp[i + 1], dp[i])

        ans = 0
        for bit in range(1 << (m - m // 2)):
            s_val = s_w = 0
            for i, (val, w) in enumerate(items_sub[m // 2:]):
                if (bit >> i) & 1:
                    s_val += val
                    s_w += w
                    if s_w > l:
                        break
            if s_w <= l:
                ans = max(ans, dp[l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


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

N=int(input())
b=[]
x=0
t=1
for i in range(N):

    a=list(input())

    a.sort(reverse=False)

    b.append(a)


while True:

    if len(b)==1:

        break

    q=b[0]

    if q==b[t]:

        x+=1

    

    if t==len(b)-1:

        del b[0]

        t=0

    t+=1





print(x)


### FIXED CODE ###

N=int(input())

H=[]
c=0
t=0
for i in range(N):
    h=list(input())
    h.sort(reverse=False)
    H.append(h)

H.sort(reverse=False)

for j in range(N-1):
    
    if H[j]==H[j+1]:
        c+=1

    else:
        t+=int((c)*(c+1)/2)
        c=0

if c:
    t+=int(((c)*(c+1)/2))
        

print(t)
### BUGGY CODE ###

S = input()
T = input()
N = len(S)
pos_S = {c: set() for c in "abcdefghijklmnopqrstuvwxyz"}
[pos_S[S[i]].add(i) for i in range(N)]
pos_T = {c: set() for c in "abcdefghijklmnopqrstuvwxyz"}
[pos_T[T[i]].add(i) for i in range(N)]
if all(pos_S[S[i]] == pos_T[T[i]] for i in range(N)):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

from collections import Counter


S = Counter(input())
T = Counter(input())
if sorted(S.values()) == sorted(T.values()):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

result = 0
for i in range(N-2) :
  for j in range(i+1,N-1) :
    for k in range(j+1,N) :
      if L[i] < L[j] + L[k] :
        result += 1

print(result)

### FIXED CODE ###

from bisect import bisect_left

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

result = 0
for i in range(N) :
  for j in range(i+1,N) :
    result += bisect_left(L,L[i]+L[j]) - (j+1)

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

import math

s = [i for i in range(1,int(input())+1)]
ans = 0 

for a in s:
    for b in s:
        for c in s:
            ans += math.gcd(math.gcd(a,b), math.gcd(b,c))
print(ans)

### FIXED CODE ###

from math import gcd

K = int(input())
ans = 0 

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += gcd(gcd(a,b), c)
print(ans)
### BUGGY CODE ###

from collections import deque
n,k=map(int,input().split())
p = list(map(int,input().split()))
def ex_even(a):
    return (a+1)/2
def ex_odd(b):
    li = []
    for i in range(1, b+1):
        li.append(i)
    return li[len(li)//2]
ans = [0] * k
q = deque(ans)
c_max = 0
for i in range(1,n+1):
    if p[i-1] % 2 == 0:
        ex = ex_even(p[i-1])
        q.popleft()
        q.append(ex)
    else:
        ex = ex_odd(p[i-1])
        q.popleft()
        q.append(ex)
    c_max = max(c_max, sum(q))
print(c_max)

### FIXED CODE ###

n,k=map(int,input().split())
p = list(map(int,input().split()))
def ex_even(a):
    return (a+1)/2
def ex_odd(b):
    return b//2 + 1
s = sum(p[0:k])
s_max = sum(p[0:k])
for i in range(n-k):
    s = s-p[i] + p[i+k]
    s_max = max(s_max,s)
if s_max % 2 == 0:
    print(ex_even(s_max) + 0.5*(k-1))
else:
    print(ex_odd(s_max) + 0.5*(k-1))
### BUGGY CODE ###

#6問目
N, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(N-1):
    if(a[i] + a[i+1] > x):
        while(a[i] + a[i+1] > x):
            count += 1
            a[i+1] -= 1
print(count)

### FIXED CODE ###

#6問目
N, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(N-1):
    #まず一番前の要素がxより小さくなければならない
    if(i == 0 and a[i] > x):
        count += a[i] - x
        a[i] = x
        
    if(a[i] + a[i+1] > x):
        count += a[i] + a[i+1] - x
        a[i+1] = x - a[i]
print(count)