Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(2**16)


def getfly(x,a,m,i):
        if x==1 and i!=0:
            return i
        else:
            return getfly((a*x)%m,a,m,i+1)

def getgcd(a,b):
    #print a,b
    (a,b)=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        return getgcd(b,a%b)

while(1):
    indata=[int(x) for x in raw_input().split()]
    if indata[0]==0:
        break
    else:
        a=indata[0::2]
        m=indata[1::2]
        A=[]
        for i in range(3):
            A.append(getfly(1,a[i],m[i],0))
        #print A
        gab=getgcd(A[0],A[1])
        lab=A[0]*A[1]/gab
        gac=getgcd(A[2],lab)
        ans=A[2]*lab/gac
        print ans

### FIXED CODE ###

def getfly(x,a,m,i):
        if x==1 and i!=0:
            return i
        else:
            return getfly((a*x)%m,a,m,i+1)

def getgcd(a,b):
    #print a,b
    (a,b)=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        return getgcd(b,a%b)

while(1):
    indata=[int(x) for x in raw_input().split()]
    if indata[0]==0:
        break
    else:
        a=indata[0::2]
        m=indata[1::2]
        A=[]
        for j in range(3):
            i=0
            x=1
            p=a[j]
            q=m[j]
            while (x!=1 or i==0):
                i+=1
                x=p*x%q
            A.append(i)
        gab=getgcd(A[0],A[1])
        lab=A[0]*A[1]/gab
        gac=getgcd(A[2],lab)
        ans=A[2]*lab/gac
        print ans
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N, K = mii()

channels = defaultdict(list)
for i in range(N):
    s, t, c = mii()
    channels[c].append([s, t])

for name, times in channels.items():
    times.sort()
    new = []
    for i, time in enumerate(times):
        s, t = time
        if i == 0:
            new.append([s, t])
            continue
        if s == new[-1][1]:
            new[-1][1] = t
        else:
            new.append([s, t])
    channels[name] = new

timetable = [0] * 100010
for name, times in channels.items():
    for s, t in times:
        timetable[s] += 1
        timetable[t+1] -= 1

acc = accumulate(timetable)

print(max(acc))


### FIXED CODE ###

from collections import defaultdict
from itertools import accumulate


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

timetables = defaultdict(list)
for i in range(N):
    s, t, c = map(int, input().split())
    timetables[c].append([s, t])

for name, times in timetables.items():
    times.sort()
    new = []
    for i, time in enumerate(times):
        s, t = time
        if i == 0:
            new.append([s, t])
            continue
        if s == new[-1][1]:
            new[-1][1] = t
        else:
            new.append([s, t])
    timetables[name] = new

time_count = [0] * 100010
for name, times in timetables.items():
    for s, t in times:
        time_count[s] += 1
        time_count[t + 1] -= 1

acc = accumulate(time_count)

print(max(acc))
k = int(input())

if k < 11:
    print(k)
else:
    l = [i for i in range(1, 10)]
    cntotal = 9
    while cntotal < k:
        n = []
        cnt = 0
        for x in l:
            y = x * 10
            b = x % 10
            if b == 0:
                n.append(y)
                n.append(y+1)
                cnt += 2
            elif b == 9:
                n.append(y+b-1)
                n.append(y+b)
                cnt += 2
            else:
                n.append(y+b-1)
                n.append(y+b)
                n.append(y+b+1)
                cnt += 3
        cntotal += cnt
        l = n[:]

print(l[k - (cntotal - cnt) - 1])


### FIXED CODE ###

k = int(input())

ans = []


l = [i for i in range(1, 10)]
ans.extend(l)

while len(ans) <= 110000:
    n = []
    cnt = 0
    for x in l:
        y = x * 10
        b = x % 10
        if b == 0:
            n.append(y)
            n.append(y+1)
        elif b == 9:
            n.append(y+b-1)
            n.append(y+b)
        else:
            n.append(y+b-1)
            n.append(y+b)
            n.append(y+b+1)
    l = n[:]
    ans.extend(l)

