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

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    print(0, flush=True)
    sys.stdout.flush()
    s = input().strip()
    if s == 'Vacant':
        exit()
    ls, rs = s, s
    l, r = 0, N
    while True:
        m = (l + r) // 2
        print(m, flush=True)
        s = input().strip()
        if s == 'Vacant':
            exit()
        if (m - l) % 2 == 0 and s != ls:
            r = m
        elif (m - l) % 2 == 1 and s == ls:
            r = m
        elif (r - m) % 2 == 0 and s != rs:
            l = m
        elif (r - m) % 2 == 1 and s == rs:
            l = m

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    print(0, flush=True)
    s = input().strip()
    if s == 'Vacant':
        return True
    ls, rs = s, s
    l, r = 0, N
    while True:
        m = (l + r) // 2
        print(m, flush=True)
        s = input().strip()
        if s == 'Vacant':
            return True
        if (m - l) % 2 == 0 and s != ls:
            r = m
            rs = s
        elif (m - l) % 2 == 1 and s == ls:
            r = m
            rs = s
        elif (r - m) % 2 == 0 and s != rs:
            l = m
            ls = s
        elif (r - m) % 2 == 1 and s == rs:
            l = m
            ls = s

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

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
#input_list = [int(input()) for i in range(N)]
input_list = list(map(int, input().split()))
ans = 1
#print(input_list)
#print( 0 in input_list)
if (0 in input_list):
    ans = 0
else:
    for input in input_list:
        ans = ans*input
        if ans > 1000000000000000000:
            ans = -1

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
#input_list = [int(input()) for i in range(N)]
input_org = input()
keta = input_org.replace(' ', '')
input_list = list(map(int, input_org.split()))
ans = 1
#print(input_list)
#print( 0 in input_list)
if (0 in input_list):
    ans = 0
elif len(keta) - N > 20:
    ans = -1
else:
    for input in input_list:
        ans = ans*input
        if ans > 1000000000000000000:
            ans = -1

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

N = int(input())
As = list(map(int, input().split(" ")))

s = ""
for i in range(1,N+1):
    for j in range(N):
        if As[j] == i:
            s += str(j+1)+" "
print(s)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split(" ")))
arr = [[] for i in range(N)]

for i,A in enumerate(As):
    arr[A-1] = i+1
print(" ".join(list(map(str, arr))))
### BUGGY CODE ###


def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


#区間更新BIT(BITを2つ用意し、BITの長さをN+2で初期化しておくべし)
def bitaddR(l,r,w,bit1,bit2): #半開区間[l,r)にwを加える

    bitadd(l,-1*w*l,bit1)
    bitadd(r,w*r,bit1)
    bitadd(l,w,bit2)
    bitadd(r,-1*w,bit2)

def bitsumR(r,bit1,bit2): #半開区間[1,r)の区間和

    return bitsum(r,bit1) + r * bitsum(r,bit2)


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

bitA = [0] * (M+2)
bitB = [0] * (M+2)

len_LR = []

for i in range(N):

    l,r = map(int,input().split())
    len_LR.append([r-l,l,r])

len_LR.sort()
len_LR.append([float("inf"),0,float("inf")])
ind = 0
ns = N

for d in range(M):

    d += 1

    while len_LR[ind][2]-len_LR[ind][1]+1 < d:

        bitaddR(len_LR[ind][1] , len_LR[ind][2]+1 , 1 ,bitA,bitB)
        ns -= 1
        ind += 1

    np = 0

    for i in range(d,M+1,d):
        np += bitsumR(i+1,bitA,bitB) - bitsumR(i,bitA,bitB)

    print (ns + np)


### FIXED CODE ###


def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(x,bit): #ind 1～aまでの和を求める
   
    ret = 0
    while x:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


#区間更新BIT(BITを2つ用意し、BITの長さをN+2で初期化しておくべし)
def bitaddR(l,r,w,bit1,bit2): #半開区間[l,r)にwを加える

    bitadd(l,-1*w*l,bit1)
    bitadd(r,w*r,bit1)
    bitadd(l,w,bit2)
    bitadd(r,-1*w,bit2)

def bitsumR(r,bit1,bit2): #半開区間[1,r)の区間和

    return bitsum(r,bit1) + r * bitsum(r,bit2)


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

BIT = [0] * (M+1)
dic = {}
for i in range(N):
    l,r = map(int,input().split())
    if r-l+1 not in dic:
        dic[r-l+1] = []
    dic[r-l+1].append([l,r])

