Harryxun/stf_run huggingface dataset:
from sys import stdin

S = str(stdin.readline().rstrip())
K = int(stdin.readline().rstrip())

lenS = len(S)
ans = 0

if S[0] == S[lenS-1]:
    S2 = S*2
    a = 0#位置
    while a < lenS*2-1:
        ans2 = 0
        if S2[a] == S2[a+1]:
            b = 2
            x = S2[a]
            for i in range(1,lenS*2-a):
                try:
                    if x == S2[a+1+i]:
                        b += 1
                    else:
                        break
                except:
                    b = 2
            ans2 += b//2
            a += 1+b
        else:
            a += 1
    a = 0#位置
    while a < lenS-1:
        ans1 = 0
        if S[a] == S[a+1]:
            b = 2
            x = S[a]
            for i in range(1,lenS-a):
                try:
                    if x == S[a+1+i]:
                        b += 1
                    else:
                        break
                except:
                    b = 2
            ans1 += b//2
            a += 1+b
        else:
            a += 1
    differ = ans2-ans1
    ans = differ*(K-1) + ans1*K
else:
    a = 0#位置
    while a < lenS-1:
        if S[a] == S[a+1]:
            b = 2
            x = S[a]
            for i in range(1,lenS-a):
                try:
                    if x == S[a+1+i]:
                        b += 1
                    else:
                        break
                except:
                    b = 2
            ans += b//2
            a += 1+b
        else:
            a += 1
    ans = ans*K


print(ans)


### FIXED CODE ###


from sys import stdin

S = str(stdin.readline().rstrip())
K = int(stdin.readline().rstrip())

l = len(S)
ans = 0

for i in range(l):
    mo = S[0]*l
    if mo == S:
        ans = l*K//2
        print(ans)
        exit()
    else:
        pass


if S[0] == S[l-1]:
    S2 = S*2
    l2 = len(S2)
    a = 0#位置
    ans2 = 0
    while a < l2-1:
        if S2[a] == S2[a+1]:
            t = S2[a]
            c = 1
            for i in range(1,l2-a):
                if t == S2[a+i]:
                    c += 1
                else:
                    break
            j = c//2
            ans2 += j
            a += c
        else:
            a += 1
    a = 0#位置
    ans1 = 0
    while a < l-1:
        if S[a] == S[a+1]:
            t = S[a]
            c = 1
            for i in range(1,l-a):
                if t == S[a+i]:
                    c += 1
                else:
                    break
            j = c//2
            ans1 += j
            a += c
        else:
            a += 1
    differ = ans2-ans1*2
    ans = differ*(K-1) + ans1*K
else:
    a = 0#位置
    while a < l-1:
        if S[a] == S[a+1]:
            t = S[a]
            c = 1
            for i in range(1,l-a):
                if t == S[a+i]:
                    c += 1
                else:
                    break
            j = c//2
            ans += j
            a += c
        else:
            a += 1

    ans = ans*K

print(ans)
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

arr=sorted(limii())

mat=[]
for i in range(m):
    b,c=mii()
    mat.append([b,c])

mat.sort(key=lambda x: x[1],reverse=True)
maxboundary=mat[0][1]
ans=0
i=0
temp=0
while maxboundary>=arr[temp] and temp<n and i<m:
    ans+=mat[i][1]
    temp+=1
    mat[i][0]-=1
    if mat[i][0]==0:
        i+=1
        if i<m:
            maxboundary=mat[i][1]
    print(ans,temp,i,mat,maxboundary)

