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

from collections import *
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S = 2*[(W+4)*["#"]]+[2*["#"]+list(input())+2*["#"] for h in range(H)]+2*[(W+4)*["#"]]
S[CH+1][CW+1] = 0
P = [[CH+1,CW+1]]
Q = deque([[CH+1,CW+1]])
D1 = [[1,0],[-1,0],[0,1],[0,-1]]
D2 = [[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
ans = 0

while P:
  P = []
  while Q:
    edge = 0
    y,x = Q.popleft()
    for dy,dx in D1:
      if S[y+dy][x+dx]==".":
        S[y+dy][x+dx] = S[y][x]
        Q.append([y+dy,x+dx])
      elif S[y+dy][x+dx]=="#" and edge==0:
        edge+=1
        P.append([y,x])

  if S[DH+1][DW+1]!=".":
    print(S[DH+1][DW+1])
    exit()
  else:
    ans+=1
    for y,x in P:
      for dy,dx in D2:
        if S[y+dy][x+dx]==".":
          S[y+dy][x+dx] = ans
          Q.append([y+dy,x+dx])

if S[DH+1][DW+1]==".":
  print(-1)
else:
  print(S[DH+1][DW+1])

### FIXED CODE ###

from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import Counter

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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

counter = Counter(A)

ans = 0
for k, v in counter.items():
    if v != 1:
        continue
    can = True
    for d in make_divisors(k):
        if d == k:
            continue
        if d in counter:
            can = False
    if can:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

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

# 同じ値が複数存在するかチェックする用のカウンタ
counter = Counter(A)

# D[a] = True: Aにaより小さいaの約数が存在する
A_max = max(A)
dp = {a: False for a in A}

for a in A:
    # xが数列Aに含まれているとき、aより大きいaの倍数tについて、dp[a * t]をTrueに変更する
    if counter[a] > 0:
        t = 2
        while a * t <= A_max:
            dp[a * t] = True
            t += 1

ans = 0
for a in A:
    if counter[a] == 1 and dp[a] is False:
        ans += 1

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

import collections

s = input()
t = input()
s_index = {}
for pos, el in enumerate(s):
	if el in s_index:
		s_index[el].append(pos)
	else:
		s_index[el] = [pos]
check = all([i in s_index for i in t])
if not check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		cursor = ans % s_size
		find = False
		if cursor > s_index[target][-1]:
			find = False
		else:
			for j in s_index[target]:
				if j >= cursor:
					find = True
					break
		diff = j - cursor + 1 if find else s_index[target][0] + s_size - cursor + 1
		ans += diff
		
print(ans)
	

### FIXED CODE ###

import collections
import bisect

s = input()
t = input()
s_index = {}
	
for pos, el in enumerate(s):
	if el in s_index:
		s_index[el].append(pos)
	else:
		s_index[el] = [pos]
check = all([i in s_index for i in t])
if not check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		cursor = ans % s_size
		find = False
		if cursor > s_index[target][-1]:
			find = False
		else:
			j = bisect.bisect_left(s_index[target], cursor)
			find = True
		diff = s_index[target][j] - cursor + 1 if find else s_index[target][0] + s_size - cursor + 1
		ans += diff
		
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
teleport_list = list(map(int, input().split()))
t_cycle = [1]
now = 1
while len(t_cycle) == len(set(t_cycle)):
  now = teleport_list[now-1]
  t_cycle.append(now)

start_cycle = t_cycle[-1]
before_cycle_len = t_cycle.index(start_cycle)
cycle_len = len(t_cycle) - t_cycle.index(start_cycle) - 1

if k <= before_cycle_len:
  print(t_cycle[k])
else:
  print(t_cycle[(k-before_cycle_len)%cycle_len + before_cycle_len])

### FIXED CODE ###

n, k = map(int, input().split())
teleport_list = list(map(int, input().split()))
t_cycle = [1]
c_set = set([1])
now = 1
while len(t_cycle) == len(c_set):
  now = teleport_list[now-1]
  t_cycle.append(now)
  c_set.add(now)

start_cycle = t_cycle[-1]
before_cycle_len = t_cycle.index(start_cycle)
cycle_len = len(t_cycle) - t_cycle.index(start_cycle) - 1

if k <= before_cycle_len:
  print(t_cycle[k])
else:
  print(t_cycle[(k-before_cycle_len)%cycle_len + before_cycle_len])
### BUGGY CODE ###

A, B, M = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
xyc = [[int(_) for _ in input().split()] for i in range(M)]

rets = []
for i in a:
    for j in b:
        rets += [i + j]
for x, y, c in xyc:
    rets += [a[x-1] + b[y-1] - c]
print(min(rets))

### FIXED CODE ###

A, B, M = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
xyc = [[int(_) for _ in input().split()] for i in range(M)]

rets = [min(a) + min(b)]

for x, y, c in xyc:
    rets += [a[x-1] + b[y-1] - c]
print(min(rets))
### BUGGY CODE ###

n=int(input())
box=[]
for i in range(1,101):
    if i%11==0 or i%4==0 or i%7==0:
        box.append(i)

for i in box:
    if i+4 not in box:
        box.append(i+4)
    if i+7 not in box:
        box.append(i+7)
    if i+11 not in box:
        box.append(i+11)
        
print("Yes" if n in box else "No")

### FIXED CODE ###

n=int(input())
for i in range(n//7+1):
    for j in range(n//4+1):
        if 7*i+4*j==n:
            print("Yes")
            exit()
print("No")
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
count=0
l=sorted(l)
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            
            if abs(l[j]-l[k])<l[i]<l[j]+l[k]:
                count+=1
            elif abs(l[j]-l[k])>=l[i]:
                break
            
print(count)

### FIXED CODE ###

#ABC143-D
n=int(input())
l=list(map(int,input().split()))
l=sorted(l,reverse=True)
ans=0
#print(l)
for i in range(n-2):
    for j in range(i+1,n-1):
        b=l[i]
        c=l[j]

        #二分探索
        ok=j
        ng=n
        while ng-ok>1:
            mid=(ok+ng)//2
            if l[mid]>b-c:
                #b>=cはわかってる
                ok=mid

            else:
                ng=mid

        ans+=ok-j
print(ans)
### BUGGY CODE ###

from collections import Counter
S = str(input())
N = len(S)

#smod = [int(S[i:])%2019 for i in range(N)]
smod = [0]
tmod = 0
keta = 1
for i in range(N):
    temp = tmod + int(S[(N-1)-i])*keta
    #print(temp)
    tmod = temp%2019
    smod.append(tmod)
    keta *= 10


cmod = Counter(smod)
#print(cmod)

ans = 0
for i in cmod.values():
    ans += i*(i-1)/2
print(int(ans))

### FIXED CODE ###

from collections import Counter
S = str(input())
N = len(S)

#smod = [int(S[i:])%2019 for i in range(N)]
smod = [0]
tmod = 0
keta = 1
for i in range(N):
    temp = tmod + int(S[(N-1)-i])*keta
    #print(temp)
    tmod = temp%2019
    smod.append(tmod)
    keta = keta*10%2019


cmod = Counter(smod)
#print(cmod)

ans = 0
for i in cmod.values():
    ans += i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

from bisect import bisect_left, bisect, insort
def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    _is = [[] for _ in range(26)]
    for i, si in enumerate(s, 1):
        _is[si].append(i)
    
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            if s[i-1] == c:
                continue
            _is[s[i-1]].remove(i)
            insort(_is[ord(c)-a], i)
            s[i-1] = ord(c)-a
        else:
            c = int(c)
            cnt = 0
            for _isi in _is:
                if _isi:
                    is_in = bisect(_isi, c)-bisect_left(_isi, i)
                    if is_in:
                        cnt += 1
            print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    bits = [BIT(n) for _ in range(26)]
    for i, si in enumerate(s, 1):
        bits[si].add(i, 1)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            bits[s[i-1]].add(i, -1)
            bits[ord(c)-a].add(i, 1)
            s[i-1] = ord(c)-a
        else:
            c = int(c)
            cnt = 0
            for bit in bits:
                is_in = bit.sum_(c) - bit.sum_(i-1)
                if is_in:
                    cnt += 1
            print(cnt)
            
            
class BIT:
    __slots__ = ["length", "data"]
    def __init__(self, length):
        self.data = [0]*(length+1)
        self.length = length
    
    def add(self, i, x):
        while i < self.length+1:
            self.data[i] += x
            i += i&-i
    
    def sum_(self, i):
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i&-i
        return x


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

# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import statistics
import string


def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)

s = input()
Q = intinput()
rev_count = 0

for i in range(Q):
    a = input()
    if a[0] == "1":
        rev_count += 1
    else:
        b = a.split()
        if rev_count % 2 == 0:
            if b[1] == "1":
                s = b[2] + s
            else:
                s = s + b[2]
        else:
            if b[1] == "1":
                s = s + b[2]
            else:
                s = b[2] + s

if rev_count % 2 == 0:
    print(s)
else:
    print(s[::-1])



### FIXED CODE ###

# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import statistics
import string
import sys
from array import array
from collections import deque

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)

s = deque()
s.append(input())
Q = int(input())
rev_count = 0

for i in range(Q):
    a = input()
    if a[0] == "1":
        rev_count += 1
    else:
        b = a.split()
        if rev_count % 2 == 0:
            if b[1] == "1":
                s.appendleft(b[2])
            else:
                s.append(b[2])
        else:
            if b[1] == "1":
                s.append(b[2])
            else:
                s.appendleft(b[2])

if rev_count % 2 == 0:
    print(''.join(s))
else:
    a = ''.join(s)
    print(a[::-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
l=tuple(input())
q=int(input())
kl=tuple(map(int,input().split()))
for i in range(q):
    k=kl[i]
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        if l[j]=='M':
            m+=1
            dm+=d
        if l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            if l[j-k+1]=='M':
                m-=1
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for k in kl:
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    mod = 998244353
    a, b, c, d = nm()
    n, m = c-a, d-b
    dp = [[0]*(m+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        dp[i+1][0] = dp[i][0] * b % mod
    for i in range(m):
        dp[0][i+1] = dp[0][i] * a % mod
    for i in range(1, n+1):
        for j in range(1, m+1):
            dp[i][j] = (dp[i][j-1] * (a + i) + dp[i-1][j] * (b + j) - dp[i-1][j-1] * (a + i - 1) * (b + j - 1)) % mod
    # if a < 10:
    #     prn(dp)
    print(dp[n][m])

    return

solve()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    mod = 998244353
    a, b, c, d = nm()
    n, m = c-a, d-b
    dp = [[0]*(m+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        dp[i+1][0] = dp[i][0] * b % mod
    for i in range(m):
        dp[0][i+1] = dp[0][i] * a % mod
    for i in range(1, n+1):
        for j in range(1, m+1):
            dp[i][j] = (dp[i][j-1] * (a + i) + dp[i-1][j] * (b + j) - dp[i-1][j-1] * (a + i - 1) * (b + j - 1)) % mod
    # if a < 10:
    #     prn(dp)
    print(dp[n][m])

    return

solve()
### BUGGY CODE ###

N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
qlist = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    qlist[p-1] += x


cnt = [-1]*N
q = [0]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    for i in L[temp]:
        if cnt[i] < 0:
            q.append(i)
            cnt[i] = cnt[temp]+qlist[i]
            
for i in range(N):
    print(cnt[i])

### FIXED CODE ###

N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x

flag = [1]*N
q = [0]
while q:
    temp = q.pop()
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
print(*cnt)
### BUGGY CODE ###

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

pAC=[]
pWA=[]
for i in range(m):
  p,s=input().split()
  if p not in pAC:
    if s=='AC':
      pAC+=[p]
    else:
      pWA+=[p]

cnt=0
for i in pWA:
  if i in pAC:
    cnt+=1

print(len(set(pAC)),cnt)

### FIXED CODE ###

n,m=map(int,input().split())
ps=[list(map(int,input().replace('WA','0').replace('AC','1').split())) for i in range(m)]
ps.sort(key=lambda x:x[0])

tmp_p=0
ac_cnt=0
wa_cnt=0
wa=0
flg=0
for i in range(m):
  p=ps[i][0]
  s=ps[i][1]
  if tmp_p!=p:
    wa=0
    flg=0
  if s==1 and flg==0:
    flg=1
    ac_cnt+=1
    wa_cnt+=wa
  elif s==0 and flg==0:
    wa+=1
  tmp_p=p
print(ac_cnt, wa_cnt)
### BUGGY CODE ###

https://atcoder.jp/contests/apc001/tasks/apc001_c#import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    ng = 0
    ok = N
    print(ng, flush=True)
    ng_s = SS()
    ok_s = ng_s
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        print(m, flush=True)
        s = SS()
        if s == 'Vacant':
            break
        elif (ok - m) % 2 == 1 and ok_s != s or (ok - m) % 2 == 0 and ok_s == s:
            ok = m
            ok_s = s
        else:
            ng = m
            ng_s = s

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    ng = 0
    ok = N
    print(ng, flush=True)
    ng_s = SS()
    ok_s = ng_s
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        print(m, flush=True)
        s = SS()
        if s == 'Vacant':
            sys.exit()
        elif (ok - m) % 2 == 1 and ok_s != s or (ok - m) % 2 == 0 and ok_s == s:
            ok = m
            ok_s = s
        else:
            ng = m
            ng_s = s

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

a, b, x = map(int,input().split())

ans = 0
for i in range(a, b + 1):
    if (i % x) == 0:
        ans += 1
print(str(ans))


### FIXED CODE ###

a, b, x = map(int,input().split())

left = a // x
right = b // x
ans = right - left
if (a % x) == 0:
    ans += 1

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

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

pin={}

l=len(S)
for i in range(10):
  for j in range(10):
    for k in range(10):
     pin['{}{}{}'.format(i,j,k)]='{}{}{}'.format(i,j,k)

ans=0
for key in pin:
  s=pin[key]
  flag=0
  start=0
  for i in range(N) :
    if S[i]==s[0]:
      start=i+1
      flag+=1
      break
  for j in range(start,N):
    if S[j]==s[1]:
      start=j+1
      flag+=1
      break
  for k in range(start,N):
    if S[k]==s[2]:
      flag+=1
      break
  if flag==3:
    ans+=1

print(ans)

### FIXED CODE ###

N=int(input())
S=input()
S=list(map(int,S))
ans=0
for s in range(1000):
      A=s//100
      B=(s-A*100)//10
      C=s-A*100-B*10
      isOne=0
      isTen=0
      isHundred=0
      for i in range(N) :
        if isOne==0:
          if S[i]==A: 
            isOne=1
        elif isTen==0:
          if S[i]==B: 
            isTen=1
        elif isHundred==0:
          if S[i]==C:
            isHundred=1
            ans+=1
        else:
          break

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

N, Q = map(int, input().split())
in_str = input()
AC_count = []
r = []
for i in range(Q):
    in1, in2 = map(int, input().split())
    AC_count.append(in_str.count("AC", in1-1, in2))

for i in range(Q):
    print(AC_count[i])

### FIXED CODE ###

N, Q = map(int, input().split())
in_str = input()
AC_count = []
r = [0]*(N+1)
for i in range(N):
    r[i+1] = r[i] + (1 if in_str[i:i+2] == "AC" else 0) 
    
    
for i in range(Q):
    in1, in2 = map(int, input().split())
    print(r[in2-1]-r[in1-1])
### BUGGY CODE ###

n = int(input())
lis = list(map(int,input().split()))
le = 0
ri = sum(lis)
ans = sum(lis)
cou = 0
for i in range(1,101):
  while lis[cou] == i:
    ri += lis[cou]
    le -= lis[cou]
  ans = min(ans,abs(le-ri))
print(ans)

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
ans = 10 ** 9
le = 0
ri = sum(lis)
ans = sum(lis)
for num in lis:
  le += num
  ri -= num
  ans = min(ans,abs(ri-le))
print(ans)
### BUGGY CODE ###

# coding:utf-8

def lucas(num):
    if num == 0:
        return 2
    elif num == 1:
        return 1
    else:
        return lucas(num - 1) + lucas(num - 2)


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


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding:utf-8
from functools import lru_cache


@lru_cache(maxsize=None)
def lucas(num):
    if num == 0:
        return 2
    elif num == 1:
        return 1
    else:
        return lucas(num - 1) + lucas(num - 2)


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


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

from math import factorial
import collections


combs = {}
results = {}


def get_combination(n):
    if n < 2:
        return 0
    if combs.get(n):
        return combs.get(n)
    else:
        combs[n] = factorial(n) // (factorial(n - 2) * factorial(2))
        return combs[n]


n = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
for a in A:
    s = 0
    if results.get(a):
        print(results[a])
    else:
        for k, v in c.items():
            if k == a:
                v -= 1
            s += get_combination(v)
        results[a] = s
        print(s)


### FIXED CODE ###

import collections
from functools import lru_cache
from scipy.misc import comb


results = {}


@lru_cache(maxsize=None)
def get_combination(n):
    if n < 2:
        return 0
    else:
        return comb(n, 2, exact=True)


n = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
S = 0
for k, v in c.items():
    S += get_combination(v)
for a in A:
    if results.get(a):
        print(results[a])
    else:
        results[a] = S - get_combination(c[a]) + get_combination(c[a] - 1)
        print(results[a])