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

import numpy as np
A,B,Q = list(map(int,input().split())) 
S = [int(input()) for _ in range(A) ]
T = [int(input()) for _ in range(B) ]
x = [int(input()) for _ in range(Q)]
S = np.array(S)
T = np.array(T)
for a in x:
    ans1 = 0
    ans2 = 0
    S1 = abs(S-a)
    T1 = abs(T-a)
    ans1 +=np.min(T1)
    ans1 += min(abs(S-T[np.argmin(T1)]))
    ans2+=np.min(S1)
    ans2+= min(abs(T-S[np.argmin(S1)]))
    print(min(ans1,ans2))

### FIXED CODE ###

import bisect
A,B,Q = map(int,input().split()) 
INF = 10**18
S = [-INF]+[int(input()) for _ in range(A)]+[INF]
T = [-INF]+[int(input()) for _ in range(B) ]+[INF]
x = [int(input()) for _ in range(Q)]

for a in x:
    ans1 = 0
    ans2 = 0
    b = bisect.bisect_left(S,a)
    c = bisect.bisect_left(T,a)
    res = INF
    for s in [S[b-1],S[b]]:
        for t in [T[c-1],T[c]]:
            d1,d2 = abs(s-a)+abs(s-t),abs(t-a)+abs(s-t)
            res = min(res,d1,d2)
    print(res)
### BUGGY CODE ###

N = int(input())
X = int(input(),2)

def popcount(n):
    return bin(n).count('1')


def f(n, popcount_1):
    count = 0
    if popcount_1 == 0:
        return 0
    else:
        n = n%popcount_1
        count += 1
    
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


X_popcount = popcount(X)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X>>(N-i-1)&1 == 1:
        ans = f(X_i, X_popcount-1)
    else:
        ans = f(X_i, X_popcount+1)
    print(ans)

### FIXED CODE ###

N = int(input())
X = int(input(),2)

def popcount(n):
    return bin(n).count('1')


def f(n):
    if n== 0:
        return 1
    count = 1
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


X_popcount = popcount(X)
X_mod_p = X%(X_popcount+1)
if X_popcount != 1:
    X_mod_m = X%(X_popcount-1)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X_i == 0:
        ans = 0
    elif X>>(N-i-1)&1 == 1:
        if X_popcount == 1:
            ans = 1
        else:
            ans = f((X_mod_m-pow(2, N-i-1, X_popcount-1))%(X_popcount-1))
    else:
        ans = f((X_mod_p+pow(2, N-i-1, X_popcount+1))%(X_popcount+1))
    print(ans)
### BUGGY CODE ###

n = int(input())
l = input().split(' ')
l = [int(i) for i in l]
l.sort(reverse=True)

cnt = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[i] < (l[j] + l[k]):
                # print(i, j, k)
                cnt += 1

print(cnt)
# print(l)


### FIXED CODE ###

import bisect

n = int(input())
l = input().split(' ')
l = [int(i) for i in l]
l.sort()

cnt = 0
for i in range(n):
    for j in range(i+1, n):
        num = l[i] + l[j]
        index = bisect.bisect_left(l, num)
        # print(index, j)
        # print(index-2)
        cnt += (index-j-1)

print(cnt)
### BUGGY CODE ###

import numpy as np

n = int(input())
A = np.array(list(map(int, input().split(' '))))

A_unique = np.unique(A)
num_dict = {}
for a in A_unique:
  tmp = np.sum(A==a)
  num_dict[a] = (tmp*(tmp-1)/2, (tmp-1)*(tmp-2)/2)
total = sum([x[0] for x in num_dict.values()])

for k in range(n):
  print(int(total - num_dict[A[k]][0] + num_dict[A[k]][1]))

### FIXED CODE ###

import collections

n = int(input())
A = list(map(int, input().split(' ')))
 
c = dict(collections.Counter(A))
num_dict = {}
total = 0
for a, count in c.items():
  num_dict[a] = (count*(count-1)/2, (count-1)*(count-2)/2)
  total += count*(count-1)/2

ans_dict = {}
for a in c.keys():
  ans_dict[a] = total - num_dict[a][0] + num_dict[a][1]

for k in range(n):
  print(int(ans_dict[A[k]]))
### BUGGY CODE ###

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

tb = [False]*10**5
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            l = int(''.join(S[i]+S[j]+S[k]))
            tb[l] = True
print(tb.count(True))