print(ans+sum(arr[temp:]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

arr=sorted(limii())

mat=[]
for i in range(m):
    b,c=mii()
    mat.append([b,c])

mat.sort(key=lambda x: x[1],reverse=True)
maxboundary=mat[0][1]
ans=0
i=0
temp=0
while maxboundary>arr[temp] and temp<n and i<m:
    ans+=mat[i][1]
    
    temp+=1
    if temp==n:
        break
    mat[i][0]-=1
    if mat[i][0]==0:
        i+=1
        if i<m:
            maxboundary=mat[i][1]
    #print(ans,temp,i,mat,maxboundary)

print(ans+sum(arr[temp:]))
W,H,N=map(int.input().split())
a,b,c,d=0,W,0,H

for i in range(N):
  x,y,A=map(int.input().split())
  if A==1:
    a=max(a,x)
  if A==2:
    b=min(b,x)
  if A==3:
    c=max(c,y)
  if A==4:
    d=min(d,y)
  
print(max(0,b-a)*max(0,d-c))

### FIXED CODE ###

W,H,N=map(int,input().split())
a,b,c,d=0,W,0,H

for i in range(N):
  x,y,A=map(int,input().split())
  if A==1:
    a=max(a,x)
  if A==2:
    b=min(b,x)
  if A==3:
    c=max(c,y)
  if A==4:
    d=min(d,y)
  
print(max(0,b-a)*max(0,d-c))
a,b,k = map(int, input().split())

for i in range(min(a,b),-1,-1):
  if a%i == 0 and b%i == 0:
    k-=1
    if k==0:
      print(i)

### FIXED CODE ###

a,b,k = map(int, input().split())
 
for i in range(min(a,b),0,-1):
  if a%i == 0 and b%i == 0:
    k-=1
    if k==0:
      print(i)
      break
a1, a2, a3 = map(int, input(), split())

if a1 + a2 + a3 >= 22:
  print('bust')
else:
  print('win')

### FIXED CODE ###

a1, a2, a3 = map(int, input().split())
 
if a1 + a2 + a3 >= 22:
  print('bust')
else:
  print('win')
while(1):
  a,b,op = raw_input().split()

  if op == "+":
    print (a+b)
  elif op == "-":
    print (a-b)
  elif op == "*":
    print (a*b)
  elif op == "/":
    print (a/b)
  elif op == "?":
    break

### FIXED CODE ###

while(1):
  a,op,b = raw_input().split()
  a = int(a)
  b = int(b)
  if op == "+":
    print (a+b)
  elif op == "-":
    print (a-b)
  elif op == "*":
    print (a*b)
  elif op == "/":
    print (a/b)
  elif op == "?":
    break
L, R = [int(i) for i in input().split()]
a = []
for i in range(L, R+1):
    a.append(i % 2019)
    if not i % 2019:
        break
a.sort()
print((a[0]*a[1]) % 2019)


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    l, r = map(int, input().split())
    if r-l >= 2018:
        print(0)
    else:
        ans = 2222
        n = [i for i in range(l, r+1)]
        for i in range(len(n)):
            for j in range(i+1, len(n)):
                s = n[i]*n[j] % 2019
                if ans > s:
                    ans = s
        print(ans)

        # n = [[i % 2019, i] for i in range(l, r+1)]
        # n.sort(key=lambda x: x[0])
        # print((n[0][1]*n[1][1]) % 2019)


if __name__ == "__main__":
    main()
x = sorted([int(i) for i in input().split()])
print("{0} {1} {2}".x)

### FIXED CODE ###

x = sorted([int(i) for i in input().split()])
print("{0} {1} {2}".format(x[0],x[1],x[2]))
line = input()

N = int(line)
A = np.array([0]*N)

for i in range(N):
    line = input()
    A[i] = int(line)

def IsNotPossible(A):
    foo = 0
    
    if A[0] != 0:
        foo = 1
        
    else:
        for i in range(N-1):
            if A[i] + 1 < A[i+1]:
                foo  = 1
                break
    
    return foo

if IsNotPossible(A):
    print(-1)
    
else:
    count = 0
    for i in range(N-1):
        a = A[N-1-i]
        
        if a == 0:
            continue
        elif a == A[N-2-i] + 1:
            count += 1
        else:
            count += a
            
    print(count)

### FIXED CODE ###

line = input().split()

A = int( line[0] )
B = int( line[1] )
C = int( line[2] )
K = int( line[3] )

if K % 2 == 0:
    print(A-B)
    
else:
    print(B-A)
str=str(input())
if str.isupper():
	print("A")
else
	print("a")

### FIXED CODE ###

str=str(input())
if str.isupper():
	print("A")
else:
	print("a")
import sys

n,m,x,y = (int(_) for _ in input().split())
xl = [int(_) for _ in input().split()]
yl = [int(_) for _ in input().split()]

xl.sort()
yl.sort()

for i in range(x+1,y+1):
    if((x < int(i) <= y) and (x[-1] < int(i)) and (y[0] >= int(i))):
        print('No War')
        sys.exit()
    else:
        pass

print('War')

### FIXED CODE ###

import sys

n,m,x,y = (int(_) for _ in input().split())
xl = [int(_) for _ in input().split()]
yl = [int(_) for _ in input().split()]

xl.append(x)
yl.append(y)

xl.sort()
yl.sort()

print('War') if (xl[-1] >= yl[0]) else print('No War')
import sys
for e in sys.stdin:
    a, b, c, d, e, f = map(int, e.split())
    a * (e*y-f) / d + b * y = c
    x = (e*y-f) / d
    print round(x, 3)+' '+round(y, 3)


### FIXED CODE ###

import sys
for e in sys.stdin:
    a, b, c, d, e, f = map(int, e.split())
    y=(c*d-a*f)/(b*d-a*e)
    x = (c-b*y)/a
    #print (str(round(x, 3))+' '+str(round(y, 3)))#dont int+str
    print("%.3f %.3f"%(x,y))
S,T=input().split()
A,B map(int, input().split())
U = input()
if S==U:
  A-=1
elif T==U:
  B-=1
print(A,B)

### FIXED CODE ###

S, T = input().split()
A, B= map(int, input().split())
U = input()
if S == U:
    print(A - 1, B)
else:
    print(A, B - 1)
N , M = (map(int , input().split()))
tree = []
for i in range(N):
    tree.append(int(input()))
sort_tree = sorted(tree)
print(min([sort_tree[N-M+i] - sort_tree[i] for i in range(N-M+1)]))

### FIXED CODE ###

N , M = (map(int , input().split()))
tree = []
for i in range(N):
    tree.append(int(input()))
sort_tree = sorted(tree)
print(min([sort_tree[i+M-1] - sort_tree[i] for i in range(N-M+1)]))
s = input()

counter = [0] * 26

for i in s:
    counter[ord(i)-97] += 1

flag = 'Yes'
for i in counter:
    if (i % 2) == 1:
        flag = 'No'

print(flag)

### FIXED CODE ###

n = int(input())
k = int(input())
x = int(input())
y = int(input())

if n > k:
    print(k * x + (n-k)*y)
else:
    print(n*x)
import math

X = int(input())
x = round(math.sqrt(X), 0)
flag = 0

for i in range(100):
    for j in range(2, x):
        if X % j == 0:
            flag = 1
            break
    if flag == 0:
        break
    else:
        flag = 0
        X += 1
print(X)

### FIXED CODE ###

import math

X = int(input())
x = int(round(math.sqrt(X), 0))
flag = 0

for i in range(100):
    for j in range(2, x):
        if X % j == 0:
            flag = 1
            break
    if flag == 0:
        break
    else:
        flag = 0
        X += 1
print(X)
N = int(input())
p = list(map(int, input().split()))
for i in range(N):
    for j in range(i + 1, N):
        if p[j - 1] < p[i] < p[j + 1] and p[i - 1] < p[j] < p[i + 1]:
            print("YES")
        else:
            continue
print("NO")


### FIXED CODE ###

N = int(input())
p = list(map(int, input().split()))
count = 0
for i in range(N):
    if p[i] != i + 1:
        count += 1
if count == 0 or count == 2:
    print("YES")
else:
    print("NO")
import math
n = int(input())
m = n**0.5
ans = 0
#print(n)
#print(m)
for i in range(1,math.floor(m+1)):
    if m%i==0:
        ans = i
print(math.floor(ans+ n/ans -2))

### FIXED CODE ###

import math
n = int(input())
m = n**0.5
ans = 1
x = 0 #確認
#print(n)
#print(m)
for i in range(1,math.floor(m)+1):
    x += 1 #確認
    if n%i==0:
        ans = i

print(math.floor(ans+ n/ans -2))
A, B  = map(int,input().split())

print(math.ceil(B / A))

### FIXED CODE ###

import math

A, B = map(int,input().split())

x = (B-1)/(A-1)

print(math.ceil(x))
class Dice2(Dice1):

    def __init__(self, v): # v [Top, Front, Right, Left, Back, Bottom ]
        super().__init__(v)

        self.dTFR = {}
        for i, j, k in ((ii, (ii++2)%6, (ii+4)%6) for ii in  range(6)):
            self.dTFR[self.view[i]]=[self.view[v] for v in (j, k, 5-j, 5-k, j)]


d2, q = Dice2(list(map(int, input().split()))), int(input())
for i in range(q):
    t, f = map(int, input().split())
    print(d2.dTFR[t][d2.dTFR[t].index(f)+1] )

### FIXED CODE ###

class Dice2():

    def __init__(self, v): # v [Top, Front, Right, Left, Back, Bottom ]
        self.view = v
        self.dTFR = {}
        for i, j, k in ((ii, (ii++2)%6, (ii+4)%6) for ii in  range(6)):
            self.dTFR[self.view[i]]=[self.view[v] for v in (j, k, 5-j, 5-k, j)]


d2, q = Dice2(list(map(int, input().split()))), int(input())
for i in range(q):
    t, f = map(int, input().split())
    print(d2.dTFR[t][d2.dTFR[t].index(f)+1] )
n, m=map(int, input().split())
p=[0]+list(map(int, input().split()))

par=[i for i in range(n+1)]
cnt=0
def root(i):
    if par[i]==i:
        return i
    else:
        par[i]=root(par[i])
        return par[i]

for i in range(m):
    x, y=map(int, input().split())
    if root(x)==root(y):
        
    else:
        par[y]=root(x)

ans=0
for i in range(n):
    n=1+i
    if root(n)==root(p[n]):
        ans=ans+1
print(ans)
'''
print(par[1:])

root_ls=[0]+[root(i+1) for i in range(n)]
print(par[1:])
print(root_ls[1:])
'''

### FIXED CODE ###

n, m=map(int, input().split())
p=[0]+list(map(int, input().split()))

par=[i for i in range(n+1)]
cnt=0
def root(i):
    if par[i]==i:
        return i
    else:
        par[i]=root(par[i])
        return par[i]


for i in range(m):
    x, y=map(int, input().split())
    if root(x)==root(y):
        0
        #print(par[1:])
    else:
        par[root(y)]=root(x)
        #print(par[1:])

ans=0
for i in range(n):
    n=1+i
    if root(n)==root(p[n]):
        ans=ans+1
print(ans)
'''
print(par[1:])

root_ls=[0]+[root(i+1) for i in range(n)]
print(par[1:])
print(root_ls[1:])
'''
N,M=map(int,input().split())
A = [int(x) for x in input().split()]
B = []
length = len(A)
for i in range(M):
  b,c = map(int,input().split())
  B.extend(b*[c])
A.sort(reverse = True)
B.sort(reverse=True)
A = A[:length] 
B = B[:length]
if A[-1] >= B[0]:
  print(sum(A))
elif B[-1] > = A[0]:
  print(sum(B)
else:
  C = A + B
  C.sort(reverse=True)
  print(C[:length])


### FIXED CODE ###

read = input 
rn = lambda :map(int, read().split())
n,m = rn()
A = list(rn())
l = len(A)
d = {}
for x in A:
    if x not in d:
        d[x]=0
    d[x] += 1
for i in range(m):
    b, c = rn()
    if c not in d:
        d[c]=0
    d[c] += b
A = list(d.items())
A.sort(reverse=True)
ans = 0
cnt = l
# print(A)
for v, c in A:
    tmp = min(cnt, c)
    ans += tmp * v
    cnt -= tmp
print(ans)
def inpl():
    return list(map(int, input().split()))


def gcd(a, b):
    # greatest common divisor
    la = max(a, b)
    sm = min(a, b)
    if la % sm == 0:
        return sm
    else:
        return gcd(sm, la - sm)


def lcm(a, b):
    # least common multiple
    return a * b // gcd(a, b)


R, G, B, N = inpl()
ans = 0
for r in range(N // R + 1):
    rest = N - r * R
    for i in range(B):
        if (G * i) % B == rest % B:
            x = i
            break
    else:
        # print(r)
        continue
    if rest - G * x < 0:
        continue
    ans += (rest - G * x) // lcm(B, G) + 1
    # print(r, rest, x, ans)

print(ans)


### FIXED CODE ###

def inpl():
    return list(map(int, input().split()))


def gcd(a, b):
    # greatest common divisor
    la = max(a, b)
    sm = min(a, b)
    if la % sm == 0:
        return sm
    else:
        return gcd(sm, la - sm)


def lcm(a, b):
    # least common multiple
    return a * b // gcd(a, b)

import sys

sys.setrecursionlimit(5000)


R, G, B, N = inpl()
ans = 0
for r in range(N // R + 1):
    rest = N - r * R
    for i in range(B):
        if (G * i) % B == rest % B:
            x = i
            break
    else:
        # print(r)
        continue
    if rest - G * x < 0:
        continue
    ans += (rest - G * x) // lcm(B, G) + 1
    # print(r, rest, x, ans)

print(ans)
n,r=map(int(input().split(' ')))
if n<10:
  print(100*(10-n))
else:
  print(r)

### FIXED CODE ###

n,r=map(int,input().split(' '))
if n<10:
  print(100*(10-n)+r)
else:
  print(r)
a,b = input().split()
A = a * int(b)
B = b * int(a)

lis=[A,B]
true_list = lis.sort(reverse=True)
print(true_list[0])

### FIXED CODE ###

a,b = input().split()
A = int(a * int(b))
B = int(b * int(a))

if A >= B:
    print(str(A))
else:
    print(str(B))
K, S = map(int, input().split())
OK = 0
for x in range(K+1):
    if(0<=S-x & S-x<=2*K): # 計算の成立条件
        if(S-x<=K): # yとzの和がk以下
            OK += S-x+1
        else: # yとzの和がk以上
            OK += (K-((S-x)-K))+1
print(OK)

### FIXED CODE ###

s = input().split(',')
print(s[0] +' '+ s[1] + ' ' + s[2])
n=int(input())
out=0
for i in (n):
  n,m=map(int,input().split())
  out+=m-n+1
print(out)

### FIXED CODE ###

n=int(input())
out=0
for i in range(n):
  a,m=map(int,input().split())
  out+=m-a+1
print(out)
N, W = map(int, input().split())
wv = []

for i in range(N):
    w, v = map(int, input().split())
    wv.append([w, v])

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

for i in range(N):
    for j in range(W+1):
        if j - wv[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = []

for i in range(N):
    w, v = map(int, input().split())
    wv.append([w, v])
MAX_V = 10**5+100
INF = 10**10
dp = [[INF]*MAX_V for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_V):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = 0
for i in range(MAX_V):
    if dp[N][i] <= W:
        ans = i
print(ans)
n=int(input())
for i in range(1,n+1):
  cnt+=i%2
  
print(cnt/n)

### FIXED CODE ###

n=int(input())
cnt=0
res=0.0
for i in range(1,n+1):
  if i%2==1:
    cnt+=1
    
res = cnt/n
print(res)
INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
def dfs(x):
    global ans
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            dfs(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
dfs(0)
print((ans*k)%INF)
        


### FIXED CODE ###

INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
import sys
sys.setrecursionlimit(10**6)
stack=[0]
ans=1
while len(stack)>0:
    x=stack.pop()
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            stack.append(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
print((ans*k)%INF)
n,k = map(int, input().split())
li = []
i = 0
for i<k:
  li.append(int(input()))
  i += 1
else:
  Li = list(n)
  while not len(set(li)&set(Li)):
    n += 1
    Li = list(n)
  else: print("".join(Li))

### FIXED CODE ###

n,k = map(str, input().split())
li = list(map(str, input().split()))
Li = list(n)
while len(set(Li)&set(li)):
  n = int(n)+1
  Li = list(str(n))
else: print("".join(Li))
a = input()
if int(a[5])=0 and int(a[6])<=4:
  print('Heisei')
else:
  print('TBD')

### FIXED CODE ###

a = input()
if int(a[5])==0 and int(a[6])<=4:
  print('Heisei')
else:
  print('TBD')
S = input()
L = S.split()
a = L[0]
b = L[1]
if int(a) < int(b):
    print('a < b')
elif int(a) > int(b):
    print('a > b')
elif int(a) == int(b):
    print('a == b')

### FIXED CODE ###

S = input()
L = S.split()
a = L[0]
a = int(a)
b = L[1]
b = int(b)
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
elif a == b:
    print('a == b')
import collections
import math

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

N = int(input())
s = [""]*N
for i in range(N):
    s[i] = ','.join(sorted(input()))

c = collections.Counter(s)
ans = 0
for value in c.values():
    ans += combinations_count(value, 2)
    
print(ans)

### FIXED CODE ###

import collections
import math

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

N = int(input())
s = [""]*N
for i in range(N):
    s[i] = ','.join(sorted(input()))

c = collections.Counter(s)
ans = 0
for value in c.values():
    if(value == 1):
        continue
    ans += combinations_count(value, 2)
    
print(ans)
a,b=map(str,input().split())
c.d=map(int,input().split())
e=input()
if a==e:
  print(c-1,d)
else:
  print(c,d-1)
 

### FIXED CODE ###

a,b=map(str,input().split())
c,d=map(int,input().split())
e=str(input())
if a==e:
    print(c-1,d)
else:
    print(c,d-1)
import numpy as np
def main():
  N,M=map(int,input().split())
  str_list = [list(input().split()) for _ in range(M)]
  np_str_list=np.array(str_list)
  wacount=0
  account=0
  if(len(str_list)==0):
    print(0,0)
  else:
    for i in range(1,N+1):
      tgtarray=np_str_list[np.where(np_str_list[:,0]==str(i)),1][0]
      if(len(tgtarray)!=0):
        ac_index=np.where(tgtarray=='AC')[0][0]
        account=account+1
        wacount=wacount+tgtarray[0:ac_index].shape[0]
    print(account,wacount)

if __name__=='__main__':
  main()
  

### FIXED CODE ###

n,m=map(int,input().split())
ps=[list(input().split()) for i in range(m)]
pen=[0]*n#ペナ数
rig=[0]*n#ACorWA

for i in range(m):
    if ps[i][1]=="AC":
        rig[int(ps[i][0])-1]=1
    else:
        if rig[int(ps[i][0])-1]==0:
            pen[int(ps[i][0])-1]+=1
cnt1,cnt2=0,0
for i in range(n):
    if rig[i]==1:
        cnt1+=rig[i]
        cnt2+=pen[i]

print(str(cnt1)+" "+str(cnt2))
(m,n)=map(int, raw_input().split())
    if n==0 & m==0 : break
    else: print ((('#'*n)'\n')*m)

### FIXED CODE ###

while True:
    (m,n)=map(int, raw_input().split())
    if n==0 and m==0: break
    else: print (('#'*n+'\n')*m)
n = int(input())
a = []
for i in range(n):
    city,score = input().split()
    score=int(score)
    a.append((city,score,i+1))
a.sort(key=lambda k: (k[1],-k[0]))

for i in range(n):
    print(a[i][2])

### FIXED CODE ###

n = int(input())
a= []
for i in range(n):
	city, score = input().split()
	score = int(score)
	a.append((city, score, i+1))
a.sort(key=lambda k : (k[0], -k[1]))
for i in range(n):
	print(a[i][2])