Harryxun/stf_run huggingface dataset:
q = input()
   
def common()
   X = raw_input()
   Y = raw_input()
      
   for i in range(0. len(X)):
      s[i] = 0
      
   for i in range(1, len(X)):
      t = s + []
      for j in range(1, len(Y)):
         if s[i-1] == j[i-1]:
            s[j+1] = t[j] + 1
         elif [j+1] < s[j]:
            s[j+1] = t[j]
   
   return s[-1]
  
for k in range(0, q-1):
   common()

### FIXED CODE ###

def common():
   X = raw_input()
   Y = raw_input()
  
   s = [0 for i in range(len(Y)+1)]
 
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if X[j] == Y[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
  
   print s[-1]
 
q = input()
for l in range(0, q):
   common()
import sys
sys.setrecursionlimit(1000000)
n,m,k=map(int,input().split())
stock=[set() for i in range(n)]
ter=[0]*n
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    ans[a-1]-=1
    ans[b-1]-=1
def dfs(j,k):
    size[k]+=1
    for next_j in stock[j]:
        if ter[next_j]==0:
            ter[next_j]=k
            dfs(next_j,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)

for i in range(n):
    ans[i]+=size[ter[i]]-1
for i in range(k):
    c, d = map(int, input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])


### FIXED CODE ###

class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent=[i for i in range(n)]
        self.rank=[1]*n#木の高さ
        self.size=[1]*n#size[i]はiを根とするグループのサイズ

    def find(self,x):#ｘの根（親）を返す
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.find(self.parent[x])#経路圧縮
            return self.parent[x]

    def unite(self,x,y):#ｘ、ｙの集合の統合
        x=self.find(x)
        y=self.find(y)
        if x!=y:
            if self.rank[x]<self.rank[y]:#ランクの比較
                self.parent[x]=y
                self.size[y]+=self.size[x]
            else:
                self.parent[y]=x
                self.size[x]+=self.size[y]
                if self.rank[x]==self.rank[y]:
                    self.rank[x]+=1
    def group_size(self,x):#ｘが属する集合の大きさ
        return self.size[self.find(x)]
    def is_same(self,x,y):#ｘ、ｙが同じ集合に属するかを判定する
        return self.find(x)==self.find(y)

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

uf=UnionFind(n)
ans = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1,b-1)
    ans[a - 1] -= 1
    ans[b - 1] -= 1
for i in range(k):
    c, d = map(int, input().split())
    if uf.is_same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1

for i in range(n):
    ans[i]+=uf.group_size(i)-1
    print(ans[i])
n=int(intput())
if(n%9==0):
   print("YES')
else:
  print("NO")

### FIXED CODE ###

n = list(input())
a = 0
for i in n:
    a += int(i)
if(a % 9 == 0):
    print("Yes")
else:
    print("No")
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = [int(x) for x in input().split()]

a.sort()

if a[0] == 0:
    print(0)
else:
    m = 1
    i = 0
    while m < 10**18:
        m *= a[i]
        if m > 10**18:
            print(-1)
            sys.exit()
        i += 1
        if i == n:
            print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]
ans = 1
if 0 in a:
    print(0)
    sys.exit()
for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        sys.exit()
print(ans)
port sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
#![allow(non_snake_case)]

fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn read_vec() -> Vec<i32> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().unwrap())
        .collect()
}

fn main() {
    let N: usize = read_line().parse().unwrap();
    let H = read_vec();
    let mut prev = 0;
    for h in H {
        if prev < h {
            prev = h - 1;
        } else if prev > h {
            println!("No");
            return;
        }
    }
    println!("Yes");
}


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
H = list(map(int, input().split()))
prev = -1
for h in H:
    if prev > h:
        print('No')
        exit()
    if prev <= h - 1:
        prev = h - 1
    else:
        prev = h
print('Yes')
s = input()
ans = []

for i in range(len(s)):
  if s[i] != "B":
    ans.append(s[i])
  else:
    if len(s) == 0:
      continue
    elif len(s) > 0:
      ans.pop(-1)
      
print("".join(ans))

### FIXED CODE ###

