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

from bisect import*
from collections import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

stop=set([-1])
def main():
    n,q=map(int,input().split())
    event=[]
    
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])

    minlist=defaultdict(int)

    for k,v in enumerate(event):
        minlist[k]=doevent(v)

    for i in range(q):
        sys.stdout.writelines(str(minlist[bisect_right(event,(int(input()),10**9))-1])+"\n")
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))
    
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop
        
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[0]*N
count=0
for i in range(N):
    for j in range(N):
        if A[i]%A[j]==0:
            count+=1
            if count==2:
                break
    if count==1:
        B[i]=1
    else:
        B[i]=0
    count=0
print(sum(B))

### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

s = input()
n = len(s)
for i in range(n):
  if '01' not in s and '10' not in s:
    break
  s=s.replace('01','')
  s=s.replace('10','')
print(n-len(s))

### FIXED CODE ###

s = input()
c1,c2=s.count('0'),s.count('1'),
print(min(c1,c2)*2)
### BUGGY CODE ###

from fractions import gcd

class SegmentTree():
    _data = []
    _offset = 0
    
    def __init__(self, size):
        t = 1
        while t <= size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)
    
    def update_all(self, iterable):
        for i, v in enumerate(iterable):
            self._data[i + self._offset] = v
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])
    
    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])
    
    def _query(self, start, stop, index, left, right):
        if right <= start or stop <= left:
            return 0
        if start <= left and right <= stop:
            return self._data[index]
        a = self._query(start, stop, index * 2 + 1, left, (left + right) // 2)
        b = self._query(start, stop, index * 2 + 2, (left + right) // 2, right)
        return gcd(a, b)
    
    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self._offset + 1)

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

st = SegmentTree(N)
st.update_all(A)

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, st.query(0, N - 1))
print(result)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
c1 = [0] * (n + 1)
c2 = [0] * (n + 1)
# c1[1] = a[0]
# c2[n - 1] = a[n - 1]
for i in range(1, n + 1):
  c1[i] = gcd(c1[i - 1], a[i - 1])
  c2[n - i] = gcd(c2[n - i + 1], a[n - i])
print(max(gcd(c1[i], c2[i + 1]) for i in range(n)))
### BUGGY CODE ###

s = input()
t = input()
s_length = len(s)
t_length = len(t)

def char2int(char):
    return ord(char) - 97

def search_index(t_atom, last_index, d):
    if d[char2int(t_atom)] == []:
        return -1

    for i in d[char2int(t_atom)]:
        if last_index < i:
            return i

    return d[char2int(t_atom)][0]

def solve():
    last_index = -1
    t_index = []
    loop_cost = 1

    d = [[] for _ in range(26)]
    for i in range(s_length):
        char = s[i]
        d[char2int(char)].append(i)

    for i in range(t_length):
        t_atom = t[i]
        t_atom_index = search_index(t_atom, last_index, d)
        if t_atom_index == -1:
            return -1
        else:
            t_index.append(t_atom_index)
            last_index = t_atom_index

    remainder_cost = t_index[-1] + 1

    for i in range(1, t_length):
        if t_index[i - 1] >= t_index[i]:
            loop_cost += 1

    return s_length * (loop_cost - 1) + remainder_cost

print(solve())


### FIXED CODE ###

import bisect

s = input()
t = input()
s_length = len(s)
t_length = len(t)

def char2int(char):
    return ord(char) - 97

def search_index(t_atom, last_index, d_list):
    t_atom_int = char2int(t_atom)
    d = d_list[t_atom_int]

    if d == []:
        return -1

    c = bisect.bisect_right(d, last_index)

    if c != len(d):
        return d[c]
    else:
        return d[0]

