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

N, M= map(int, input().split())
L1, R1= map(int, input().split())
Ans = set(range(L1, R1+1))

for x in range(M-1):
    L, R = map(int, input().split())
    List = set(range(L, R+1))
    Ans = (Ans) & (List)

print(len(Ans))

### FIXED CODE ###

N, M= map(int, input().split())
L1, R1= map(int, input().split())

for x in range(M-1):
    L, R = map(int, input().split())
    if L > L1:
        L1 = int(L)
    if R < R1:
        R1 = int(R)

if R1 == L1:
    print("1")
if L1 > R1:
    print("0")
if L1 < R1: 
	print(R1-L1+1)
### BUGGY CODE ###

from sys import stdin
import sys

# A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
# A,B = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]
N = int(input())
S = list(input())
r = []
g = []
b = []
for i in range(N):
    if S[i] == 'R':
        r.append(i+1)
    elif S[i] == 'G':
        g.append(i+1)
    else:
        b.append(i+1)
# print(r)
# print(g)
# print(b)
cnt = 0
for i in range(len(r)):
    for j in range(len(g)):
        for k in range(len(b)):
            temp = [r[i], g[j], b[k]]
            temp.sort()

            if temp[1]-temp[0] != temp[2]-temp[1]:
                cnt += 1
                if temp[2] == b[k] and temp[1]-temp[0] < temp[2]-temp[1]:
                    cnt = cnt+len(b)-1-k
                    break
print(cnt)


### FIXED CODE ###

from sys import stdin
import sys

# A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
# A,B = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]
N = int(input())
S = list(input())
r = []
g = []
b = []
for i in range(N):
    if S[i] == 'R':
        r.append(i+1)
    elif S[i] == 'G':
        g.append(i+1)
    else:
        b.append(i+1)
# print(r)
# print(g)
# print(b)
cnt = len(r)*len(g)*len(b)
for i in range(N):
    for j in range(i+1, N):
        k = 2*j-i
        if k < N and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            cnt -= 1
print(cnt)
### BUGGY CODE ###

n,w = map(int,input().split())
v = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(1,n+1):
  for j in range(w+1):
    if j < v[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i-1][0]]+v[i-1][1])
print(dp[n][w])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
  w_,v_ = map(int,input().split())
  w.append(w_)
  v.append(v_)

dp = [[0]*(W+1) for _ in range(N+1)]

def memo(i,j):
  if dp[i][j]:
    return dp[i][j]
  if i == N:
    dp[i][j] = 0
  elif w[i] > j:
    dp[i][j] = memo(i+1,j)
  else:
    dp[i][j] = max(memo(i+1,j),memo(i+1,j-w[i])+v[i])
  return dp[i][j] 
print(memo(0,W))
### BUGGY CODE ###

import copy
N, M = map(int, input().split())
res = [[] for i in range(N+5)]


for i in range(M) :
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    res[a].append(b)
    res[b].append(a)
    
pre = [-1] * N
d = 1
dl = []
pre[0] = 0

for i in res[0] :
    dl.append((i,0))

while(len(dl) != 0) :
    a,b = dl[0]
    dl.pop(0)
    if(pre[a] != -1) :
        continue
    pre[a] = b
    for i in res[a] :
        if(pre[i] != -1):
            continue
        dl.append((i,a))
        
for i in range(N) :
    if(i == 0) :
        print("Yes")
        continue
    print(pre[i] + 1)

### FIXED CODE ###

import copy
N, M = map(int, input().split())
res = [[] for i in range(N+5)]


for i in range(M) :
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    res[a].append(b)
    res[b].append(a)
    
pre = [-1] * N
dist = [-1] * N
d = 1
dl = []
pre[0] = 0
dist[0] = 0
dl.append(0)

while(len(dl) != 0) :
    a = dl[0]
    dl.pop(0)
    for i in res[a] :
        if(dist[i] != -1):
            continue
        dist[i] = dist[a] + 1
        pre[i] = a
        dl.append(i)
        
for i in range(N) :
    if(i == 0) :
        print("Yes")
        continue
    print(pre[i] + 1)
### BUGGY CODE ###

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

s = list(input())

'''
l = [list(input().split()) for i in range(4)]
'''

ooo = [[] for i in range(26)]

for i in range(n):
    k = ord(s[i]) - 65
    ooo[k].append(i)

o = [1 for i in range(n)]
for i in range(q):
    r,t = input().split()
    if t == "R":
        for j in ooo[ord(r) - 65]:
            if j == n-1:
                o[n-1] = 0
            else:
                o[j+1] += o[j]
                o[j] = 0
    else:
        for j in ooo[ord(r) - 65]:
            if j == 0:
                o[0] = 0
            else:
                o[j-1] += o[j]
                o[j] = 0