s = input()
ans = []
for i in range(len(s)):
  if s[i] == "0":
    ans.append("0")
  elif s[i] == "1":
    ans.append("1")
  elif s[i] == "B":
    if len(ans) > 0:
      ans.pop(-1)

print("".join(ans))
N = int(input())
Tlist = [int(N) for N in input().split()]
M = int(input())
PXlist = [[int(i) for i in input().split()]for j in range(M)]
def time_sum():
    s = 0
    for i in range(0,N):
        s = s+Tlist[i]
    return s
def time_cal():
    empty = []
    for i in range(0,M):
        empty.append(time_sum() - Tlist[i] + PXlist[i][1])
    return empty
for i in time_cal():
    print(i)

### FIXED CODE ###

N = int(input())
Tlist = [int(N) for N in input().split()]
M = int(input())
PXlist = [[int(i) for i in input().split()]for j in range(M)]
def time_sum():
    s = 0
    for i in range(0,N):
        s = s+Tlist[i]
    return s
def time_cal():
    empty = []
    for i in range(0,M):
        empty.append(time_sum() - Tlist[PXlist[i][0]-1] + PXlist[i][1])
    return empty
for i in time_cal():
    print(i)
N=int(input())
A=list(map(int,input().split()))
Sum =0
for i in range(len(A)):
  Sum += (A[0]-A[i])**2
Answer = Sum
for j in range(len(A)):
  Sum =0
  for k in range(-100,101):
    Sum+= (A[k]-j)**2
  Answer =min(Answer, Sum)
print(Answer)
  


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Sum =0
for i in range(len(A)):
  Sum += (A[0]-A[i])**2
Answer = Sum
for j in range(-100,101):
  Sum =0
  for k in range(len(A)):
    Sum+= (A[k]-j)**2
  Answer =min(Answer, Sum)
print(Answer)
-*- coding: utf-8 -*-
  
n = input()

if n%2 == 0:
  print(n/2)
else:
  print((n+1)/2)

### FIXED CODE ###

n = int(input())