### FIXED CODE ###

from collections import defaultdict
n = int(input())
S = input()

d1 = defaultdict(int)
d2 = defaultdict(int)
d3 = defaultdict(int)

for s in S:
    for x in d2:
        d3[x+s]+=1
    for y in d1:
        d2[y+s]+=1
    d1[s]+=1

print(len(d3))
### BUGGY CODE ###

from math import sqrt
from fractions import gcd
from collections import defaultdict
from copy import deepcopy

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

def f(n):
    d = defaultdict(int)
    if n % 2 == 0:
        r = 0
        while n % 2 == 0:
            n //= 2
            r += 1
        d[2] = r
    for i in range(3,int(sqrt(n))+1,2):
        if n % i == 0:
            s = 0
            while n % i == 0:
                n //= i
                s += 1
            d[i] = s
    if n != 1:
        d[n] = 1
    return d

B = []
for i in range(N):
    B.append(f(A[i]))

lp = deepcopy(B[0])

for i in range(N-1):
    for j in list(set(B[i+1].keys()) | set(lp.keys())):
        lp[j] = max(B[i+1][j],lp[j])

ans = 0

for i in range(N):
    r = 1
    for j in list(lp.keys()):
        r = (r*pow(j,lp[j]-B[i][j],mod)) % mod
    ans = (ans + r) % mod

print(ans)


### FIXED CODE ###

def main():
    from math import sqrt
    from fractions import gcd
    from collections import defaultdict
    from copy import deepcopy

    N = int(input())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    p = [1] * (1001)
    P = []  # 1000までの素数表
    p[0] = p[1] = 0
    for x in range(2, int(sqrt(1000000)) + 1):
        if p[x]:
            P.append(x)
            for y in range(x * x, 1001, x):
                p[y] = 0

    B = [defaultdict(int) for i in range(N)]  # N個の数を素因数分解したもの
    lcm = defaultdict(int)  # N個の数のlcmを素因数分解したもの

    for i in range(N):
        for j in P:
            if A[i] % j == 0:
                while A[i] % j == 0:
                    A[i] //= j
                    B[i][j] += 1
            lcm[j] = max(lcm[j], B[i][j])
        if A[i] != 1:
            B[i][A[i]] = 1
            lcm[A[i]] = 1

    l = 1  # N個の数のlcm
    for i in lcm.keys():
        l = (l * pow(i, lcm[i], mod)) % mod

    ans = 0
    # l/A[i]の和を求めていく
    for i in range(N):
        r = l
        for j in list(B[i].keys()):
            r = (r * pow(j, mod - B[i][j] - 1, mod)) % mod
        ans = (ans + r) % mod

    print(ans)

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

N=int(input())
A = list(map(int,input().split()))
Q=int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i],C[i]=map(int,input().split())
#print(B,C)
#print(A)
a = 0
for i in range(N):
    a += A[i]
#print(a)
for j in range(Q):
    for i in range(N):
        if A[i] == B[j]:
            a = a + (C[j]-A[i])
            A[i] = C[j]
    #print(A)
    print(a)


### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
Q=int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i],C[i]=map(int,input().split())
#print(B,C)
#print(A)
#a = 0
#for i in range(N):
    #a += A[i]
#print(a)
ls = [0]*100000
for i in A:
    ls[i-1] += 1
#print(ls)
sumA = sum(A)
#print("sumA",sumA)
for j in range(Q):
    #print(B[j]-1)
    #print(ls)
    sumA += (C[j]-B[j])*ls[B[j]-1]
    #print("j","C[j]","B[j]","ls[B[j]]",j,C[j],B[j],ls[B[j]-1])
    ls[C[j]-1] += ls[B[j]-1]
    ls[B[j]-1] = 0
    print(sumA)
### BUGGY CODE ###

n = int(input())
p_list = list(map(int, input().split(" ")))
count = 0
for i in range(n):
    for j in range(i+1):
        if p_list[i] > p_list[j]:
            break
    else:
        count += 1
print(count)


### FIXED CODE ###

n = int(input())
p_list = list(map(int, input().split(" ")))
count = 0
minimum = 10000000
for i in p_list:
    if(i <= minimum):
        minimum = i
        count += 1
print(count)
### BUGGY CODE ###

