Harryxun/stf_run huggingface dataset:
"""
KがAの最大公約数の倍数であれば実現可能。そうでなければ実現不可能。
"""
import sys
sys.setrecursionlimit(200000)
N,K = map(int,input().split())
A = list(map(int,input().split()))

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

g = gcd(A[0],A[1])
for i in range(2,N):
    g = gcd(g,A[2])

if K<=max(A) and K%g == 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)
N,K = map(int,input().split())
A = list(map(int,input().split()))
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
if N ==1:
    g = A[0]
else:
    g = gcd(A[0],A[1])
    if N > 2:
        for i in range(2,N):
            g = gcd(g,A[i])
if K <= max(A) and K%g==0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
h,w= (int(i) for i in input().split())
c = [int(input()) for i in range(h)]

for x in c:
    print(x)
    print(x)

### FIXED CODE ###

h,w= (int(i) for i in input().split())
c = [input() for i in range(h)]

for x in c:
    print(x)
    print(x)
a, b, c, d = map(int, input().split())
if (a + b) / 2 == a:
  print('Bad')
elif (b + c) / 2 == b:
  print('Bad')
elif (c + d) / 2 == c:
  print('Bad')
else:
  print('Good')


### FIXED CODE ###

a, b, c, d = map(int, list(input()))
if (a + b) / 2 == a:
  print('Bad')
elif (b + c) / 2 == b:
  print('Bad')
elif (c + d) / 2 == c:
  print('Bad')
else:
  print('Good')
S = list(input("Enter :"))
ans = 0
C_location = 0
for i in range(2,len(S)-1):
  if S[i] == "C":
    ans += 1
	S[i].lower()
if all(S[0]=="A" and ans==1):
  S.swapcase(S[0])
  if S.islower():
	print("AC")
  else:
    print("WA")
else:
  print("WA")

### FIXED CODE ###

S = list(input())
ans = 0
for i in range(2,len(S)-1):
  if S[i] == "C":
    ans += 1
    S[i] = S[i].lower()
if S[0]=="A" and ans==1:
  S[0] = S[0].lower()
  s = ""
  for i in range(len(S)):
    s += S[i]
  if s.islower():
    print("AC")
  else:
    print("WA")
else:
  print("WA")
n = int(input())
h = list(map(int,input().split()))

dp = [float("inf")] * n #dpテーブル
#dp[i]メモ化テーブル
#まずは使わない

def rec(i):#再帰による全探索
    if i == 0:
        return 0
    elif i == 1:
        return abs(h[0]-h[1])
    else:
        return min(rec(i-1)+abs(h[i]-h[i-1]),rec(i-2)+abs(h[i]-h[i-2]))

print(rec(n-1))


### FIXED CODE ###

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

dp = [float("inf")] * n #dpテーブル
#dp[i]:=i番目の足場まで来るのに必要な最小コスト

#初期条件
dp[0]=0
dp[1]=abs(h[1]-h[0])

for i in range(2,n):
    dp[i] = min(dp[i-1] + abs(h[i-1]-h[i]) ,dp[i-2] + abs(h[i-2]-h[i]))

print(dp[n-1])
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n,a,b,c,d = LI_()
    n += 1
    s = S()
    if d < c:
        f = 0
        for i in range(max(0,b-1), min(min(n-1,d+1)), c-1):
            if s[i:i+3] == '...':
                f = 1
                break
        if f == 0:
            return 'No'

    for i in range(a+1,c-1):
        if s[i:i+2] == '##':
            return 'No'
    for i in range(b+1,d-1):
        if s[i:i+2] == '##':
            return 'No'


    return 'Yes'


print(main())



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n,a,b,c,d = LI_()
    n += 1
    s = S()
    if d < c:
        f = 0
        for i in range(max(0,b-1), min(min(n-1,d), c-1)):
            if s[i:i+3] == '...':
                f = 1
                break
        if f == 0:
            return 'No'

    for i in range(a+1,c-1):
        if s[i:i+2] == '##':
            return 'No'
    for i in range(b+1,d-1):
        if s[i:i+2] == '##':
            return 'No'


    return 'Yes'


print(main())
memo = {}
def solve(S):
    if len(S)<1:
        return 0
    crs = 0
    if S in memo:
        return memo[S]
    while crs + 1 < len(S):
        if S[crs] != S[crs+1]:
            memo[S] = solve(S[:crs]+S[crs+2:])+2
            return memo[S]
        crs += 1
    return 0
S = input()
print(solve(S))

### FIXED CODE ###

def solve(S):
    return min(S.count("0"),S.count("1"))*2
  
S = input()
print(solve(S))
#include <iostream>