def solve():
    last_index = -1
    t_index = []
    loop_cost = 1

    d = [[] for _ in range(26)]
    for i in range(s_length):
        char = s[i]
        d[char2int(char)].append(i)

    for i in range(t_length):
        t_atom = t[i]
        t_atom_index = search_index(t_atom, last_index, d)
        if t_atom_index == -1:
            return -1
        else:
            t_index.append(t_atom_index)
            last_index = t_atom_index

    remainder_cost = t_index[-1] + 1

    for i in range(1, t_length):
        if t_index[i - 1] >= t_index[i]:
            loop_cost += 1

    return s_length * (loop_cost - 1) + remainder_cost

print(solve())
### BUGGY CODE ###

S = input()
count = 0
l = [0]*2019
l[0] = 1

for i in range(1,len(S)+1):
    n =(int(S[len(S)-i:])%2019)
    l[n] += 1
    

for j in range(2019):
    if l[j] >= 2:
        count += l[j]*(l[j]-1)//2

print(count)


### FIXED CODE ###

S = input()
count = 0
l = [0]*2019
l[0] = 1
mod = 2019
tmp = 0

for i in range(1,len(S)+1):
    tmp = (tmp + int(S[len(S)-i])*pow(10,i-1,mod))%mod
    l[tmp] += 1
    

for j in range(2019):
    if l[j] >= 2:
        count += l[j]*(l[j]-1)//2

print(count)
### BUGGY CODE ###

S = list(input())
ans = 0
i = 0
while len(S)>i+1:
  if S[i] != S[i+1]:
    S.pop(i)
    S.pop(i)
    ans += 2
    i = 0
  else:
    i = i+1
    
print(ans)

### FIXED CODE ###

S = list(input())
a = 0
b = 0
for s in S:
  if s == '0':
    a += 1
  else:
    b += 1
ans = min(a,b)
ans = ans * 2
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

ans = 1

from math import gcd

for i in range(n):
    tmp = -1
    for j in range(n):
        if i != j:
            if tmp == -1:
                tmp = a[j]
            else:
                tmp = gcd(tmp, a[j])
    ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

"""
累積GCD
"""

import sys
sys.setrecursionlimit(10**6)

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

from math import gcd

L = [0] * n
R = [0] * n

for i in range(n-1):
    L[i+1] = gcd(L[i], A[i])
for i in range(n-1, 0, -1):
    R[i-1] = gcd(R[i], A[i])

ans = 0
for i in range(n):
    ans = max(ans, gcd(L[i], R[i]))

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

import itertools


def main():
    n = int(input())
    s = [sorted(input()) for _ in range(n)]
    seq = list(itertools.combinations(s, 2))
    ans = 0
    for i in seq:
        if i[0] == i[1]:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = ["".join(sorted(input())) for _ in range(n)]
    ans = 0
    dic = {}
    for i in s:
        if i not in dic:
            dic[i] = 0
        else:
            dic[i] += 1
            ans += dic[i]
        # print(ans)
    print(ans)


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

A, B, K = map(int, input().split())
if A + B == K:
  print("0 0")
  exit()
while (K > 0):
  if A >= K:
    t1 = K
    K -= A
    A -= t1
  elif A > 0:
    A -= 1
    K -= 1
  elif B >= K:
    t2 = K
    K -= B
    B -= t2
  elif B > 0:
    B -= 1
    K -= 1
print(str(A) + " " + str(B))

### FIXED CODE ###

A, B, K = map(int, input().split())
if A >= K:
  print(A - K, B)
elif B >= (K - A):
  print(0, B - (K - A))
else:
  print(0, 0)
### BUGGY CODE ###

from collections import defaultdict


def prime_factor(n):
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

    if n != 1:
        d[n] += 1

    return d


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

ctr = defaultdict(int)
buf = []
for n in X:
    d = prime_factor(n)
    buf.append(d)
    for key in d:
        ctr[key] = max(ctr[key], d[key])

ans = 0
for i, n in enumerate(X):
    cur = 1
    for key in ctr:
        cnt = ctr[key] - buf[i][key]
        if cnt > 0:
            cur = cur * pow(key, cnt, MOD) % MOD

    ans += cur
    ans %= MOD

print(ans)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

N, *A = map(int, open(0).read().split())