ind = 0
ns = N
ans = []
for d in range(M):

    d += 1

    if d in dic:
        for L,R in dic[d]:

            bitadd(L , 1 ,BIT)
            bitadd(R+1 , -1 , BIT)
            ns -= 1

    nm = 0
    for i in range(d,M+1,d):
        
        nm += bitsum(i,BIT)
    ans.append(nm+ns)

print ("\n".join(map(str,ans)))
### BUGGY CODE ###

N = int(input())
A_list = [int(item) for item in input().split()]

mini = 2020202020 * 200000
for j in range(1,N):
    F, B = A_list[:j], A_list[j:]
    delta = abs(sum(F) - sum(B))
    if delta <= mini:
        mini = delta

print(mini)

### FIXED CODE ###

N = int(input())
A_list = [int(item) for item in input().split()]

all_sum = sum(A_list)

F_sum_list = [A_list[0]]

for j in range(1,N):
    F_sum_list.append(F_sum_list[-1] + A_list[j])

delta_list = [abs(all_sum - 2* i) for i in F_sum_list]

print(min(delta_list))
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
e = []
queue = deque([])
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(temp)
    G[temp[0]].append(temp[1])
    G[temp[1]].append(temp[0])
    if l == 0:
        queue.append(temp[0])
#使えない色
nuc = [[0] for _ in range(N)]
#使った色
auc = []
#答え
ans = [[0] * N for _ in range(N)]
def bfs(x):
    for i in G[x]:
        if ans[x][i] ==0 and ans[i][x] == 0:
            queue.append(i)
            for k in range(N):
                if k not in nuc[x] and k not in nuc[i]:
                    ans[x][i] = k
                    ans[i][x] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    break
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m[0]][m[1]])

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
ans = {}
queue = deque([])
e = []
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(tuple(temp))
    ans[(temp[0],temp[1])] = 0
    ans[(temp[1],temp[0])] = 0
    G[temp[0]].append(temp[1])
    G[temp[1]].append(temp[0])
    if l == 0:
        queue.append(temp[0])
#使えない色
nuc = [[0] for _ in range(N)]
#使った色
auc = []
#答え
def bfs(x):
    k = 1
    for i in G[x]:
        if ans[(x,i)] ==0:
            queue.append(i)
            flag = 1
            while flag:
                if k not in nuc[x]:         
                    ans[(x,i)] = k
                    ans[(i,x)] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    flag = 0
                else:
                    k += 1
                
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m])
### BUGGY CODE ###

import math

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

count = 0
MaxSum = 0

for i in p:
    tmp_slice = p[count:count + K]
    if MaxSum < sum(tmp_slice):
        MaxSum = sum(tmp_slice)
    count += 1 

print((MaxSum+K)/2)


### FIXED CODE ###

N, K = map(int,input().split())
p = tuple(map(int,input().split()))
MaxSum = sum(p[:K])
tmp_SumSlice = MaxSum
for i in range(K, N):
    tmp_SumSlice = tmp_SumSlice + p[i] - p[i - K]
    if MaxSum < tmp_SumSlice:
        MaxSum = tmp_SumSlice
print((MaxSum+K)/2)
### BUGGY CODE ###

#!/usr/bin/evn python3

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

cnt = 0

for i in range(1, N+1):
    if not A:
        break
    else:
        print(A.count(i))
        A =[j for j in A if j != i]
    cnt += 1

print('\n'.join(map(str, [0]*(N-cnt))))

### FIXED CODE ###

#!/usr/bin/env python3

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

lis = [0] * N
for i in A:
    lis[i-1] += 1

for i in range(len(lis)):
    print(lis[i])
### BUGGY CODE ###

import numpy
N = int(input())
a = []
for i in range(N):
    a.append(list(input()))
nda = numpy.array(a)
count = 0
for i in range(N):
    for j in range(N):
        rolled = numpy.roll(numpy.roll(nda, i, axis=0), j, axis=1)
        transed = rolled.T
        if numpy.all(rolled == transed):
            count += 1
print(count)

### FIXED CODE ###

import numpy
N = int(input())
a = []
for i in range(N):
    a.append(list(input()))
nda = numpy.array(a)
count = 0
for i in range(N):
    rolled = numpy.roll(nda, i, axis=1)
    transed = rolled.T
    if numpy.all(rolled == transed):
        count += 1
print(count * N)
### BUGGY CODE ###

