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

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
import networkx as nx
G = nx.Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())

G.add_nodes_from(list(range(1,N+1)))
for _ in range(M):
    A,B = map(int,input().split())
    G.add_edge(A, B)

shortestPath = nx.shortest_path(G, target=1)
if len(shortestPath) != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(shortestPath[i][1])

# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
s=input()
sl=len(s)
if len(s)>1:
  while True:
    ll=len(s)
    s=s.replace('01','')
    s=s.replace('10','')
    if ll==len(s):
      break

print(sl-len(s))



### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
s=input()
sl=len(s)
l=list(s)
nl=[l.pop(0)]
si=0
while len(l)>0:
  c=l.pop(0)
  if len(nl)>0:
    if nl[si]!=c:
      nl.pop(si)
      si=si-1
    else:
      nl.append(c)
      si=si+1
  else:
    nl=[c]
    si=0

print(sl-len(nl))
### BUGGY CODE ###

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

S = [0]
for i in range(N):
    S.append(A[i]+S[i])

pS = []
for j in range(N):
    for k in range(j, N):
        pS.append((S[k+1]-S[j])%M==0)

print(sum(pS))

### FIXED CODE ###

from collections import Counter
from itertools import accumulate
 
N, M = map(int, input().split())
acc = [0]
acc.extend(accumulate(map(int, input().split())))

acc = Counter(a%M for a in acc)
print(sum(c*(c-1)//2 for c in acc.values()))
### BUGGY CODE ###

import functools
n = int(input())
a_list = list(map(int,input().split()))

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x%y==0:
        return y
    else:
        while x%y!=0:
            x,y = y,x%y
        return y

res = []
tmp = []
for i in range(n):
    if a_list[i] in tmp:
        continue
    if a_list[:i]==[]:
        res.append(functools.reduce(gcd, a_list[i+1:]))
    elif a_list[i+1:]==[]:
        res.append(functools.reduce(gcd, a_list[:i]))
    else:
        l_gcd = functools.reduce(gcd, a_list[:i])
        r_gcd = functools.reduce(gcd, a_list[i+1:])
        res.append(gcd(l_gcd,r_gcd))
    tmp.append(a_list[i])
print(max(res))

### FIXED CODE ###

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if y==0:
        return x
    else:
        while x%y!=0:
            x,y = y,x%y
        return y

res = []
l_gcd = [0]*(n+2)
r_gcd = [0]*(n+2)
for i in range(n+1):
    if i ==0:
        l_gcd[i] = 0
        r_gcd[n-i+1] = 0
        continue
    l_gcd[i] = gcd(l_gcd[i-1], a_list[i-1])
    r_gcd[n-i] = gcd(r_gcd[n-i+1], a_list[n-i])

for i in range(n+1):
    res.append(gcd(l_gcd[i],r_gcd[i+1]))

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

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

costs = [float('inf')] * N
costs[0] = 0
for i in range(1,N):
  s = max(i-K, 0)
  mn = float('inf')
  for j in range(s,i):
    cur = costs[j] + abs(h[i] - h[j])
    mn = min(mn,cur)
  costs[i] = mn
print(costs[-1])

### FIXED CODE ###

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

def aa (n,k,ll):
  dp = [0] * n
  for i in range(1,n):
    s = max(i-k,0)
    mn = float('inf')
    for a,b in zip(dp[s:i],ll[s:i]):
      cur = a + abs(ll[i]-b)
      if cur < mn:
        mn = cur
  
    dp[i] = mn
  print(dp[-1])

aa(N,K,h)
### BUGGY CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
dp = [0 for i in range(len(s)+1)]
u = 1
for i in range(1,len(s)+1):
    k = len(s) - i
    dp[i] = (dp[i-1] + int(s[k])*u)%2019
    u *= 10%2019
    mods[dp[i]] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)//2
print(cnt)

### FIXED CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
t = 0
u = 1
for i in range(1,len(s)+1):
    t = (t + int(s[-i])*u)%2019
    u = u*10%2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))
### BUGGY CODE ###

