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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

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

n = INT()
ans = [0, 0]
for i in range(n):
    t,a = MAP()
    k = 1
    while True:
        if ans[0] <= k * t and ans[1] <= k * a:
            break
        k += 1
    ans[0] = k * t
    ans[1] = k * a
    #print('a', t+a, ans)
print(sum(ans))


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

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

n = INT()
ans = [1, 1]
for i in range(n):
    t,a = MAP()
    k = max((ans[0] + t - 1) // t, (ans[1] + a - 1) // a)
    ans[0] = k * t
    ans[1] = k * a
    #print('a', t+a, ans)
print(sum(ans))
### BUGGY CODE ###

from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("YES")
    else:print("NO")
    exit(0)


def ct(x,y):
    if (x>y):print("GREATER")
    elif (x<y): print("LESS")
    else: print("EQUAL")

def ip():
    return int(input())
#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#b = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
a = []
b = []
for i in range(n):
    c,d = (int(i) for i in input().split())
    a.append(c)
    b.append(d)
s = 0
sp = 0
while m>s:
    minpos = a.index(min(set(a)))
    if s+b[minpos]>=m:
        amo = m-s
  #      print(amo)
        s+=amo
        sp+=(a[minpos]*amo)
 #       print(s,sp)
 #       print(a,b)
    else:
        s+=b[minpos]
        sp+=(a[minpos]*b[minpos])
        a.pop(minpos)
        b.pop(minpos)
#        print(s,sp)
 #       print(a,b)
print(sp)

### FIXED CODE ###

from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("YES")
    else:print("NO")
    exit(0)


def ct(x,y):
    if (x>y):print("GREATER")
    elif (x<y): print("LESS")
    else: print("EQUAL")

def ip():
    return int(input())
#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#b = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
b = []
a = []
for i in range(n):
    c,d = (int(i) for i in input().split())
    a.append([c,d])
a.sort(key=lambda x:(x[0]))
s = 0
sp = 0
for i in range(n):
  #  print(s,sp)
    add = a[i][1]
    addprice = a[i][0]
    if s+add>=m:
        amo  = m-s
        s+=amo
        sp+=(addprice*amo)
 #       print(s,sp)
    else:
        s+=add
        sp+=(add*addprice)
    if m<=s: break
print(sp)


"""
while m>s:
    minpos = a.index(min(set(a)))
    if s+b[minpos]>=m:
        amo = m-s
  #      print(amo)
        s+=amo
        sp+=(a[minpos]*amo)
 #       print(s,sp)
 #       print(a,b)
    else:
        s+=b[minpos]
        sp+=(a[minpos]*b[minpos])
        a.pop(minpos)
        b.pop(minpos)
#        print(s,sp)
 #       print(a,b)
print(sp)
"""
### BUGGY CODE ###

N=int(input())
S=input()

r,g,b=[],[],[]
for i in range(N):
  s = S[i]
  if s=='R':r.append(i)
  elif s=='G':g.append(i)
  else:b.append(i)

count = 0
for i in r:
  for j in g:
    for k in b:
      if (i+j+k)/3 not in [i,j,k]:
        count += 1
print(count)

### FIXED CODE ###

from collections import Counter

N=int(input())
S=input()

c=Counter(S+'RGB')
ans = (c['R']-1)*(c['G']-1)*(c['B']-1)

max_d = (N-3)//2+1

for d in range(1,max_d+1):
  for i in range(N-2):
    j = i+d
    k = j+d
    if k > N-1:break
    if len(set([S[i],S[j],S[k]]))==3:
      ans -= 1
      
print(ans)
### BUGGY CODE ###

import collections


def main():
    n = int(input())
    *v, = map(int, input().split())

    v0 = count(v[::2])
    v1 = count(v[1::2])

    if len(v0) == 1 and len(v1) == 1:
        if v0[0][0] == v1[0][0]:
            print(n // 2)
        else:
            print(0)
        return

    l0 = max(2, len(v0))
    l1 = max(2, len(v1))

    INF = 10 ** 9
    score = [[0] * l1 for _ in range(l0)]
    for i in range(l0):
        for j in range(l1):
            score[i][j] = sum_v(v0, i) + sum_v(v1, j)
            if i >= l0 - 1 or j >= l1 - 1 or v0[i][0] == v1[j][0]:
                score[i][j] = INF
    print(min([min(s) for s in score]))


def count(v):
    return sorted(list(collections.Counter(v).items()), key=lambda x: x[1], reverse=True)


def sum_v(v, ii):
    return sum([vv[1] for i, vv in enumerate(v) if i != ii])


main()


### FIXED CODE ###

def main():
    n = int(input())
    *v, = map(int, input().split())

    v0 = assemble(v[::2])
    v1 = assemble(v[1::2])

    if len(v0) == 1 and len(v1) == 1:
        if v0[0][0] == v1[0][0]:
            print(n // 2)
        else:
            print(0)
        return
    elif len(v0) == 1:
        if v0[0][0] == v1[0][0]:
            print(sum_v(v1, 1))
        else:
            print(sum_v(v1, 0))
        return
    elif len(v1) == 1:
        if v0[0][0] == v1[0][0]:
            print(sum_v(v0, 1))
        else:
            print(sum_v(v0, 0))
        return

    score = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            score[i][j] = sum_v(v0, i) + sum_v(v1, j)
            if v0[i][0] == v1[j][0]:
                score[i][j] = 10 ** 9
    print(min([min(s) for s in score]))


def assemble(v):
    dct = {}
    for vel in v:
        if vel in dct:
            dct[vel] += 1
        else:
            dct[vel] = 1
    return sorted(list(dct.items()), key=lambda x: x[1], reverse=True)


def sum_v(v, ii):
    return sum([vv[1] for i, vv in enumerate(v) if i != ii])


main()
### BUGGY CODE ###

[n] = map(int, input().split())
[*p_list] = map(int, input().split())

count = 0

for i,p in enumerate(p_list):
  s_p = p_list[:i+1]
  if min(s_p) == p:
    count += 1

print(count)

### FIXED CODE ###

[n] = map(int, input().split())
[*p_list] = map(int, input().split())

count = 0
p_min = 2 * 10 ** 5

for p in p_list:
  if p_min >= p:
    count += 1
    p_min = p

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

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())
    a.sort()
    a = tuple(a)
    TorF = [0] * (a[-1] + 1)
    for ae in a:
        TorF[ae] = 1
    for i1 in range(n - 1):
        if TorF[a[i1]]:
            t = a[i1] * 2
            while t <= max(a):
                TorF[t] = 0
                t += a[i1]
        if a[i1 + 1] == a[i1]:
            TorF[a[i1]] = 0
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()
    tf = [0] * (a[-1] + 1)
    for ea in a:
        tf[ea] = 1
    for i1 in range(n - 1):
        if a[i1] == a[i1 + 1]:
            tf[a[i1]] = 0

        for i2 in range(2, a[-1]//a[i1] + 1):
            tf[a[i1] * i2] = 0
    r = sum(tf)
    print(r)


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

h,w=map(int,input().split())
ans=[[-3]*w for _ in range(h)]
s=[input() for _ in range(h)]
for i in range(h):
    tmp=0
    for j in range(w):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp
    tmp=0
    for j in range(w-1,-1,-1):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp

for j in range(w):
    tmp=0
    for i in range(h):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp
    tmp=0
    for i in range(h-1,-1,-1):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp

print(max( max(ans[i]) for i in range(h) ))

### FIXED CODE ###

h,w=map(int,input().split())
ans=[[-3]*w for _ in range(h)]
s=[input() for _ in range(h)]
for i in range(h):
    tmp=0
    for j in range(w):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp
    tmp=0
    for j in range(w-1,-1,-1):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp

for j in range(w):
    tmp=0
    for i in range(h):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp
    tmp=0
    for i in range(h-1,-1,-1):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp

print(max( max(ans[i]) for i in range(h) ))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_first = sorted(a)[-1]
a_second = sorted(a)[-2]
for i in range(n):
    print(a_second if i == a.index(a_first) else a_first)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_first = sorted(a)[-1]
a_second = sorted(a)[-2]
for i in a:
    print(a_second if i == a_first else a_first)
### BUGGY CODE ###

#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


def main():
    [N, M, X] = list(map(int, input().split()))

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)

    status = [0]*M
    for n in range(N):
        for m in range(M):
            status[m] += l[n][m + 1]
    for v in status:
        if v < X:
            print(-1)
            return
    
    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            if min_cost < cost:
                break
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C - Skill Up
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""

N, M, X = 0, 0, 0
BOOKS = []


def calc_price(book_combinations):
    price = 0
    understandings = [0] * M
    for i in range(len(book_combinations)):
        if book_combinations[i]:
            price += BOOKS[i][0]
            for j in range(len(BOOKS[i][1:])):
                understandings[j] += BOOKS[i][j + 1]
    for u in understandings:
        if u < X:  # couldn't understand
            return -1
    return price


def main():
    global N, M, X, BOOKS
    N, M, X = list(map(int, input().split()))
    BOOKS = [list(map(int, input().split())) for i in range(N)]

    ans = float('inf')
    for i in range(1, 2 ** N):  # => 1: at least one book should be buy
        price = calc_price([(i >> j) & 1 for j in range(N)])
        if 0 < price and price < ans:
            ans = price
    if ans == float('inf'):
        ans = -1
    print(ans)


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

def maxHeapify(H, A, i):
    left = 2*i
    right = left + 1
  
    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)
  
def buildmaxHeap(H,A):
    for i in range(H//2,0,-1):
        maxHeapify(H,A,i)
 
A = [None]
import sys
for x in sys.stdin.readlines():
    if x[0] == 'i':
        A.append(int(x[7:]))
    elif x[1] == 'x':
        buildmaxHeap(len(A) - 1, A)
        print(str(A[1]))
        A = [None] + A[2:]
    else:
        pass

### FIXED CODE ###

import heapq
pq = []

def insert(S,k):
    heapq.heappush(pq, - k)

def extractMax(S):
    a = - heapq.heappop(S)
    print(str(a))

L = input()
while L != "end":
    if L =="extract":
        extractMax(pq)
    else:
        L = L.split()
        insert(pq, int(L[1]))
    L = input()
### BUGGY CODE ###

big = 10**9 + 7

def typical_stairs(n,m,a):

    route = [0]*(n+1)
    route[0] = 1
    ans = route[0]
    tmp = 0
    a.append(-1)
    for j in range(m+1):
        for i in range(tmp,n):
            if a[j] == i+1:
                #print("a=%d, i+2=%d "%(a[j],i+2))
                route[i+1] = 0
                tmp = a[j]
                #print("route%d, %d = 0 + 0, route-> %s"%(i+1,route[i+1],route))
                if route[i] == 0 and route[i+1] == 0:
                    return 0
                else:
                    break
            else:
                route[i+1] = route[i] + route[i-1]

                #print("route%d, %d = %d + %d, route-> %s"%(i+1,route[i+1],route[i],route[i-1],route))
            ans = route[i+1]
    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]

    print typical_stairs(n,m,a)

### FIXED CODE ###

big = 10**9 + 7

def typical_stairs(n,m,a):

    flag = [True]*(n+1)
    for i in range(m):
        tmp = a[i]
        flag[tmp] = False

    route = [0]*(n+1)
    route[0] = 1
    ans = route[0]
    if flag[1]:
        route[1] = 1
    else:
        route[1] = 0

    for i in range(2,n+1):
        if flag[i]:
            route[i] = route[i-1] + route[i-2]

        ans = route[i]

    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]
    print typical_stairs(n,m,a)
