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

n, q = [int(i) for i in input().split()]
s = input()
l = []
r = []
for _ in range(q):
    i, k = [int(i) for i in input().split()]
    l.append(i)
    r.append(k)

for i, k in zip(l, r):
    print(s[i-1:k].count('AC'))


### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()
l = []
r = []
for _ in range(q):
    i, k = [int(i) for i in input().split()]
    l.append(i)
    r.append(k)

cum_sum = [0]
for i in range(n-1):
    if s[i:i+2] == 'AC':
        cum_sum.append(cum_sum[-1]+1)
    else:
        cum_sum.append(cum_sum[-1])
else:
    cum_sum.append(cum_sum[-1])

for i, k in zip(l, r):
    print(cum_sum[k-1] - cum_sum[i-1])
### BUGGY CODE ###

#!/usr/bin/python
import sys
#if sys.version_info[0]>=3:raw_input=input

from scipy.sparse import*
g=[]
n=int(raw_input())
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g+=[(a-1,b-1,1)]
	g+=[(b-1,a-1,1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g+=[(n,a-1,b)]
	z[a-1]=b
a,b,c=zip(*g)
a=map(int,csgraph.dijkstra(coo_matrix((c,(a,b)),[n+1]*2),1,n))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for e in g:
	if e[0]<e[1] and abs(a[e[0]]-a[e[1]])!=1:
		print('No')
		sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))

### FIXED CODE ###

#!/usr/bin/python
def shortestPath(g,s,dist,prev):
	n = len(g)-1
	Q=[]
	heapq.heappush(Q,(0,-2,s))
	while Q:
		e = heapq.heappop(Q)
		if prev[e[2]]!=-1: continue
		prev[e[2]] = e[1]
		for f in g[e[2]]:
			if dist[f[2]] > e[0] + f[0]:
				dist[f[2]] = e[0] + f[0]
				heapq.heappush(Q,(e[0]+f[0],f[1],f[2]))

import sys,heapq
#if sys.version_info[0]>=3:raw_input=input

n=int(raw_input())
g=[[] for _ in range(n+1)]
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g[a-1]+=[(1,a-1,b-1)]
	g[b-1]+=[(1,b-1,a-1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g[n]+=[(b,n,a-1)]
	z[a-1]=b
a=[1e9]*n+[0]
shortestPath(g,n,a,[-1]*(n+1))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for _ in g:
	for e in _:
		if e[1]<e[2] and abs(a[e[1]]-a[e[2]])!=1:
			print('No')
			sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))
### BUGGY CODE ###

n, m = map(int, input().split())
cnt = n
num = m//n
while num > 1:
    if m % num == 0 and num*cnt <= m:
        break
    else:
        num -= 1
print(num)

### FIXED CODE ###

