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

# C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

# 比がa:bとなる合計最小の票分布はa,b
# 次にc:dになったとき、a<=cかつb<=dを満たすまでc,dを2倍、3倍、と増やしていく

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

a, b = TA[0]
ans = a + b

for idx in range(1,N):
    c, d = TA[idx]
    ori_c, ori_d = c, d
    while c < a or d < b:
        c += ori_c
        d += ori_d
    ans = c+d
    a,b = c,d
    
print(ans)

### FIXED CODE ###

# C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

# 比がa:bとなる合計最小の票分布はa,b
# 次にc:dになったとき、a<=cかつb<=dとなるようにc,dに同じ数をかける

import math

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

a, b = TA[0]
c, d = a, b

for idx in range(1,N):
    c, d = TA[idx]
    multi = max((a+c-1)//c, (b+d-1)//d)
    c *= multi
    d *= multi
    a,b = c,d
    
print(c+d)
### BUGGY CODE ###

import numpy as np
n,w,*wv=map(int,open(0).read().split())
wei=wv[0::2]
val=wv[1::2]
sack=np.array([[0 for i in range(w+1)] for j in range(2)])
for i in range(n):
  t=i&1
  np.maximum(sack[t-1][:-wei[i]]+val[i],sack[t-1][wei[i]:],out=sack[t][wei[i]:])
  sack[t][:wei[i]]=sack[t-1][:wei[i]]
print(sack[(n-1)&1][-1])

### FIXED CODE ###

import numpy as np
n,w,*wv=map(int,open(0).read().split())
wei=wv[0::2]
val=wv[1::2]
sack=np.array([float('inf') for i in range(sum(val)+1)])
sack[0]=0
for i in range(n):
  sack[val[i]:]=np.minimum(sack[val[i]:],sack[:-val[i]]+wei[i])
print(np.where(sack<=w)[0][-1])
### BUGGY CODE ###

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

count = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      pas = (str(i),str(j),str(k))
      key = 0
      for c in S:
        if c == pas[key]:
          key += 1
          if key ==3:
            count +=1
            break
print(count)

### FIXED CODE ###

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

count = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      pas = (str(i),str(j),str(k))
      key = 0
      for c in S:
        if c == pas[key]:
          key += 1
          if key ==3:
            count +=1
            break
print(count)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = A[0]
INF = 1000000000000000000
for i in range(1,n):
    ans = ans * A[i]
    if ans > INF:
        ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = A[0]
INF = 1000000000000000000
for i in range(1,n):
    l,r = len(str(ans)),len(str(A[i]))
    if l+r > 21:
        ans = -1
        break
    else:
        ans = ans * A[i]
        if ans > INF:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split(" "))
stores = []
for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    stock = 0
    last_idx = -1
    tg_idx = -1
    for idx, s in enumerate(stores):
        if s[0] > Ai and tg_idx == -1:
          stock += Bi
          tg_idx = idx
        if stock < M:
            stock += s[1]
        else:
            last_idx = idx
            break
    if tg_idx != -1:
        stores.insert(tg_idx, (Ai, Bi))
    else:
        stores.append((Ai, Bi))
    if last_idx != -1:
        stores = stores[:last_idx+1]

price = 0
for store in stores:
    if M <= store[1]:
        price += store[0] * M
        break
    else:
        price += store[0] * store[1]
        M -= store[1]
print(price)


### FIXED CODE ###

N, M = map(int, input().split(" "))
stores = []

for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    stores.append((Ai, Bi))    

price = 0
for a, b in sorted(stores, key=lambda x: x[0]):
    if M <= b:
        price += a * M
        break
    else:
        price += a * b
        M -= b
print(price)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0

for r in range(3000 + 1):
    if R * r <= N:
        for g in range(3000 + 1):
            v = R * r + G * g
            if N >= v and (N - v) % B == 0:
                ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0

