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

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

ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a-1, b-1))

uni = [set([i]) for i in range(n)]

start = (n * (n - 1)) // 2

blis = [start]
for a, b in ab[::-1]:
  ap = a
  bp = b
  while isinstance(uni[ap], int):
    _ap = uni[ap]
    uni[ap] = _ap
    ap = _ap
  while isinstance(uni[bp], int):
    _bp = uni[bp]
    uni[bp] = _bp
    bp = _bp
  _ap = uni[ap]
  _bp = uni[bp]
  if _ap.intersection(_bp) == set():
    start -= len(_ap) * len(_bp)
  if ap != bp:
    uni[ap] = uni[ap].union(uni[bp])
    uni[bp] = ap
  blis.append(start)
for p in blis[::-1][1:]:
  print(p)


### FIXED CODE ###

def comb(n):
    return n*(n+1)//2

class UnionFind:
  def __init__(self, N):
    self.parent = [i for i in range(N)]
    self.rank = [0] * N
    self.count = 0
    self.size = [1] * N
    self.connection = 0

  def root(self, a):
    if self.parent[a] == a:
      return a
    else:
      self.parent[a] = self.root(self.parent[a])
      return self.parent[a]

  def is_same(self, a, b):
    return self.root(a) == self.root(b)

  def unite(self, a, b):
    ra = self.root(a)
    rb = self.root(b)
    if ra == rb:
      return
    self.connection -= (comb(self.size[ra]) + comb(self.size[rb]))
    self.connection += comb(self.size[ra] + self.size[rb])
    if self.rank[ra] < self.rank[rb]:
      self.size[rb] += self.size[ra]
      self.parent[ra] = rb
    else:
      self.size[ra] += self.size[rb]
      self.parent[rb] = ra
      if self.rank[ra] == self.rank[rb]:
        self.rank[ra] += 1
    self.count += 1

n, m = map(int, input().split())
uni = UnionFind(n)
remain = [comb(n-1)]
abl = []
for _ in range(m):
  a, b = map(int, input().split())
  abl.append((a-1, b-1))
for a, b in abl[::-1]:
  uni.unite(a, b)
  remain.append(remain[0] - uni.connection)
for r in reversed(remain[:-1]):
  print(r)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

def bfs(y, x):
    cnt = [[-1] * w for _ in range(h)]
    queue = deque([[y, x]])
    cnt[y][x] = 1
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                if s[i + di][j + dj] == ".":
                    cnt[i + di][j + dj] = cnt[i][j] + 1
                    queue.append([i + di, j + dj])
                else:
                    return cnt[i][j]
                    break

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, bfs(i, j))
print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
cnt = [[-1] * w for _ in range(h)]

def bfs():
    queue = deque()
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                queue.append([i, j])
                cnt[i][j] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                queue.append([i + di, j + dj])
                cnt[i + di][j + dj] = cnt[i][j] + 1

bfs()
print(max([max(l) for l in cnt]))
### BUGGY CODE ###

if __name__ == "__main__":
    n = int(raw_input())
    dic = []
    for i in range(n):
        t = raw_input().split()
        if t[0] == "insert":
            dic.append(t[1])
        if t[0] == "find":
            if(t[1] in dic):
                print("yes")
            else:
                print("no")

### FIXED CODE ###

n = input()
table =	set()

for i in range(n):
    com	= raw_input().split()
    if(com[0][0] == "i"):
	table.add(com[1])
    else:
	if com[1] in table:
            print("yes")
	else:
            print("no")
### BUGGY CODE ###

n=int(input())

print(0)
zero=input()
if zero=="Vacant":exit()

left,right=0,n
while left<right:
    mid=(left+right)//2
    print(mid)
    ans=input()
    if ans=="Vacant":exit()

    if (ans==zero and mid%2==1) or (ans!=zero and mid%2==0):left=mid+1
    else:right=mid

### FIXED CODE ###

n=int(input())

print(0)
zero=input()
if zero=="Vacant":exit()