print(ans[k-1])
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in range(1, N): A[i] += A[i - 1]
for i in range(1, M): B[i] += B[i - 1]
print(A)
print(B)
ans, j = 0, M - 1
for i in range(N):
    if A[i] > K: break
    while B[j] > K - A[i]: j -= 1
    ans = max(ans, i + j + 2)
    j = M - 1
print(ans)


### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
	a.append(a[i] + A[i])
for i in range(M):
	b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
	if a[i] > K: break
	while b[j] > K - a[i]: j -= 1
	ans = max(ans, i + j)
print(ans)
price = int(input())

comma_price = math.ceil(price / 1000)
comma_price *= comma_price

print(comma_price - price)


### FIXED CODE ###

import math
price = int(input())
 
comma_price = math.ceil(price / 1000)
comma_price *= 1000
 
print(comma_price - price)
from collections import defaultdict 

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

if M == 0:
  print(-1)
  exit()

INF = 10**20
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(N)]
G = defaultdict(dict)
lines = [set() for _ in range(N)]
for p,q,c in pqc:
  G[(p,c)][(q,c)] = G[(q,c)][(p,c)] = 0
  lines[p].add(c)
  lines[q].add(c)
  
for v in range(N):
  if len(lines[v])>1:
    tmp = list(lines[v])
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        G[(v,tmp[i])][(v,tmp[j])] = G[(v,tmp[j])][(v,tmp[i])] = 1
        
def dijkstra(start = 0):
    from heapq import heappop, heappush
    d = defaultdict(lambda:INF)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d
  
ans = INF
for c in lines[0]:
  d = dijkstra((0,c))
  ans = min(ans, min(d[(N-1,c2)] for c2 in lines[N-1]))
  
print(ans+1 if ans < INF else -1)

### FIXED CODE ###

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

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()
from collections import defaultdict

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

d = defaultdict(list)
root = []
p = 1

s, e = 0, 0

for i in range(10):
    d[p].append(i)
    root.append(A[p - 1])
    if len(d[p]) == 2:
        s = d[p][0]
        e = i
        break
    p = A[p - 1]
#print(s, e)

#print(root)

n = (K - s) % (e - s)
#print(n)
print(root[s + n - 1])

### FIXED CODE ###

from collections import defaultdict

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

d = defaultdict(list)

p = 1
root = []

#s, e = 0, 0

for i in range(K):
    d[p].append(i)
    root.append(p)
    if len(d[p]) == 2:
        s = d[p][0]
        e = i
        n = (K - s) % (e - s)
        p = root[s + n]
        break
    p = A[p - 1]
#print(s, e)

#print(root)

#n = (K - s) % (e - s)
print(p)
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

q = ni()

lh = []
hh = []
ln = 0
hn = 0
ls = 0
hs = 0
off = 0
for z in range(q):
    line = na()
    if line[0] == 1:
        _, a, b = line
        off += b

        if len(lh) > 0:
            mid = -lh[0]
            if a <= mid:
                heapq.heappush(lh, -a)
                ls += a
                ln += 1
            else:
                heapq.heappush(hh, a)
                hs += a
                hn += 1
        else:
            heapq.heappush(lh, -a)
            ls += a
            ln += 1

        while ln < hn:
            mx = heapq.heappop(hh)
            hs -= mx
            hn -= 1
            ls += mx
            ln += 1
            heapq.heappush(lh, -mx)

        while ln > hn + (ln+hn)%2:
            mx = -heapq.heappop(lh)
            ls -= mx
            ln -= 1
            heapq.heappush(hh, mx)
            hs += mx
            hn += 1
    else:
        lls = -lh[0]*ln - ls
        hhs = hs - (-lh[0]*hn)
        print(-lh[0], lls+hhs+off)

### FIXED CODE ###

import sys
import heapq

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

q = ni()