for r in range(min(3000, 3000 // R) + 1):
    if R * r <= N:
        for g in range(min(3000, 3000 // G) + 1):
            v = R * r + G * g
            if N >= v and (N - v) % B == 0:
                ans += 1

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

s = input()
de_num = 0
le_num = 0
ans = [0]*(len(s)+1)

for i in range(len(s)+1):
    mae = 0
    ato = 0
    j = i
    k = i
    while j > 0 and s[j-1] == "<":
        mae += 1
        j -= 1
    while k < len(s) and s[k] == ">":
        ato += 1
        k += 1
    ans[i] = max(mae,ato)

print(sum(ans))

### FIXED CODE ###

s = input()
de_num = 0
le_num = 0
ans = [0]*(len(s)+1)

for i in range(len(s)):
    if s[i] == "<":
        de_num += 1
    else:
        de_num = 0
    ans[i+1] = de_num

s = s[::-1]
ans.reverse()

for i in range(len(s)):
    if s[i] == ">":
        le_num += 1
    else:
        le_num = 0
    ans[i+1] = max(le_num,ans[i+1])

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

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    ユークリッドの互除法より
    aの逆元 ax = 1 (mod N)を満たすxを返す。
    O(log a)
    """

    def extgcd(a, b):
        """
        Extended Great Common Divisor
        ax + by = gcd(a, b) = dを満たすx, y, dを返す。
        """
        d = fractions.gcd(a, b)
        if b == 0:
            return 1, 0, a
        else:
            q, r = divmod(a, b)
            x, y, d = extgcd(b, r)
            s, t = y, x - q * y
            return s, t, d

    return extgcd(a, N)[0]


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log2(y) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)


### FIXED CODE ###

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    ユークリッドの互除法より
    aの逆元 ax = 1 (mod N)を満たすxを返す。
    O(log a)
    """

    def extgcd(a, b):
        """
        Extended Great Common Divisor
        ax + by = gcd(a, b) = dを満たすx, y, dを返す。
        """
        d = fractions.gcd(a, b)
        if b == 0:
            return 1, 0, a
        else:
            q, r = divmod(a, b)
            x, y, d = extgcd(b, r)
            s, t = y, x - q * y
            return s, t, d

    return extgcd(a, N)[0]


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

def combination(n, m):
    m = min(m, n-m)
    c = 1
    for i in range(m):
        c *= (n-i) * pow(m-i, MOD-2, MOD) % MOD
    return c % MOD

pattern = combination(N*M-2, K-2) % MOD

def diff_x_pattern(val):
    # for d in range(1, val):
    #     ret += (val - d) * d
    return (val * (val - 1) * val // 2 - (val - 1) * (2 * val - 1) * val // 6) % MOD

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7

def combination(n, m):
    c = 1
    m = min(n-m, m)
    for i in range(m):
        c = c * (n-i) * pow(m-i, MOD-2, MOD) % MOD
    return c

pattern = combination(N*M-2, K-2)

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)
### BUGGY CODE ###

import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p][0]
        if tmp == x: return True
        if x < tmp:
            p = tree[p][1]
        else:
            p = tree[p][2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p][0]
    if x== tmp: return p
    elif x<tmp:
        tree[p][1]=insert(tree[p][1],x)
    else:
        tree[p][2]=insert(tree[p][2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(home,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

### FIXED CODE ###

import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p]
        if tmp[0] == x: return True
        if x < tmp[0]:
            p = tmp[1]
        else:
            p = tmp[2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p]
    if x== tmp[0]: return p
    elif x<tmp[0]:
        tree[p][1]=insert(tmp[1],x)
    else:
        tree[p][2]=insert(tmp[2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1
### BUGGY CODE ###

n, q = map(int, raw_input().split())
s = str(raw_input())
ans = []
arr = []
for i in range(n-1):
	if s[i:i+2] == 'AC':
		arr.append(1)
	else:
		arr.append(0)
for i in range(q):
	l, r = map(int, raw_input().split())
	print sum(arr[l-1:r-1])

### FIXED CODE ###

n, q = map(int, raw_input().split())
s = str(raw_input())
t = [0] * (n + 1)
for i in range(n):
	t[i + 1] = t[i] + (1 if s[i : i + 2] == 'AC' else 0)
for i in range(q):
	l, r = map(int, raw_input().split())
	print t[r-1] - t[l-1]
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side="right") - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1] + dp[d - 1][np.arange(N) + dp[d - 1]]

# print(dp)

dp = dp.T


def solve(l, r):
    ret = 0
    d = len(dp[0]) - 1
    while l + 1 < r:
        while d > 0 and dp[l, d] >= r - l:
            d -= 1
        ret += 2 ** d
        l += dp[l, d]
    if l < r:
        ret += 1
    return ret


ans = []
for a, b in AB:
    ans.append(solve(min(a, b), max(a, b)))
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side="right") - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1][dp[d - 1]]
dp = dp.tolist()


def solve(l, r):
    ret = 0
    d = len(dp) - 1
    while l + 1 < r:
        while d > 0 and dp[d][l] >= r:
            d -= 1
        ret += 1 << d
        l = dp[d][l]
    if l < r:
        ret += 1
    return ret


ans = []
for a, b in AB:
    ans.append(solve(min(a, b), max(a, b)))
print(*ans, sep='\n')
### BUGGY CODE ###

from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]
dict={".":10000000,"#":-1}
s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]

s[c[0]-1][c[1]-1]=0
que=deque([[c[0]-1,c[1]-1]])
temp=[(1,0),(0,1),(-1,0),(0,-1),(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)]
while que:
    y,x=que.popleft()
    for i,j in temp:
        if 0<=y+i<h and 0<=x+j<w and s[y+i][x+j]>=0:
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if i*i+j*j==1 and dist>s[y][x]:
                s[nexty][nextx]=s[y][x]
                que.append([nexty,nextx])
            elif dist>s[y][x]+1:
                s[nexty][nextx]=s[y][x]+1
                que.append([nexty,nextx])

if s[d[0]-1][d[1]-1]==10000000:
    print(-1)
else:
    print(s[d[0]-1][d[1]-1])


### FIXED CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()
### BUGGY CODE ###

import sys
 
N, Q = map(int, input().split())
 
S = input()
 
lr = [list(map(int, i.split())) for i in sys.stdin]
  
for q in lr:
  st = q[0]-1
  en = q[1]
  left = st
  right = st
  s = S[st:en]
  ans = 0
  while right < en+1:
    dif = right - left
    if dif == 2:
      if S[left:right] == 'AC':
        ans += 1
      left += 1
    elif dif == 1:
      right += 1
    elif dif == 0:
      right += 1
      
  print(ans)

### FIXED CODE ###

import sys
 
N, Q = map(int, input().split())
 
S = input()
 
lr = [list(map(int, i.split())) for i in sys.stdin]

Sum = [0]

sum_ = 0

for i in range(len(S)-1):
  if S[i] == 'A' and S[i+1] == 'C':
    sum_ += 1
  Sum.append(sum_)

for  q in range(Q):
  ans = Sum[lr[q][1]-1]-Sum[lr[q][0]-1]
  print(ans)
### BUGGY CODE ###

from itertools import product
def cnt(b,e,n_str):
  res=0
  for i in range(int(n_str)+1):
    if int(str(i)[0])==b and i%10==e:
      res+=1
  return res
def sol():
  n_str=input()
  c={i:{j:cnt(i,j,n_str) for j in range(1,10)} for i in range(1,10)}
  return sum(c[b][e]*c[e][b] 
             for b,e in product(range(1,10),repeat=2))

print(sol())  




### FIXED CODE ###

from itertools import product
from functools import reduce
import operator
def prod(iterable):
    return reduce(operator.mul, iterable, 1)
def cnt_samelen(b,e,n_str):
  n0=int(n_str[0])
  if b>n0 or len(n_str)==1:
    return 0
  if b<n0:
    return b*int(10**(len(n_str)-2))
  
  return (int(n_str[1:-1])+1 if len(n_str)>2 else 1)-(1 if e>int(n_str[-1]) else 0)
def cnt(b,e,n_str):
  res=0
  l=len(n_str)
  if b==e and int(n_str)>=b:
    res+=1
  for i in range(l-2):
    res+=10**(i)
  res+=cnt_samelen(b,e,n_str)
  return res
def sol():
  n_str=input()
  return sum(cnt(b,e,n_str)*cnt(e,b,n_str) 
             for b,e in product(range(1,10),repeat=2))

print(sol())
### BUGGY CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())

grid = [[v for v in input()[:-1]] for _ in range(H)]
dist = [[float('inf')]*W for _ in range(H)]

Q = []
cnt = 0
for row in range(H):
    for col in range(W):
        if grid[row][col] == "#":
            dist[row][col] = 0
            Q.append([row, col])
            cnt += 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
current_dist = 0
while cnt < H*W and Q:
    current_dist += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(dx, dy):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if dist[new_x][new_y] == float('inf'):
                    dist[new_x][new_y] = current_dist
                    tmp.append([new_x, new_y])
                    cnt += 1
    Q = tmp
print(current_dist)


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0
# for _ in range(5):
while cnt < H*W:
    d += 1
    tmp = []
    #print("d->", d)
    # print(Q)
    # print(dist)
    # print(cnt)
    # print("-------")
    for x, y in Q:
        for dx, dy in zip(DX, DY):
            nx = x+dx
            ny = y+dy
            if 0 <= nx < H and 0 <= ny < W:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = "#"
                    tmp.append([nx, ny])
                    cnt += 1
            else:
                continue
    Q = tmp
# print(dist)
print(d)
### BUGGY CODE ###

(n,m) = map(int,input().split())
a,A = [0]*m,[0]*m
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
b = [-1]*n
me = [1]*n
d = [0]*n
w = [0]*m
s = (n*(n-1))//2
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

### FIXED CODE ###

#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])
### BUGGY CODE ###

A,B = map(int,input().split())
for K in range(1,max(A,B)+1):
  if abs(A-K) == abs(B-K):
    print(K)
    exit()
print('IMPOSSIBLE')


### FIXED CODE ###

A,B = map(int,input().split())
if ((A+B)/2)-((A+B)//2)==0:
  print(((A+B)//2))
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
lim = max(a)
amount = [0]*lim
for i in range(lim):
    amount[i] = a.count(i+1)
    ans += amount[i]*(amount[i]-1)//2
for j in range(n):
    ansout = ans
    ansout -= amount[a[j]-1] -1
    print(ansout)

### FIXED CODE ###

import numpy as np
def main():
    from collections import Counter
    n = int(input())
    a = tuple(map(int, input().split()))
    ans = 0
    c = Counter(a)
    for i in range(n):
        ans += c[i+1]*(c[i+1]-1)//2
    for j in range(n):
        print(ans - c[a[j]] + 1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        i = 2
        while i*i <= x:
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
            i += 1
        if x != 1:
            res.append((x, 1))
        return res

    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import math 
def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        for i in range(2, int(math.sqrt(x))+1):
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
        if x != 1:
            res.append((x, 1))
        return res

    g = gcd(A, B)
    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()