print(sum(o))


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
l = [list(input().split()) for i in range(q)]

def rb(x):
    st = x
    for i in range(q):
        if st == n:
            return True
        if st == -1:
            return False
        if l[i][0] == s[st]:
            if l[i][1] == "R":
                st += 1
            else:
                st -= 1
    if st == n:
        return True
    return False
def lb(x):
    st = x
    for i in range(q):
        if st == -1:
            return True
        if st == n:
            return False
        if l[i][0] == s[st]:
            if l[i][1] == "R":
                st += 1
            else:
                st -= 1
    if st == -1:
        return True
    return False
def bs():
    p = n
    ng = -1
    while abs(p - ng) > 1:
        m = (p+ng)//2
        if rb(m):
            p = m
        else:
            ng = m
    return p
def bs2():
    p = -1
    ng = n
    while abs(p-ng) > 1:
        m = (p+ng)//2
        if lb(m):
            p = m
        else:
            ng = m
    return p
print(bs() - bs2() -1)
### BUGGY CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


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


N = inp()
a = np.zeros((N, 3), dtype=int)

for i in range(N):
    a[i] = inp_list()

# dp[i + 1][j]: i日目までの活動で、i日目に活動 j (0: A, 1: B, 2:C) を選んだときの i + 1 日目の幸福の最大値
dp = np.zeros((N + 1, 3), dtype=int)
for i in range(N):
    for j in range(3): # i 日目の活動
        for k in range(3): # i + 1 日目の活動
            if j == k: continue
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i][k])

ans = 0
for i in range(3):
    ans = max(ans, dp[N][i]) # N 日目を終了したときの幸福度 => dp[N][] (N + 1 番目)

# print(a)
# print(dp)
print(ans)


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


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


N = inp()
# a = np.zeros((N, 3), dtype=int)
a = [0] * N

for i in range(N):
    a[i] = inp_list()

# dp[i + 1][j]: i日目までの活動で、i日目に活動 j (0: A, 1: B, 2:C) を選んだときの i + 1 日目の幸福の最大値
# dp = np.zeros((N + 1, 3), dtype=int)
dp = [[0] * 3 for _ in range(N + 1)]
for i in range(N):
    for j in range(3): # i 日目の活動
        for k in range(3): # i + 1 日目の活動
            if j == k: continue
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i][k])

ans = 0
for i in range(3):
    ans = max(ans, dp[N][i]) # N 日目を終了したときの幸福度 => dp[N][] (N + 1 番目)

# print(a)
# print(dp)
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(raw_input())
a = []
count = 0
for i in range(5):
	a.append(int(raw_input()))
b = np.array(a)
num = np.array((n, 0, 0, 0, 0, 0))
move = np.empty(5, dtype=np.int)
while num[5] < n:
	for i in range(5):
		move[i] = min(num[i], b[i])
	num = num - np.hstack((move,0)) + np.hstack((0,move))
	count += 1

print count

### FIXED CODE ###

import numpy as np
import math

n = int(raw_input())
a = []
for i in range(5):
	a.append(int(raw_input()))
b = np.array(a)
print int(math.ceil(n *1. / np.min(b))) + 4
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int, input().split()))
big = []
Max = 0
for i in range(N):
    Sum=0
    if i+K<=N:
        for j in range(K):
            Sum += p[i + j]
        if Sum > Max:
            Max = Sum
            index = i
    else:
        break
for i in range(K):
    big.append(p[index+i])
ans = []
for i in big:
    kitai=0
    for j in range(1,i+1):
        kitai += j
    kitai = kitai / i
    ans.append(kitai)
print(sum(ans))

### FIXED CODE ###

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

s=[0]*(N+1)
for i in range(N):
    s[i + 1] = s[i] + p[i]

Max = 0
for i in range(N):
    Sum=0
    if i+K<=N:
        Sum = s[K+i] - s[i]
        if Sum > Max:
            Max = Sum
            index = i
    else:
        break
Sum=0
for i in range(K):
    kitai=1/2*p[index+i]*(p[index+i]+1)
    kitai = kitai / p[index+i]
    Sum+=kitai
print(Sum)
### BUGGY CODE ###

zeroone = list(input())

cnt = [0]
for i in range(len(zeroone)-1):
    if zeroone[i+1] != zeroone[i]:
        cnt.append(i+1)
cnt.append(len(zeroone))

ans = [0] * (len(zeroone)+1)