### BUGGY CODE ###

N,X=(int(i) for i in input().split())
x = [int(i) for i in input().split()]
x.append(X)
x.sort()
b=[]
for i in range(N):
    c=x[i+1]-x[i]
    b.append(c)

d=max(b)
for j in range(d):
    zako = map(lambda x: x%(d-j), b)
    if list(zako).count(0) == N:
        ans=(d-j)
        print(ans)
        break

### FIXED CODE ###

N,X=(int(i) for i in input().split())
x = [int(i) for i in input().split()]
x.append(X)
x.sort()
b=[]
for i in range(N):
    c=x[i+1]-x[i]
    b.append(c)

def zako(m,n):
    s=max(m,n)
    t=min(m,n)
    while s%t!=0:
        ss =s%t
        s=t
        t=ss
    else:
        return t
dodo=b[0]
for j in range(N-1):
    bobo = zako(b[j+1],dodo)
    dodo = bobo
print(dodo)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import numpy as np

MOD = 10 ** 9 + 7
N = int(input())

graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

"""
包除の原理。各頂点を根として
・偶数個を選ぶ、そこが反例となっている、他は何でもよい、
・奇数個を選ぶ、そこが反例となっている、他は何でもよい
・根を含む成分は保留してある。保留している頂点の数を持っておく。
・偶数個の場合と奇数の場合の差分だけ持っておく
"""

