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

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

def nibun(lis,x):
    i=len(lis)
    if i==1:
        if lis[0]<=x:
            return lis[0]
    elif lis[i//2]==x:
        return x
    else:
        if x<lis[i//2]:
            return nibun(lis[:i//2],x)
        else:
            return nibun(lis[i//2:],x)
X.sort()
a={}
a[X[0][0]]=1
a[-np.inf]=0
T=[]
b={}
for i in range(1,N):
    T.append(X[i-1][0])
    k=nibun(T,X[i][1])
    if k==None:
        b[i]=-np.inf
    else:
        b[i]=k
    a[X[i][0]]=max(a[X[i-1][0]],a[b[i]]+1)
print(a[X[N-1][0]])

### FIXED CODE ###

N=int(input())
X=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append([a+b,a-b])
X.sort()
D={}
D[0]=1
exe=[0]
for i in range(1,N):
    k=X[i][0]
    if X[i][1]<X[exe[-1]][0]:
        D[i]=D[exe[-1]]
    else:
        D[i]=D[exe[-1]]+1
        exe.append(i)
print(len(exe))
### BUGGY CODE ###

k=int(input())
if k%2==0:
    print(-1)
    exit()
count=1
while True:
    if int('7'*count)%k==0:
        print(count)
        break
    count+=1

### FIXED CODE ###

k=int(input())
if k%2==0 or k%5==0:
    print(-1)
    exit()
a=0
for i in range(k):
    a=(a*10+7)%k
    if a==0:
        print(i+1)
        exit()
### BUGGY CODE ###

k = int(input())

Queue = [i for i in range(1, 10, 1)]

cnt = 1

while(cnt <= k) : 
    x = Queue.pop(0)
    xx = x
    if len(str(xx)) >= 2 : 
        while(len(str(xx)) >= 2) : 
            xx = xx % 10

    ## 1つ目            
    if xx != 0 : 
        y = int("".join(map(str, [x, xx-1])))
        Queue.append(y)
        
    ## 2つ目            
    y = int("".join(map(str, [x, xx])))    
    Queue.append(y)

    ## 3つ目            
    if xx != 9 : 
        y = int("".join(map(str, [x, xx+1])))
        Queue.append(y)

    cnt += 1
            
print(x)

### FIXED CODE ###

k = int(input())

Queue = [i for i in range(1, 10, 1)]

cnt = 0

while(cnt < k) : 
    cnt += 1
    x = Queue.pop(0)
    
    if cnt + len(Queue) >= k : 
        continue
    
    xx = x
    if len(str(xx)) >= 2 : 
        while(len(str(xx)) >= 2) : 
            xx = xx % 10

    ## 1つ目            
    if xx != 0 : 
        y = int("".join(map(str, [x, xx-1])))
        Queue.append(y)
        
    ## 2つ目            
    y = int("".join(map(str, [x, xx])))    
    Queue.append(y)

    ## 3つ目            
    if xx != 9 : 
        y = int("".join(map(str, [x, xx+1])))
        Queue.append(y)


print(x)
### BUGGY CODE ###

K,S=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                ans+=1

print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        if  0<=S-i-j<=K:
            ans+=1

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

n,m = map(int,input().split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(n):
	a_dash,b_dash = map(int,input().split())
	a.append(a_dash)
	b.append(b_dash)

c = zip(a,b)
c = sorted(c)
a,b = zip(*c)
a = list(a)
b = list(b)

for i in reversed(range(m)):
	for j in range(count,len(a)):
		if a[j] + i == m:
			l.append(b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		ans += max(l)
		#index = b.index(max(l))
		#a.pop(index)
		#b.pop(index)
		l.pop(l.index(max(l)))
	#l.clear()

print(ans)

### FIXED CODE ###

import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

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

import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
a,b,n=map(int,input().split())

cnt=0

for i in range(n+1):
	cnt=max(cnt,(a*i)//b-a*(i//b))

print(cnt)

### FIXED CODE ###

import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
a,b,n=map(int,input().split())
cnt=0

if n//b>0:
	print(a*(b-1)//b-a*((b-1)//b))
else:
	print(a*(n)//b-a*((n)//b))
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = input()
ans = 0
D = Counter(S)
id = 0
dic = {}
for k in D.keys():
    dic[k] = id
    id += 1
m = 0
OB = [-1]*N
for i in range(N):
    if D[S[i]]<=1:
        pass
    else:
        OB[i] = dic[S[i]]
        m = max(m,dic[S[i]])
SSS = [[] for i in range(m+1)]
for i in range(N):
    SSS[OB[i]].append(i)
SSS.sort()
for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(i,lss):
            ni = SSS[n][i]
            nj = SSS[n][j]
            if i==j or ans>nj-ni or ans>N-nj:
                continue
            id = 0
            while True:
                if nj+id>=N or ni+id>=nj:
                    break
                if S[ni+id]==S[nj+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
right = 0
for left in range(N):
    while S[left:right + 1] in S[right + 1:]:
        ans = max(ans, right + 1 - left)
        right += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
if N % 2 == 1:
    if A.count(0) != 1:
        print(0)
        exit()
    for i in range(2, N, 2):
        if A.count(i) != 2:
            print(0)
            exit()
    print(2 ** ((N - 1) // 2))
else:
    for i in range(1, N, 2):
        if A.count(i) != 2:
            print(0)
            exit()
    print(2 ** (N // 2))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
C = [0] * N
for a in A:
    C[a] += 1
if N % 2 == 1:
    if C[0] != 1:
        print(0)
        exit()
    for i in range(2, N, 2):
        if C[i] != 2:
            print(0)
            exit()
    print(2 ** ((N - 1) // 2) % 1000000007)
else:
    for i in range(1, N, 2):
        if C[i] != 2:
            print(0)
            exit()
    print(2 ** (N // 2) % 1000000007)
### BUGGY CODE ###

n = int(input())
l = [list(input()) for i in range(n)]
l = ["".join(sorted(i)) for i in l]
l = [i for i in l if i != 1]
s = 0
for i in range(len(l)-1):
  for j in range(i+1,len(l)):
    if l[i] == l[j]:
      s += 1
print(s)


### FIXED CODE ###

import collections
n = int(input())
s = ["".join(sorted(input())) for i in range(n)]
l = collections.Counter(s)
ans = sum(i*(i-1)//2 for i in l.values())
print(ans)
### BUGGY CODE ###

def main():
    N=int(input())
    A=[int(n) for n in input().split()]
    p = 1
    ov = False
    for i in range(N):
        np = p * A[i]
        if np > 10**18:
            ov = True
        if A[i] == 0:
            print(0)
            return
        p = np
    if ov:
        print(-1)
    else:
        print(np)
main()

### FIXED CODE ###

def main():
    N=int(input())
    A=[int(n) for n in input().split()]
    p = 1
    ov = False
    for i in range(N):
        if not ov:
            np = p * A[i]
        if np > 10**18:
            ov = True
        if A[i] == 0:
            print(0)
            return
        p = np
    if ov:
        print(-1)
    else:
        print(np)
main()
### BUGGY CODE ###

r, g, b, n = list(map(int, input().split()))

cnt = 0
for i in range(n//r + 1):
    for j in range(n//g + 1):
        nb = (n - (i*r+j*g))/b

        if (nb >= 0) and (nb % 1 == 0):
            cnt += 1

print(cnt)

### FIXED CODE ###

r, g, b, n = list(map(int, input().split()))

cnt = 0
for i in range(n//r + 1):
    for j in range(n//g + 1):
        nb = (n - (i*r+j*g))

        if (nb >= 0):
            if (nb % b == 0):
                cnt += 1
        else:
            break

print(cnt)
### BUGGY CODE ###

import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = dict()
        for pp, s in queue:
            footsteps[pp] = -1

        while queue:
            p, s = queue.popleft()
            footsteps[p] = s

            for pp in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]:
                if 0 <= pp[0] < width and 0 <= pp[1] < height and pp not in footsteps:
                    queue.append((pp, s + 1))
                    footsteps[pp] = -1  # placeholder

        return s

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append(((x, y), 0))

    return fill(queue)


def main():
    print(solve())


main()


### FIXED CODE ###

import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = [[None] * width for _ in range(height)]

        for x, y in queue:
            footsteps[y][x] = 0

        s = 0
        while queue:
            queue2 = deque()
            s += 1
            while queue:
                x, y = queue.popleft()

                if x > 0 and footsteps[y][x - 1] is None:
                    queue2.append((x - 1, y))
                    footsteps[y][x - 1] = s
                if x < width - 1 and footsteps[y][x + 1] is None:
                    queue2.append((x + 1, y))
                    footsteps[y][x + 1] = s
                if y > 0 and footsteps[y - 1][x] is None:
                    queue2.append((x, y - 1))
                    footsteps[y - 1][x] = s
                if y < height - 1 and footsteps[y + 1][x] is None:
                    queue2.append((x, y + 1))
                    footsteps[y + 1][x] = s

            queue = queue2

        return s - 1

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append((x, y))
    # queue.append((10, 10))


    return fill(queue)


def main():
    print(solve())


main()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}
ans = [0] * q
query.sort(key=itemgetter(1))
ind = 0

for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

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


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}
ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0

for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

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

s = input()
q = int(input())
reverse = False
for i in range(q):
    inp = list(input().split())
    if len(inp) == 1:
        if reverse:
            reverse = False
        else:
            reverse = True
        continue
    t, f, c = inp[0], int(inp[1]), inp[2]
    if not reverse:
        if f == 1:
            s = c + s
        else:
            s = s + c
    else:
        if f == 2:
            s = c + s
        else:
            s = s + c
if reverse:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###

s = input()
q = int(input())
reverse = False
front = []
back = []
for i in range(q):
    inp = list(input().split())
    if len(inp) == 1:
        if reverse:
            reverse = False
        else:
            reverse = True
        continue
    t, f, c = inp[0], int(inp[1]), inp[2]
    if not reverse:
        if f == 1:
            front.append(c)
        else:
            back.append(c)
    else:
        if f == 2:
            front.append(c)
        else:
            back.append(c)
s = "".join(front[::-1]) + s + "".join(back)
if reverse:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]

#隣接リストで管理
adj = [[] for j in range(N)]
for edge in edges:
    x, y = edge
    adj[x-1].append(y)
    adj[y-1].append(x)
cnt = 0

def dfs(t, start, past, now):
    global cnt
    if t == 3:
        if not now in adj[start-1] and now != start:
            adj[start-1].append(now)
            adj[now-1].append(start)
            cnt += 1
    else:
        for node in adj[now-1]:
            if node != past:
                dfs(t+1, start, now, node)

for j in range(1,N+1):
    dfs(0, j, j, j)

print(cnt)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]

#隣接リストで管理
adj = [[] for j in range(N)]
for edge in edges:
    x, y = edge
    adj[x-1].append(y)
    adj[y-1].append(x)

color = [0] * N

#二部グラフ判定
def dfs(node, c):
    color[node-1] = c
    for i in adj[node-1]:
        if c == color[i-1]:
            return False
        if color[i-1] == 0 and not dfs(i, -c):
            return False
    return True

if dfs(1, 1):
    black = color.count(1)
    white = N - black
    print(black * white - M)
else:
    print(N * (N-1) // 2 - M)
### BUGGY CODE ###

import sys
from fractions import gcd
A, B = map(int, input().split())

glst = []
tmp = gcd(A, B)
for i in range(1, (tmp // 2) + 1):
    if tmp % i == 0:
        glst.append(i)
glst.append(tmp)
cnt = 0
for i in range(1, len(glst) + 1):
    cntF = True
    for j in range(i + 1, len(glst) + 1):
        if gcd(glst[-i], glst[-j]) != 1:
            cntF = False
            break

    if cntF:
        cnt += 1

print(cnt)

### FIXED CODE ###

import sys
from fractions import gcd
A, B = map(int, input().split())

glst = []
tmp = gcd(A, B)
for i in range(1, int(tmp ** 0.5) + 1):
    if tmp % i == 0:
        glst.append(i)
        if i != tmp // i:
            glst.append(tmp // i)

glst.sort()
cnt = 0
for i in range(1, len(glst) + 1):
    cntF = True
    for j in range(i + 1, len(glst) + 1):
        if gcd(glst[-i], glst[-j]) != 1:
            cntF = False
            break

    if cntF:
        cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans  = 0
for i in range(n):
  if p[i] == min(p[:i+1]):
        ans+=1 
                 
print(ans)                 
                 

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans  = 0
current = max(p)+1
for i in range(n):
  if p[i]  <= current:
    current = p[i]
    ans +=1
  
#  if p[i] == min(p[:i+1]):
#        ans+=1 
                 
print(ans)
### BUGGY CODE ###

import sys
import copy
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in read() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    H, W = in_nn()
    grid = in_map()

    ans = 0
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while sum(grid) != 0:

        next_grid = copy.copy(grid)
        for y in range(H):
            for x in range(W):
                if not grid[x + y * W]:
                    continue
                for (px, py) in move:
                    nx, ny = x + px, y + py
                    if 0 <= nx < W and 0 <= ny < H:
                        if not grid[nx + ny * W]:
                            next_grid[x + y * W] = False
                            break
        ans += 1
        grid = next_grid

    # print(grid)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
from copy import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs_grid(H, W, s, grid):

    q = deque(s)
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    ans = 0

    while True:

        nq = deque()
        f = False
        while q:
            now = q.popleft()
            x, y = now
            for m in move:
                nx, ny = x + m[0], y + m[1]
                if 0 <= nx < W and 0 <= ny < H:
                    if grid[ny][nx]:
                        f = True
                        grid[ny][nx] = False
                        nq.append((nx, ny))

        if f:
            ans += 1
        if nq:
            q = nq
        else:
            break

    return ans


def main():

    H, W = in_nn()
    grid = in_map2(H)

    s = []
    for y in range(H):
        for x in range(W):
            if not grid[y][x]:
                s.append((x, y))

    if len(s) == H * W:
        print(0)
        exit()

    print(bfs_grid(H, W, s, grid))


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

from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

def f(B):
    base = (X + B**5 )
    if base < 0:
        return 0.1
    return (X + B**5 ) ** (1/float(5))

[X] = getInts()
Q = deque([(0,0)])
V = set()
BP, BN = 0,0
while not f(BP).is_integer() and not f(BN).is_integer() and not f(-BP).is_integer() and not f(-BN).is_integer():
    (BP,BN) = Q.pop()
    l = [(BP+1,BN),(BP,BN+1),(BP+1,BN+1)]
    l = filter(lambda x: x not in V, l)
    for each in l:
        V.add(each)
        Q.appendleft(each)

if f(BP).is_integer():
    print(int(f(BP)), BP)
elif f(-BP).is_integer():
    print(int(f(-BP)), -BP)
elif f(BN).is_integer():
    print(int(f(BN)), BN)
else:
    print(int(f(-BN)), -BN)

### FIXED CODE ###

from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

def f(A,B):
    return A**5 - B**5

[X] = getInts()
Q = deque([(0,0)])
V = set()
A, B = 0,0
r = []
while not r:
    (A,B) = Q.pop()
    l = [(A+1,B),(A,B+1),(A+1,B+1)]
    l = filter(lambda x: x not in V, l)
    for each in l:
        V.add(each)
        Q.appendleft(each)
    
    r = list(filter(lambda x: f(*x)==X, [(A,B), (A,-B), (-A,B), (-A, -B)]))

print(r[0][0], r[0][1])
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    p = [i // 100, (i // 10) % 10 , i % 10, -1]
    idx = 0
    for j in range(n):
        if int(s[j]) == p[idx]:
            idx += 1
    if idx == 3:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
a = [set(), set(), set()]
for i in range(n):
    for j in a[1]:
        a[2].add(j + s[i])
    for j in a[0]:
        a[1].add(j + s[i])
    a[0].add(s[i])
print(len(a[2]))