def lcm(x, y):
    return x * y // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

MOD = 10 ** 9 + 7
num = lcm_list(A)
print(sum(num * pow(v, MOD - 2, MOD) for v in A) % MOD)
### BUGGY CODE ###

a,b,k=map(int,input().split());
for i in range(a,b+1):
	if i<a+k or b-k<i:
		print(i)

### FIXED CODE ###

a, b, k = [int(m) for m in input().split(" ")]

for i in range(a, min(a+k, b+1)):
    print(i)
for i in range(max(b+1-k, a+k), b+1):
    print(i)
### BUGGY CODE ###

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

for _ in range(m):
  A.sort(reverse=True)
  A[0]=A[0]//2
print(sum(A))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
A=list(map(int,input().split()))

q=[]
for a in A:
  heapq.heappush(q,-a)
  
for _ in range(m):
  p=-heapq.heappop(q)//2
  heapq.heappush(q,-p)
print(-sum(q))
### BUGGY CODE ###

_, M = map(int, input().split())
A = list(map(int, input().split()))
opes = [tuple(map(int, input().split())) for _ in range(M)]

for B, C in opes:
    A.sort()
    for i in range(B):
        A[i] = C if A[i] < C else A[i]

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
opes = [tuple(map(int, input().split())) for _ in range(M)]
opes.sort(key=lambda x:-x[1])

D = []
lenD = 0
for B, C in opes:
    D += [C]*B
    lenD += B
    if lenD >= N:
        break

A.sort()
for i, d in enumerate(D[:N]):
    if A[i] >= d:
        break
    A[i] = d

print(sum(A))
### BUGGY CODE ###

from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def main():
    n, c = map(int, input().split())
    stk = [list(map(int, input().split())) for i in range(n)]
    stk = sorted(stk,key=lambda x:x[0])

    ans = 1
    l = []
    heapify(l)
    heappush(l,[stk[0][1],stk[0][2]])
    for i in range(1, n):
        ll = []
        heapify(ll)
        size = len(l)
        for j in range(size):
            v = heappop(l)
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    heappush(ll,v)
            else:
                if stk[i][0] - 0.5 < v[0] :
                    heappush(ll,v)
        heappush(ll, stk[i][1:])
        l = ll
        ans = max(ans , len(l))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

input = sys.stdin.readline
def main():
    n, c = map(int, input().split())
    stk = [tuple(map(int, input().split())) for i in range(n)]
    stk = sorted(stk, key=lambda x: x[0])

    ans = 1
    l = []
    # heapify(l)
    # heappush(l, (stk[0][1], stk[0][2]))
    l = [(stk[0][1], stk[0][2])]
    for i in range(1, n):
        ll = []
        #heapify(ll)
        for j in range(len(l)):
            # v = heappop(l)
            v = l[j]
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    # heappush(ll, v)
                    ll.append(v)
            else:
                if stk[i][0] - 0.5 < v[0]:
                    # heappush(ll, v)
                    ll.append(v)
        # heappush(ll, stk[i][1:])
        ll.append(stk[i][1:])
        l = ll
        ans = max(ans, len(l))
    print(ans)


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

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a={}
for i in range(1,N+1):
  a.update({i:0})
for j in A:
  a[j]+=1
for k,l in a.items():
  print(l)
### BUGGY CODE ###

#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations_with_replacement
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10 ** 6)

def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    ans = 0
    for c in combinations_with_replacement(list(range(1, n+1)), 3):
        if c[0] == c[1] and c[1] == c[2]:
            ans += gcd(gcd(c[0], c[1]), c[2])
        elif c[0] != c[1] and c[1] != c[2]:
            ans += gcd(gcd(c[0], c[1]), c[2]) * 6
        else:
            ans += gcd(gcd(c[0], c[1]), c[2]) * 3
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
from math import gcd
from math import ceil, floor
sys.setrecursionlimit(10 ** 6)