S = input()
Q = int(input())
rev_flag = False
for i in range(Q):
    query = input()
    if query == "1":
        rev_flag = not rev_flag
    else:
        if not rev_flag:
            if query[2] == "1":
                S = query[4] + S
            else:
                S = S + query[4]
        else:
            if query[2] == "2":
                S = query[4] + S
            else:
                S = S + query[4]
    #print(query)

if rev_flag:
    S = S[::-1]
print(S)



### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
ans = deque(S)
rev_flag = False
for i in range(Q):
    query = input()
    if query == "1":
        rev_flag = not rev_flag
    elif not rev_flag:
        if query[2] == "1":
            ans.appendleft(query[4])
        else:
            ans.append(query[4])
    else:
        if query[2] == "2":
            ans.appendleft(query[4])
        else:
            ans.append(query[4])

if rev_flag:
    ans.reverse()

print("".join(ans))
### BUGGY CODE ###

N, K= map(int, input().split())
H=list(map(int, input().split()))
if K>=len(H):
    print(0)
else:
    for i in range(K):
        H=sorted(H)
        H.pop(-1)
    print(sum(H))

### FIXED CODE ###

N, K= map(int, input().split())
H=list(map(int, input().split()))
if K>=len(H):
    print(0)
else:
    if K==0:
        print(sum(H))
    else:
        H=sorted(H)
        print(sum(H[:-K]))
### BUGGY CODE ###

from collections import Counter
def main():
    S=input()
    remainders=[0]
    sub=0
    for i in range(len(S)-1,-1,-1):
        sub=int(S[i])*pow(10,len(S)-i-1)+sub
        remainders.append(sub%2019)
    d=Counter(remainders)
    ans=0
    for key in d:
        ans+=(d[key]*(d[key]-1))//2
    print(ans)
if __name__=='__main__':
    main()

### FIXED CODE ###

from collections import Counter
def main():
    S=input()
    remainders=[0]
    sub=0
    pow10=1
    for i in range(len(S)-1,-1,-1):
        remainders.append((remainders[-1]+pow10*int(S[i]))%2019)
        pow10=((pow10%2019)*(10%2019))%2019
    d=Counter(remainders)
    ans=0
    for key in d:
        ans+=(d[key]*(d[key]-1))//2
    print(ans)
if __name__=='__main__':
    main()
### BUGGY CODE ###

from collections import Counter
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=Counter(A).most_common()
print(sum(B[K:][i][1] for i in range(len(B[K:]))))

### FIXED CODE ###

from collections import Counter
N,K=map(int,input().split())
A=input().split()
B=Counter(A)
C=sorted(B.values(),reverse=True)
print(sum(C[K:]))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = sorted(a, key=lambda x: x)
ans = [a.index(x)+1 for x in b]
print(' '.join(map(str,ans)))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n):
    b[a[i]-1] = i + 1
print(' '.join(map(str,b)))
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = [[0]*10 for _ in range(n)]
ans = 0
for i in range(n):
    str_s = input()
    for j in range(10):
        s[i][j] = str_s[j]

for i in range(n):
    s[i].sort()
    s[i] = tuple(s[i])
set_s = set(s)

if n-len(set_s) == 0:
    print(0)
elif n-len(set_s) == 1:
    print(n-len(set_s))
else:
    for item in set_s:
        count = 0
        for j in range(n):
            if item == s[j]:
                count += 1
        ans += count*(count-1)//2
    print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [[0]*10 for _ in range(n)]
ans = 0
for i in range(n):
    str_s = input()
    for j in range(10):
        s[i][j] = str_s[j]

dict_s = {}
for i in range(n):
    s[i].sort()
    si = "".join(s[i])
    dict_s.setdefault(si, 0)
    dict_s[si] += 1

for x in dict_s.values():
    ans += x*(x-1)//2
print(ans)
### BUGGY CODE ###

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

ai = []
aj = []
ans = 0
aiajmin = -9999999


for i in range(n):
    ai.append(i+l[i])

for j in range(n):
    aj.append(j-l[j])

#print(ai)
#print(aj)
    
aiajmin = min(max(ai),max(aj))
ai.sort()
aj.sort()

for x in range(n):
    if(ai[x] <= aiajmin):
        ans = ans + aj.count(ai[x])
    else:
        break
    
print(ans)

### FIXED CODE ###

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

a=[]
b={}
ans=0

for i in range(n):
    a.append(i+l[i])
    b[i-l[i]] = b.get(i-l[i],0) + 1