using namespace std;

int main(){
    int i,j,N;
    int a[N+1],b[N+1];
    cin >> N;

    for(i=1;i<=N;i++){
        cin >> a[i];
        b[i]=0;
    }

    int M = 0;
    int k = 0;
    for(i=N;i>0;i--){
        int val = 0;
        for(j=2;i*j<=N;j++){
            val+=b[i*j];
        }
        if(val%2!=a[i]){
            b[i]=1;
            M++;
            k=max(k,i);
        }            
    }
    cout << M << endl;
    for(i=1;i<=N;i++){
        if(b[i]==1){
            cout<<i<<" ";
        }
    }
    if(M!=0)
        cout<<endl;
}


### FIXED CODE ###

N = int(input())
a = [0]+list(map(int,input().split()))

b = [0 for i in range(N+1)]
M = 0

for i in range(N):
    ind = N-i
    val = 0
    j=2
    while ind*j<=N:
        val += b[ind*j]
        j+=1
    if val%2 != a[ind]:
        M+=1
        b[ind]=1
print(M)
if M!=0:
    for i in range(1,N+1):
        if b[i]==1:
            if M!=1:
                print(i,end=' ')
            else:
                print(i)
D, N = list(map(int, input().split()))
if N==100 and D==0
    print(101)
else:
    print(N*100**D)


### FIXED CODE ###

D, N = list(map(int, input().split()))
if N==100:# and D==0:
    print((N+1)*100**D)
else:
    print(N*100**D)
N = int(input())
B = list(map(int,input().split()))

A = [0,0,0,0,0,0]
A[N-1] = B[N-1-1]
for i in range(1,N):
    A[N-1-i] = min(B[N-1-i],B[N-1-i-1])
print(sum(A))

### FIXED CODE ###

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

A = [0]*N
A[0] = B[0]
A[N-1] = B[N-1-1]
for i in range(1,N-1):
    A[N-1-i] = min(B[N-1-i],B[N-1-i-1])
print(sum(A))
N_baito,M_days = map(int,input().split())
baitoList = np.array([list(map(int,input().split())) for i in range(N_baito)])
workList = []
hosyu = 0
for day in range(M_days+1):
    workList.extend(baitoList[baitoList[:,0]==day][:,1].tolist())
    workList.sort(reverse=True)
    if workList:
        hosyu += workList[0]
        del workList[0]
print(hosyu)


### FIXED CODE ###

import heapq
N_baito,M_days = map(int,input().split())
hosyuList = [[] for _ in range(M_days)]

for _ in range(N_baito):
    days,hosyu = map(int,input().split())
    if days <= M_days:
        hosyuList[days-1].append(hosyu)

workList = []
hosyu = 0
for day in range(M_days):
    for baito in hosyuList[day]:
        heapq.heappush(workList,-1*baito)
    if workList:
        hosyu += heapq.heappop(workList)
print(-1*hosyu)
# coding: utf-8
# Here your code !

def func():
    data=[]
    while(True):
        try:
            line=[ int(item) for item in input().rstrip().split(" ") ]
            if(line == [0,0]):
                break
            data.append(line)
        except EOFError:
            break
        except:
            return inputError()
    
    left=1
    numbers=3
    [print(len(sumcombination(left,line[0],numbers,line[1]))) for line in data]

def sumcombination(left,right,numbers,total):
    result=[]
    if(numbers==1):
        if( (left <= total) and (right >= total) ):
            result=[total]
        return(result)
    
    for i in range(left,right+1):
        if( numbers == 2):
            if(i >= total-i):
                break
            elif( (i != total-i) and (left <= total-i) and (right >= total-i) ):
                result.append([i,total-i])
        elif( ( len( range(i,right+1) ) < numbers ) or ( sum( range(i+1,i+numbers) ) > total-i ) ):
            break
        elif( sum( range(right-numbers+2,right+1) ) < total-i ):
            continue
        else:
            sub = sumcombination(i+1,right,numbers-1,total-i)
            if(len(sub)>0):
                [items.insert(0,i) for items in sub]
                result.extend(sub)

    return(result)

def inputError():
    print("input error")
    return -1

func()

### FIXED CODE ###

# coding: utf-8
# Here your code !

def func():
    data=[]
    while(True):
        try:
            line=[ int(item) for item in input().rstrip().split(" ") ]
            if(line == [0,0]):
                break
            data.append(line)
        except EOFError:
            break
        except:
            return inputError()
    
    left=1
    numbers=3
    [print(len(sumcombination(left,line[0],numbers,line[1]))) for line in data]

