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

n = int(input())
strings = []
num = []
answer = 0
for i in range(n):
  string = input()
  string = ''.join(sorted(string))
  if string not in strings:
    strings.append(string)
    num.append(0)
  else:
    num[strings.index(string)] += 1
    answer = answer + num[strings.index(string)]
print(answer)

### FIXED CODE ###

n = int(input())
strings = {}
answer = 0
for i in range(n):
  string = input()
  string = ''.join(sorted(string))
  if string not in strings:
    strings[string]=1
  else:
    answer += strings[string]
    strings[string] += 1
print(answer)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    S = [i for i in input()]
    Q = int(input())
    Query = [input().split() for _ in range(Q)]

    for q in Query:
        if q[0]=='1':
            S.reverse()
        elif q[0]=='2':
            if q[1]=='1':
                S.insert(0, q[2])
            elif q[1]=='2':
                S.append(q[2])

    print(*S, sep='')

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
from collections import deque

def resolve():
    S = input()
    Q = int(input())
    Query = [input().split() for _ in range(Q)]

    S_deque = deque()
    for s in S:
        S_deque.append(s)
 
    is_reversed = False
    for q in Query:
        if q[0]=='1':
            is_reversed = not is_reversed
        elif q[0]=='2':
            if (not is_reversed and q[1]=='1') or (is_reversed and q[1]=='2'):
                S_deque.appendleft(q[2])
            else:
                S_deque.append(q[2])

    if is_reversed:
        S_deque.reverse()

    print(*S_deque, sep='')

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

import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    for i in range(N):
        k1 = abs(X-i)
        for j in range(i+1,N):
            k2 = abs(j-Y)
            shortest[i][j] = min(j-i, k1+1+k2)

    coll = [collections.Counter(s) for s in shortest]
    for i in range(1,N):
        count = 0
        for j in range(N):
            count += coll[j].get(i,0)
        print(count)
main()


### FIXED CODE ###

import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    coll = collections.Counter()
    for i in range(N):
        k1 = abs(X-i)
        for j in range(i+1,N):
            k2 = abs(j-Y)
            shortest[i][j] = min(j-i, k1+1+k2)
        coll += collections.Counter(shortest[i])

    for i in range(1,N):
        print(coll.get(i,0))
        
main()
### BUGGY CODE ###

N ,K = list(map(int, input().split()))
p = list(map(int, input().split()))
pline=[]
for i in range(N-K+1):
  num = 0
  for j in range(K):
    num+= (p[i+j]+1)/2
  pline.append(num)

print(max(pline))

### FIXED CODE ###

N ,K = list(map(int, input().split()))
p = list(map(lambda x: (1+int(x))/2, input().split()))
s = [0]*N
s[0]=p[0]
for i in range(1,N):
  s[i] = s[i-1]+p[i]

l = [s[K-1]]
for i in range(N-K):
  l.append(s[i+K]-s[i])

print(max(l))
### BUGGY CODE ###

#coding: utf-8
s = list(map(int, input()))
cnt = 0
while len(set(s)) > 1:
    for i in range(len(s)-1):
        if s[i] == 1 and s[i+1] == 0:
            cnt += 2
            del s[i:i+2]
            break
print(cnt)

### FIXED CODE ###

#coding: utf-8
s = list(map(int, input()))
cnt = 0
zero = s.count(0)
one = s.count(1)
print(zero*2 if zero < one else one * 2)
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
lines = [input().split() for _ in range(M)]

ans = ['1']

while(True):
	start = ans[0]
	for i in range(M):
		for j in range(2):
			if lines[i][j] == start:
				if j == 0:
					n = 1
				else:
					n = 0
				if lines[i][n] not in ans:
					ans.insert(0,lines[i][n])
					break
		if start != ans[0]:
			break
	if start == ans[0]:
		break