def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    ans = 0
    for a in range(1, n+1):
        for b in range(1, n+1):
            tmp = gcd(a, b)
            for c in range(1, n+1):
                ans += gcd(tmp, c)
    print(ans)

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

N = int(input())
As = list(map(int, input().split()))
sort_as = sorted(As)
shine = [x + 1 for x in range(N)]
c = 0
s = 0
j = 0
for x in range(N):
  for y in range(len(As)):
    if shine[x] == As[y]:
      c += 1
    if shine[x] < As[y]:
      break
  print(c)
  c = 0

### FIXED CODE ###

n = int(input())
As = list(map(int, input().split()))
 
x = [0] * n
for i in As:
    x[i-1] += 1
for y in x:
    print(y)
### BUGGY CODE ###

import sys 
input=sys.stdin.readline

N=int(input())
L=[[]]

for i in range(N):
    a=list(map(int,input().split()))
    L.append(a)
#print(L)
Z=[0 for i in range(N+1)]
day=0
cnt=0
for i in range(10**6+5):
    if cnt==N*(N-1)/2:
        break
    D=dict()
    CNT=0
    for j in range(1,N+1):
        if Z[j]==N-1 or j in D:
            continue
        elif L[L[j][Z[j]]][Z[L[j][Z[j]]]]==j and L[j][Z[j]] not in D:
            D[j]=1
            D[L[j][Z[j]]]=1
            X=L[j][Z[j]]
            Z[j]+=1
            Z[X]+=1
            CNT+=1
    if CNT==0:
        print(-1)
        exit()
    cnt+=CNT
    day+=1
#print(L)
#print(cnt)
print(day)


### FIXED CODE ###

N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)
    
#print(A)
B=[0 for i in range(N+1)]
C=[a for a in range(1,N+1)]
cnt=0
for i in range(10**6):
    D=[]
    F=0
    for j in C:
        if A[A[j][B[j]]][B[A[j][B[j]]]]==j and j not in D and A[j][B[j]] not in D:
            D.append(j)
            D.append(A[j][B[j]])
            B[A[j][B[j]]]+=1
            B[j]+=1
            F=1
            cnt+=1
            #print("A",i,B,D)
            #print(A[j][B[j]],B,D)
    if F==0:
        break
    D.sort()
    C=D
    
if cnt==N*(N-1)//2:
    print(i)
else:
    print(-1)
### BUGGY CODE ###

n,p=map(int,input().split())
s=list(map(int,list(input()[::-1])))
if p in [2,5]:
  ans=0
  for i in range(n):
    if s[-i-1]%p==0:ans+=i+1
  print(ans)
  exit()
from collections import defaultdict
d=defaultdict(int)
t=0
d[t]+=1
for i in range(n):
  t+=(10**i)*s[i]
  t%=p
  d[t]+=1
