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

N,Q = map(int,input().split())
line = list(input())
AC_locate = []
count_s = []
for i in range(N-1):
    if line[i] == 'A' and line[i+1] == 'C':
        AC_locate.append(int(i))
for i in range(Q):
    l,r = map(int,input().split())
    count = 0
    for locate in AC_locate:
        if locate > r-2:
            break
        if locate >= l-1:
            count += 1
    # for i in range(l-1,r):
    #     if line[i] == 'A' and line[i+1] == 'C':
    #         count += 1
    count_s.append(count)
for c in count_s:
    print(c)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
AC_cnt = [0] * N
for i in range(N-1):
  if S[i] == 'A' and  S[i+1] == 'C':
    AC_cnt[i+1] = AC_cnt[i] + 1
  else:
    AC_cnt[i+1] = AC_cnt[i]

for i in range(Q):
  begin, end = map(int,input().split())
  print(AC_cnt[end-1]-AC_cnt[begin-1])
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=[]
def ap2(num2):
    ans.append(num2)
for i in range(n-k+1):
    ap2(sum(p[i:i+k]))
print((max(ans)+k)/2)


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
num=[sum(p[0:k])]
def ap(num1):
    num.append(num1)
for i in range(n-k):
    ap(num[i]-p[i]+p[k+i])
print((max(num)+k)/2)
### BUGGY CODE ###

h,n= map(int, input().split())
p = []
for i in range(n):
  z = list(map(int, input().split()))
  p.append(z)
dp = [0]*(h+1)
for i in range(1,h+1):
  q = []
  for j in p:
    q.append(dp[max(0,i-j[0])]+j[1])
  dp[i] = min(q)
print(dp[h])

### FIXED CODE ###

import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = [0]*(h+max_a)
for i in range(1, h+max_a):
    dp[i] = min(dp[i-a] + b for a,b in ab)
print(min(dp[h:]))
### BUGGY CODE ###

from functools import reduce

N = int(input())


def u_gcd(a, b):
    x = a
    y = b
    while True:
        tmp = x % y
        if tmp == 0:
            return y
        else:
            x = y
            y = tmp


def gcd(*numbers):
    return reduce(u_gcd, numbers)


sum_N = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            sum_N += gcd(i, j, k)

print(sum_N)

### FIXED CODE ###

import math
from functools import reduce
N = int(input())
 
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
 
sum_N = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            sum_N += gcd(i, j, k)
 
print(sum_N)
### BUGGY CODE ###

import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
MOD = 10**9+7
def gcd(a, b):
    while a and b:
        if a > b:
            a %= b
        else:
            b %= a
    return max(a, b)

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

_a = a_ls[0]
for a in a_ls:
    _a = lcm(_a, a)