left,right=0,n
while left<right:
    mid=(left+right)//2
    print(mid)
    ans=input()
    if ans=="Vacant":exit()

    if (ans==zero and mid%2==1) or (ans!=zero and mid%2==0):right=mid+1
    else:left=mid
### BUGGY CODE ###

def main():
    N = int(input())
    infos = []
    for i in range(1,N):
        infos.append(list(map(int, input().split())))

    for i in range(1,N):
        current_time = 0
        for station_number in range(i,N):
            current_time = next_arrival_time(current_time, infos[station_number -1])
        print(current_time)
    print(0)

def next_arrival_time(current_time, info):
    if current_time <= info[1]:
        return info[1] + info[0]

    next_time = info[1]
    while next_time < current_time:
        next_time += info[2]

    return next_time + info[0]

main()

### FIXED CODE ###

from functools import lru_cache

def main():
    N = int(input())
    infos = []
    for i in range(1,N):
        infos.append(tuple(map(int, input().split())))

    for i in range(1,N):
        current_time = 0
        for station_number in range(i,N):
            current_time = next_arrival_time(current_time, infos[station_number -1])
        print(current_time)
    print(0)

@lru_cache(maxsize = 2**26)
def next_arrival_time(current_time, info):
    if current_time <= info[1]:
        return info[1] + info[0]

    next_time = current_time
    remainder = next_time % info[2]
    while remainder != 0:
        next_time += 1
        remainder = next_time % info[2]
    while next_time < current_time:
        next_time += info[2]

    return next_time + info[0]

main()
### BUGGY CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))
INF = 999999999999999999999999999
dp = [INF] * n
dp[0] = 0
for i in range(1, n):
    for j in range(1, k+1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))
    
print(dp[n-1])
        

### FIXED CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))
INF = 999999999999999999999999999
dp = [INF] * n
dp[0] = 0
for i in range(1, n):
    for j in range(1, k+1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))
    
print(dp[n-1])
### BUGGY CODE ###

S = input()
Q = int(input())

flag = False
for _ in range(Q):
    IN = list(map(str,input().split()))

    if IN[0] == "1":
        flag = not flag
        continue

    _,F,C = IN
    if flag:
        if F == "1":
            S += C
        else:
            S = C + S
    else:
        if F == "1":
            S = C + S
        else:
            S += C

if flag:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

flag = False
for _ in range(Q):
    IN = list(map(str,input().split()))

    if IN[0] == "1":
        flag = not flag
        continue

    _,F,C = IN
    if flag:
        if F == "1":
            S.append(C)
        else:
            S.appendleft(C)
    else:
        if F == "1":
            S.appendleft(C)
        else:
            S.append(C)

if flag:
    print(*reversed(S),sep="")
else:
    print(*S,sep="")
### BUGGY CODE ###

n = int(input())
s = [list(map(int, input().split())) for _ in range(n - 1)]
for i in range(0, n):
    t = 0
    m = i
    if i != n - 1:
        t = s[i][0] + s[i][1]
        m += 1
    while True:
        if m == n - 1:
            break
        while True:
            if (t - s[m][1]) % s[m][2] == 0 and t >= s[m][1]:
                break
            t += 1
        t += s[m][0]
        m += 1
    print(t)

### FIXED CODE ###

n = int(input())
s = [list(map(int, input().split())) for _ in range(n - 1)]
for i in range(0, n):
    t = 0
    m = i
    if i != n - 1:
        t = s[i][0] + s[i][1]
        m += 1
    while True:
        if m == n - 1:
            break
        while True:
            if (t - s[m][1]) % s[m][2] == 0 and t < s[m][1]:
                t = s[m][1]
            if (t - s[m][1]) % s[m][2] == 0 and t >= s[m][1]:
                break
            t += 1
        t += s[m][0]
        m += 1
    print(t)
### BUGGY CODE ###


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

max_num = 0
ind = 0
for i in range(N-K+1):
    if sum(A[i:i+K])> max_num:
        ind = i
        max_num = max(max_num,sum(A[i:i+K]))

ans = 0
for i in range(ind,ind+K):
    ans += sum(range(1,A[i]+1))/A[i]
    
print(ans)

### FIXED CODE ###