lh = []
hh = []
ln = 0
hn = 0
ls = 0
hs = 0
off = 0
for z in range(q):
    line = na()
    if line[0] == 1:
        _, a, b = line
        off += b

        if len(lh) > 0:
            mid = -lh[0]
            if a <= mid:
                heapq.heappush(lh, -a)
                ls += a
                ln += 1
            else:
                heapq.heappush(hh, a)
                hs += a
                hn += 1
        else:
            heapq.heappush(lh, -a)
            ls += a
            ln += 1

        while ln < hn:
            mx = heapq.heappop(hh)
            hs -= mx
            hn -= 1
            ls += mx
            ln += 1
            heapq.heappush(lh, -mx)

        while ln > hn + (ln+hn)%2:
            mx = -heapq.heappop(lh)
            ls -= mx
            ln -= 1
            heapq.heappush(hh, mx)
            hs += mx
            hn += 1
    else:
        lls = -lh[0]*ln - ls
        hhs = hs - (-lh[0]*hn)
        print(-lh[0], lls+hhs+off)
a,b,c=input().upper().split();print(''.join(a[0],b[0],c[0]))

### FIXED CODE ###

a,b,c=input().upper().split();print(''.join([a[0],b[0],c[0]]))
import sys
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 II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict, Counter
import bisect

sys.setrecursionlimit(10000000)

n = SI()
xy = [(0,0) for _ in range(n)]
div = []
for i in range(n):
    x, y = LI()
    xy[i] = (x, y)
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            div.append("{}_{}".format(xy[i][0] - xy[j][0], xy[i][1]- xy[j][1]))
c = Counter(div)
max_ = c.most_common()[0][1]
print(n - max_)

### FIXED CODE ###

import sys
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 II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict
import bisect

sys.setrecursionlimit(1000000000)

n = SI()
a_list = LI()

a_list =  sorted(a_list)
minus = bisect.bisect_left(a_list, 0)
minus_list = a_list[:minus]

plus_list = a_list[minus:]

ans = 0
p_i = 0
m_i = 0
if minus == 0:
    print(sum(plus_list) - 2*plus_list[0])
    minus_list = plus_list[0:1]
    plus_list = plus_list[1:]


elif minus == n:
    print(-sum(minus_list) + 2*minus_list[-1])
    plus_list = minus_list[-1:]
    minus_list = minus_list[:-1]

else:
    print(sum(plus_list) - sum(minus_list))

ans = minus_list[m_i]
m_i += 1
minus = len(minus_list)
plus = len(plus_list)


while p_i != (plus-1):
    print(ans, plus_list[p_i])
    ans = ans - plus_list[p_i]
    p_i += 1

print(plus_list[p_i], ans)
ans = plus_list[p_i] - ans

while m_i != minus:
    print(ans, minus_list[m_i])
    ans = ans - minus_list[m_i]
    m_i += 1
x
print(x^3)


### FIXED CODE ###

x=int(input())
print(x*x*x)
import numpy as np
MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = np.zeros((N,M),dtype=np.int64)
dp[0,0] = 1
m = list(range(M))
t = list(range(10))

for i in range(len(s)):
    for j in m:
        for k in t:
            if s[i] == "?" or s[i] == str(k):
                dp[i+1,(j*10 +k) % M] += dp[i,j]
                dp[i+1,(j*10 +k) % M] %= MOD


print(dp[len(s),5])


### FIXED CODE ###

MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N+10)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


print(dp[len(s)][5])
n,m = list(map(int,input().split()))
ans = [-1]*n
for i in range(m):
    s,c = list(map(int,input().split()))
    if ans[s-1] != -1 and ans[s-1] != c:
        ans = -1
        break
    ans[s-1] = c
    if s == 1 and n != 1 and c == 0:
        ans = -1
        break    
if ans[0] == -1 and n != 1:
    ans[0] = 1
if ans != -1:
    for i in range(n):
        if ans[i] == -1:
            ans[i] = '0'
        else:
            ans[i] = str(ans[i])
    print(''.join(ans))
else:
    print(ans)

### FIXED CODE ###