ls = [_a // a % MOD for a in a_ls]
print(sum(ls) % MOD)

### FIXED CODE ###

import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
MOD = 10**9+7
def gcd(a, b):
    while a and b:
        if a > b:
            a %= b
        else:
            b %= a
    return max(a, b)

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

_a = a_ls[0]
for a in a_ls:
    _a = lcm(_a, a)
ls = [_a // a for a in a_ls]
print(sum(ls) % MOD)
### BUGGY CODE ###

n = int(input())
s = input()

m = n

for i in range(n):

    turn = s[:i].count('W') + s[i+1:].count('E')

    m = min(turn, m)

print(m)

### FIXED CODE ###

n = int(input())
s = input()

m = n
turn = s[1:].count('E')
m = min(turn, m)
for i in range(1, n):
    if s[i-1] == 'W': turn += 1
    if s[i] == 'E': turn -= 1

    m = min(turn, m)

print(m)
### BUGGY CODE ###

import bisect

n=int(raw_input())
x=map(int,raw_input().split())+[float('inf')]
l=int(raw_input())
q=int(raw_input())
for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    cnt=0
    if a<b:
        while a!=b:
            cnt+=1
            if x[a]+l==x[bisect.bisect_left(x,x[a]+l)]:
                a=bisect.bisect_left(x,x[a]+l)
            else:
                a=bisect.bisect_left(x,x[a]+l)-1
            if a>b:
                break
    else:
        while a!=b:
            cnt+=1
            if x[a]-l==x[bisect.bisect_left(x,x[a]-l)]:
                a=bisect.bisect_left(x,x[a]-l)
            else:
                a=bisect.bisect_left(x,x[a]-l)
            if a<b:
                break
    print(cnt)

### FIXED CODE ###

import bisect

n=int(raw_input())
x=map(int,raw_input().split())+[float('inf')]
l=int(raw_input())
q=int(raw_input())
r=[[0]*20 for _ in xrange(n)]

for i in xrange(n):
    if x[i]+l==x[bisect.bisect_left(x,x[i]+l)]:
        r[i][0]=bisect.bisect_left(x,x[i]+l)
    else:
        r[i][0]=bisect.bisect_left(x,x[i]+l)-1

for k in xrange(19):
    for i in xrange(n):
        r[i][k+1]=r[r[i][k]][k]
        
for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    ans=0
    if a>b:
        a,b=b,a
    while 1:
        if bisect.bisect_left(r[a],b)>=1:
            ans+=1<<(bisect.bisect_left(r[a],b)-1)
            a=r[a][bisect.bisect_left(r[a],b)-1]
        else :
            ans+=1<<bisect.bisect_left(r[a],b)
            break
    print(ans)
### BUGGY CODE ###

a,b,n=map(int,input().split())
ans=0
for i in range(n+1):
    if int(a*i/b)-a*int(i/b)>=ans:
        ans=int(a*i/b)-a*int(i/b)
print(ans)

### FIXED CODE ###

a,b,n=map(int,input().split())
def f(x):
    y=(a*x)//b-a*(x//b)
    return y
print(f(min(b-1,n)))
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    if 1 in a and num != 1:
        ans -= count
        continue
    i = 2
    while i * i <= num:
        if num % i == 0:
            if i in a or (num // i) in a:
                ans -= count
                break
        i += 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
MAX = 1000000 + 9
dp = [True] * MAX
for num in a:
    for i in range(num*2, MAX, num):
        dp[i] = False
ans = 0
for num in a:
    if dp[num] and a[num] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()
count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            count += (right + 1)
else:
    mod_p_count = [0 for i in range(p)]
    mod_p_count[0] += 1
    for i in range(n):
        sub_s = int(s[i:])
        mod_p_count[sub_s % p] += 1
    for i in mod_p_count:
        count += i*(i - 1) // 2
print(count)

### FIXED CODE ###

n, p = map(int, input().split())
s = input()
sum_count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            sum_count += (right + 1)
else:
    modp_count = [0] * p
    modp_count[0] = 1
    subs_modp, pow = 0, 1
    for si in s[::-1]:
        subs_modp += ((int(si)*pow) % p)
        subs_modp %= p
        modp_count[subs_modp] += 1
        pow = (pow*10) % p
        
    for count in modp_count:
        sum_count += count*(count - 1) // 2
print(sum_count)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

N = I()
A = LI()

for idx in range(0, len(A)):
    A[idx] -= idx + 1
#  print(A)
# 全探索？
result = 10**12
for a in set(A):
    b = a
    tmp = 0
    for sub_a in A:
        tmp += abs(sub_a- b)
    result = min(result, tmp)
print(result)
exit()
#  b = sum(A) / len(A)
#  print('b', b)
#  if b < 0:
#      b = -(round(-b))
#  else:
#      b = round(b)
#  print('b', b)
#  result = 0
#  for a in A:
#      result += abs(a-b)
#  print(result)


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

test = False
if test:
    N = 2*10**5
    A = [i*2 for i in range(N)]
else:
    N = I()
    A = LI()

for idx in range(0, N):
    A[idx] -= idx + 1

import statistics
b = statistics.median(A)
#  print('b', b)
result = 0
for a in A:
    result += abs(a-b)
print(int(result))
### BUGGY CODE ###

from statistics import mode
from math import factorial

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1)
O = factorial(outside)

L = list(range(1, N+2))
M = [1] + list(range(1, outside+1))

l1 = 1
l2 = X
o1 = O
oc = 0
X %= MOD
O %= MOD

for k in range(1, len(A)+1):
    l1 *= k
    l2 //= L[-k]
    if k > outside + 1:
        Y = pow((l1 * l2) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        oc += 1
        Y = pow(l1 * l2 % MOD, MOD - 2, MOD)
        Y2 = pow(l1//k * o1 % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))
        o1 //= M[-oc]



### FIXED CODE ###

from statistics import mode

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

# 階乗・逆元の値を保存
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1]*i % MOD)
    inverse.append((pow(factorial[i], MOD-2, MOD)))

# combination計算
def nCr(n, r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % MOD


print(N)
for i in range(2, N+2):
    print(int(nCr(N+1, i) - nCr(outside, i-1)) % MOD)
### BUGGY CODE ###

import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    D.add(idx)
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

from collections import deque

if __name__ == "__main__":

    h,w = list(map(int,input().split()))

    a = [[None]]*h
    for i in range(h): a[i] = input()

    reached = [[True]*(w+2) for i in range(h+2)]
    for i in range(1, h+1): reached[i][1:-1] = [False]*w

    q = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append([i+1, j+1])
                reached[i+1][j+1] = True

    res = 0
    head = 0
    tail = len(q)
    count = len(q)
    i = 0
    while tail - head > 0:
        k = q[0][0]
        l = q[0][1]
        if not reached[k+1][l]:
            q.append([k+1,l])
            reached[k+1][l] = True
            tail += 1
        if not reached[k][l+1]:
            q.append([k,l+1])
            reached[k][l+1] = True
            tail += 1
        if not reached[k-1][l]:
            q.append([k-1,l])
            reached[k-1][l] = True
            tail += 1
        if not reached[k][l-1]:
            q.append([k,l-1])
            reached[k][l-1] = True
            tail += 1

        tail -= 1
        i += 1
        q.popleft()
        if i == count and tail - head > 0:
            count = tail
            i = 0
            res += 1
        else:
            pass

    print(res)

### FIXED CODE ###

def main():
  h,w = map(int,input().split())

  q = []
  reached = [[True]*(w+2)]
  for i in range(1, h+1):
    reached.append([True] + [s == '#' for s in list(input())] + [True])
    for j in range(1,w+1):
      if reached[i][j]: q.append((i,j))
  reached.append([True]*(w+2))

  res = 0
  for i in range(100000000):
    qq = []
    for k,l in q:
      if not reached[k+1][l]:
        qq.append((k+1, l))
        reached[k+1][l] = True
      if not reached[k][l+1]:
        qq.append((k, l+1))
        reached[k][l+1] = True
      if not reached[k-1][l]:
        qq.append((k-1, l))
        reached[k-1][l] = True
      if not reached[k][l-1]:
        qq.append((k, l-1))
        reached[k][l-1] = True
    if len(qq) == 0:
      break
    else:
      pass

    q = qq
    res += 1

  print(res)
  return 0

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

import sys
sys.setrecursionlimit(10**6)

def dfs1(s,c):
    visited[s]=1
    for i in v[s]:
        if visited[i]==0:
            d[c][i]=d[c][s]+1
            dfs1(i,c)
    return

def dfs2(c1,c2):
    visited[c2]=1
    dfs1(c1,c1)
    dfs1(c2,c2)
    return

n,k=map(int,raw_input().split())
d=[[0]*n for _ in xrange(n)]
v=[[] for _ in xrange(n)]
e=[]
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    e.append([a,b])
if k%2==0:
    min_del=1000000
    for i in xrange(n):
        cnt=0
        visited=[0]*n
        dfs1(i,i)
        for j in xrange(n):
            if d[i][j]>k/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)
else:
    min_del=1000000
    for i,j in e:
        cnt=0
        visited=[0]*n
        d=[[0]*n for _ in xrange(n)]
        dfs2(i,j)
        for l in xrange(n):
            if d[i][l]>(k-1)/2 or d[j][l]>(k-1)/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)

def bfs1(c):
    visited[c]=1
    q=deque([c])
    while len(q)>0:
        p=q.popleft()
        for i in v[p]:
            if visited[i]==0:
                q.append(i)
                visited[i]=1
                d[c][i]=d[c][p]+1

def bfs2(c1,c2):
    visited[c2]=1
    bfs1(c1)
    bfs1(c2)

n,k=map(int,raw_input().split())
d=[[0]*n for _ in xrange(n)]
v=[[] for _ in xrange(n)]
e=[]
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    e.append([a,b])
if k%2==0:
    min_del=2005
    for i in xrange(n):
        cnt=0
        visited=[0]*n
        bfs1(i)
        for j in xrange(n):
            if d[i][j]>k/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)