for av in a:
    ans = ans + b.get(av,0)

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

dic=[]
n=int(input())
cmd=[list(input().split()) for i in range(n)]
for c, l in cmd:
    if c=="insert":
        dic.append(l)
    if c=="find":
        if l in dic:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

dic=set()
n=int(input())
cmd=[list(input().split()) for i in range(n)]
for c, l in cmd:
    if c=="insert":
        dic.add(l)
    if c=="find":
        if l in dic:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

def make_daker(mas, H, W):
  #mas_new = [["." for i in range(W)] for j in range(H)]
  import copy
  mas_new = copy.deepcopy(mas)
  for i in range(H):
    for j in range(W):
      if mas[i][j] == "#":
        mas_new[i][j] = "#"
        if i-1 >= 0:
          mas_new[i-1][j] = "#"
        if i+1 < H:
          mas_new[i+1][j] = "#"
        if j-1 >= 0:
          mas_new[i][j-1] = "#"
        if j+1 < W:
          mas_new[i][j+1] = "#"
  return mas_new

def include_white(mas):
  for row in mas:
    if "." in row:
      return True
  return False

H, W = map(int, input().split())
mas = [[i for i in input()] for i in range(H)]

ans = 0

while include_white(mas) is True:
  mas = make_daker(mas, H, W)
  ans +=1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy as np
# from time import perf_counter


def main():
    h, w = map(int, input().split())
    max_value = h + w
    gridmap = []

    for y in range(h):
        gridmap.append([0 if v == '#' else max_value for v in input().strip()])

    values = np.array(gridmap)

    for x in range(w - 1):
        values[:, x + 1] = np.minimum(values[:, x] + 1, values[:, x + 1])

    for x in range(w - 1, 0, -1):
        values[:, x - 1] = np.minimum(values[:, x] + 1, values[:, x - 1])

    for y in range(h - 1):
        values[y + 1, :] = np.minimum(values[y, :] + 1, values[y + 1, :])

    for y in range(h - 1, 0, -1):
        values[y - 1, :] = np.minimum(values[y, :] + 1, values[y - 1, :])

    print(np.max(values))


if __name__ == '__main__':
    # st = perf_counter()
    main()
    # ed = perf_counter()
    # print(ed - st)
### BUGGY CODE ###

import itertools
N, K, L = [int(_) for _ in input().split()]
PQ = [[int(_) for _ in input().split()] for _ in range(K)]
RS = [[int(_) for _ in input().split()] for _ in range(L)]

road = [[1 if i == j else 0 for j in range(N + 1)] for i in range(N + 1)]
road[0][0] = 0
train = [[1 if i == j else 0 for j in range(N + 1)] for i in range(N + 1)]
train[0][0] = 0

for i, j in itertools.product(range(K), range(1, N + 1)):
    if road[PQ[i][0]][j] or road[PQ[i][1]][j]:
        road[PQ[i][0]][j] = 1
        road[PQ[i][1]][j] = 1
        road[j][PQ[i][0]] = 1
        road[j][PQ[i][1]] = 1

for i, j in itertools.product(range(L), range(1, N + 1)):
    if train[RS[i][0]][j] or train[RS[i][1]][j]:
        train[RS[i][0]][j] = 1
        train[RS[i][1]][j] = 1
        train[j][RS[i][0]] = 1
        train[j][RS[i][1]] = 1

print(' '.join([str(sum([road[i][j] and train[i][j] for j in range(1, N + 1)])) for i in range(1, N + 1)]))

### FIXED CODE ###

class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

    def find(self, x):
        if self.par.get(x, x) == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N, K, L = [int(_) for _ in input().split()]

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get((Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)]) for i in range(1, N + 1)))
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit
input = sys.stdin.buffer.readline

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

n = min(2**1, N)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

@njit("(i4[::], i4[::], i4, i4)", cache = True)
def func(vs, ws, V, L):
    bits = np.arange(1 << len(vs))
    values = np.zeros_like(bits, np.int32)
    weights = np.zeros_like(bits, np.int32)
    for i in range(len(vs)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vs[i]
        weights[indices] += ws[i]

    mask = (weights <= L)     
    print(np.amax(dp[V][L - weights[mask]] + values[mask]))


Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V][L])
    else:
        vws_choose = []
        while V >= n:
            vws_choose.append(vws[V])
            V = (V-1) // 2
        vs, ws = zip(*vws_choose)
        func(np.array(vs, np.int32), np.array(ws, np.int32), V, L)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

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

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ans = 0
card = [1] * N
for _ in range(M):
	L, R = map(int, input().split())
	for i in range(N):
		if i < L-1 or R-1 < i:
			card[i] = 0