N,K = map(int, input().split())
A=list(map(int, input().split()))  
 
num = sum(A[0:K])
ind = 0
max_num =0
for i in range(N-K):
    num -= A[i]
    num += A[i+K]
    if num> max_num:
        ind = i+1
        max_num = num
 
ans = 0
for i in range(ind,ind+K):
    ans += (1+A[i])/2
    
print(ans)
### BUGGY CODE ###

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]

for i in range(len(rcvs)):
    rcvs[i][0] -= 1
    rcvs[i][1] -= 1

rewards = [[0 for _ in range(C)] for _ in range(R)]

for rcv in rcvs:
    rewards[rcv[0]][rcv[1]] = rcv[2]
    
#%%

dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
answer = 0

for i in range(R):
    for j in range(C):
        reward = rewards[i][j]
        for k in range(4): # move downside without selecting
            if dp[i][j+1][k] > dp[i+1][j+1][0]:
                dp[i+1][j+1][0] = dp[i][j+1][k]
                
            if dp[i][j+1][k] + reward > dp[i+1][j+1][1]:
                dp[i+1][j+1][1] = dp[i][j+1][k] + reward
                
        for k in range(4): # move downside without selecting
            if dp[i+1][j][k] > dp[i+1][j+1][k]:
                dp[i+1][j+1][k] = dp[i+1][j][k]
            if k <= 2:
                if dp[i+1][j][k] + reward > dp[i+1][j+1][k+1]:
                    dp[i+1][j+1][k+1] = dp[i+1][j][k] + reward
print(max(dp[-1][-1]))

### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit(i8(i8[:,:]), cache=True)
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))
### BUGGY CODE ###

A,B,N=map(int, input().split())
answer=0
import math
for i in range(1,N+1):
    newans=math.modf(i/B)[0]*A
    newans//=1
    answer=newans if newans>answer else answer
print(int(answer))

### FIXED CODE ###

A,B,N=map(int, input().split())
answer=0
import math
if N < B:
    print(int(math.modf(N/B)[0]*A))
else:
    apple=min(B,N)
    startnum = B-1 if B>1 else 1
    for i in range(startnum,apple+1):
        newans=math.modf(i/B)[0]*A
        newans//=1
        answer=newans if newans>answer else answer
    print(int(answer))
### BUGGY CODE ###

def bin_digit(n: int):
    return len(bin(n)[2:]) + 1


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            n = (n - 1) // 2
        else:
            x = x ** 2
            n = n // 2

    return K * x


MOD = 10**9 + 7

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

digit = bin_digit(max(An))

res = 0
for d in range(digit):
    n0, n1 = 0, 0
    for i in range(N):
        if An[i] & pow_k(2, d):
            n1 += 1
        else:
            n0 += 1

    temp = pow_k(2, d) % MOD
    n = n0 * n1 % MOD
    temp *= n % MOD
    res = (res + temp) % MOD

print(res)

### FIXED CODE ###

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            n = (n - 1) // 2
        else:
            x = x ** 2
            n = n // 2

    return K * x


MOD = 10**9 + 7

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

res = 0
for d in range(60):
    n0, n1 = 0, 0
    for i in range(N):
        if (An[i] >> d) & 1:
            n1 += 1
        else:
            n0 += 1

    temp = pow_k(2, d) % MOD
    temp *= (n0*n1) % MOD
    res = (res + temp) % MOD

print(res)
### BUGGY CODE ###

import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = []
    for i in range(n):
        r.append(input())
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        d = r[0:i] + r[i:]
        index = bisect.bisect_right(d, tmp)
        ans += index
    print ans / 2

### FIXED CODE ###

import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            index = bisect.bisect_left(r, tmp)
            if (index <= i):
                ans += n - index - 1
            else:
                ans += n - index
    print ans / 2
### BUGGY CODE ###

n=10^100
s=list(input())
ls=len(s)
ds=n//ls
rs=n%ls

sisr=[]
for ss in s:
  if ss=="R":
    sisr.append(True)
  else:
    sisr.append(False)