#ABC066C
n=int(input())
a=list(map(int, input().split()))
front=[]
back=[]
flg=n%2
for i in range(n//2):
    front.insert(0, a[2*i-flg+1])
    #back.append(a[2*i+flg])
back=[a[2*i+flg] for i in range(n//2)]
if flg==1:
    front.insert(0, a[n-1])
print(' '.join(map(str, front+back)))


### FIXED CODE ###

#ABC066C
n=int(input())
a=list(map(int, input().split()))
flg=n%2
half=n//2
front=[0]*(half+flg)
back=[0]*(half)
for i in range(half):
    front[half+flg-1-i]=a[2*i-flg+1]
    back[i]=a[2*i+flg]
if flg==1:
    front[0]=a[n-1]
print(' '.join(map(str, front+back)))
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = flag2 = False
            for s in S:
                if flag1 and flag2 and int(s) == k:
                    count += 1
                    break
                elif flag1 and int(s) == j:
                    flag2 = True
                elif int(s) == i:
                    flag1 = True

print(count)



### FIXED CODE ###

N = int(input())
S = input()
count = 0

for i in range(1000):
    pin = ("00" + str(i))[-3:]

    j = 0
    for num in S:
        if pin[j] == num:
            j += 1
        if j == 3:
            count += 1
            break

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

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(i8(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = (th+x)*w+tw+y
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check == -1 or check > loop:
                    heapq.heappush(queue,[loop,next_n])

    return used_map[dh*w+dw]

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(ch,cw,dh,dw,road_map))



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

N, M = map(int, input().split())
sum = 0
height = list(map(int, input().split()))
road = []
for i in range(M):
  R = list(map(int, input().split()))
  road.append(R)

for i in range(N):#0~N-1
  p = 0
  s = 0
  for j in range(M):#0~M-1
    if road[j][0] - 1 == i or road[j][1] - 1 == i: 
      s += 1
      if height[road[j][1] - 1] >= height[i] and height[road[j][0] - 1] >= height[i]:
        p += 1
    
  if p == 0 or s == 0:
    sum += 1
print(sum)

### FIXED CODE ###

N, M = map(int, input().split())
sum = 0
height = list(map(int, input().split()))
road = []
for i in range(M):
  R = list(map(int, input().split()))
  road.append(R)

other = []

for i in range(N):
  other.append([0])

for i in range(M):
  other[road[i][0] - 1].append(height[road[i][1] - 1])
  other[road[i][1] - 1].append(height[road[i][0] - 1])
for i in range(N):
  if height[i] > max(other[i]):
    sum += 1

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

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
li=[]

for i in range(m):
    if ab[i][0]==1:
        li.append(ab[i][1])

for j in range(m):
    if ab[j][0] in li:
        if ab[j][1]==n:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

sa=set()
sb=set()

for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        sb.add(b)
    if b==n:
        sa.add(a)

if sa&sb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

def cal(n, S):
    if n == 1:
        return sum(S)
    ans = 0
    if n == 2:
        for i in range(len(S) - 1):
            for j in range(i+1, len(S)):
                ans += S[i] * S[j]
    else:
        for i in range(len(S) - n + 1):
            cross = cal(n-1, S[i+1:])
            cross %= 10 ** 9 + 7
            ans += S[i] * cross
            ans %= 10 ** 9 + 7
    return ans % (10 ** 9 + 7)

ans = 0
for i in range(n):
    ans += cal(i+1, S)

ans %= 10 ** 9 + 7
print(ans)



### FIXED CODE ###

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

ans = 1
for i in S:
    ans *= i + 1
    ans %= 10 ** 9 + 7

print(ans - 1)
### BUGGY CODE ###

k, n = map(int, input().split())
l = list(map(int, input().split()))
c = n*(n-1)//(n-1)
s = [0 for _ in range(c)]
for i in range(c):
  for j in range(n-1):
    if l[j+1] == 0:
      s[i] += abs(k-l[j])
    else:
      s[i] += abs(l[j+1]-l[j])
  temp = l.pop(0)
  l.append(temp)
print(min(s))

### FIXED CODE ###

k,n = map(int, input().split())
l = list(map(int, input().split()))
d = []
for i in range(n):
  if i + 1 < n:
    d.append(l[i+1]-l[i])
  else:
    if 0 in l:
      d.append(k - l[i])
    else:
      d.append(k - l[i] + l[0])
sum = sum(d)
a = []
for i in range(n):
  a.append(sum - d[i])
print(min(a))
### BUGGY CODE ###

import math
n, a, b=[int(i) for i in input().split()]
ab=a-b
t=[int(input()) for i in range(n)]
mx = sum([i//a +1 for i in t])
mi = 1

while mx - mi > 1:
  i = (mx + mi) // 2
    
  ti= [j- i * b for j in t]
  if sum([max(math.ceil(j/ab),0) for j in ti]) <= i:
    mx = i
  else:
    mi = i
  
print(mx)

### FIXED CODE ###

import math
n, a, b=[int(i) for i in input().split()]
ab=a-b
t=[int(input()) for i in range(n)]
mx = sum([i//a +1 for i in t])
mi = 1

while mx - mi > 1:
  i = (mx + mi) // 2
    
  if sum([max(math.ceil((j- i * b) /ab),0) for j in t ]) <= i:
    mx = i
  else:
    mi = i
  
print(mx)
### BUGGY CODE ###

MOD = 2019
L, R = map(int, input().split())

ans = float('inf')
for i in range(L,R):
    if i%MOD==0:
        print(0)
        exit()
    for j in range(i+1,R+1):
        if i%MOD==0:
            print(0)
            exit()
        ans = min(ans,(i*j)%MOD)
print(ans)


### FIXED CODE ###

MOD = 2019
L, R = map(int, input().split())

if R - L > 2019:
    print(0)
    exit()

ans = float('inf')
for i in range(L,R):
    for j in range(i+1,R+1):
        ans = min(ans,(i*j)%MOD)
print(ans)
### BUGGY CODE ###

import itertools
import sys

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

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = read_int_list()

    r = [a-1 for a in read_int_list()]

    d = [[float('inf')]*N for _ in range(N)]

    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    for a in range(N):
        d[a][a] = 0

    res = float('inf')

    for i, j, k in itertools.product(range(N), repeat=3):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import sys

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

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())

    inf = float("inf")
    d = [[inf] * (N + 1) for _ in range(N + 1)]
    for n in range(1, N + 1):
        d[n][n] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        d[a][b] = c
        d[b][a] = c

    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    min_cost = inf
    for p in itertools.permutations(r):
        cost = 0
        for i in range(len(p) - 1):
            src, dst = p[i:i + 2]
            cost += d[src][dst]
        min_cost = min(min_cost, cost)

    print(min_cost)


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

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,m = LI()
    d = [LI() for _ in range(n)]
    a = [1] * (10001)
    t = [set([1]),set([1])]
    for i in range(2,10001):
        if a[i] == 1:
            t.append(set([1,i]))
        else:
            ti = t[a[i]]
            c = i//a[i]
            ti = ti | set(c*_ for _ in ti)
            t.append(ti)
        ai = i*2
        while ai <= 10000:
            a[ai] = i
            ai += i

    e = [0] * 10001
    for l,r in d:
        if l*2 < r:
            for i in range(1,r+1):
                e[i] += 1
            continue
        s = t[r]
        for i in range(l,r):
            s = s | t[i]
        for c in s:
            e[c] += 1
    for i in range(1,m+1):
        print(e[i])


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 ###

H,N=map(int, input().split())
AB = [list(map(int,input().split())) for i in range(N)]
dp=[10**8]*(H+1)
dp[0]=0
for i in range(1,H+1):
  for ab in AB:
    dp[i]=min(dp[max(0,i-ab[0])] + ab[1], dp[i])
print(dp[-1])

### FIXED CODE ###

import numpy as np
H,N=map(int, input().split())
A = [None]*N
B = [None]*N
for i in range(N):
  A[i],B[i]=map(int,input().split())
dp=[10**8]*(H+1)
A = np.array(A)
B = np.array(B)
dp = np.array(dp)
dp[0]=0
for i in range(1,H+1):
  x=np.amin((dp[np.maximum(0,i-A)]+B))
  dp[i]=min(x,dp[i])
print(dp[-1])
### BUGGY CODE ###

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

A.sort()
tmp = A.pop(-1)
index = 0
for _ in range(M):
  tmp //= 2
  index = bisect.bisect_right(A,tmp)
  if index < N - 1:
    bisect.insort_right(A, tmp)
    tmp = A.pop(-1)
A.append(tmp)

print(sum(A))

### FIXED CODE ###

import heapq

def minus_int(s):
  return -1 * int(s)

N, M = map(int, input().split())
A = list(map(minus_int, input().split()))
heapq.heapify(A)
for _ in range(M):
  tmp = int(heapq.heappop(A) / 2)
  heapq.heappush(A, tmp)

print(sum(A) * (-1))
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]

for i in range(N):
    w, v = map(int, input().split())
    wv[i] = [w, v]

dp = [[0 for i in range(2*100)] for j in range(2*10**5)]

for i in range(N):
    for j in range(W+1):
        if (j - wv[i][0] >= 0):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-wv[i][0]] + wv[i][1])
        
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]

for i in range(N):
    w, v = map(int, input().split())
    wv[i] = [w, v]

dp = [[0 for i in range(2*W)] for j in range(2*N)]

for i in range(N):
    for j in range(W+1):
        if (j - wv[i][0] >= 0):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-wv[i][0]] + wv[i][1])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])