def sumcombination(left,right,numbers,total):
    '''
    left ~ right??????????????°??????(numbers)????????´??°???????¨????total?????????????????????????????????????????????
    '''
    result=[]
    if(numbers==1):
        if( (left <= total) and (right >= total) ):
            result=[total]
        return(result)
    
    for i in range(left,right+1):
        if( numbers == 2):
            if(i >= total-i):
                break
            elif( (i != total-i) and (left <= total-i) and (right >= total-i) ):
                result.append([i,total-i])
        elif( ( len( range(i,right+1) ) < numbers ) or ( sum( range(i+1,i+numbers) ) > total-i ) ):
            break
        elif( sum( range(right-numbers+2,right+1) ) < total-i ):
            continue
        else:
            sub = sumcombination(i+1,right,numbers-1,total-i)
            if(len(sub)>0):
                [items.insert(0,i) for items in sub]
                result.extend(sub)

    return(result)

def inputError():
    print("input error")
    return -1

func()
n, k, q = map(int, input().split())
point = [k - q] * n

for i in range(q):
    answer = int(input())
    point[answer - 1} += 1

for j in point:
    if p <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n, k, q = map(int, input().split())
point = [k - q] * n

for i in range(q):
    answer = int(input())
    point[answer - 1] += 1

for j in point:
    if j <= 0:
        print('No')
    else:
        print('Yes')
A, B = map(long, raw_input().split())
ans = 0
msb = B >> (B.bit_length()-1) << (B.bit_length() - 1)
if msb + A > B:
    begin = B
    end = A
else:
    begin = B
    end = msb + A
for i in range(begin, end - 1, -1):
    ans ^= i
if (B - A) % 2 == 1:
    ans += msb
print(ans)


### FIXED CODE ###

A, B = map(int, input().split())
ans = 0
cnt = 0
def f(arg):
    ans = 0
    if arg < 0:
        return 0
    for pos in range(1, 41):
        # ループする数
        loop = 1 << pos
        # cnt = sum([int((n & v) / v) for n in range(arg+1)])
        cnt = int((arg + 1) / loop) * (loop >> 1)
        cnt += max(0, (arg + 1) % (loop) - (loop >> 1))
        ans += cnt%2 * (loop>>1)
        # print(arg, pos, loop, cnt, ans)
        if loop > arg:
            break
    return ans
print(f(A-1)^f(B))
a, b = list(map(int, input().split()))

if a * b // 2 == 1:
  return "Odd"
else:
  return "Even"


### FIXED CODE ###

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

if (a % 2 == 1) & (b % 2 == 1):
    print("Odd")
else:
    print("Even")
b=input()
if b=='A':
    print('T')
elif b=='T'
    print('A')
elif b=='C'
    print('G')
else:
    print('C')

### FIXED CODE ###

b=input()
if b=='A':
    print('T')
elif b=='T':
    print('A')
elif b=='C':
    print('G')
else:
    print('C')
# coding: utf-8
# Your code here!
l=input()
if(l=="Sunny"):
    ans="Cloudy"
if(l=="Cloudy"):
    ans="Rainny"
if(l=="Rainny"):
    ans="Sunny"
print(ans)


### FIXED CODE ###

# coding: utf-8
# Your code here!
l=input()
if(l=="Sunny"):
    ans="Cloudy"
if(l=="Cloudy"):
    ans="Rainy"
if(l=="Rainy"):
    ans="Sunny"
print(ans)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
正則二部グラフの辺彩色
"""

import numpy as np

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

edge = []
for i,row in enumerate(grid):
    for j,x in enumerate(row):
        edge.append(((x-1)//M,N+i))

graph = [dict() for _ in range(N+N)] # 頂点ごろに、色->相手
rest_color = [set(range(M)) for _ in range(N+N)]

for u,v in edge:
    c = rest_color[u].pop()
    if c in rest_color[v]:
        graph[u][c] = v
        graph[v][c] = u
        rest_color[v].remove(c)
        continue
    # 交互道を作って色c,dと当てていく
    d = rest_color[v].pop()
    cd = c + d
    V = [u,v]
    next_c = c
    while next_c not in rest_color[v]:
        v = graph[v][next_c]
        V.append(v)
        next_c = cd - next_c
    rest_color[v].remove(next_c)
    rest_color[v].add(cd - next_c)
    for i,(u,v) in enumerate(zip(V,V[1:])):
        if i%2 == 0:
            graph[u][c] = v
            graph[v][c] = u
        else:
            graph[u][d] = v
            graph[v][d] = u

after = [[None] * M for _ in range(N)]

for i,row in enumerate(grid):
    mod_to_x = [[] for _ in range(N)]
    for x in row:
        mod_to_x[(x-1)//M].append(x)
    for color in range(M):
        after[i][color] = mod_to_x[graph[i][color] - N].pop()

B = np.array(after)
C = B.copy()
C.sort(axis = 0)
print('\n'.join(' '.join(row) for row in B.astype(str)))
print('\n'.join(' '.join(row) for row in C.astype(str)))



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
正則二部グラフの辺彩色
"""