print(card.count(1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
max_L = 1
min_R = 100000
for _ in range(M):
	L, R = map(int, input().split())
	if max_L < L:
		max_L = L
	if R < min_R:
		min_R = R
if min_R - max_L + 1 < 0:
	print(0)
else:
	print(min_R - max_L + 1)
### BUGGY CODE ###

import re

n, q = map(int, input().split())
s = input()
for _ in range(q):
    l, r = map(int, input().split())
    li = re.findall("AC", s[l-1:r])
    print(len(li))


### FIXED CODE ###

from bisect import bisect, bisect_left

n, q = map(int, input().split())
s = input()

bi = []

for i in range(n - 1):
    if s[i:i+2] == "AC":
        bi.append(i)

for _ in range(q):
    l, r = map(int, input().split())
    answer = bisect(bi, r - 1) - bisect_left(bi, l - 1)
    if r < n and s[r - 1:r + 1] == "AC":
        answer -= 1
    print(answer)
### BUGGY CODE ###

N=int(input())
A = [int(hoge) for hoge in input().split()]
print(*[A.index(j)+1 for j in range(1,N+1)] )

### FIXED CODE ###

N=int(input())
A = [int(hoge) for hoge in input().split()]
ans = [0]*N
for n,a in enumerate(A):
    ans[a-1] = n+1
print(*ans)
### BUGGY CODE ###

import math
n = int(input())
S = list(map(int,input().split()))

def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = []
    for i in range(n1+1):
        L.append(i)
    R = []
    for i in range(n2+1):
        R.append(i)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = 10000000000
    R[n2] = 10000000000
    i = 0
    j = 0
    for k in range(left,right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

count = 0
mergeSort(S,0,len(S))
print(*S)
print(count)

### FIXED CODE ###

n = int(input())
S = list(map(int,input().split()))
M = 10**9 + 1
def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = A[left:left + n1]
    R = A[mid:mid + n2]
    L.append(M)
    R.append(M)
    i = 0
    j = 0
    for k in range(left,right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

count = 0
mergeSort(S,0,len(S))
print(*S)
print(count)
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                cnt +=1

print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
            if 0 <= s-(x+y) < k+1:
                cnt +=1

print(cnt)
### BUGGY CODE ###

from collections import defaultdict
s = input()
k = int(input())
dd = {}
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    dd[s[i]] = 1
for i in range(len(s)-1):
    for j in range(i+1, len(s)):
        dd[s[i:j+1]] = 1
li = []
for key in dd:
    li.append(key)
li.sort()
print(li[k-1])

### FIXED CODE ###

from collections import defaultdict
s = input()
k = int(input())
dd = {}
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    dd[s[i]] = 1
for i in range(len(s)-1):
    for j in range(i+1, len(s)):
        if j-i+1 <= k:
            dd[s[i:j+1]] = 1
li = []
for key in dd:
    li.append(key)
li.sort()
print(li[k-1])
### BUGGY CODE ###

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

banned_list = []*M
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))

banned_list = sorted(banned_list,key=lambda x:x[1])
status = [True for _ in range(N-1)]
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if sum(status[a-1:b-1]) ==  b-a:
        counter += 1
        status[b-2] = False
print(counter)

### FIXED CODE ###

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

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
banned_list = sorted(banned_list,key=lambda x:x[1])
#status = [1 for _ in range(N-1)]
status = set()
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if len([one for one in status if (one >= a-1 and one < b-1)]) == 0:
        status  |= {b-2}
        counter += 1
print(counter)
### BUGGY CODE ###

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

cnt = [0 for _ in range(N)]
for i in range(N-1):
    cnt_i = 0
    for j in range(i+1, N):
        if (cnt[j] != 0):
            continue
        if (s[i] == s[j]):
            cnt_i += 1
            cnt[j] = cnt_i

print(sum(cnt))


### FIXED CODE ###

from collections import defaultdict
N = int(input())
s = [''.join(sorted(input())) for i in range(N)]
d = defaultdict(lambda: 0)

for _s in s:
    d[_s] += 1

print(sum(map(lambda x: x * (x-1) // 2, d.values())))