while(True):
	end = ans[len(ans) - 1]
	for i in range(M):
		for j in range(2):
			if lines[i][j] == end:
				if j == 0:
					n = 1
				else:
					n = 0
				if lines[i][n] not in ans:
					ans.append(lines[i][n])
					break
		if end != ans[len(ans) - 1]:
			break
	if end == ans[len(ans) - 1]:
		break

print(len(ans))
for i in range(len(ans)):
	print(ans[i],end='')
	if i < len(ans) - 1:
		print(' ',end='')
	else:
		print()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100005)

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

E = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    E[A].append(B)
    E[B].append(A)

visited = [False for _ in range(N)]
ans = []

def dfs(p, one):
    if visited[p]:
        return False
    visited[p] = True
    if not one:
        ans.append(p+1)
    for i in E[p]:
        if dfs(i, one):
            break
    if one:
        ans.append(p+1)
    return True

dfs(0, True)
for i in E[0]:
    if dfs(i, False):
        break
print(len(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

INT_MAX= 100000000
n,k=map(int,input().split())
dp  = [INT_MAX]*(n)
h=[int(X) for X in input().split()]
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    p=1
    while(p<k+1 or i-p>=0):
        dp[i]= min(dp[i-p+1]+abs(h[i-p+1]-h[i]),dp[i])
        p+=1
print(dp[n-1])

### FIXED CODE ###

from sys import stdin,stdout
INT_MAX= 10**18
n,k=map(int,stdin.readline().split())
dp  = [INT_MAX]*(n)
h=[int(X) for X in stdin.readline().split()]
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    p=1
    while(p<k+1 and (i-p)>=0):
        dp[i]= min(dp[i-p]+abs(h[i-p]-h[i]),dp[i])
        p+=1
stdout.write(str(dp[n-1])+"\n")
### BUGGY CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
g=a[0]
for m in a:
  g=math.gcd(g,m)
  if g==1:break
else:
  print("not coprime")
  exit()

j=2
l=[0]*2+[1]*(10**6-1)
while j<10*6+1:
  k=1
  if l[j]==1:
    while k*j<10**6:
      l[k*j]==0
      k+=1
  j+=1
d=[]
for i in range(len(l)):
  if l[i]==1: d.append(i)
              
e=set()
for i in range(n):
  z=a[i]
  for m in d:
    if z%m==0:
      if m in e:
        print("setwise coprime")
        exit()
      e.add(m)
print("pairwise coprime")
  
    


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[0]*(10**6+100)
x=0
for m in a:
  l[m]+=1

j=2
#print(l)


while j <10**6+1:
  c=0
  k=1
  while j*k<=10**6+1 :
    if l[j*k]>0:
      c+=l[j*k]
    k+=1

  if c==n:
    print("not coprime")
    exit()
  elif c>1:
    x=1
  j+=1 
  
if x==1:
  print("setwise coprime")
else:
  print("pairwise coprime")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
number = a[0]
for i in range(1,n):
    number = number * a[i]
    
if number > 10**18:
    print(-1)
else:
    print(number)
    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a=sorted(a,reverse = True)
if a[-1]==0:
    print(0)
    exit()
else:
    
    number = a[0]
    for i in range(1,n):
        number = number * a[i]
        if number > 10**18:
            print(-1)
            exit()

print(number)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
assert len(A) == N
total = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    total += A[i] * A[j]
#    print(A[i], A[j])
print(total % (10 ** 9 + 7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
assert len(A) == N
total = 0
sum_A = sum(A)
for i,ai in enumerate(A):
  sum_A -= ai
  total += ai * sum_A
print(total % (10 ** 9 + 7))
### BUGGY CODE ###

import collections as c
import math

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

def C(n, r):
  return P(n, r)//math.factorial(r)

N = int(input())
s = [input() for _ in range(N)]
count = []

for i in s:
  count.append(dict(c.Counter(i).most_common()))

unique_count = []
comb = []
for i in count:
  if not i in unique_count:
    unique_count.append(i)
    comb.append(count.count(i))

print(sum([C(i, 2) for i in comb if i >= 2]))
  
  

### FIXED CODE ###

import collections as c
import math

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

def C(n, r):
  return P(n, r)//math.factorial(r)

N = int(input())
s = [input() for _ in range(N)]
count = []

for i in s:
  count.append(''.join(sorted(list(i))))

# print(count)

comb = [i[1] for i in c.Counter(count).most_common()]
print(sum([C(i, 2) for i in comb if i >= 2]))
### BUGGY CODE ###

from bisect import bisect_left
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 0, 10000000000
while r - l > 1:
    m = (l + r) // 2
    res = 0
    for x in a:
        res += n - bisect_left(a, m - x)
    if res >= k:
        l = m
    else:
        r = m
b = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[n - i]
cnt = 0
ans = 0
for x in a:
    t = n - bisect_left(a, l - x)
    ans += b[t] + x * t
    cnt += t
print(ans - (cnt - k) * l)


### FIXED CODE ###

from bisect import bisect_left
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 0, 10000000000
while r - l > 1:
    m = (l + r) // 2
    res = 0
    for x in a:
        res += n - bisect_left(a, m - x)
    if res >= k:
        l = m
    else:
        r = m
b = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[n - i]
cnt = 0
ans = 0
for x in a:
    t = n - bisect_left(a, l - x)
    ans += b[t] + x * t
    cnt += t
print(ans - (cnt - k) * l)
### BUGGY CODE ###

from collections import defaultdict
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0] -q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

#　aの逆元を求める
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def combination(m,k):
    res = 1
    for i in range(1,m+1):
        res = res*i%(10**9+7)
    for i in range(1,k+1):
        res = res*mod_inv(i,10**9+7)
    for i in range(1,m-k+1):
        res = res*mod_inv(i,10**9+7)
    return res%(10**9+7)

def main():
    n = int(input())
    ls = [int(x) for x in input().split()]
    cumsum = [0]*(n+1)
    for i in range(1,n+1):
        cumsum[i] = cumsum[i-1]+ls[i-1]
    cnt = defaultdict(int)
    for i in cumsum:
        cnt[i] +=1
    ans = 0
    for i in cnt.values():
        if i==1:
            pass
        else:
            ans += combination(i,2)
    print(ans)



if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
def main():
    n = int(input())
    ls = [int(x) for x in input().split()]
    cumsum = [0]*(n+1)
    for i in range(1,n+1):
        cumsum[i] = cumsum[i-1]+ls[i-1]
    cnt = defaultdict(int)
    for i in cumsum:
        cnt[i] +=1
    ans = 0
    for i in cnt.values():
        if i==1:
            continue
        ans += int(i*(i-1)/2)
    print(ans)



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

s = input()
q = int(input())
querys = [list(input().split()) for i in range(q)]

rev = 0
moji = []
for query in querys:
    if query[0] == '1':
        rev += 1
    else:
        query[1] = int(query[1])
        p = True if query[1] == 1 else False
        moji.append([query[2], rev, p])

if rev%2 != 0:
    s = s[::-1]

for m in moji:
    if (rev - m[1]) % 2 != 0:
        m[2] = not(m[2])
    
    if m[2]:
        s = m[0] + s
    else:
        s = s + m[0]

print(s)

### FIXED CODE ###

s = input()
q = int(input())
querys = [list(input().split()) for i in range(q)]

rev = 0
moji = []
for query in querys:
    if query[0] == '1':
        rev += 1
    else:
        query[1] = int(query[1])
        p = True if query[1] == 1 else False
        moji.append([query[2], rev, p])

if rev%2 != 0:
    s = s[::-1]
head = ""
end = ""
for m in moji:
    if (rev - m[1]) % 2 != 0:
        m[2] = not(m[2])
    
    if m[2]:
        head = m[0] + head
    else:
        end = end + m[0]

s = head + s + end
print(s)
### BUGGY CODE ###

A = list(map(int , input().split()))
B = list(map(int , input().split()))
print(sum([sum(i) for i in [[float(1/max({sum(B[i:i+A[1]]):B[i:i+A[1]] for i in range(len(B)-A[1]+1)}.values())[i]*x) for x in list(range(1,max({sum(B[i:i+A[1]]):B[i:i+A[1]] for i in range(len(B)-A[1]+1)}.values())[i]+1))] for i in range(len(max({sum(B[i:i+A[1]]):B[i:i+A[1]] for i in range(len(B)-A[1]+1)}.values())))]]))

### FIXED CODE ###

A = list(map(int , input().split()))
B = list(map(int , input().split()))
kitaiti =[(i+1)/2 for i in B]
ans = []
dd = [0]
for i in range(A[0]):
    dd.append(dd[i] + kitaiti[i])
for i in range(A[1] , A[0]+1):
    ans.append(dd[i] - dd[i - A[1]])
print(max(ans))
### BUGGY CODE ###

n = int(input())
l = 0
r = n-1
print(0, flush=True)
s = str(input())
if s == 'Vacant':
    exit()
else:
    sl = s
print(n-1, flush=True)
s = str(input())
if s == 'Vacant':
    exit()
else:
    sr = s

while l+1 < r:
    c = (l+r)//2
    print(c, flush=True)
    s = str(input())
    if s == 'Vacant':
        exit()
    else:
        if s == sl:
            l = c
            sl = s
        else:
            r = c
            sr = s

### FIXED CODE ###

def main():
    n = int(input())

    def q(i):
        print(i, )
        s = str(input())
        if s == 'Vacant':
            exit()
        else:
            return s

    x = q(n-1)
    x = q(0)

    def ok(m):
        if m == 0:
            return False
        else:
            if (m%2 == 0 and q(m) != x) or (m%2 == 1 and q(m) == x):
                return True
            else:
                return False

    l = 0
    r = n-1
    while l+1 < r:
        c = (l+r)//2
        if ok(c):
            r = c
        else:
            l = c

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

# -*- coding:utf-8 -*-
# /usr/bin/python3

from bisect import insort

def main():
  n, m = map(int, input().strip().split(' '))
  liAB = sorted([tuple(map(int, input().strip().split(' '))) for _ in range(n)], key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      if len(top) > a-k:
        s += sum(top[-(a-k):])
        del top[-(a-k):]
      else:
        s += sum(top)
        top = []
      k = a

    insort(top, b)


  s += sum(top[-(m-k+1):])

  print(s)
  
  pass

if __name__=='__main__':
  main()


### FIXED CODE ###

# -*- coding:utf-8 -*-
# /usr/bin/python3

from heapq import heappush, heappop

def main():
  n, m = map(int, input().strip().split(' '))
  liAB = [tuple(map(int, input().strip().split(' '))) for _ in range(n)]
  liAB.sort(key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      s += (-sum([heappop(top) for _ in range(a-k) if len(top) != 0]))
      k = a
    heappush(top, -b)

  s += (-sum([heappop(top) for _ in range(m-k+1) if len(top) != 0]))
  print(s)

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

n,m = list(map(int,input().split()))
d = []
ma = 0
mi = 0
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )
  ma = max(ma,a,b)
  mi = min(mi,a,b)
s = ((1<<ma)-1) | ((1<<mi)-1) 
for bit in range(1<<n):
  if bit & s:
    spr = [True]*m
    for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
    if sum(spr) == 0:
      print(sum([1 for i in range(n) if bit & 1<<i]))
      exit()


### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

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

def main():
    N, M = map(int, input().split())
    broken = [int(input()) for _ in range(M)]
    div = 1000000007

    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1

    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div

    print(comb_list[-1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)

    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1

    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div

    print(comb_list[-1])


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

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

s = 1
l=10**18

for i in a:
    s *= i
    if i > l:
        print(-1)
        exit()
if s > l:
    print(-1)
else:
    print(s)

### FIXED CODE ###

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

s = 1
l=10**18

for i in a:
    s *= i
    if s > l:
        print(-1)
        exit()
print(s)
### BUGGY CODE ###

L, R = map(int, input().split())

ans = 2019
for i in range(L, R):
    for j in range(i+1, R+1):
        ans = min(((i % 2019) * (j % 2019)) % 2019, ans)
print(ans)


### FIXED CODE ###

L, R = map(int, input().split())

if R - L >= 2019:
    print(0)
    exit()

flag = True
ans = 2020
for i in range(L, R+1):
    for j in range(i+1, R+1):
        ans = min(((i % 2019) * (j % 2019)) % 2019, ans)
print(ans)
### BUGGY CODE ###

import numpy as np
import fractions
N = int(input())
numbers = np.array(list(map(int, input().split())))
# numbers = np.array([7, 6, 8])
# numbers = np.array([12, 15, 18])
# numbers = np.array([1000000000, 1000000000])
# N = len(numbers)
gcd = np.frompyfunc(fractions.gcd, 2, 1)


def calculate_maximum_sub_gcd(numbers):
    sub_gcds = np.array([sub_gcd(numbers[:i], numbers[i+1:]) for i in range(N)])
    return np.max(sub_gcds)


def sub_gcd(left, right):
    if not left.size > 0:
        return np.ufunc.reduce(gcd, right)
    if not right.size > 0:
        return np.ufunc.reduce(gcd, left)
    else:
        subleft = np.ufunc.reduce(gcd, left)
        subright = np.ufunc.reduce(gcd, right)
        return gcd(subleft, subright)


print(calculate_maximum_sub_gcd(numbers))


### FIXED CODE ###

# import math
import fractions
import numpy as np
from itertools import accumulate, chain, islice, starmap
N = int(input())
numbers = list(map(int, input().split()))
# numbers = [2, 4, 8, 8]
# N = len(numbers)


def calculate_maximum_subgcd_with_np_ufunc(numbers):
    gcd = np.frompyfunc(fractions.gcd, 2, 1)
    cumgcds = gcd.accumulate(numbers, dtype=np.object).astype(np.int)
    sub_cumgcds = np.roll(cumgcds, 1)
    sub_cumgcds[0] = 0
    reverse_cumgcds = gcd.accumulate(
        numbers[::-1], dtype=np.object).astype(np.int)
    sub_reverse_cumgcds = np.roll(reverse_cumgcds, 1)
    sub_reverse_cumgcds[0] = 0
    return np.max(gcd(sub_cumgcds, sub_reverse_cumgcds[::-1]))


def calculate_maximum_subgcd_with_func(numbers):
    operation = fractions.gcd
    cumgcds = accumulate(numbers, operation)
    sub_cumgcds = islice(chain([0], cumgcds), len(numbers))
    reverse_cumgcds = accumulate(numbers[::-1], operation)
    sub_reverse_cumgcds = islice(chain([0], reverse_cumgcds), len(numbers))
    sub_gcds = starmap(operation, zip(sub_cumgcds, list(sub_reverse_cumgcds)[::-1]))
    return max(sub_gcds)


# calculate_maximum_subgcd = calculate_maximum_subgcd_with_np_ufunc
calculate_maximum_subgcd = calculate_maximum_subgcd_with_func

print(calculate_maximum_subgcd(numbers))
### BUGGY CODE ###

from itertools import combinations as com
N = int(input())
l = list(map(int, input().split()))
cnt = 0
for a, b, c in com(l, 3):
    if a < b+c and b < c+a and c < a+b:
        cnt+=1
print(cnt)

### FIXED CODE ###

N = int(input())
l = sorted(list(map(int, input().split())))
 
from bisect import bisect_left

cnt = 0
for i in range(N):
    a = l[i]
    for j in range(i+1, N):
        b = l[j]
        cnt += bisect_left(l[j+1:], a+b)
print(cnt)
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
check=[]
ans=0
for i in range(n):
    if min(i+1,a[i])+max(i+1,a[i])*1000000 not in check:
        check.append(min(i+1,a[i])+max(i+1,a[i])*1000000)
    else:
        ans+=1
print(ans)





### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
pair=[]
for i in range(n):
    if i+1 > a[i]:
        w=i+1
        i=a[i]
    else:
        w=a[i]
        i+=1
    pair.append([i,w])
pair.sort()
ans=0
for i in range(len(pair)-1):
    if pair[i]==pair[i+1]:
        ans+=1
print(ans)
### BUGGY CODE ###

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

Rs = 0
Gs = 0
Bs = 0
for i, il in enumerate(S):
    if il == 'R':
        Rs += 1
    if il == 'G':
        Gs += 1
    if il == 'B':
        Bs += 1
num = 0
for i in range(N):
    for step in range(1, N):
        j = i + step
        k = i + 2*step
        if k > N - 1:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            num += 1
print(Rs*Gs*Bs - num)


### FIXED CODE ###

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

Rs = 0
Gs = 0
Bs = 0
for il in S:
    if il == 'R':
        Rs += 1
    if il == 'G':
        Gs += 1
    if il == 'B':
        Bs += 1
num = 0
for i in range(N):
    for step in range(1, N):
        j = i + step
        k = i + 2*step
        if k > N - 1:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            num += 1
print(Rs*Gs*Bs - num)
### BUGGY CODE ###

N, MA, MB = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(N)]

inf = 1000 * N
M = N * 10 + 1
DP = [[[inf] * M for _ in range(M)] for _ in range(N)]

a, b, c = abc[0]
DP[0][a][b] = c

for i in range(1, N):
  a, b, c = abc[i]
  DP[i][a][b] = min(DP[i - 1][a][b], c)
  for j in range(M - 10):
    for k in range(M - 10):
      DP[i][j][k] = min(DP[i][j][k], DP[i - 1][j][k])
      if DP[i - 1][j][k] < inf:
        jj = j + a
        kk = k + b
        DP[i][jj][kk] = min(DP[i - 1][jj][kk], DP[i - 1][j][k] + c)
ans = inf
i = MA
j = MB
while i < M and j < M:
  ans = min(ans, DP[-1][i][j])
  i += MA
  j += MB

if ans == inf:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

N, MA, MB = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(N)]

inf = 1000 * N
M = N * 10 + 1
DP = [[[inf] * M for _ in range(M)] for _ in range(N)]

a, b, c = abc[0]
DP[0][a][b] = c

for i in range(1, N):
  a, b, c = abc[i]
  DP[i][a][b] = min(DP[i - 1][a][b], c)
  for j in range(M - 10):
    for k in range(M - 10):
      DP[i][j][k] = min(DP[i][j][k], DP[i - 1][j][k])
      if DP[i - 1][j][k] < inf:
        jj = j + a
        kk = k + b
        DP[i][jj][kk] = min(DP[i - 1][jj][kk], DP[i - 1][j][k] + c)
ans = inf
i = MA
j = MB
while i < M and j < M:
  ans = min(ans, DP[-1][i][j])
  i += MA
  j += MB

if ans == inf:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

import numpy as np
import math

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


total = sum(A)
for i in range(M):
    max_index = np.argmax(A)
    total -= math.ceil(A[max_index] / 2)
    A[max_index] = A[max_index] // 2

print(total)
    

### FIXED CODE ###

import heapq
import math

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

B = [-A[i] for i in range(N)]
heapq.heapify(B)
while M:
    p = heapq.heappop(B)
    p /= 2
    heapq.heappush(B, p)
    M -= 1

ans = 0
for i in range(N):
    ans += math.floor(-B[i])
print(ans)