n,m = list(map(int,input().split()))
ans = [-1]*n
for i in range(m):
    s,c = list(map(int,input().split()))
    if ans[s-1] != -1 and ans[s-1] != c:
        ans = -1
        break
    ans[s-1] = c
    if s == 1 and n != 1 and c == 0:
        ans = -1
        break    

if ans != -1:
    if ans[0] == -1 and n != 1:
        ans[0] = 1
    for i in range(n):
        if ans[i] == -1:
            ans[i] = '0'
        else:
            ans[i] = str(ans[i])
    print(''.join(ans))
else:
    print(ans)
N,M = map(int, input().split())

from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import *
import numpy as np
from time import process_time as timer

G = lil_matrix((N,N), dtype='i4')

for i in range(M):
  a,b,c = map(int, input().split())
  G[a-1,b-1] = -c

# remove nodes unreachable from goal or start
n1 = set(depth_first_order(G, 0, return_predecessors=False))
n2 = set(depth_first_order(G.T, N-1, return_predecessors=False))
n = n1&n2
# N = len(nodes)
# nodes.sort()
# G = G[np.ix_(nodes,nodes)]

try:
  dist = bellman_ford(G,list(n))
  print(-int(dist[0,N-1]))
except NegativeCycleError:
  print('inf')

### FIXED CODE ###



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

from collections import defaultdict
neighbor = defaultdict(list)
Rneighbor = defaultdict(list)
edges = []
for i in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  edges += [(a,b,c)]
  neighbor[a].append(b)
  Rneighbor[b].append(a)

# only vertices that are reachable from 1 or N
v1 = set()
v1.add(0)
stack = [0]
while stack:
  v = stack.pop()
  for u in neighbor[v]:
    if u not in v1:
      v1.add(u)
      stack.append(u)

vn = set()
vn.add(N-1)
stack = [N-1]
while stack:
  v = stack.pop()
  for u in Rneighbor[v]:
    if u not in vn:
      vn.add(u)
      stack.append(u)

V = v1 & vn

edges = [(a,b,c) for a,b,c in edges if a in V and b in V]
score = [float('-inf')]*N
score[0] = 0

updated = True
i = 0

positive_cycle = False

while updated:
  if i == len(V):
    positive_cycle = True
    break

  updated = False
  for a,b,w in edges:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1

if positive_cycle:
  print('inf')
else:
  print(score[N-1])
import math
ans=0
m=[]
N=int(input())
rN=math.floor(math.sqrt(N))
for i in range(1,rN+1):
    if N%i==0:
        m.append(i)
        m.append(int(N/i))
    else:
        pass
m.sort()
m2=list(map(lambda x: x-1,m))
m2.pop(0)
for i in m2:
    a,b=divmod(N,i)
    if a==b:
        ans+=i
    else:
        pass
print(ans)

### FIXED CODE ###

import math
ans=0
m=[]
N=int(input())
rN=math.floor(math.sqrt(N))
for i in range(1,rN+1):
    if N%i==0:
        m.append(i)
        m.append(int(N/i))
    else:
        pass
m.sort()
m2=list(map(lambda x: x-1,m))
for i in m2:
    if i==0:
        pass
    else:
        a,b=divmod(N,i)
        if a==b:
            ans+=i
        else:
            pass
print(ans)
n=int(input())
N=list(map(int,input().split()))
even=[]
odd=[]
for i in range(len(N)):
    if i%2==0:
        even.append(N[i])
    if i%2==1:
        odd.append(N[i])
import collections
c = collections.Counter(even)
x=c.most_common()[0][0]
o=even.count(x)
d= collections.Counter(odd)
y=d.most_common()[0][0]
p=odd.count(y)
s=len(even)-even.count(x)
t=len(odd)-odd.count(y)
if x!=y and o==len(even) and p==len(odd):
    print(0)
elif x!=y:
    print(s+t)
elif x==y and o==len(even) and p==len(odd):
    print(n/2)
else:
    if o>p:
        y=d.most_common()[1][0]
        s=len(even)-even.count(x)
        t=len(odd)-odd.count(y)
        print(s+t)
    else:
        x=c.most_common()[1][0]
        s=len(even)-even.count(x)
        t=len(odd)-odd.count(y)
        print(s+t)
    
        


