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

import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

INF = 1001001001
from scipy.sparse.csgraph import floyd_warshall
from collections import deque

N = int(input())
S = [input() for _ in range(N)]
G = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            G[i][j] = 0
        elif S[i][j] == '1':
            G[i][j] = 1
# print(G)

dist = floyd_warshall(G)
# print(dist)

k_1 = 0
for i in range(N):
    for j in range(N):
        if int(dist[i][j]) > k_1:
            k_1 = int(dist[i][j])
            max_i = i
            max_j = j
k = k_1 + 1

dist = [-1] * N
dist[max_i] = 1
q = deque()
q.append([max_i, 1])

while q:
    i, d = q.popleft()
    if dist[i] == -1:
        dist[i] = d
    elif dist[i] != d:
        k = -1
        break
    for j in range(N):
        if S[i][j] == '1' and dist[j] != d-1:
            q.append([j, d+1])

print(k)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

from collections import deque

N = int(input())
S = [input() for _ in range(N)]

def bfs(start):
    res = 0
    dist = [-1] * N
    dist[start] = 1
    q = deque()
    q.append([start, 1])
    st = set()
    st.add((start, 1))

    while q:
        i, d = q.popleft()
        if dist[i] == -1:
            dist[i] = d
            res = max(res, d)
        elif dist[i] != d:
            res = -1
            break
        for j in range(N):
            if S[i][j] == '1' and dist[j] != d-1:
                if (j, d+1) not in st:
                    q.append([j, d+1])
                    st.add((j, d+1))
    return res

ans = -1
for i in range(N):
    k = bfs(i)
    if k == -1:
        break
    else:
        ans = max(ans, k)

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

import sys
N = int(sys.stdin.readline().rstrip())
H = list(map(int, sys.stdin.readline().rstrip().split()))
for k in range(N-1):
    if H[k]-1 > min(H[k+1:]):
        print("No");exit()
print("Yes")

### FIXED CODE ###

import sys
N = int(sys.stdin.readline().rstrip())
H = list(map(int, sys.stdin.readline().rstrip().split()))
for k in range(2,N+1):
    if H[-k] <= H[-k+1]:
        continue
    elif H[-k] == H[-k+1] + 1:
    	H[-k] -= 1
    else:
        print("No");exit()
print("Yes")
### BUGGY CODE ###

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


for i in range(n):
    cnt = 0
    for j in range(n):
        if (j+1) % (n-i) == 0:
            cnt += a[j]
    b.append(cnt%2)

c = 0
for i in b:
    if i != 0:
        c += 1

print(c)
str_b = []
for i in reversed(b):
    if i != 0:
        str_b.append(str(i))
print(' '.join(str_b))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]*n

for i in range(n)[::-1]:
    cnt = sum(b[i::i+1])
    if (cnt %2) != a[i]:
        b[i] = 1
    

print(sum(b))

for i, j in enumerate(b):
    if j == 1:
        print(i+1)
### BUGGY CODE ###

a = input()
N = int(a)
A = [int(input()) for i in range(N)]

for i in range(N):
    if i == A.index(max(A)):
        B = sorted(A)
        print(B[N-2])
    else:
        print(max(A))

### FIXED CODE ###

a = input()
N = int(a)
A = [int(input()) for i in range(N)]
ind = A.index(max(A))
max = max(A)

for i in range(N):
    if i == ind:
        B = sorted(A)
        print(B[N-2])
    else:
        print(max)
### BUGGY CODE ###

import bisect
from collections import deque
def solve():
  
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  a.sort()
  tmp = []
  for i in range(m):
    l,r = (int(i) for i in input().split())
    tmp.append((l,r))
  tmp.sort(key=lambda tmp: tmp[1],reverse =True)
  rightpoint = n-1
  ans = 0
  while tmp:
    if len(a) == 0:
      break
    b,c = tmp.pop(0)
    place = bisect.bisect_left(a,c)-1
    if place == -1:
      break
    else:
      for i in range(min(1+place,b)):
       # print(b,place)
        a.pop(0)
        ans += c
    #print(a)
  while a:
    ans += a.pop(0)
  print (ans)
solve()

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  a = deque(sorted(a))
  tmp = deque([])
  for i in range(m):
    r,l = (int(i) for i in input().split())
    tmp.append((l,r))
  tmp= deque(sorted(tmp,reverse =True))
  ans = 0
  while tmp:
    c,b = tmp.popleft()
    place = bisect.bisect_left(a,c)-1
    if place == -1:
      break
    else:
        if len(a) == 0:
           break
        for i in range(min(1+place,b)):
           a.popleft()
        ans += c*(min(1+place,b))
    #print(a)
  if a:
   ans += sum(a)
  print (ans)