if zeroone[0] == "<":
    for j in range(0, cnt[1]):
            ans[j+1] = ans[j] + 1

for i in range(len(zeroone)-1):
    if zeroone[i+1] == "<" and zeroone[i] == ">":
        ans[i+1] = 0
        for j in range(i+1, cnt[cnt.index(i+1) + 1]):
            ans[j+1] = ans[j] + 1

        for k in range(cnt[cnt.index(i+1) - 1], i+1)[::-1]:
            ans[k] = max(ans[k+1] + 1, ans[k])

if zeroone[-1] == ">":
    for k in range(cnt[-2], cnt[-1])[::-1]:
            ans[k] = max(ans[k+1] + 1, ans[k])

print(sum(ans))

### FIXED CODE ###

# coding: utf-8

S = list(input())
S.append("end")

def count(r, l):
    part_sum = ((r-1)*r + (l-1)*l)/2 #"<<<>>>"頂点の値以外
    part_max = max(r, l) #"<<<>>>"頂点の値
    return(part_sum + part_max)

ans = 0
r = l = 0
for i in range(len(S)-1):
    if S[i+1] != S[i] and S[i] == ">": #"<<<>>>"をセットとして足す
        r += 1
        ans += count(r, l)
        r = l = 0
    elif S[i] == "<":
        l += 1
    elif S[i] == ">":
        r += 1
ans += count(r, l) #"<"終わりの時は、その分がカウントされないので足す(ただしl = 0)
print(int(ans))
### BUGGY CODE ###

import numpy as np
N = int(input())
H = [int(i) for i in input().split()]

result ='Yes'
for i in range(N-2):
    num = H[i] - 1
    tmp = H[i+1:]
    if num > np.min(tmp):
        result = 'No'
        break
print(result)

### FIXED CODE ###

import numpy as np
N = int(input())
H = [int(i) for i in input().split()]

result = 'Yes'
for i in range(N-2, -1, -1):
    if H[i] - H[i+1] >= 2:
        result = 'No'
        break
    elif H[i] - H[i+1] == 1:
        H[i] -= 1
    else:
        continue
print(result)
### BUGGY CODE ###

def f(N,L):
    S=N*[0]
    for i in range(N-1):
        S[L[i]-1]+=1
    return S
N=int(input())
L=list(map(int,input().split()))
for j in range(N):
    print(f(N,L)[j])
        

### FIXED CODE ###

def f(N,L):
    S=N*[0]
    for i in range(N-1):
        S[L[i]-1]+=1
    return S
N=int(input())
L=list(map(int,input().split()))
A=f(N,L)
for j in range(N):
    print(A[j])
### BUGGY CODE ###

while True:
    n = int(input())
    if n == 0:
        break

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

    m = 0
    for i in range(0, len(a)):
        for j in range(i + 1, len(a) + 1):
            m = max(m, sum(a[i:j]))

    print(m)

### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break

    s = [0]
    for i in range(n):
        s.append(int(input()) + s[i])

    m = -100000 * 5000
    for i in range(0, n):
        for j in range(i + 1, n + 1):
            m = max(m, s[j] - s[i])

    print(m)
### BUGGY CODE ###

from math import gcd
k = int(input())
li = []
cnt = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for l in range(1, k + 1):
            li.append(gcd(gcd(i, j), gcd(j, l)))
print(sum(li))

### FIXED CODE ###