import numpy as np

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

edge = []
for i,row in enumerate(grid):
    for j,x in enumerate(row):
        edge.append(((x-1)//M,N+i))

graph = [dict() for _ in range(N+N)] # 頂点ごろに、色->相手
rest_color = [set(range(M)) for _ in range(N+N)]

for u,v in edge:
    common = rest_color[u] & rest_color[v]
    if common:
        c = common.pop()
        graph[u][c] = v
        graph[v][c] = u
        rest_color[u].remove(c)
        rest_color[v].remove(c)
        continue
    # 交互道を作って色c,dと当てていく
    c = rest_color[u].pop()
    d = rest_color[v].pop()
    cd = c + d
    V = [u,v]
    next_c = c
    while next_c not in rest_color[v]:
        v = graph[v][next_c]
        V.append(v)
        next_c = cd - next_c
    rest_color[v].remove(next_c)
    rest_color[v].add(cd - next_c)
    for i,(u,v) in enumerate(zip(V,V[1:])):
        if i%2 == 0:
            graph[u][c] = v
            graph[v][c] = u
        else:
            graph[u][d] = v
            graph[v][d] = u

after = [[None] * M for _ in range(N)]

for i,row in enumerate(grid):
    mod_to_x = [[] for _ in range(N)]
    for x in row:
        mod_to_x[(x-1)//M].append(x)
    for color in range(M):
        after[i][color] = mod_to_x[graph[i+N][color]].pop()

B = np.array(after)
C = B.copy()
C.sort(axis = 0)
print('\n'.join(' '.join(row) for row in B.astype(str)))
print('\n'.join(' '.join(row) for row in C.astype(str)))
n = int(input())
li_a = list(map(int, input().split()))
sum_ = 0
li_a.sort()
for i in range(1, n):
  sum_ += li_a[n-1-(i)//2]
print(sum_)


### FIXED CODE ###

n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    elif i == 0:
        li.append((0, 0))
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    if k %2 ==1:
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[n-1-i][0]
            ans %= mod
        print(ans)
        exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] >= 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] <= 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if (not p1) and (not P1) and (not M1) and (not m1):
        if mini*Mini > plus*Plus:
            print(ans1)
        else:
            print(ans2)
    elif (not p1) and (not M1):
        print(ans2)
    elif (not m1) and (not P1):
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= li[i][0]
            ans %= mod
        ans *= -1
        ans %= mod
        print(ans)
package main

import (
	"fmt"
)

func main(){
	var a int
	for i:=1; i<10000; i++{
		fmt.Scan(&a)
		if a == 0{
			break
		}
		fmt.Printf("Case %d: %d", i, a)
	}
}


### FIXED CODE ###

import sys
a = sys.stdin.readlines()[:-1]
for i in range(len(a)):
    print('Case {}: {}'.format(i+1, a[i]), end='')
X = int(input())
Y = int(input())
flag =0
for crane in range(X + 1):
  if (Y - crane*2 - (X-crane)*4 ) == 0:
    print("Yes")
    flag =1
    break
if flag == 0:
    print("No")

### FIXED CODE ###

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()


X, Y = list(map(int, input().split()))
Turtle = (Y - 2*X ) / 2
Crane = X - Turtle
if Turtle >= 0 and Crane >= 0 and is_integer(Turtle) and is_integer(Crane):
    print("Yes")
else:
    print("No")
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, read().split())
    a = {int(read()) - 1 for _ in range(m)}
    mod = 10**9 + 7
    dp = [0] * n
    if 0 not in a:
        dp[0] = 1
    if 1 not in a:
        dp[1] = 1 + dp[0]
    for i in range(2, n):
        if i in a:
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input():
  return sys.stdin.readline().rstrip()
mod = 10**9 + 7
n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
notin = [1] * n
for i in a:
  notin[i] = 0
dp = [0] * n
dp[n - 1] = 1
if n > 1:
	dp[n - 2] = 1 + notin[n - 1]
for i in range(n - 3, -1, -1):
  dp[i] += dp[i + 1] * notin[i + 1] % mod
  dp[i] += dp[i + 2] * notin[i + 2] % mod
  dp[i] %= mod
print(dp[0])
import sys

args = sys.argv
a = args[1]
b = args[2]
c = args[3]
d = args[4]

aa = int(a)*int(c)
bb = int(a)*int(d)
cc = int(b)*int(c)
dd = int(b)*int(d)

li = [aa,bb,cc,dd]

print(max(li))

### FIXED CODE ###

a,b,c,d = input().split()

aa = int(a)*int(c)
bb = int(a)*int(d)
cc = int(b)*int(c)
dd = int(b)*int(d)

li = [aa,bb,cc,dd]

print(max(li))
def find(tab, a):
    if tab[0][a]==-1:
        return a
    tab[0][a] = find(tab, tab[0][a])
    return tab[0][a]

def union(tab, a, b):
    try:
        p1, p2 = find(tab, a), find(tab, b)
        if p1 != p2:
            tab[0][p1] = p2
            tab[1][p2] += tab[1][p1]
    except:
        pass

def size(tab, a):
    return tab[1][a]

N, M = [int(a) for a in input().split(" ")]
ABs = [[int(a) for a in input().split(" ")] for i in range(M)]
tab = [[-1]*N, [1]*N]
arr = []



for a, b in reversed(ABs):
    a, b = a-1, b-1
    pa, pb = find(tab, a), find(tab, b)
    na, nb = size(tab, pa), size(tab, pb)
    if pa!=pb:
        dn = ((na+nb)*(na+nb-1)//2)-(na*(na-1)//2)-(nb*(nb-1)//2)
        arr.append(dn)
        union(tab, a, b)
    else:
        arr.append(0)

acc = 0
for cp in reversed(arr):
    acc += cp
    print(acc)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def find(tab, a):
    if tab[0][a]==a:
        return a
    tab[0][a] = find(tab, tab[0][a])
    return tab[0][a]

def union(tab, a, b):
    p1, p2 = (find(tab, a), find(tab, b))
    if p1 != p2:
        tab[0][p1] = p2
        tab[1][p2] += tab[1][p1]

def size(tab, a):
    return tab[1][a]

N, M = [int(a) for a in input().split(" ")]
ABs = [[int(a) for a in input().split(" ")] for i in range(M)]
tab = [[i for i in range(N)], [1 for i in range(N)]]
arr = []

for a, b in reversed(ABs):
        a, b = (a-1, b-1)
        pa, pb = (find(tab, a), find(tab, b))
        na, nb = (size(tab, pa), size(tab, pb))
        if pa!=pb:
            dn = ((na+nb)*(na+nb-1)//2)-(na*(na-1)//2)-(nb*(nb-1)//2)
            arr.append(dn)
            union(tab, a, b)
        else:
            arr.append(0)

acc = 0
for cp in reversed(arr):
    acc += cp
    print(acc)
a, b, b, k = map(int, input().split())
p = min(a, k)
s = p
k -= p
 
q = min(b, k)
k -= q
s -= k

r = min(c, k)
k -= r
s -= k
print(s)

### FIXED CODE ###

a, b, c, k = map(int, input().split())
p = min(a, k)
s = p
k -= p
 
q = min(b, k)
k -= q
s -= k
 
r = min(c, k)
k -= r
s -= k
print(s)
for i in range(5):

### FIXED CODE ###

X=[int(input()) for i in range(5)]
Y=[]
for x in X:
  Y.append(-(-x//10)*10-x)
print(sum(X)+sum(Y)-(max(Y)))
import sys
from collections import Counter
from math import factorial
import numpy as np
def main():
    input = sys.stdin.readline
    N = int(input())
    S = ["".join(sorted(list(input()))).strip() for _ in range(N)]
    #print(S)
    c = Counter(S)
    mosc = c.most_common()
    
    ans = np.int64(0)
    for i in range(len(mosc)):
        elem = mosc[i]
        if elem[1] > 1:
          n = elem[1]
          r = 2
          ans += np.int64(np.int64(factorial(n)) / np.int64(factorial(r)) / np.int64(factorial(n - r)))
          #ans +=  scipy.special.comb(n, r, exact=True)
    print(ans)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import Counter
from math import factorial
import numpy as np
from scipy.misc import comb
def main():
    input = sys.stdin.readline
    N = int(input())
    S = ["".join(sorted(list(input()))).strip() for _ in range(N)]
    #print(S)
    c = Counter(S)
    mosc = c.most_common()
    
    ans = np.int64(0)
    for i in range(len(mosc)):
        elem = mosc[i]
        if elem[1] > 1:
          n = elem[1]
          r = 2
          #ans += np.int64(factorial(n) / factorial(r) / factorial(n - r))
          ans +=  comb(n, r, exact=True)
    print(ans)
 
if __name__ == '__main__':
    main()