### FIXED CODE ###

n=list(input())
for i in range(len(n)):
    if n[i]=='9':
        n[i]=1
    if n[i]=='1':
        n[i]=9
for i in range(len(n)):
    print(n[i],end='')
import math, sys
def lcm(a,b):
    return int(a*b/math.gcd(a,b))

if __name__ == '__main__':
    for line in sys.stdin:
        a,b = map(int,line.split())
        print(int(math.gcd(a,b)),lcm(a,b))

### FIXED CODE ###

import sys
import fractions
def lcm(a,b):
    return int(a*b/fractions.gcd(a,b))

if __name__ == '__main__':
    for line in sys.stdin:
        a,b = map(int,line.split())
        print(int(fractions.gcd(a,b)),lcm(a,b))
g_m=0
g_G=[]
g_cnt=0
A=[]
n = int(input())
for i in range(n):
    A.append(int(input()))
def insertionSort(A,n,g):
    global g_cnt
    for i in range(g,n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j-g
            g_cnt += 1
        A[j+g]=v
    
def shellSort(A,n):
    m=1
    G=[]
    j=1
    for i in range(0,100):
        G.append(j)
        j=3*j+1
    
    while G[m]<=n:
        m+=1
    G=G[:m]
    G.reverse()
    for i in range(0,m):
        insertionSort(A,n,G[i])
    return A,m,G
A,g_m,g_G=shellSort(A,n)
print(g_m)
print(" ".join(map(str,g_G)))
print(g_cnt)
print(*A,sep="\n")

### FIXED CODE ###

g_m=0
g_G=[]
g_cnt=0
A=[]
n = int(input())
for i in range(n):
    A.append(int(input()))
def insertionSort(A,n,g):
    global g_cnt
    for i in range(g,n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j-g
            g_cnt += 1
        A[j+g]=v
    
def shellSort(A,n):
    m=1
    G=[]
    j=1
    for i in range(0,100):
        G.append(j)
        j=3*j+1
    
    while G[m]<=n:
        m+=1
    G=G[:m]
    G.reverse()
    for i in range(0,m):
        insertionSort(A,n,G[i])
    return A,m,G
A,g_m,g_G=shellSort(A,n)
print(g_m)
print(" ".join(map(str,g_G)))
print(g_cnt)
print(*A,sep="\n")
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


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

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n = I()
    ranges = []
    for i in range(n):
        x, l = LI()
        ranges.append((x - l + 1, x + l - 1))
    ranges.sort(key=lambda x: x[0])
    ans = n
    for i in range(1, n):
        if ranges[i - 1][1] >= ranges[i][0]:
            ans -= 1
            ranges[i][1] = -INF
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


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

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n = I()
    ranges = []
    for i in range(n):
        x, l = LI()
        ranges.append([x - l, x + l])
    ranges.sort(key=lambda x: x[1])
    ans = n
    for i in range(1, n):
        if ranges[i - 1][1] > ranges[i][0]:
            ans -= 1
            ranges[i][1] = ranges[i - 1][1]
    print(ans)


if __name__ == "__main__":
    main()
N, M = map(int, input().split())
a = [0] * M
b = [0] * M

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

index = []
for i in range(M):
    if b[i] == N:
        index  = i

for j in range(M):
    if b[j] == a[index]:
        print(a[j])
        if a[j] == 1:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
        break

### FIXED CODE ###

N, M = map(int, input().split())
a = [0] * M
b = [0] * M

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

s = []
t = []

for i in range(M):
    if a[i] == 1:
        s.append(b[i])
    elif b[i] == N:
        t.append(a[i])

if len(set(s) & set(t)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
A = map(int, input().split())
A.sort()
if A[2] == A[1] + A[0]:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

A = list(map(int, input().split()))
A.sort()
if A[2] == A[1] + A[0]:
  print('Yes')
else:
  print('No')