def solve():
    N = int(input())
    Ss = input().rstrip()

    for L in reversed(range(1, N//2+1)):
        setCand = set()
        RHs = []
        for i in range(N-L+1):
            RH = hash(Ss[i:i+L])
            RHs.append(RH)
            if i-L >= 0:
                setCand.add(RHs[i-L])
            if RH in setCand:
                print(L)
                break
        else:
            continue
        break
    else:
        print(0)


solve()


### FIXED CODE ###

N = int(input())
Ss = input()

def isOK(k):
    strAs = ['' for _ in range(N)]
    strBs = ['' for _ in range(N)]
    for L in range(N-k+1):
        R = L+k-1
        ss = Ss[L:R+1]
        strAs[R] = ss
        strBs[L] = ss

    strCands = set()
    for iEn in range(N-1):
        if strAs[iEn] != '':
            strCands.add(strAs[iEn])
        if strBs[iEn+1] != '' and strBs[iEn+1] in strCands:
            return True

    return False


ng, ok = N//2 + 1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

b = input()
l = list(map(int, input().split()))
plus = 0
for i in range (len(l)-1):
	v = l[0]
	l.pop(0)
	if l.count(v)>0:
		plus += 1
        
if plus > 0:
  	print('NO')
else:
	print('YES')

### FIXED CODE ###

b = input()
l = list(map(int, input().split()))
ldistinct = set(l)

if len(ldistinct) < len(l):
	print('NO')
else:
	print('YES')
### BUGGY CODE ###

A, B = input().split()
A = int(A)
B = int(B)
ans = A
for i in range(A + 1, B + 1):
    ans ^= i
print(ans)

### FIXED CODE ###

A,B = map(int, input().split())


def f(n):
    if n % 4 == 0:
        return n
    elif n % 4 == 1:
        return 1
    elif n % 4 == 2:
        return n ^ (n-1) ^ (n-2)
    elif n % 4 == 3:
        return 0

print(f(A-1) ^ f(B))
### 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 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())
p = list(map(int, input().split()))

uf = UnionFind(N)

for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

D = uf.all_group_members()

ans = 0

for L in D.values():
  temp = set()
  for i in L:
    temp.add(p[i]-1)
  ans += len(set(L) & temp)

print(ans)

### 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
    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 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())
P = list(map(int, input().split()))

uf = UnionFind(N)

for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

ans = 0

for i, p in enumerate(P):
  if uf.same(i, p-1):
    ans += 1

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

import numpy as np


def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7
    
    DP_table = np.zeros(13)
    
    # 初期化
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[i] = 1
    else:
        DP_table[int(digit)] = 1
    
    # DP
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            transition_matrix = np.zeros((13, 13))
            for j in range(10):
                for k in range(13):
                    transition_matrix[(j * multiplier + k) % 13, k] += 1
        else:
            transition_matrix = np.zeros((13, 13))
            devided = int(digit) * multiplier
            for k in range(13):
                transition_matrix[(devided + k) % 13, k] = 1
        
        DP_table = np.dot(transition_matrix, DP_table)
        DP_table %= MOD

    print(int(DP_table[5]))

    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

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

import math

q = int(input())

def is_prime(a):
    if a == 1:
        return False
    for i in range(2,int(math.sqrt(a)+1)):
        if a%i == 0:
            return False
    else:
        return True

s = [0 for i in range(0,100001)]
for i in range(3,100001,2):
    if is_prime(i) and is_prime((i+1)//2):
        s[i] = 1

for i in range(q):
    l,r = map(int,input().split())
    ans = sum(s[l:r+1])
    print(ans)

### FIXED CODE ###

import math

q = int(input())

def is_prime(a):
    if a == 1:
        return False
    for i in range(2,int(math.sqrt(a)+1)):
        if a%i == 0:
            return False
    else:
        return True

s = [0 for i in range(0,100001)]
for i in range(3,100001,2):
    if is_prime(i) and is_prime((i+1)//2):
        s[i] = 1

s2 = [0 for i in range(0,100001)]
tmp = 0
for i in range(100001):
    tmp += s[i]
    s2[i] = tmp

for i in range(q):
    l,r = map(int,input().split())
    ans = s2[r] - s2[l-1]
    print(ans)
### BUGGY CODE ###

N,W = map(int,input().split())
#N,W = [3,8]
wvlist = [list(map(int,input().split())) for _ in range(N)]
INF = 10**15
ans = INF
#初期条件
dp = [[INF for _ in range(N*1000+1)] for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for v in range(N*1000+1):
        if v-wvlist[i][1]>=0:
            dp[i+1][v] = min(dp[i+1][v],dp[i][v-wvlist[i][1]]+wvlist[i][0])
        dp[i+1][v] = min(dp[i+1][v],dp[i][v])
        
for i in range(N*1000+1):
    if W >= dp[N][i]:
        ans = i
        
print(ans)
    

### FIXED CODE ###

import numpy as np
N,W = map(int,input().split())
#N,W = [3,8]
wvlist = [list(map(int,input().split())) for _ in range(N)]
INF = 10**15
ans = INF

#初期条件
#dp = [[INF for _ in range(N*1000+1)] for i in range(N+1)]
dp = np.full((N+1,N*1000+1),INF)
dp[0][0] = 0

for i in range(N):
    dp[i+1][:wvlist[i][1]] = dp[i][:wvlist[i][1]]
    dp[i+1][wvlist[i][1]:] = np.minimum(dp[i][wvlist[i][1]:],dp[i][:-wvlist[i][1]]+wvlist[i][0])
        
for i in range(N*1000+1):
    if W >= dp[N][i]:
        ans = i
        
print(ans)
### BUGGY CODE ###

from collections import defaultdict


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
dp = defaultdict(int)
for a in A:
    for prev in list(dp.keys()):
        if abs(prev - a) <= K:
            dp[a] = max(dp[prev] + 1, dp[a])
    dp[a] = max(1, dp[a])
print(max(dp.values()))

### FIXED CODE ###

def update(i, v):
    i += length
    dp[i] = max(v, dp[i])
    while i:
        i //= 2
        dp[i] = max(dp[2 * i], dp[2 * i + 1])


def query(l, r):
    l += length
    r += length
    res = 0
    while l < r:
        if l % 2:
            res = max(dp[l], res)
            l += 1
        l //= 2
        if r % 2:
            res = max(dp[r - 1], res)
            r -= 1
        r //= 2
    return res


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
length = 1 << 20
dp = [0] * (2 * length)
res = 0
for a in A:
    cur = query(max(a - K, 0), min(a + K + 1, 300005))
    res = max(res, cur + 1)
    update(a, cur + 1)
print(res)
### BUGGY CODE ###

N = int(input())
c = 0
n = 0
list = []
for l in range(1,N+1):
    list = []
    for i in range(1,N+1):
        for j in range(1,N-i):
            for k in range(1,N-j):
                #print(i,j,k,l)
                if i*i + j*j + k*k + i*j +j*k + i*k > l:
                    break;
                if i*i + j*j + k*k + i*j +j*k + i*k == l:
                    list.append(1)
                    break;
    print(sum(list))

### FIXED CODE ###

N = int(input())
list = [0]*(N+1)
for i in range(1,100):  
    for j in range(1,100):
        a = i*i + j*j + i*j
        for k in range(1,100):
            a = i*i + j*j + k*k + i*j +j*k + i*k
            if a <= N:
                list[a] += 1
for i in range(1,N+1):
    print(list[i])
### BUGGY CODE ###

from sys import stdin


def totalcost_recur(i,cost,N,lookup):
  if i>=N:
    return 0
  if i in lookup:
      return lookup[i]
  option1 = abs(cost[i]-cost[i+1]) + totalcost_recur(i+1,cost,N,lookup)
  ans = option1
  if i+2<=N:
    option2 = abs(cost[i]-cost[i+2]) + totalcost_recur(i+2,cost,N,lookup)
    ans = min(option2,ans)
  lookup[i] = ans
  return ans



def totalcost_dp(cost,N,k):
    dp = [float('inf')]*(N+1)
    dp[1] = 0
    
    
    for i in range(1,N+1):
        
        for j in range(i+1,k+i+1):
            if j < N+1:
                dp[j] = min(dp[j],dp[i]+abs(cost[i]-cost[j]))
                
            
        
        

    return dp[N]


n ,k= map(int,stdin.readline().split())
cost = list(map(int,stdin.readline().split()))
cost = [0]+cost


print(totalcost_dp(cost,n,k))

### FIXED CODE ###


def totalcost_dp(cost,N,k):
    dp = [float('inf')]*(N+1)
    dp[1] = 0
    
    
    for i in range(1,N+1):
        
        for j in range(i+1,k+i+1):
            if j < N+1:
                dp[j] = min(dp[j],dp[i]+abs(cost[i]-cost[j]))
                
    return dp[N]


n ,k= map(int,input().split())
cost = list(map(int,input().split()))
cost = [0]+cost
print(totalcost_dp(cost,n,k))
### BUGGY CODE ###

from math import factorial

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod



n,a,b=map(int, input().split())
mo=10**9+7

fn=2*10**5
fac=[0]*fn
fac[1]=n
for i in range(2,fn):
    fac[i]=fac[i-1]*(n-i+1)*power(i, mo-2, mo) % mo

print((power(2, n, mo)-1-fac[a]-fac[b])%mo)

### FIXED CODE ###

import time
from math import factorial

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=1
    for i in range(n, n-k, -1):
        a=a * i % mod
    b=framod(k, mod)
    return (a * power(b, mod-2, mod)) % mod

n,a,b=map(int, input().split())
mo=10**9+7

fn=2*10**5
fac=[0]*fn
fac[1]=n

print((power(2, n, mo)-1-comb(n,a,mo)-comb(n,b,mo))%mo)
### BUGGY CODE ###

import sys
i=1
while True:
    x=sys.stdin.readline().strip()
    if x==0:
        break
    print("Case %d: %s"%(i,x))
    i+=1

### FIXED CODE ###

import sys
i=1
while True:
    x=sys.stdin.readline().strip()
    if x=="0":
        break
    print("Case %d: %s"%(i,x))
    i+=1
### BUGGY CODE ###

n = int(input())
strings = []
answer = 0
for i in range(n):
  strn = input()
  strn = ''.join(sorted(strn))
  answer += strings.count(strn)
  strings.append(strn)
print(answer)

### FIXED CODE ###

n = int(input())
strings = {}
answer = 0
for i in range(n):
  string = input()
  string = ''.join(sorted(string))
  if string not in strings:
    strings[string]=1
  else:
    answer += strings[string]
    strings[string] += 1
print(answer)
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
hlist=list(map(int,input().split()))
 
mins=[0]

if n == 2:
	print(abs(hlist[1]-hlist[0]))
	sys.exit()

for i in range(1,n):
	tmplist=[]
	tmp=hlist[i]
	for j in range(min(k,i)):
		tmplist.append(mins[i-j-1]+abs(tmp-hlist[i-j-1]))
	mins.append(min(tmplist))
	

print(mins[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
hlist=list(map(int,input().split()))
 
mins=[0]
 
for i in range(1,n):
	if i == 1:
		mins.append(abs(hlist[1]-hlist[0]))
		continue
	
	tmplist=[]
	tmp=hlist[i]
	for j in range(min(k,i)):
		tmplist.append(mins[i-j-1]+abs(tmp-hlist[i-j-1]))
	mins.append(min(tmplist))
 
print(mins[n-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
L=[]
dis=[A[0]]
L.append(A[0])
L.append(A[0])
#print(L)
num=0
for i in range(1,len(A)):
    ind=dis.index(max(dis))
    num+=dis[ind]
    #L.insert(ind+1,A[i])
    del dis[ind]
    dis[ind:ind]=[A[i],A[i]]
print(num)
#print(L)
#print(dis)

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
dis=deque([A[0]])
num=0
for i in range(1,len(A)):
    num+=dis.popleft()
    #L.insert(ind+1,A[i])
    dis.append(A[i])
    dis.append(A[i])
print(num)
#print(L)
#print(dis)
### BUGGY CODE ###

n = int(input())
from collections import defaultdict
d = defaultdict(list)
X = []
xl = [tuple(map(int,input().split())) for i in range(n)]
for x,l in xl:
    d[x].append(x-l)
    d[x].append(x+l)
    X.append(x)

X.sort()

i = 1

while len(X)>i:
    x_1 = X[i-1]
    x_2 = X[i]
    min_1 , max_1 = d[x_1]
    min_2 , max_2 = d[x_2]

    if max_1 > min_2:
        if max_2 >= max_1:
            del d[x_2]
            X.pop(i)
            i -= 1
        else:
            del d[x_1]
            X.pop(i-1)
            i -= 1

    i += 1
ans = len(d)
print(ans)


### FIXED CODE ###

n = int(input())
from collections import defaultdict
d = defaultdict(list)
X = []
xl = [tuple(map(int,input().split())) for i in range(n)]
for x,l in xl:
    d[x].append(x-l)
    d[x].append(x+l)
    X.append(x)

X.sort()


n_remove = 0


for i in range(1,n):
    x_1 = X[i-1]
    x_2 = X[i]
    min_1 , max_1 = d[x_1]
    min_2 , max_2 = d[x_2]

    if max_1 > min_2:
        n_remove += 1
        if max_2 >= max_1:
            d[x_2] = d[x_1]
            X[i] = X[i-1]


ans = n - n_remove
print(ans)
### BUGGY CODE ###

import math
def multi_gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = math.gcd(ans, a[i])
    #print(ans)
    return ans
K = int(input())
sum_ = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            sum_ += multi_gcd([i, j, k])
print(sum_)


### FIXED CODE ###

import math
k = int(input())
ans = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        gcd1 = math.gcd(i, j)
        for l in range(1, k + 1):
            gcd2 = math.gcd(gcd1, l)
            ans += gcd2
print(ans)
### BUGGY CODE ###

c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
l=list(set(s))
l.sort()
for i in t:
	for j in l:
		if int(i)==int(j):
			c +=1
			break
print(c)


### FIXED CODE ###

c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
s.sort()

print(len(set(s)&set(t)))
### BUGGY CODE ###

import heapq
import sys
sys.setrecursionlimit(10 ** 7)

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

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))

for i in range(q):
    event.append((int(input()),2,i))
event.sort()

ans=[0]*q

stop=set()
hq=[]
for t,op,x in event:
    if op==1:
        heapq.heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heapq.heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()