else:
    min_del=2005
    for i,j in e:
        cnt=0
        visited=[0]*n
        bfs2(i,j)
        for l in xrange(n):
            if d[i][l]>(k-1)/2 or d[j][l]>(k-1)/2:
                cnt+=1
        min_del=min(min_del,cnt)
        d[i]=[0]*n
        d[j]=[0]*n
    print(min_del)
### BUGGY CODE ###

N,M=map(int, input().split())
tmp=M//N
ma=1
for i in range(1, tmp+1):
    if not M % i:
        ma = max(i, ma)
print(ma)


### FIXED CODE ###

from math import sqrt
N,M=map(int, input().split())
tmp=int(sqrt(M))
ma=1
for i in range(1, tmp+1):
    if not M % i:
        div = M//i
        ma = max(i if i*N <= M else 0, ma, div if div*N <= M else 0)
print(ma)
### BUGGY CODE ###

N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,N-1):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q,K = map(int,input().split())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

d = [-1 for _ in range(0,N+1)]
d[K] = 0
queue = []
queue.append((K,g[K]))
while queue:
    start,edge = queue.pop(0)
    for to,cost in edge:
        if d[to] != -1:
            continue
        d[to] = d[start] + cost
        queue.append((to,g[to]))

for x,y in xy:
    print(d[x] + d[y])