n, m = map(int, input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
div = make_divisors(m)
for i in div[::-1]:
    if i <= m / n:
        print(i)
        break
### BUGGY CODE ###

import numpy as np

N = int(input())
A = []
for _ in range(N):
    arr = np.array(list(map(int, input().split())))
    A.append(np.flatnonzero(arr))

MOD = 10 ** 9 + 7
dp = np.zeros(1 << N, dtype=np.int64)
dp[0] = 1
for a in A:
    new_dp = np.zeros_like(dp)
    for i in a:
        x = (1 << i)
        new_dp[x:] += dp[:-x]
    dp = new_dp
    dp %= MOD
print(dp[-1])


### FIXED CODE ###

N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7

dp = [0] * (1 << N)
dp[0] = 1
for b in range(1, 1 << N):
    i = bin(b).count('1')
    for x in range(N):
        if (b >> x) & 1 and A[i - 1][x]:
            dp[b] += dp[b ^ (1 << x)]
    dp[b] %= MOD
print(dp[-1])
### BUGGY CODE ###

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

mm = ['#' + input() + '#' for i in range(h)]
m = ['#' * (w+2)] + mm + ['#' * (w+2)]

vertical = [[0] * (w+1) for i in range(h+1)]
for i in range(1, h+1):
    c = 0
    for j in range(1, w+2):
        if m[i][j] == '#':
            for k in range(c+1, j):
                vertical[i][k] = j-c-1
            c = j


horizontal = [[0] * (w+1) for i in range(h+1)]
for i in range(1, w+1):
    c = 0
    for j in range(1, h+2):
        if m[j][i] == '#':
            for k in range(c+1, j):
                horizontal[k][i] = j-c-1
            c = j

ans = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        ans = max(ans, vertical[i][j] + horizontal[i][j] - 1)

print(ans)


### FIXED CODE ###

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

mm = ['#' + input() + '#' for i in range(h)]
m = ['#' * (w+2)] + mm + ['#' * (w+2)]

vertical = [[0] * (w+1) for i in range(h+1)]
for i in range(1, h+1):
    c = 0
    for j in range(1, w+2):
        if m[i][j] == '#':
            for k in range(c+1, j):
                vertical[i][k] = j-c-1
            c = j


horizontal = [[0] * (w+1) for i in range(h+1)]
for i in range(1, w+1):
    c = 0
    for j in range(1, h+2):
        if m[j][i] == '#':
            for k in range(c+1, j):
                horizontal[k][i] = j-c-1
            c = j

ans = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        if m[i][j] == '#':
            continue
        ans = max(ans, vertical[i][j] + horizontal[i][j] - 1)

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

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
set_a = set(a)

count_list = []
if len(set_a) <= k:
    print(0)
else:
    for num in set_a:
        count_list.append(a.count(num))
    count_list = sorted(count_list, reverse = True)

    print(sum(count_list[k:]))

### FIXED CODE ###

from collections import Counter

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
set_a = set(a)

count_list = []
if len(set_a) <= k:
    print(0)
else:
    a = Counter(a)
    cost = 0
    for (v, c) in a.most_common()[k:]:
        cost += c
    print(cost)
### BUGGY CODE ###

N,M = map(int,input().split())
L_list = []
R_list = []
count = 0

for i in range(M):
    L,R=map(int,input().split())
    L_list.append(L)
    R_list.append(R)

for i in range(1,N+1):
    for j in range(M):
        if(i >= L_list[j] and i<=R_list[j]):
           
            if j==M-1:
                count+=1
        else:
            break
print(count)

### FIXED CODE ###

N,M = map(int,input().split())
L_list = []
R_list = []
count = 0
min_mn=float('inf')
max_mn=0
for i in range(M):
    L,R=map(int,input().split())
    min_mn = min(min_mn,R)
    max_mn = max(max_mn,L)

for i in range(1,N+1):
    if(i>=max_mn and i<=min_mn):
        count += 1
print(count)
### BUGGY CODE ###

n = int(input())
a = input().split()
flag = False
for i in range(n):
    for j in range(i + 1, n):
        if a[i] == a[j]:
            flag = True
            break
    if flag:
        break

if flag:
    print("NO")
else:
    print("YES")


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
if len(a) != len(set(a)):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N,M=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    for i in range(M):
        A[N-1]=int(A[N-1]/2)
        A.sort()
    print(sum(A))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A =  [-int(x) for x in input().split()]
A.sort()
for i in range(M):
    rem=A[0]
    heapq.heappush(A,int(rem/2))
    heapq.heappop(A)
    
print(-sum(A))
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
l=list(map(int,input().split()))
m=np.array([0])

for i in range(k,n+1):
  p = np.array(l[i-k:i])
  if np.sum(m) < np.sum(p):
    m = p
  
print(np.sum([m[j]*(m[j]+1)/2/m[j] for j in range(k)]))

### FIXED CODE ###

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
s = sum(p[:k])
m = s

for i in range(n-k):
  s = s-p[i]+p[i+k]
  if m < s:
    m = s
print((m+k)/2)
### BUGGY CODE ###

n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np
nums.sort()
npnums = np.array(nums)

cnt = 0 #個数のカウント


for i,v in enumerate(nums):
    if np.count_nonzero(v % npnums[:i+2] == 0) > 1:
        cnt +=1
    else:
        continue
print(n-cnt)

### FIXED CODE ###

n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np

ans= np.zeros(max(nums)+1)

for i in nums:
    if ans[i] >1:
        continue
    else:
        ans[i::i] +=1

cnt = 0
for i in nums:
    if ans[i] ==1:
        cnt +=1

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

import sys
input = sys.stdin.readline

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

for i in range(M):
    a[i] = int(input())

DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1

for i in range(2, N+1):
    if(i not in a):
        DP[i] = (DP[i-1]+DP[i-2])%mod
        
print(DP[N])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0]*M
mod = 10**9+7