from math import gcd
k = int(input())
li = []
li2 = [6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
cnt = 0
if k < 170:
    for i in range(1, k + 1):
    	for j in range(1, k + 1):
            for l in range(1, k + 1):
        	    li.append(gcd(gcd(i, j), gcd(j, l)))
    print(sum(li))
else:
    print(li2[k - 170])
### BUGGY CODE ###

N=input()
a=map(int,raw_input().split())
check=[]
ans=0
for i,a_i in enumerate(a):
    if i in check:
        continue
    else:
        if i+1==a[a_i-1]:
            ans+=1
            check.append(a_i-1)
print ans


### FIXED CODE ###

N=input()
a=map(int,raw_input().split())
ans=0
for i,a_i in enumerate(a):
    if i+1==a[a_i-1]:
        ans+=1
print ans/2
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

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

h,w,d=map(int,input().split())

l={}
m={}
for i in range(1,h+1):
  *a,=map(int,input().split())
  l[i]={j+1:k for (j,k) in enumerate(a)}
  for (j,k) in enumerate(a):
    m[k]=(i,j+1)

for _ in range(int(input())):
  a,b=map(int,input().split())
  v=0
  for i in range(a,b,d):
    x1,y1=m[i]
    x2,y2=m[i+d]
    v+=abs(x1-x2)+abs(y1-y2)
  print(v)

### FIXED CODE ###

h,w,d=map(int,input().split())

m={}
for i in range(1,h+1):
  for (j,k) in enumerate(map(int,input().split())):
    m[k]=(i,j+1)

s=[0 for _ in range(1+h*w)]
for i in range(d+1,1+h*w):
  s[i]=s[i-d]+abs(m[i][0]-m[i-d][0])+abs(m[i][1]-m[i-d][1])

for _ in range(int(input())):
  a,b=map(int,input().split())
  print(s[b]-s[a])
### BUGGY CODE ###

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

thre = 10**18

a.sort()
#print(a)

tmp = a[0]
if(tmp==0):
  print(0)
else:
  for i in range(1,n):
    tmp*= a[i]
  if(tmp > thre):
    print(-1)
  else:
    print(tmp)

### FIXED CODE ###

#import numpy as np
n = int(input())
a = list(map(int,input().split()))

thre = 10**18

a.sort(reverse=True)
#print(a)

flag = 0
tm = a[n-1]
if(tm==0):
  print(0)
else:
  tmp=a[0]
  for i in range(1,n):
    tmp*= a[i]
    if(tmp > thre):
      flag = 1
      break
  if(flag == 1):
    print(-1)
  else:
    print(tmp)
### BUGGY CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

p = []
i = 0
while i < len(s) - 1:
    if s[i] == 'A' and s[i+1] == 'C':
        p.append(i)
        i += 2
    else:
        i += 1

for i in range(q):
    l, r = read_line(int, int)
    l, r = l - 1, r - 1

    if len(p) == 0:
        print(0)
        continue

    c = 0
    for j in range(len(p)):
        pp = p[j]
        if l <= pp:
            break
        c += 1

    for jj in reversed(range(j, len(p))):
        pp = p[jj]
        if pp + 1 <= r:
            break
        c += 1

    print(len(p) - c)


### FIXED CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

m = [0 for _ in range(len(s) + 1)]

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)

    if c == 0:
        print(0)
        continue
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

N = int(input())
K = [0]*N
A = [int(i) for i in input().split()]

for i in range(N-1):
    K[A[i]-1] += 1
for i in K:
    print(i)
### BUGGY CODE ###

s = input()

ans = 0
while s.count('ABC')>0:
    ans += s.count('ABC')
    s=s.replace('ABC','BCA')

print(ans)


### FIXED CODE ###

s = input()
s = s.replace("BC", "D")
#print(s)

ans = 0
cnt_a = 0
for i in range(len(s)):
    if s[i] in ["B", "C"]:
        cnt_a = 0
    elif s[i] == "A":
        cnt_a += 1
    elif s[i] == "D":
        ans += cnt_a

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

h,w,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]
bit = list([0 for i in range(w)] for _ in range(h))
for j,k in l:
    count_h[j-1] += 1
    count_w[k-1] += 1
    bit[j-1][k-1] = 1
h_max = max(count_h)
w_max = max(count_w)
h_kouho = []
w_kouho = []
ans = h_max + w_max - 1
for i in range(h):
    if count_h[i]==h_max:
        h_kouho.append(i)
for j in range(w):
    if count_w[j]==w_max:
        w_kouho.append(j)

for i in w_kouho:
    for j in h_kouho:
        if bit[j][i] == 0:
            ans += 1
            print(ans)
            exit()
print(ans)


### FIXED CODE ###

h,w,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]

for j,k in l:
    count_h[j-1] += 1
    count_w[k-1] += 1

h_max = max(count_h)
w_max = max(count_w)
h_kouho = []
ko_hh = [0 for _ in range(h)]
ko_ww = [0 for _ in range(w)]
w_kouho = []
ans = h_max + w_max -1
for i in range(h):
    if count_h[i]==h_max:
        h_kouho.append(i)
        ko_hh[i] = 1
for j in range(w):
    if count_w[j]==w_max:
        w_kouho.append(j)
        ko_ww[j] = 1


ans_kouho = len(h_kouho) * len(w_kouho)
su = 0
for j,k in l:
    if ko_hh[j-1]==1 and ko_ww[k-1]==1:
        su += 1
if su==ans_kouho:
    print(ans)
else:
    print(ans+1)
### BUGGY CODE ###

import bisect
import collections
from collections import deque

n=int(input())
a= list(map(int, input().split()))
a1= [list(map(int, input().split())) for i in range(n-1)]

g=[[] for i in range(n)]

for x,y in a1:
    g[x-1].append(y-1)
    g[y-1].append(x-1)