### FIXED CODE ###

from collections import deque

N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,N-1):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q,K = map(int,input().split())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

d = [-1 for _ in range(0,N+1)]
d[K] = 0
queue = deque([[K,g[K]]])
while queue:
    start,edge = queue.popleft()
    for to,cost in edge:
        if d[to] != -1:
            continue
        d[to] = d[start] + cost
        queue.append((to,g[to]))

for x,y in xy:
    print(d[x] + d[y])
### BUGGY CODE ###

import itertools
K, S = map(int, input().split())
ans = 0

for i in itertools.product(range(K+1), repeat=2):
    if (S - sum(i)>=0) and (S - sum(i)<=K):
        ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
for x in range(K+1):
    for y in range (K+1):
        if  0 <= S - x- y <= K:
            ans +=1

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

n = int(input())
A = list(map(int, input().split()))
M = 1000000007
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        ans += (A[i] * A[j] % M)
print(ans%M)

### FIXED CODE ###

import sys
input = sys.stdin.readline
M = 1000000007
n = int(input())
A = list(map(int, input().split()))
ans = 0
s = 0
for i in range(n):
    s += A[i]
    s %= M

for i in range(n):
    s = s - A[i]
    if s < 0:
        s += M
    ans += A[i] * s
    ans %= M
print(ans)
### BUGGY CODE ###

#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
for m in range(M):
	I=list(map(int,input().split()))
	A.append(I[0])
	B.append(I[1])
tA=[]
tB=[]
for i,x in enumerate(A):
	if x==1:
		tA.append(B[i])
for i,x in enumerate(B):
	if x==N:
		if A[i] in tA:
			print('POSSIBLE')
			break
else:
	print('IMPOSSIBLE')

### FIXED CODE ###

#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for m in range(M):
	I=list(map(int,input().split()))
	if I[0]==1:
		A.append(I[0])
		B.append(I[1])
	elif I[1]==N:
		C.append(I[0])
		D.append(I[1])