r=[-1]*ls
for ii in range(ls):
  iii=ii
  for jj in range(ls):
    if sisr[iii]:
      iii+=1
    else:
      iii-=1
  r[ii]=iii
      
r2=[-1]*ls
for ii in range(ls):
  iii=ii
  for jj in range(ds):
    iii=r[iii]
  r2[ii]=iii

r3=[-1]*ls
for ii in range(ls):
  iii=r2[ii]
  for jj in range(rs):
    if sisr[iii]:
      iii+=1
    else:
      iii-=1
  r3[ii]=iii
      
"""
print(ds,rs)
print(sisr)
print(r)
print(r2)
print(r3)
"""
rs=[]
for ii in range(ls):
  rs.append(str(r3.count(ii)))
print(*rs)

### FIXED CODE ###

s=list(input())
ls=len(s)
r=[0]*ls
c=0
for ii in range(ls-1):
  if s[ii]=="R" and s[ii+1]=="R":
    c+=1
  elif s[ii]=="R" and s[ii+1]=="L":
    c+=1
    r[ii]+=c//2+c%2
    r[ii+1]+=c//2
    c=0
  elif s[ii]=="L" and s[ii+1]=="L":
    pass
  elif s[ii]=="L" and s[ii+1]=="R":
    pass
  #print(c)
#print(*r)
c=0  
for jj in range(ls-1):
  ii=ls-1-jj
  if s[ii-1]=="R" and s[ii]=="R":
    pass
  elif s[ii-1]=="R" and s[ii]=="L":
    c+=1
    r[ii-1]+=c//2
    r[ii]+=c//2+c%2
    c=0
  elif s[ii-1]=="L" and s[ii]=="L":
    c+=1
  elif s[ii-1]=="L" and s[ii]=="R":
    pass
  #print(ii,c)
print(*r)
### BUGGY CODE ###

from fractions import gcd
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
now = A[0]
ans = 0
for i in range(1,N):
    now = now//gcd(now, A[i])*A[i]
for i in range(N):
    ans += now//A[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

def prime_factors(n):
    d = {}
    while n%2 == 0:
        d[2] = d.get(2, 0) + 1
        n //= 2
    i = 3
    while i*i <= n:
        while n%i == 0:
            d[i] = d.get(i, 0) + 1
            n //= i
        i += 2
    if n > 2:
        d[n] = d.get(n, 0) + 1
    return d

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
G = {}
for a in A:
    pf = prime_factors(a)
    for k,v in pf.items():
        G[k] = max(G.get(k, 0), v)
lcm = 1
for k,v in G.items():
    lcm *= pow(k, v, MOD)
    lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD) % MOD
    ans %= MOD
print(ans)
### BUGGY CODE ###

import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_count = max(h_lst)
w_count = max(w_lst)
h_cand = [i+1 for i, h_ in enumerate(h_lst) if h_ == h_count]
w_cand = [i+1 for i, w_ in enumerate(w_lst) if w_ == w_count]
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)





### FIXED CODE ###

import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_count = max(h_lst)
w_count = max(w_lst)
h_cand = set([i+1 for i, h_ in enumerate(h_lst) if h_ == h_count])
w_cand = set([i+1 for i, w_ in enumerate(w_lst) if w_ == w_count])
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)
### BUGGY CODE ###

n = int(input())
s = input()
a_list = s.split()
k = 1
while k <= n:
  a = a_list.count(str(k))
  print(a)
  k += 1

### FIXED CODE ###

from collections import Counter
n = int(input())
s = input()
a_list = s.split()
dic =  Counter(a_list)
k = 1
while k <= n:
  print(dic[str(k)])
  k += 1
### BUGGY CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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)

class BIT():
    def __init__(self, n):
        i = 1
        while 2**i <= n:
            i += 1
        self.H = i
        self.N = 2**i
        self.A = [0] * self.N

    def find(self, i):
        r = 0
        while i:
            r += self.A[i]
            i -= i & (i-1) ^ i
        return r

    def update(self, i, x):
        while i < self.N:
            self.A[i] += x
            i += i & (i-1) ^ i

    def query(self, a, b):
        return self.find(b-1) - self.find(a-1)