if n%2:
  print((n+1)//2)
else:
  print(n//2)
A=int(input())
B=int(input())
if(A>0 & B%A==0):
  print(B+A)
else:
  print(B-A)
  

### FIXED CODE ###

A,B=map(int,input().split())
if(A>0 and B%A==0):
  print(B+A)
else:
  print(B-A)
N, M = map(int, input().split())
k = []
s = []
for _ in range(M):
    std_in = list(map(int, input().split()))
    k.append(std_in[0])
    for i in range(std_in[0]):
        std_in[i+1] -= 1
    s.append(std_in[1:])
p = [int(i) for i in input().split()]

switches = [0] * N

def judge_bulbs(switches):
    for i in range(M):

        k_sum = 0
        for ki in range(k[i]):
            k_sum += switches[ki]

        if k_sum % 2 == p[i]:
            continue
        else:
            return False
    return True

def solve(idx, switches):
    if idx == N:
        if judge_bulbs(switches):
            return 1
        else:
            return 0

    ans = 0
    switches = switches.copy()
    
    ans += solve(idx+1, switches)

    switches[idx] = 1
    ans += solve(idx+1, switches)
    return ans

print(solve(0, switches))





### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
s = [LIST()[1:] for _ in range(M)]
p = LIST()

ans = 0
for x in product([0, 1], repeat=N):
    for i in range(M):
    	cnt = 0
    	for n in s[i]:
    		if x[n-1] == 1:
    			cnt += 1
    	if cnt%2 != p[i]:
    		break
    else:
    	ans += 1
print(ans)
A, B = input().split()
A = int(A)
fb = float(B)
B100 = int(fb * 100)
ans = A * B100
print(int(ans/100))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
A.sort(reverse=True)
t = A.pop()
if t == 0:
    print(0)
    exit(0)

A.append(t)

for i in range(N):
    n = A[i]
    if ans * n > 10 ** 18:
        print(-1)
        exit(0)
    else:
        ans *= n
print(ans)
a, b, k = map(int, input().split())

ans = 0

if (a < b):
    list = [i for i in range(b) if a % i == 0 && b % i == 0 && i != 0]
    ans = list[k-1]
else:
    list = [i for i in range(a) if a % i == 0 && b % i == 0 && i != 0]
    ans = list[k-1]

print(ans)

### FIXED CODE ###

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

ans = 0

lista = list(range(a+1))
aa = lista.pop(0)

listb = list(range(b+1))
bb = listb.pop(0)

if (a < b):
    li = [i for i in lista if a % i == 0 and b % i == 0]
    li = sorted(li, reverse=True)
    ans = li[k-1]
else:
    li = [i for i in listb if a % i == 0 and b % i == 0]
    li = sorted(li, reverse=True)
    ans = li[k-1]

print(ans)
s = input()

char_number = len(s)

start = s[0]
end   = s[-0]

answer = start + char_number + end
print(answer)

### FIXED CODE ###

s = input()

char_number = len(s)

start = s[0]
end   = s[-1]

answer = start + str(char_number - 2) + end
print(answer)
a = int(input())
b = int(input())
c = int(input())
cond = int(input())

count = 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
		res = 500 * i + 100 * j + 50 * k
        if(res == cond):
          count = count + 1
print(count)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
cond = int(input())

count = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            res = 500 * i + 100 * j + 50 * k
            if(res == cond):
                count = count + 1
print(count)
N, K = map(int, input().split())
S = list(input())
s_l = S[K].lower()
S[K] = s_l
print("".join(S))

### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
s_l = S[K-1].lower()
S[K-1] = s_l
print("".join(S))
import math
n, x, *a = list(map(int, open(0).read().split()))
a.append(x)
a = sorted(a)
ans = a[1] - a[0]
for i in range(1, n - 1):
    ans = math.gcd(ans, abs(a[i + 1] - a[i]))
print(ans)


### FIXED CODE ###

from fractions import gcd
n, x, *a = list(map(int, open(0).read().split()))
ans = abs(a[0] - x)
for i in range(1, n):
    ans = gcd(ans, abs(x - a[i]))
print(ans)
# coding: utf-8
s = input()
s_list=list(s)
s_len=len(s_list)
s_first=int(s_list[0]+s_list[1])
s_second=int(s_list[2]+s_list[3])
if s_first<13:#MMYY case
    if s_second<13:
        print('AMBIGOUS')
    else:
        print('MMYY')

else if: #YYMM case
    if s_second==0:
        print('NA')
    else:
        print('YYMM')

else
    print('NA')


### FIXED CODE ###

# coding: utf-8
s = input()
s_list=list(s)
s_len=len(s_list)
s_first=int(s_list[0]+s_list[1])
s_second=int(s_list[2]+s_list[3])
if s_first<13 and s_first>0: #MMYY case
    if s_second<13 and s_second>0:
        print('AMBIGUOUS')
    else:
        print('MMYY')

else: #YYMM case
    if s_second<13 and s_second>0:
        print('YYMM')
    else:
        print('NA')
n,k=int(input().split())
if (n+k)%3 == 0:
  print("Possible")
else:
  print("Impossible")

### FIXED CODE ###

a,b=map(int,input().split())
if a%3==0 or b%3==0 or (a+b)%3==0:
    print("Possible")
else:
    print("Impossible")
a,b,c,d = map(int,input().split())

def lcm(a,b):
    return a*b//gcd(a,b)

count = 0
for _ in range(a//c, (b+1)//c):
    count += 1

for _ in range(a//d, (b+1)//d):
    count += 1
for _ in range(a//lcm(c,d), (b+1)//lcm(c,d)):
    count -= 1

print(b+1-a-count)

### FIXED CODE ###

def lcm(a,b):
    ab = a*b
    while b != 0:
        a, b = b, a%b
    return ab //a

def su(n,c,d):
    return n - n//c - n//d + n//lcm(c,d)
    
def main():
    a,b,c,d = map(int,input().split())
    print(su(b,c,d) - su(a-1,c,d))
    
if __name__ == '__main__':
    main()
s,w=map(int,raw_input().split())
if s>w:
    print "safe"
else:
    print "unsafe"





### FIXED CODE ###

s,w=map(int,input().split())
if s>w:
    print ("safe")
else:
    print ("unsafe")
s = list(raw_input())
for loop in xrange(input()):
    c = raw_input().split()
    if c[0] == "replace":
        s[int(c[1]): int(c[2]) + 1] = list(c[3])
    if c[0] == "reverse":
        s[int(c[1]): int(c[2]) + 1] = s[int(c[1]): int(c[2) + 1][::-1]
    if c[0] == "print":
        print "".join(s[int(c[1]): int(c[2]) + 1]

### FIXED CODE ###

s = list(raw_input())
for loop in xrange(input()):
    c = raw_input().split()
    if c[0] == "replace":
        s[int(c[1]): int(c[2]) + 1] = list(c[3])
    if c[0] == "reverse":
        s[int(c[1]): int(c[2]) + 1] = s[int(c[1]): int(c[2]) + 1][::-1]
    if c[0] == "print":
        print "".join(s[int(c[1]): int(c[2]) + 1])
n=int(input())

table=[0]*10**5

for i in range(n):
    a=int(input())
    table[a-1]+=1

ans=0

for j in range(10**5):
    if table[j]%2==1:
        ans+=1

print(ans)

### FIXED CODE ###

n=int(input())

a=[int(input()) for i in range(n)]

dic={}

for i in range(n):
    if a[i] not in dic:
        dic[a[i]]=1
    else:
        dic[a[i]]+=1

ans=0

for val in dic.values():
    if val%2==1:
        ans+=1

print(ans)
N = int(input())

L = list(map(int, input().split()))

count = 0 
L.sort()

for i in range(N-2):
    k = i + 2
    for j in range(i+1,n):
        while (k<n and L[i] + L[j]):
            k += 1

        if k > j:
            count += k - j - 1


print(count)



### FIXED CODE ###

N = int(input())

L = list(map(int, input().split()))

count = 0 
L.sort()

for i in range(N-2):
    k = i + 2
    for j in range(i+1,N):
        while (k<N and L[i] + L[j] > L[k]):
            k += 1

        if k > j:
            count += k - j - 1


print(count)
A, B, C, D = map(int, input().split())

print( min(A,B) + min(C,D))

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
D = int(input())

print( min(A,B) + min(C,D))
n,k=[int(i) for i in input().split()]
arr=[int(i) for i in input().split()]
ans=0
mod=10**9+7
arr.sort() 
c=[0 for i in range(n)]
r=k-1
c[r]=1
def modinv(x.mod):
    return pow(x,mod-2,mod)
for i in range(r+1,n):
    c[i]=((c[i-1]*(i))*modinv(i-r,mod))%mod
pos=0
neg=0
for i in range(n):
    pos+=(arr[-1-i]*c[-1-i])%mod
    neg+=(arr[i]*c[-1-i])%mod
    pos%=mod
    neg%=mod
print((pos-neg)%mod)


### FIXED CODE ###

n,k=[int(i) for i in input().split()]
arr=[int(i) for i in input().split()]
ans=0
mod=10**9+7
arr.sort() 
c=[0 for i in range(n)]
r=k-1
c[r]=1
def modinv(x,mod):
    return pow(x,mod-2,mod)
for i in range(r+1,n):
    c[i]=((c[i-1]*(i))*modinv(i-r,mod))%mod
pos=0
neg=0
for i in range(n):
    pos+=(arr[-1-i]*c[-1-i])%mod
    neg+=(arr[i]*c[-1-i])%mod
    pos%=mod
    neg%=mod
print((pos-neg)%mod)
n, w = list(map(int, input().split()))
nums = []
for _ in range(n):
  nums.append(list(map(int, input().split())))

dp = [[0 for _ in range(w+1)] for _ in range(1, n)]

for i in range(1, n):
  for j in range(1, w+1):
    if j >= nums[i-1][1]:
      dp[i][j] = max(dp[i][j], dp[i-1][j-nums[i-1][1]] + nums[i-1][0])
    else:
      dp[i][j] = max(dp[i][j], dp[i-1][j])
print(max(dp[-1][-1]))

### FIXED CODE ###

n, w = list(map(int, input().split()))
nums = []
for _ in range(n):
  nums.append(list(map(int, input().split())))
  
dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(1, n+1):
  for j in range(1, w+1):
    if j < nums[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1][0]] + nums[i-1][1])
print(dp[-1][-1])
import sys
input = sys.stdin.readline
n = int(input())
c = []
for i in range(n):
  a = [int(i) for i in input().split()]
  c.append(a)

p,q,r = c[0]
if n == 1:
  print(p,q,r)
  exit()

end = c[-1]
c = c[1:]
for i in range(101):
  for j in range(101):
    chk = abs(p-i)+abs(q-j)+r
    for num,k in enumerate(c):
      x,y,h = k
      if abs(x-i)+abs(y-j)+h != chk and h != 0:
        break
      if k == end:
        ans = (i,j,chk)

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
c = []
for i in range(n):
  a = [int(i) for i in input().split()]
  c.append(a)

from operator import itemgetter
c = sorted(c,key=itemgetter(2),reverse=True)
p,q,r = c[0]
end = c[-1]
c = c[1:]
for i in range(101):
  for j in range(101):
    if r > 0:
      chk = abs(p-i)+abs(q-j)+r
    else:
      chk = 1
    for num,k in enumerate(c):
      x,y,h = k
      if h == 0:
        if abs(x-i)+abs(y-j) < chk:
          break
      else:
        if abs(x-i)+abs(y-j)+h != chk:
          break
      if k == end:
        ans = (i,j,chk)

print(*ans)
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

def get_size(s):
    return size[get_root(s)]

def update_size(x, y, s):
    size[get_root(s)] = x + y

n, m = map(int, input().split())
c = (n * (n - 1)) // 2
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
size = [1 for _ in range(n)]
ans = [c]
s = [list(map(int, input().split())) for _ in range(m)]
for i in range(m - 1, -1, -1):
    t = s[i]
    t[0] -= 1
    t[1] -= 1
    if not same(t[0], t[1]):
        x = get_size(t[0])
        y = get_size(t[1])
        unite(t[0], t[1])
        update_size(x, y, t[0])
        c -= x * y
    ans.append(c)
for i in range(m - 1, -1, -1):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

def get_size(s):
    return size[get_root(s)]

def update_size(x, y, s):
    size[get_root(s)] = x + y

n, m = map(int, input().split())
c = (n * (n - 1)) // 2
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
size = [1 for _ in range(n)]
ans = [c]
v = [list(map(int, input().split())) for _ in range(m)]
for i in range(m - 1, -1, -1):
    u = v[i]
    u[0] -= 1
    u[1] -= 1
    if not same(u[0], u[1]):
        x = get_size(u[0])
        y = get_size(u[1])
        unite(u[0], u[1])
        update_size(x, y, u[0])
        c -= x * y
    ans.append(c)
for i in range(m - 1, -1, -1):
    print(ans[i])
import collections

class UnionFind:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.parent = [i for i in range(N+1)]
        self.count = [1 for _ in range(N+1)]

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        df = 0
        if pi != pj:
            self.parent[pj] = pi
            df += self.count[pi] * self.count[pj]
            self.count[pi] += self.count[pj]
        return df

def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])

    UF = UnionFind(N, M)

    ans = [N*(N-1)//2]
    for i in range(M-1, 0, -1):
        a, b = bridges[i]
        d = UF.union(a, b)
        ans.append(ans[-1]-d)
    return ans

if __name__ == '__main__':
    output = main()
    for i in range(len(output)-1, -1, -1):
        print(output[i])

### FIXED CODE ###

import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])
    bridges = bridges[::-1]
    parent = [i for i in range(N+1)]
    count = dict()
    for i in range(N+1): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            if count[pi] > count[pj]:
                parent[pj] = pi
                df += count[pi] * count[pj]
                count[pi] += count[pj]
                del count[pj]
            else:
                parent[pi] = pj
                df += count[pi] * count[pj]
                count[pj] += count[pi]
                del count[pi]                
        return df

    ans = [N*(N-1)//2]
    for a, b in bridges[:-1]:
        d = union(a, b)
        ans.append(ans[-1]-d)
    return ans[::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(v)
from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=gcd(a[0],a[1])
for i in a:
  x=gcd(x,i)
print(x)

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
x=a[0]
for i in a:
  x=gcd(x,i)
print(x)