if len(set(B)&set(C))>0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')
### BUGGY CODE ###

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

current_n = N
b_cnt = 0
flag = True
while current_n != 0:
    if flag:
        if current_n - A > 0:
            current_n = current_n - A
            b_cnt += A
        else:
            b_cnt += current_n
            current_n = 0
        flag = False
    else:
        if current_n - B > 0:
            current_n = current_n - B
        else:
            current_n = 0
        flag = True

print(b_cnt)


### FIXED CODE ###

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

q, r = divmod(N, A+B)

if r >= A:
    print(q*A+A)
else:
    print(q*A+r)
### BUGGY CODE ###

#encoding:utf-8

import math

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

def factorint(N):
    table = {}
    while(N > 1):
        for i in range(2,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    if i in table.keys():
                        table[i] += 1
                    else:
                        table[i] = 1
                break
    return table
ans = 1
if N == 1:
    ans = P
elif 1 < N < 40:
    #Nが２以上なのでpをｓｑｒｔしても良い
    facters = factorint(P)
    # print(facters)

    ans = 1
    for key in facters.keys():
        if facters[key]/N >= 1:
            ans *= key**(facters[key]//N)
else:
    pass

print(int(ans))
# print(type(ans))


### FIXED CODE ###

#encoding:utf-8

import math

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

def factorint(N):
    table = {}
    while(N > 1):
        for i in range(2,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    if i in table.keys():
                        table[i] += 1
                    else:
                        table[i] = 1
                break
    return table

ans = 1
if N == 1:
    ans = P
elif 1 < N < 40:
    for i in range(2,round(P**(1/N))+1):
        if P % i**N == 0:
            ans = i

else:
    pass

print(int(ans))
# print(type(ans))
### BUGGY CODE ###

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

Total = 0
for i in range(N):
    Synmmetry = True
    for a in range(N):
        for b in range(N):
            if S[a][(b + i) % N] != S[b][(a + i) % N]:
                Synmmetry = False
                break
        if not Synmmetry: break
    else: Total += 1
print(Total * N)

### FIXED CODE ###

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

Total = 0
for i in range(N):
    Synmmetry = True
    for a in range(N):
        for b in range(a, N):
            if S[a][(b + i) % N] != S[b][(a + i) % N]:
                Synmmetry = False
                break
        if not Synmmetry: break
    else: Total += 1
print(Total * N)
### BUGGY CODE ###

N = int(input())
p = set()
for _ in range(N):
    x, y = map(int, input().split())
    p.add((x, y))
p = list(p)

def cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])
def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        while len(qs)>1 and cross(qs[-1], qs[-2], qs[-1], p) >= 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n-2, -1, -1):
        p = ps[i]
        while len(qs)>t and cross(qs[-1], qs[-2], qs[-1], p) >= 0:
            qs.pop()
        qs.append(p)
    return qs

def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def rotating_calipers(ps):
    qs = convex_hull(ps)
    n = len(qs)
    if n == 2:
        return dist(qs[0], qs[1])
    i = j = 0
    for k in range(n):
        if qs[k] < qs[i]: i = k
        if qs[j] < qs[k]: j = k
    res = 0
    si = i; sj = j
    while i != sj or j != si:
        res = max(res, dist(qs[i], qs[j]))
        if cross(qs[i], qs[i-n+1], qs[j], qs[j-n+1]) < 0:
            i = (i + 1) % n
        else:
            j = (j + 1) % n
    return res


print(rotating_calipers(p))


### FIXED CODE ###

N = int(input())
p = []
for _ in range(N):
    x, y = map(int, input().split())
    p.append((x, y))
p = sorted(p, key=lambda i: i[0] + i[1])
x1, y1 = p[0]
x2, y2 = p[-1]
res = abs((x1 + y1) - (x2 + y2))
p = sorted(p, key=lambda i: i[0] - i[1])
x1, y1 = p[0]
x2, y2 = p[-1]
res = max(abs((x1 - y1) - (x2 - y2)), res)
print(res)