def dp_merge(data1,data2):
    # parity, size
    N1 = len(data1) - 1
    N2 = len(data2) - 1
    data = np.zeros(N1+N2, dtype = np.int64)
    for n in range(N1+1):
        data[n:n+N2] += data1[n] * data2[1:] % MOD
    data %= MOD
    return data

fact_2 = [1,0,1]
for n in range(3,N+10):
    fact_2.append(fact_2[n-2] * (n-1) % MOD)
fact_2 = np.array(fact_2, dtype = np.int64)

def dp_add_edge(data):
    N = len(data) - 1
    data1 = np.zeros(N+2, dtype=np.int64)
    # 辺を反例に加えない
    data1[1:] = data
    # 辺を反例に加える
    data1[1] = - (data * fact_2[:N+1] % MOD).sum() % MOD
    return data1

def dfs(v, parent = None):
    data = None
    for y in graph[v]:
        if y == parent:
            continue
        data1 = dfs(y, v)
        # mergeする前に、最後の辺をひとつ加える
        data1 = dp_add_edge(data1)
        if data is None:
            data = data1
        else:
            data = dp_merge(data, data1)
    if data is None:
        return np.array([0,1],dtype=np.int64)
    return data

data = dfs(1)

answer = (data * fact_2[:N+1] % MOD).sum() % MOD

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import numpy as np