solve()
### BUGGY CODE ###

# import sys
# sample = sys.stdin.read().splitlines()
# n, stones = int(sample[0]), list(map(int, sample[1].split()))
# print(n, stones)


# def frog_jump(n:int, stones)->int:
#     dp = [float('inf')] * n
#     jumps = (1, 2)
#     dp[0] = 0
#     for idx in range(len(dp)):
#         for jump in jumps:
#             if idx+jump < len(dp):
#                 dp[idx+jump] =  min(dp[idx]+abs(stones[idx+jump]-stones[idx]), dp[idx+jump])
#     return dp[-1]
 
# frog_jump(n, stones) 

import sys
sample = sys.stdin.read().splitlines()
nandk  = list(map(int, sample[0].split()))
stones = list(map(int, sample[1].split()))
n, k = nandk[0], nandk[1]
dp = [float('inf')] * n
#jumps = range(1, k+1)
dp[0] = 0
for idx in range(len(dp)):
  for jump in range(1,k+1):
    if idx+jump < len(dp):
      dp[idx+jump] =  min(dp[idx]+abs(stones[idx+jump]-stones[idx]), dp[idx+jump])
print(dp[-1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

N = int(input())
A = input().split()

result = 1
length = len(A)

for num in range(length):
    result = result * int(A[num])

max = 10 ** 18

if result <= max:
    print(result)
else:
    print("-1")

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #配列を昇順ソートしておく(配列に0がある場合0が先頭に来るので、場合分けの必要がなくなる)
ans=1
for val in arr:
 ans*=val #Pythonは多倍長整数をサポートしているので単に積を求めれば十分
 if ans>10**18:
   print(-1)
   break
else:
 print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
dic = {}
amari = {}
for i in range(N-1):
  k, v = map(int, input().split())
  try:
    dic[k].append(v)
  except KeyError:
    dic[k] = [v]
  try:
    amari.pop(k)
  except KeyError:
    pass
  amari[v] = []
dic.update(amari)
counter = [list(map(int, input().split())) for i in range(Q)]
q = {i: 0 for i in dic.keys()}
 
def child_sum(q,v, child):
  if child == []:
    return q
  else:
    for j in child:
      q[j] += v
      child = dic[j]
      q = child_sum(q, v, child)
  return q
    
for i, v in counter:
  q[i] += v
  child = dic[i]
  #print(q, i, child)
  q = child_sum(q, v, child)
print(*q.values())

### FIXED CODE ###

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
q = [0 for i in range(N)]
 
for i in range(N-1):
  a, b = map(int, input().split())
  edge[a-1].append(b)
for i in range(Q):
  a, v = map(int, input().split())
  q[a-1] += v
 
for i, v in enumerate(q):
  #print(i, v)
  for j in edge[i]:
    #print(j)
    q[j-1] += v
print(*q)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
p=1
for i in range(n):
  p*=a[i]
  
if(p>1000000000000000000):
    print("-1")
    exit()
print(p)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=1
if(a.count(0)>=1):
  print("0")
  exit()
for i in range(n):
  p*=a[i]
  if(p>1000000000000000000):
    print("-1")
    exit()
print(p)
### BUGGY CODE ###

import bisect

def main():
    N,M = map(int,input().split())
    A =[int(x) for x in input().split()]
    A.sort()
    for _ in range(M):
        b,c = map(int,input().split())
        k=0
        for i in range(b):
            if A[i]<c:
                A[i]=c
                k+=1
        a = bisect.bisect(A[k:],c)
        d,e = A[:a+k],A[a+k:]
        d.sort()
        A = d+e
    print(sum(A))
main()   

### FIXED CODE ###

from operator import itemgetter

def main():
    N,M = map(int, input().split())
    A = [[1,int(x)] for x in input().split()]
    for _ in range(M):
        b,c = map(int, input().split())
        A.append([b,c])
    A.sort(key=itemgetter(1))
    A.reverse()
    n=0
    s=0
    for a in A:
        n+=a[0]
        if n<=N:
            s+=a[1]*a[0]
        elif n>N:
            d=a[0]
            e=a[1]
            break
    s+=(N-n+d)*e
    print(s)
    
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    edges[u].append([v, w])
    edges[v].append([u, w])
parent = [[] for _ in range(N)]
ans = [0 for _ in range(N)]


def dfs(edge, pd):
    for child, d in edges[edge]:
        if edge in parent[child-1]:
            continue
        cd = pd + d
        if cd % 2 == 0:
            ans[child-1] = 0
        else:
            ans[child-1] = 1
        parent[child-1].append(edge)
        dfs(child, cd)


def solve():
    dfs(1, 0)
    for i in range(N):
        print(ans[i])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    edges[u].append([v, w])
    edges[v].append([u, w])
ans = [-1 for _ in range(N)]


def dfs(edge, pd):
    for child, d in edges[edge]:
        if ans[child-1] != -1:
            continue
        cd = pd + d
        if cd % 2 == 0:
            ans[child-1] = 0
        else:
            ans[child-1] = 1
        dfs(child, cd)


def solve():
    dfs(1, 0)
    for i in range(N):
        print(ans[i])


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

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = input()
flag = [True] * 10
check = defaultdict(lambda : 0)
ans = 0
for i in range(n):
    if flag[int(s[i])]:
        for j in range(i+1, n):
            for k in range(j+1, n):
                x = s[i] + s[j] + s[k]
                if check[x]:
                    continue
                check[x] = 1
                ans += 1
        flag[int(s[i])] = False
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
#三井住友信託銀行プログラミングコンテスト2019 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def C(n,r):
    return math.factorial(n)//math.factorial(n-r)//math.factorial(r)

n = I()
s = input()
t = list(map(int,list(s)))
ans = 0
for i in range(10):
    for j in range(n):
        if i == t[j]:
            tmp = j
            break
    else:
        continue
    for j in range(100):
        if len(str(j)) == 2:
            x,y = list(str(j))
        else:
            x,y = '0',str(j)
        flg = False
        for k in range(tmp+1,n):
            if flg and y == str(t[k]):
                ans += 1
                break
            if x == str(t[k]):
                flg = True
print(ans)
### BUGGY CODE ###

from math import sqrt
from collections import Counter

def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = set()
    while F[x] > 0:
        primeFactors.add(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.add(x)
    return Counter(primeFactors)

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

amax = max(A)
F  = arrayF(amax)

P = Counter()
for a in A:
    p = factorization(a, F)
    P += p

p_max = max(P.values()) if P else 1
if  p_max == 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = []
    while F[x] > 0:
        primeFactors.append(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.append(x)
    return set(primeFactors)

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

amax = max(A)
F  = arrayF(amax)

P = [0] *  (amax+1)
for a in A:
    for p in factorization(a,  F):
        P[p] += 1
p_max = max(P)
if  p_max <= 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=i1()
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=max(t[i*2+1],t[i*2+2]) 
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         L = max(L, t[a])
      if b&1==0:
         b-=1
         R = max(t[b], R)
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append(i2())
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 j=bisect.bisect_left(dx,dx[i]+dd[i])
 tt=qr(i,j)
 ud(i,max(j-1,tt))
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)>>1
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])
### BUGGY CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    a = readInt()
    ans = 0
    for i in range(n-1):
        for j in range(i+1,n):
            ans += a[i] * a[j]
            ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()



### FIXED CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    a = readInt()
    c_sum = [0]
    for i in range(n):
        c_sum.append(c_sum[i]+a[i])
    ans = 0
    for i in range(n-1):
        ans += a[i] * (c_sum[-1] - c_sum[i+1])
        ans %= mod
    print(ans)
    return

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

def main():
    import sys
    sys.setrecursionlimit(10**4)
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    num1,num2,num3=0,0,0
    for i in range(n):
        if a[i]==1:
            num1+=1
        elif a[i]==2:
            num2+=1
        else:
            num3+=1
    dp=[[[-1 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
    def f(n1,n2,n3):
        if dp[n1][n2][n3]>=0:
            return dp[n1][n2][n3]
        if n1==n2==n3==0:
            return 0
        ret=0
        if n1>0:
            ret+=f(n1-1,n2,n3)*n1
        if n2>0:
            ret+=f(n1+1,n2-1,n3)*n2
        if n3>0:
            ret+=f(n1,n2+1,n3-1)*n3
        ret+=n
        ret*=1/(n1+n2+n3)
        dp[n1][n2][n3]=ret
        return dp[n1][n2][n3]
    print(f(num1,num2,num3))
if __name__=="__main__":
    main()

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

#ABC084D
def main():
    import sys
    Q = int(sys.stdin.readline())
    LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    #print(LR)
    
    check = [1 for _ in range(10**5+1)]
    check[0], check[1] = 0, 0
    for i in range(2, 10**5+1):
        if check[i] ==0:
            continue
        elif check[i] ==1:
            for j in range(2*i, 10**5+1, i):
                check[j] =0
    check2 = check.copy()
    for i in range(2, 10**5+1):
        if check[i]==1:
            #print((i+1)/2, check[(i+1)//2])
            if (i+1)%2==0 and check[(i+1)//2] ==1:
                continue
            else:
                check2[i] = 0
    
    #print(check)
    for lr in LR:
        #print(lr[0], lr[1])
        print(check2[lr[0]:lr[1]+1].count(1))
                


if __name__ =='__main__':
    main()

### FIXED CODE ###

#ABC084D
def main():
    import sys
    Q = int(sys.stdin.readline())
    LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    #print(LR)
    
    def calc(N):
        import math
        for i in range(3, int(math.sqrt(N))+1):
            while N % i==0:
                N =N//i
                return 0
        else:
            num = (N+1)//2
            #if num ==2:
                #return N
            for j in range(2, int(math.sqrt(num)+1)):
                while num % j==0:
                    num = num//j
                    return 0
            else:
                return N
    
     
    L = []
    for i in range(3, 10**5+1, 2):
        tmp = calc(i)
        if tmp !=0:
            L+=[tmp]
    #print(L)
    import bisect
    
    for row in LR:
        l = bisect.bisect_left(L, row[0])
        r = bisect.bisect_right(L, row[1])
        print(r-l)

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

e=enumerate
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=eval('[0]*-~n,'*3)
for i,t in e(s):
  m[i+1]=m[i]+(t=='M')
  f=t=='C'
  c[i+1]=c[i]+f
  x[i+1]=x[i]+f*m[i+1]
for k in k:
  k=int(k)
  a=0
  for i,t in e(s):
    j=min(n,i+k)
    a+=t=='D'and(c[i]-c[j])*m[i]+x[j]-x[i]
  print(a)

### FIXED CODE ###

from numpy import*
_,s,_,k=open(0)
s=array(list('='+s[:-1]))
d,m,c=[s==t for t in'DMC']
x,y=map(cumsum,(d,m))
for k in int32(k.split()):
  t=copy(x)
  t[k:]-=x[:-k]
  t*=m
  t[k+1:]-=d[1:-k]*(y[k:-1]-y[:~k])
  print(sum(cumsum(t)*c))
### BUGGY CODE ###

import numpy as np
N=int(input())
XL=[]
for i in range(N):
    a,b=map(int,input().split())
    XL.append([a-b,a+b])
    #XL.append(list(map(int,input().split())))
XL=np.array(XL)

ans=0
end=-10**(19)
for i in range(N):
    x=XL[XL[:,0]>=end][:,1]
    if x.size!=0:
        end=min(x)
        ans+=1
    else:
        break
print(ans)

### FIXED CODE ###

N=int(input())
XL=[]
for i in range(N):
    a,b=map(int,input().split())
    XL.append([a-b,a+b])
    #XL.append(list(map(int,input().split())))
XL=sorted(XL,key = lambda x: (x[1], x[0]))




ans=0
end=-10**(19)
for i in range(N):
    if XL[i][0]>=end:
        ans+=1
        end=XL[i][1]
        
print(ans)
### BUGGY CODE ###

mod = 998244353
from bisect import bisect_left as bisect
from operator import itemgetter
N = int(input())
XD = [list(map(int,input().split())) for _ in range(N)]
XD.sort(key=itemgetter(0))
X = [XD[i][0] for i in range(N)]
D = [XD[i][1] for i in range(N)]

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(4*N0)

def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N-1,-1,-1):
    x,d = XD[i]
    j = bisect(X,x+d)
    update(i,-i)
    update(i,query(i,j))

dp = [1]*(N+1)

for i in range(N-1,-1,-1):
    j = -query(i,i+1)
    dp[i] = dp[i+1] + dp[j+1]
    dp[i] %= mod

print(dp[0])


### FIXED CODE ###

mod = 998244353
from bisect import bisect_left
from operator import itemgetter
N = int(input())
xd = [list(map(int,input().split())) for _ in range(N)]
xd.sort(key=itemgetter(0))
X = [xd[i][0] for i in range(N)]
D = [xd[i][1] for i in range(N)]

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(4*N0) #長さが足りないことがある. 3*N0にすればいい?

# k番目の要素をxに更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N-1,-1,-1):
    j = bisect_left(X,X[i]+D[i])
    update(i,-i)
    update(i,query(i,j))

dp = [0]*(N+1)
dp[-1] = 1
for i in range(N-1,-1,-1):
    dp[i] += dp[i+1]
    dp[i] += dp[-query(i,i+1)+1]
    dp[i] %= mod

print(dp[0])