print(sum(d[i]*(d[i]-1)//2 for i in range(p)))

### FIXED CODE ###

n,p=map(int,input().split())
s=list(map(int,list(input()[::-1])))
if p in [2,5]:
  ans=0
  for i in range(n):
    if s[-i-1]%p==0:ans+=i+1
  print(ans)
  exit()
from collections import defaultdict
d=defaultdict(int)
t=0
d[t]+=1
m=1
for i in range(n):
  t+=m*s[i]
  t%=p
  d[t]+=1
  m*=10
  m%=p
print(sum(d[i]*(d[i]-1)//2 for i in range(p)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
sn = [input().strip('\n') for _ in range(n)]

mod = 10**5 + 7
hs = [[0, ''] for _ in range(mod)]

def hypo(s, Mod):
    h_num = 1
    for i in s:
        h_num = h_num * ord(i) % Mod
    return h_num

for s in sn:
    s = ''.join(sorted(s))
    h = hypo(s, mod)
    while True:
        if h >= mod :
            h = 0
        if hs[h][0] == 0:
            hs[h][0] += 1
            hs[h][1] += s
            break
        if hs[h][1] == s:
            hs[h][0] += 1
            break
        h += 1

ans = 0
for j, t in hs:
    if j >= 2:
        ans += j * (j-1) / 2

print(int(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
sn = [input().strip('\n') for _ in range(n)]

mod = 10**6 + 7
hs = [[0, ''] for _ in range(mod)]

def hypo(s, Mod):
    h_num = 1
    for i in s:
        h_num = h_num * ord(i) % Mod
    return h_num

for s in sn:
    s = ''.join(sorted(s))
    h = hypo(s, mod)
    while True:
        if h >= mod :
            h = 0
        if hs[h][0] == 0:
            hs[h][0] += 1
            hs[h][1] += s
            break
        if hs[h][1] == s:
            hs[h][0] += 1
            break
        h += 1

ans = 0
for j, t in hs:
    if j >= 2:
        ans += j * (j-1) / 2

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

ans = 0
N = int(input())
array = list(map(int, input().split()))
for i in range(N):
  for j in range(N):
    if i != j and i < j:
      ans += array[i]*array[j]
print(ans%(10**9+7))
      

### FIXED CODE ###

ans = 0
N = int(input())
array = list(map(int, input().split()))
x = sum(array)
y = 0
for i in range(N):
  y += array[i]**2

ans = x**2 -y
print((ans//2)%(10**9+7))
### BUGGY CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

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

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-self.parents[r] for r in self.roots()]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[0]*(M+1)
ans[M]=N*(N-1)//2
i=M-1
for a,b in AB[::-1]:
  uf.union(a-1,b-1)
  ans[i]=ans[-1]-sum([x*(x-1)//2 for x in uf.all_group_numbers()])
  i-=1
for a in ans[1:]:
  print(a)

### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return False,0,0

    if self.parents[x] > self.parents[y]:
      x, y = y, x
    nx=self.size(x)
    ny=self.size(y)
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
    return True,nx,ny

  def size(self, x):
    return -self.parents[self.find(x)]

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

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-x for x in self.parents if x < -1]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[0]*(M+1)
ans[M]=N*(N-1)//2
i=M-1
for a,b in AB[::-1]:
  flg,na,nb=uf.union(a-1,b-1)
  if flg:
    ans[i]=ans[i+1]-na*nb
  else:
    ans[i]=ans[i+1]
  i-=1
for a in ans[1:]:
  print(a)
### BUGGY CODE ###

import math
g = 0
K = int(input())
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            g += math.gcd(math.gcd(a,b),c)
print(g)

### FIXED CODE ###

import math
g = 0
K = int(input())
for a in range(1,K-1):
    for b in range(a+1,K):
        for c in range(b+1,K+1):
            g += math.gcd(math.gcd(a,b),c)*6
for d in range(1,K):
    for e in range(d+1,K+1):
        g+= math.gcd(d,e)*6
g+= K*(K+1)//2
print(g)
### BUGGY CODE ###

from collections import Counter
s = input()
MOD = 2019
ts = [0]
cur = 0
for i, j in enumerate(s[::-1], 1):
    cur = (cur + int(j) * 10**i % MOD) % MOD
    ts.append(cur)
ct = Counter(ts)
res = 0
for k, v in ct.items():
    if v > 1:
        res += v * (v-1) // 2
print(res)

### FIXED CODE ###

from collections import Counter
s = input()
MOD = 2019
ts = [0]
cur = 0
for i, j in enumerate(s[::-1], 1):
    cur = (cur + pow(10, i, MOD) * int(j)) % MOD
    ts.append(cur)
ct = Counter(ts)
res = 0
for k, v in ct.items():
    if v > 1:
        res += v * (v-1) // 2
print(res)
### BUGGY CODE ###

import math
n = int(input())
ans = 0
for i in range(1,n+1):
    if math.sqrt(i).is_integer():
        ans = max(ans,math.sqrt(i))
print(int(ans**2))

### FIXED CODE ###

n = int(input())
ans = 0
if n == 1:
    print(1)
else:
    for i in range(1,n+1):
        if i ** 2 > n:
            print(int((i-1)**2))
            break