MOD = 10 ** 9 + 7
N = int(input())

graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

"""
包除の原理。各頂点を根として
・偶数個を選ぶ、そこが反例となっている、他は何でもよい、
・奇数個を選ぶ、そこが反例となっている、他は何でもよい
・根を含む成分は保留してある。保留している頂点の数を持っておく。
・偶数個の場合と奇数の場合の差分だけ持っておく
"""

def dp_merge(data1,data2):
    N1 = len(data1) - 1
    N2 = len(data2) - 1
    if N1 > N2:
        N1,N2 = N2,N1
        data1,data2 = data2,data1
    data = np.zeros(N1+N2, dtype = np.int64)
    for n in range(1,N1+1):
        data[n:n+N2] += data1[n] * data2[1:] % MOD
    data %= MOD
    return data

fact_2 = [1,0,1]
for n in range(3,N+10):
    fact_2.append(fact_2[n-2] * (n-1) % MOD)
fact_2 = np.array(fact_2, dtype = np.int64)

def dp_add_edge(data):
    N = len(data) - 1
    data1 = np.zeros(N+2, dtype=np.int64)
    # 辺を反例に加えない
    data1[1:] = data
    # 辺を反例に加える
    data1[1] = - (data * fact_2[:N+1] % MOD).sum() % MOD
    return data1

def dfs(v, parent = None):
    data = None
    for y in graph[v]:
        if y == parent:
            continue
        data1 = dfs(y, v)
        # mergeする前に、最後の辺をひとつ加える
        data1 = dp_add_edge(data1)
        if data is None:
            data = data1
        else:
            data = dp_merge(data, data1)
    if data is None:
        return np.array([0,1],dtype=np.int64)
    return data

data = dfs(1)

answer = (data * fact_2[:N+1] % MOD).sum() % MOD

print(answer)
### BUGGY CODE ###

n = int(input())
a = input().split()
a = [int(a[i]) for i in range(n)]
m = max(a)
ss = []
for b in range(-1 * m,m):
  s = 0
  for i in range(n):
    s = s + abs(a[i] - (b+i+1))
  ss.append(s)
print(min(ss))

### FIXED CODE ###

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

b_low=-1*(10**12)
b_high=10**12
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

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

from collections import deque

H, W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for x in range(H)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
print(costmap[Dh-1][Dw-1])


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]
 
#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])
### BUGGY CODE ###

from functools import reduce
N = int(input())
XL = [list(map(int,input().split())) for _ in range(N)]
area = sorted([[x-l,x+l] for x,l in XL], key=lambda x: x[1])
area_ = [area[0]]
for i in range(1,N):
  if reduce(lambda x,y: x and (area[i][0]>=y[1]), area_, True):
    area_.append(area[i])
print(len(area_))

### FIXED CODE ###

N = int(input())
XL = sorted([list(map(int,input().split())) for _ in range(N)], key=lambda x: x[0]+x[1])
n = 1
S_,T_ = XL[0][0]-XL[0][1], XL[0][0]+XL[0][1]
for i in range(1,N):
  S,T = XL[i][0]-XL[i][1], XL[i][0]+XL[i][1]
  if not (S < T_):
    n += 1
    S_,T_ = S,T
print(n)
### BUGGY CODE ###

N, M = map(int, input().split())
AC = []
WA = []
wa = 0
for i in range(M):
  p, S = input().split()
  p = int(p)
  if S == 'AC':
    if p in set(AC):
      continue
    else:
      AC.append(p)
      if p in set(WA):
        wa += WA.count(p)
  else:
    if p in set(AC):
      continue
    else:
      WA.append(p)
c = len(AC)
print(c, wa, sep=' ')

  

### FIXED CODE ###

N, M = map(int, input().split())
AC = [0 for i in range(N)]
WA = [0 for i in range(N)]
a = [0 for i in range(N)]
for i in range(M):
  p, S = input().split()
  p = int(p)
  if S == 'AC':
    AC[p-1] = 1
    a[p-1] = 0
  else:
    if AC[p-1] == 0:
      WA[p-1] += 1
      a[p-1] += 1
c = sum(AC)
wa = sum(WA) - sum(a)
print(c, wa, sep=' ')