def main():
    n,m = LI()
    d = collections.defaultdict(list)
    for _ in range(n):
        l,r = LI()
        d[r-l+1].append((l,r))
    r = [n]
    bit = BIT(m+3)
    c = n
    for i in range(2,m+1):
        for a,b in d[i-1]:
            c -= 1
            bit.update(a,1)
            bit.update(b+1,-1)
        t = c
        for j in range(i,m+1,i):
            t += bit.find(j)
        r.append(t)

    return '\n'.join(map(str,r))


print(main())




### FIXED CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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)

class BIT():
    def __init__(self, n):
        i = 1
        while 2**i <= n:
            i += 1
        self.H = i
        self.N = 2**i
        self.A = [0] * self.N

    def find(self, i):
        r = 0
        while i:
            r += self.A[i]
            i -= i & (i-1) ^ i
        return r

    def update(self, i, x):
        while i < self.N:
            self.A[i] += x
            i += i & (i-1) ^ i

    def query(self, a, b):
        return self.find(b-1) - self.find(a-1)

def main():
    n,m = LI()
    d = collections.defaultdict(list)
    for _ in range(n):
        l,r = LI()
        d[r-l+1].append((l,r))
    r = [n]
    bit = BIT(m+3)
    c = n
    for i in range(2,m+1):
        for a,b in d[i-1]:
            c -= 1
            bit.update(a,1)
            bit.update(b+1,-1)
        t = c
        for j in range(i,m+1,i):
            t += bit.find(j)
        r.append(t)

    return '\n'.join(map(str,r))


print(main())
### BUGGY CODE ###

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

### FIXED CODE ###

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

K, N = map(int, input().rstrip().split())
dist_list = list(map(int, input().rstrip().split()))

result = 10000000
for i, v in enumerate(dist_list):
  offset = 1
  total = 0
  while offset < N:
    if total >= result:
      break
    now_pos = dist_list[((i + offset - 1) % N)]
    next_pos = dist_list[((i + offset) % N)]
    if next_pos < now_pos:
      next_pos += K
    total += next_pos - now_pos
    offset += 1

  if result > total:
    result = total

print(result)


### FIXED CODE ###

K, N = map(int, input().rstrip().split())
dist_list = list(map(int, input().rstrip().split()))

maxdist = 0
for i in range(N - 1):
  dist = dist_list[i + 1] - dist_list[i]
  maxdist = max(maxdist, dist)
else:
  dist = (dist_list[0] + K) - dist_list[-1]
  maxdist = max(maxdist, dist)

print(K - maxdist)
### BUGGY CODE ###

N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
lang=defaultdict(set)
inp=[]
for i in range(N):
    X=list(map(int,input().split()))
    for k in range(X[0]):
        lang[X[k+1]]|={i}
    inp.append(X[1:])
for i in range(N):
    for l in inp[i]:
        branch[i]|=lang[l]
checked={0}
check={0}
while len(check)>0:
    now=check.pop()
    check|=branch[now]-checked
    checked|=branch[now]
    if len(checked)==N:
        break
if len(checked)==N:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

N,M=map(int,input().split())
from collections import defaultdict
lang=[-1]*(M+1)
data=defaultdict(int)
def search(l):
    if lang[l]>=0:
        lang[l]=search(lang[l])
    elif lang[l]<0:
        return l
    return lang[l]
def union(i,j,lang):
    iidx=search(i)
    jidx=search(j)
    if iidx==jidx:
        return lang
    elif lang[iidx]<=lang[jidx]:
        lang[iidx]+=lang[jidx]
        lang[jidx]=iidx
    else:
        lang[jidx]+=lang[iidx]
        lang[iidx]=jidx
    return lang
for i in range(N):
    line=list(map(int,input().split()))
    data[line[1]]+=1
    for k in range(1,line[0]):
        data[line[k+1]]+=1
        lang=union(line[k],line[k+1],lang)
L=set()
for k in range(1,1+M):
    if data[k]==0:continue
    L|={search(k)}
if len(L)>1:
    print('NO')
elif len(L)==1:
    print('YES')