for i in range(M):
    a[i] = int(input())

a = set(a)
DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1

for i in range(2, N+1):
    if(i not in a):
        DP[i] = (DP[i-1]+DP[i-2])%mod
        
print(DP[-1])
### BUGGY CODE ###

N = int(input())
Aj = list(map(int, input().split()))

ans = 1
for A in Aj:
	ans *= A

if ans > 10**18:
	ans = -1
print(ans)


### FIXED CODE ###

N = int(input())
Aj = list(map(int, input().split()))

ans = 1
ng = False
max = 10**18
for A in Aj:
	if A == 0:
		ans = 0
		break
	if ng or ans*A > max:
		ans = -1
		ng = True
	else:
		ans *= A
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(map(str, input())) for _ in range(H)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] == '.':
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[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(map(str, input())) for _ in range(H)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] == '.':
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[DH-1][DW-1])
### BUGGY CODE ###

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

import math
def combi(n,r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

max_combi = 0
l=0
for r in range(1,n):

    while a[l] <= (a[r]+1)//2:
        l+=1
    l-=1
    
    c = combi(a[r], a[l])
    if c > max_combi:
        max_combi = c
        x,y = a[r], a[l]

print(x,y)


### FIXED CODE ###

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

import bisect

mid = (a[-1]+1)//2
mid_idx = bisect.bisect_left(a, mid)

if abs(mid - a[mid_idx-1]) <= abs(a[mid_idx] - mid):
    print(a[-1], a[mid_idx-1])
else:
    print(a[-1], a[mid_idx])
### BUGGY CODE ###

import math
(N, M) = map(int, input().split())
TMPM = M

MAX_SQRT = int(math.sqrt(M))
prime_flag = [True] * (MAX_SQRT+1)
primes = []

prime_flag[0] = False
prime_flag[1] = False

for i in range(2, MAX_SQRT+1):
    mul = 2
    while True:
        p = i * mul
        if p > MAX_SQRT:
            break
        prime_flag[p] = False
        mul += 1

for i in range(2, MAX_SQRT+1):
    if prime_flag[i]:
        while M%i == 0:
            primes.append(i)
            M = int(M/i)

if M > 1:
    primes.append(M)


max_mul = 1
def Rec(primes, p, mul):
    global max_mul

    if TMPM//mul < N:
        return

    if p >= len(primes):
        if mul > max_mul:
            max_mul = mul
    else:
        Rec(primes, p+1, mul)
        Rec(primes, p+1, mul*primes[p])


Rec(primes, 0, 1)
print(max_mul)



### FIXED CODE ###

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

MAX_SQRT = int(math.sqrt(M))
prime_flag = [True] * (MAX_SQRT+1)
prime_dic = {}

prime_flag[0] = False
prime_flag[1] = False

for i in range(2, MAX_SQRT+1):
    mul = 2
    while True:
        p = i * mul
        if p > MAX_SQRT:
            break
        prime_flag[p] = False
        mul += 1

TMPM = M
for i in range(2, MAX_SQRT+1):
    if prime_flag[i]:
        while TMPM%i == 0:
            if i in prime_dic:
                prime_dic[i] += 1
            else:
                prime_dic[i] = 1
            TMPM = int(TMPM/i)

if TMPM > 1 or len(prime_dic) == 0:
    prime_dic[TMPM] = 1

max_mul = 1
def Rec(mul, p):
    global max_mul
    if M//mul < N:
        return

    if p >= len(prime_dic):
        if mul > max_mul:
            max_mul = mul
        return

    k = list(prime_dic.keys())[p]
    v = list(prime_dic.values())[p]
    for i in range(v+1):
        Rec(mul*(k**i), p+1)

Rec(1, 0)
print(max_mul)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float("inf")
mod = 10 ** 9 + 7

X, Y = MAP()

def grundy(a, b):
	if 0 <= a <= 1 and 0 <= b <= 1:
		return 0

	s = set()
	if a >= 2:
		i = a//2
		s.add(grundy(a%2, b+i))
		if a >= 4:
			s.add(grundy(a%2+2, b+(i-1)))
	if b >= 2:
		i = b//2
		s.add(grundy(a+i, b%2))
		if b >= 4:
			s.add(grundy(a+(i-1), b%2+2))

	ret = 0
	while ret in s:
		ret += 1

	return ret

print("Alice" if grundy(X, Y) else "Brown")


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float("inf")
mod = 10 ** 9 + 7

X, Y = MAP()
if abs(X-Y) <= 1:
	print("Brown")
else:
	print("Alice")
### BUGGY CODE ###

s = input()
t = input()
a = 1
b = 1
c = 0
while a <= len(s):
    for n in s:
        for m in t:
            if a == b and n == m:
                c += 1
            b += 1
        a += 1
        b = 1
print(len(s) - c)


### FIXED CODE ###

s = input()
t = input()
a = 0
for i in range(0, len(s)):
    if s[i] != t[i]:
        a += 1
print(a)
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    # test = []
    X, Y = 0, 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            X += v[j]
            Y += c[j]
            # test.append([v[j], c[j]])
    if ans < X - Y:
        ans = X - Y
    # print(test)

print(ans)

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    # test = []
    X, Y = 0, 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            X += v[j]
            Y += c[j]
            # test.append([v[j], c[j]])
    if ans < X - Y:
        ans = X - Y
    # print(test)

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

import sys
input = sys.stdin.readline

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

    while max(a) - min(a) > 0:
        a.sort()
        a[-1] = a[-1]%a[0]
        if a[-1] == 0:
            del a[-1]

    print(min(a))

main()

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    g = a[0]

    for i in range(1, n):
        g = fractions.gcd(g, a[i])
    
    print(g)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M,P = map(int,input().split())
ABC = [[int(x) for x in input().split()] for _ in range(M)]

INF = 10 ** 18
dist = [INF] * (N+1)
dist[1] = 0

loop = False
for i in range(2*N+100):
    for a,b,c in ABC:
        x = dist[a] + P - c
        if dist[b] > x:
            dist[b] = x
            if b == N and i > N:
                loop = True

if loop:
    answer = -1
else:
    answer = -dist[N]
    if answer < 0:
        answer = 0

print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M,P = map(int,input().split())
ABC = [[int(x) for x in input().split()] for _ in range(M)]

INF = 10 ** 18
dist = [INF] * (N+1)
dist[1] = 0

loop = False
for i in range(2*N+100):
    for a,b,c in ABC:
        x = dist[a] + P - c
        if dist[b] > x:
            dist[b] = x
            if b == N and i > N:
                loop = True

if loop:
    answer = -1
else:
    answer = -dist[N]
    if answer < 0:
        answer = 0

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

S = input()
n = len(S)
a = [0 for _ in range(n+1)]
l = [0 for _ in range(2019)]

a[0] = int(S)
l[a[0]%2019] += 1

for i in range(n):
    a[i+1] = a[i] - int(S[i])*pow(10, n-i-1)
    l[a[i+1]%2019] += 1

print(sum(map(lambda x: x*(x-1)//2, l)))


### FIXED CODE ###

import sys

input = sys.stdin.readline

S = input().rstrip()
n = len(S)
l = [0]*2019
d = 10

t = int(S[n-1])
l[t%2019] += 1

l[0] += 1

for i in range(n-2, -1, -1):
    t += int(S[i])*d%2019
    l[t%2019] += 1 
    d *= 10
    d %= 2019

ans = 0

for i in l:
    ans += i*(i-1)//2

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

def TrainingCamp():
    N = int(input())
    power = 1
    for i in range(1, N + 1):
        power *= i
    print(power % (10 ** 9 + 7))

TrainingCamp()


### FIXED CODE ###

def TrainingCamp():
    mod = 10 ** 9 + 7
    N = int(input())
    power = 1
    for i in range(1, N + 1):
        power *= i
        power %= mod
    print(power)

TrainingCamp()
### BUGGY CODE ###

A, B, Q = map(int, input().split())
shrine = [int(input()) for i in range(A)]
temple = [int(input()) for i in range(B)]

for i in range(Q):
    pos = int(input())
    plusA, plusB, minusA, minusB = 2E10, 2E10, -2E10, -2E10
    for i in range(A):
        a = pos - shrine[i]
        if(a>= 0):
            plusA = min(plusA, a)
        else:
            minusA = max(minusA, a)
    for i in range(B):
        b = pos - temple[i]
        if(b>= 0):
            plusB = min(plusB, b)
        else:
            minusB = max(minusB, b)
    lis = [max(plusA, plusB), abs(min(minusA, minusB)), abs(2*plusA-minusB), abs(2*minusA - plusB), abs(2*plusB - minusA), abs(2*minusB - plusA)]
    print(min(lis))

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10**18
shrine = [-INF] + [int(input()) for i in range(A)] + [INF]
temple = [-INF] + [int(input()) for i in range(B)] + [INF]

for i in range(Q):
    pos = int(input())
    b,d = bisect.bisect_right(shrine, pos), bisect.bisect_right(temple, pos)
    res = INF
    for S in [shrine[b-1], shrine[b]]:
        for T in [temple[d-1], temple[d]]:
            d1, d2 = abs(S-pos)+abs(T-S), abs(T-pos)+abs(S-T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1;Cw-=1;Dh-=1;Dw-=1
C=(Ch,Cw)
D=(Dh,Dw)
S=[list(input()) for i in range(H)]
dist=[[10**15 for j in range(W)] for i in range(H)]
dist[Ch][Cw]=0
q=deque([C])
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)>0):
    x,y=q.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if S[nx][ny]=="#":
                continue
            if dist[nx][ny]>dist[x][y]:
                dist[nx][ny]=dist[x][y]
                q.appendleft((nx,ny))
    for i in range(-2,3):
        for j in range(-2,3):
            nx=x+i
            ny=y+j
            if 0<=nx<H and 0<=ny<W:
                if S[nx][ny]=="#":
                    continue
                if dist[nx][ny]>dist[x][y]+1:
                    dist[nx][ny]=dist[x][y]+1
                    q.append((nx,ny))
if dist[Dh][Dw]==10**15:
    print(-1)
else:
    print(dist[Dh][Dw])


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1;Cw-=1;Dh-=1;Dw-=1
C=(Ch,Cw)
D=(Dh,Dw)
S=[list(input()) for i in range(H)]
dist=[[10**15 for j in range(W)] for i in range(H)]
dist[Ch][Cw]=0
q=deque([C])
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)>0):
    x,y=q.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if S[nx][ny]=="#":
                continue
            if dist[nx][ny]>dist[x][y]:
                dist[nx][ny]=dist[x][y]
                q.appendleft((nx,ny))
    for i in range(-2,3):
        for j in range(-2,3):
            nx=x+i
            ny=y+j
            if 0<=nx<H and 0<=ny<W:
                if S[nx][ny]=="#":
                    continue
                if dist[nx][ny]>dist[x][y]+1:
                    dist[nx][ny]=dist[x][y]+1
                    q.append((nx,ny))
if dist[Dh][Dw]==10**15:
    print(-1)
else:
    print(dist[Dh][Dw])
### BUGGY CODE ###

import bisect
import copy
from itertools import combinations


n = int(input())
l = list(map(int, input().split()))
l.sort()

li = list(combinations(l, 2))


ans = 0
for i in li:
    x = copy.deepcopy(l)
    x.remove(i[0])
    x.remove(i[1])
    left = abs(i[0] - i[1])
    right = min(i[0], i[1])

    left_div = bisect.bisect_left(x, left+1)
    right_div = bisect.bisect_right(x, right-1)
    ans += max(0, right_div - left_div)

print(ans)

### FIXED CODE ###

from bisect import bisect_left
import copy

n = int(input())
l = list(map(int, input().split()))
l.sort()


ans = 0
for small in range(n - 2):
    for mid in range(small + 1, n - 1):
        div = bisect_left(l, l[small] + l[mid], 0, n)
        if div > mid + 1:
            ans += div - mid - 1

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

S = input()
Q = int(input())

for _ in range(Q):
    Query = input().split()
    if Query[0] == '1':
        S = S[::-1]
    else:
        if Query[1] == '1':
            S = Query[2] + S
        else:
            S += Query[2]
print(S)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())

st = True
deq = deque(S)
for _ in range(Q):
    Query = input().split()
    if Query[0] == '1':
        st = not st
    else:
        if (Query[1] == '1') ^ st:
            deq.append(Query[2])
        else:
            deq.appendleft(Query[2])
if st:
    print(''.join(deq))
else:
    print(''.join(reversed(deq)))