vis = [0] * n
order = []
parent = [0] * (n + 1)
s = [0]

while len(s):
    x = s.pop()
    vis[x] = 1
    order.append(x)
    for y in g[x]:
        if vis[y]: continue
        s.append(y)
        parent[y] = x


ans=[0]*n
LIS = [[0] for i in range(n)]

for x in order:
    LIS[x]=LIS[parent[x]][:]
    if a[x] > LIS[x][-1]:
        LIS[x].append(a[x])
    else:
        LIS[x][bisect.bisect_left(LIS[x], a[x])] = a[x]
    ans[x]=len(LIS[x])-1

for i in range(n):
    print(ans[i])

### FIXED CODE ###

from bisect import bisect_left
from collections import deque

N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
INF=float('inf')
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = max(i,ans[p])

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

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

N, X, Y = map(int, input().split())
dists = [[-1] * N for _ in range(N)]
graph = [[1]]
graph .extend([i - 1, i + 1] for i in range(1, N - 1))
graph.append([N - 2])
graph[X - 1].append(Y - 1)
graph[Y - 1].append(X - 1)

d_count = [0] * N

for i in range(N):
    q = [i]
    dists[i][i] = 0
    while len(q) >= 1:
        n = q.pop(0)
        for n_next in graph[n]:
            if dists[i][n_next] >= 0:
                continue
            dists[i][n_next] = dists[i][n] + 1
            d_count[dists[i][n_next]] += 1
            q.append(n_next)

print("\n".join(str(d_count[i] // 2) for i in range(1, N)))

### FIXED CODE ###

N, X, Y = map(int, input().split())
dists = [[-1] * N for _ in range(N)]
graph = [[1]]
graph .extend([i - 1, i + 1] for i in range(1, N - 1))
graph.append([N - 2])
graph[X - 1].append(Y - 1)
graph[Y - 1].append(X - 1)

d_count = [0] * N

for i in range(N):
    q = [i]
    dists[i][i] = 0
    while len(q) >= 1:
        n = q.pop(0)
        for n_next in graph[n]:
            if dists[i][n_next] >= 0:
                continue
            dists[i][n_next] = dists[i][n] + 1
            d_count[dists[i][n_next]] += 1
            q.append(n_next)

print("\n".join(str(d_count[i] // 2) for i in range(1, N)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
ans=10**20
for i in range(N):
    for j in range(N):
        if i!=j and x[i]<x[j]:
            xmin=x[i]
            xmax=x[j]
        else:
            continue
        for k in range(N):
            for l in range(N):
                if k!=l and y[k]<y[l]:
                    ymin=y[k]
                    ymax=y[l]
                else:
                    continue
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=x[m] and x[m]<=xmax and ymin<=y[m] and y[m]<=ymax:
                        ct+=1
                if ct>=K:
                    ans=min(ans,A)
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
point=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    point.append([xt,yt])
ans=10**20
x.sort()
y.sort()
point.sort(key=lambda x:x[1])


for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            ymin=y[k]
#            ymax=y[l]
#            
            ct=0
            for p in point:
                if xmin<=p[0] and p[0]<=xmax and ymin<=p[1]:
                    ct+=1
                if ct==K:
                    A=(xmax-xmin)*(p[1]-ymin)
                    ans=min(ans,A)
                    break
print(ans)
### BUGGY CODE ###

L = int(input())

n = 0
while 2**n < L:
    n += 1

side_lst = []
    
rest = L - 2**(n-1)
next_num = 2**(n-1)

m = n
while rest > 0:
    if rest >= 2**(m-2):
        side_lst.append([m-1, n, next_num])
        next_num += 2**(m-2)
        rest -= 2**(m-2)
    m -= 1
    
print(n, len(side_lst)+(n-1)*2)
for i in side_lst:
    print(i[0], i[1], i[2])
    
for i in range(1, n):
    print(i, i+1, 0)
    print(i, i+1, 2**(i-1))

### FIXED CODE ###

L = int(input())

n = 0
while 2**n <= L:
    n += 1

side_lst = []
    
rest = L - 2**(n-1)
next_num = 2**(n-1)

m = n
while rest > 0:
    if rest >= 2**(m-2):
        side_lst.append([m-1, n, next_num])
        next_num += 2**(m-2)
        rest -= 2**(m-2)
    m -= 1
    
print(n, len(side_lst)+(n-1)*2)
for i in side_lst:
    print(i[0], i[1], i[2])
    
for i in range(1, n):
    print(i, i+1, 0)
    print(i, i+1, 2**(i-1))