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

import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    #    print(A)
    #    print(A_plus)
    #    print(A_minus)
    if N == K:
        ans = 1
        for i in A:
            ans *= i % mod
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)] % mod
        print(ans % mod)

    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= mod
        print(ans % mod)



    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)
    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


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

def floor(x):
    return int(x)

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

### FIXED CODE ###

a,b,n=map(int,input().split())
m=min(n,b-1)
tmp=(a*m//b)-((m//b)*a)    
print(tmp)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a_sum = sum(a)
#y = sum - x
ans = 10**15
for i in range(1,n):
    x = sum(a[:i])
    aa = abs(2 * x - a_sum)
    ans = min(ans,aa)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
a_c = a.cumsum()
a_t = a_c[-1]
diff = np.abs(2 * a_c - a_t)
ans = diff[:-1].min()
print(ans)
### BUGGY CODE ###

from functools import reduce

def nCr(N,a,mod):
    if a == 0:return 1
    num = reduce(lambda x,y:x * y % mod,range(N,N-a,-1))
    den = reduce(lambda x,y:x * y % mod,range(1,a+1))
    return num * pow(den,mod-2,mod)%mod

def nHr(n,a,mod):
    return nCr(n-1+a,n-1,mod)

mod = 10 ** 9 + 7

n = int(input())
lis = list(map(int,input().split()))
li = [-1] * n

for i in range(n+1):
    if li[lis[i]-1] != -1:
        left = li[lis[i]-1]+1
        right = i+1
        break
    else:li[lis[i]-1] = i

for k in range(1,n+2):
  #     print(nCr(n+1,k,mod),nCr(left+n-right,k-1,mod))
    print(nCr(n+1,k,mod)-nCr(left+n-right,k-1,mod))


### FIXED CODE ###

def cmb(N, r, mod):
    if ( r<0 or r>N ):
        return 0
    r = min(r, N-r)
    return g1[N] * g2[r] * g2[N-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
mod = 10 ** 9 + 7

n = int(input())
lis = list(map(int,input().split()))
li = [-1] * n

for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

for i in range(n+1):
    if li[lis[i]-1] != -1:
        left = li[lis[i]-1]+1
        right = i+1
        break
    else:li[lis[i]-1] = i

for k in range(1,n+2):
  #     print(nCr(n+1,k,mod),nCr(left+n-right,k-1,mod))
    ans = cmb(n+1,k,mod)-cmb(left+n-right,k-1,mod)
    if ans < 0:
        ans += mod
    print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    # dp[i][w]
    #   i番目の品物までで w を超えないように選んだ最大価値
    dp = { 0: 0 }   # { <sum weight>: <sum value> }
    for i in range(1, n + 1):
        dp_ = {}
        wi, vi = map(int, input().rstrip().split())
        for w, v in dp.items():
            w_ = w + wi
            v_ = v + vi
            if w_ <= wlimit and (w_ not in dp or dp[w_] < v_):
                dp_[w_] = v_
        dp.update(dp_)
    return(max(dp.values()))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))


### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]
clist, cnt = [], []
for si in s:
    c = Counter(si)
    # print(c)
    if c in clist:
        cnt[clist.index(c)] += 1
    else:
        clist.append(c)
        cnt.append(1)
ans = 0
for ci in cnt:
    ans += sum(range(1, ci))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = ["".join(sorted(input().split()[0])) for _ in range(n)]
cnt = {}
result = 0
for si in s:
    if si in cnt:
        result += cnt[si]
        cnt[si] += 1
    else:
        cnt[si] = 1
print(result)
### BUGGY CODE ###

s = input()
r = 0
while True:
    z = s.count('01')
    o = s.count('10')
    if z+o == 0:
        break
    elif z > o:
        s = s.replace('01', '')
        r += z
    else:
        s = s.replace('10', '')
        r += o
print(2*r)

### FIXED CODE ###

s = input()
print(2*min(s.count('0'), s.count('1')))
### BUGGY CODE ###

import itertools
n = int(input())
names = []
initial = ['M', 'A', 'R', 'C', 'H']
ans = 0
for i in range(n):
  name = input()
  if name[0] in initial:
    names.append(name)

combo = list(itertools.combinations(names, 3))

for i in combo:
  if not i[0][0] == i[1][0] and not i[0][0] == i[2][0] and not i[1][0] == i[2][0]:
    ans += 1

print(ans)

### FIXED CODE ###

import itertools
import time
n = int(input())
names = []
ans = 0
ini = ["M", "A", "R", "C", "H"]
count = {"M":0, "A":0, "R":0, "C":0, "H":0}
for i in range(n):
  name = input()
  if name[0] in ini:
    count[name[0]] += 1

combo = list(itertools.combinations(ini, 3))

for a, b, c in combo:
  ans += count[a]*count[b]*count[c]

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

import sys
readline = sys.stdin.readline

N, L = map(int, readline().split())
node = set([1])
for _ in range(N):
    S = list(map(int, readline().strip()))
    ls = len(S)
    pre = 1
    for s in S:
        vn = 2*pre + s
        if vn not in node:
            node.add(vn)
        pre = vn
cnt = 0
for d in node:
    h = 0
    if 2*d in node:
        h += 1
    if 2*d+1 in node:
        h += 1
    if h == 1:
        depth = L-d.bit_length()+1
        cnt ^= (-depth&depth)

print('Alice' if cnt else 'Bob')        


### FIXED CODE ###

import sys
readline = sys.stdin.readline

class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

sigma = 2
root = Node(sigma, 0)
def add_trie(S):
    vn = root
    for cs in S:
        if vn[cs] is None:
            vn[cs] = Node(sigma, vn.depth + 1)
        vn = vn[cs]
    vn.end = True

ans = 0

N, L = map(int, readline().split())

for _ in range(N):
    S = list(map(int, readline().strip()))
    add_trie(S)

cnt = 0
stack = [root]
while stack:
    vn = stack.pop()
    for i in range(2):
        if vn[i] is None:
            r = L - vn.depth
            cnt ^= -r&r
        else:
            stack.append(vn[i])

print('Alice' if cnt else 'Bob')
### BUGGY CODE ###

import numpy as np
N=input()
a=np.arange(np.float(N))+1
for i in range(len(a)):
    if a[i]%3==0 and a[i]%5==0:
        a[i]=0
    elif a[i]%3==0:
        a[i]=0
    elif a[i]%5==0:
        a[i]=0
print(int(sum(a)))


### FIXED CODE ###

import numpy as np
N=input()
a=np.arange(np.float(N))+1
a=np.where(a%3==0.,0,a)
a=np.where(a%5==0.,0,a)
print(int(sum(a)))
### BUGGY CODE ###

def main():
    S = input()
    t = len(list(S))
    while True:

        temp = S
        if '01' in S:
            S = S.replace('01', '')
        if '10' in S:
            S = S.replace('10', '')
        
        if temp == S:
            break
    print(t-len(list(S)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()
    c0, c1 = 0, 0
    c0 = S.count('0')
    c1 = S.count('1')
    print(2*min(c0, c1))
    


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

n=int(input())
l=[int(i) for i in input().split()]
from collections import Counter 
c=Counter(l) 
ans=[]
for i in c: 
    if c[i]>=2:
        ans=ans+[i]*(c[i]//2)
ans.sort(reverse=1)
if len(ans)<=1:
    print(0)
else: 
    print(ans[0]*ans[1])

### FIXED CODE ###

n=int(raw_input())
l=[int(i) for i in raw_input().split()]
from collections import Counter 
c=Counter(l) 
ans=[]
for i in c: 
    if c[i]>=2:
        ans=ans+[i]*(c[i]//2)
ans.sort(reverse=1)
if len(ans)<=1:
    print(0)
else: 
    print(ans[0]*ans[1])
### BUGGY CODE ###

N = int(input())
stones = input()
# stones = "...."


def count_painted_stones(stones, length):
    repainted_times = []
    for i in range(length+1):
        left_stones = stones[:i]
        left_black_stones = left_stones.count("#")
        right_stones = stones[i:]
        right_white_stones = right_stones.count(".")
        repainted_stones = left_black_stones + right_white_stones
        repainted_times.append(repainted_stones)

    return min(repainted_times)


print(count_painted_stones(stones, len(stones)))


### FIXED CODE ###

import numpy as np
N = int(input())
stones = np.array([0 if stone == "." else 1 for stone in input()])
# stones = np.array([0 if stone == "." else 1 for stone in ".#....."])


def count_painted_stones_by_cumsum(stones, length):
    left_black_stones = np.roll(np.cumsum(stones), 1)
    left_black_stones[0] = 0
    right_white_stones = np.roll(np.cumsum(1 - stones[::-1]), 1)
    right_white_stones[0] = 0

    return np.min(left_black_stones + right_white_stones[::-1])


print(count_painted_stones_by_cumsum(stones, len(stones)))
### BUGGY CODE ###

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 

res = [str(one) for one in final]
print ("\n".join(res))

### FIXED CODE ###

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)


for i in range(n-1):
    for j in range(i+2, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
final[0] = n
res = [str(one) for one in final]
print ("\n".join(res))
### BUGGY CODE ###

s = input()

count = 0

def str_del(str,index):
    str = str[:index]+str[index+1:]
    return str
 
string = s
can_remove = True
while can_remove:
  new_text = ''
  search_count_10 = string.count('10')
  if search_count_10 > 0:
    new_text = string.replace('10', '', search_count_10)
    count += search_count_10 * 2
    string = new_text

  search_count_01 = string.count('01')
  if search_count_01 > 0:
    new_text = string.replace('01', '', search_count_01)
    count += search_count_01 * 2
    string = new_text
  
  if search_count_01 == 0 and search_count_10 == 0:
    can_remove = False

print(count)


### FIXED CODE ###

s = input()

count0 = s.count('0')
count1 = s.count('1')
print(min(count0, count1) * 2)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
fs=0
a=sorted(a)
from itertools import combinations
#listからkコ選ぶ組み合わせ
for i in combinations(a,k):
    fs+=(i[-1]-i[0])%(10**9+7)
    if fs>=10**9+7:
        fs=fs%(10**9+7)
print(fs)    

### FIXED CODE ###

def pre_c(n, mod):
    f = [0] * (n + 1)
    g = [0] * (n + 1)
    for i in range(n + 1):
        if i == 0:
            f[i] = 1
            g[i] = 1
        else:
            f[i] = (f[i - 1] * i) % mod
            g[i] = pow(f[i], mod - 2, mod)

    return f, g

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10 ** 9 + 7
f, g = pre_c(n, mod)

ans = 0
for i in range(n - k + 1):
    min_temp = a[i] * f[n - i - 1] * g[k - 1] * g[n - i - 1 - k + 1] % mod
    max_temp = a[n - i - 1] * f[n - i - 1] * g[k - 1] * g[n - i - 1 - k + 1] % mod

    ans = (ans + (max_temp - min_temp) % mod ) %mod
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush
from math import sqrt
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

INF = 10**15

def dijkstra(E, s, g):
    d = [INF] * len(E)
    d[0] = 0

    queue = []
    heappush(queue, (0, s))

    while queue:
        dist_v, v = heappop(queue)
        if dist_v > d[v]:
            continue
        
        for e, w in E[v]:
            tmp = d[v] + w
            if tmp < d[e]:
                d[e] = tmp
                heappush(queue, (tmp, e))
    
    return d[g]


def main():
    x_s, y_s, x_t, y_t = map(int, readline().split())
    N,*xyr = map(int, read().split())

    XYR = []
    XYR.append((x_s, y_s, 0))
    XYR.append((x_t, y_t, 0))
    for x, y, r in zip(*[iter(xyr)]*3):
        XYR.append((x, y, r))
    
    E = [[] for _ in range(N+2)]
    for i in range(N+1):
        x_i, y_i, r_i = XYR[i]
        for j in range(i+1, N+2):
            x_j, y_j, r_j = XYR[j]
            d = sqrt((x_i - x_j)**2 + (y_i - y_j)**2)
            d -= r_i + r_j
            d = max(0, d)
            E[i].append((j, d))
            E[j].append((i, d))

    ans = dijkstra(E, 0, 1)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heappop, heappush
from math import sqrt
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

INF = 10**15

def dijkstra(E, s, g):
    d = [INF] * len(E)
    d[0] = 0

    queue = []
    heappush(queue, (0, s))

    while queue:
        dist_v, v = heappop(queue)
        if dist_v > d[v]:
            continue
        
        for e, w in E[v]:
            tmp = d[v] + w
            if tmp < d[e]:
                d[e] = tmp
                heappush(queue, (tmp, e))
    
    return d[g]


def main():
    x_s, y_s, x_t, y_t = map(int, readline().split())
    N,*xyr = map(int, read().split())

    XYR = []
    XYR.append((x_s, y_s, 0))
    XYR.append((x_t, y_t, 0))
    for x, y, r in zip(*[iter(xyr)]*3):
        XYR.append((x, y, r))
    
    E = [[] for _ in range(N+2)]
    for i in range(N+1):
        x_i, y_i, r_i = XYR[i]
        for j in range(i+1, N+2):
            x_j, y_j, r_j = XYR[j]
            d = sqrt((x_i - x_j)**2 + (y_i - y_j)**2)
            d -= r_i + r_j
            d = max(0, d)
            E[i].append((j, d))
            E[j].append((i, d))

    ans = dijkstra(E, 0, 1)
    print(ans)


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

import math
n,m=map(int,input().split())
a=list(map(int,input().split()))
ans=0

for i in range(m):
    a=sorted(a,reverse=True)
    a[0]=math.floor(a[0]/2)
     
for j in range(n):
    ans+=a[j]
    
print(ans)


### FIXED CODE ###

import heapq as hq
n,m=map(int,input().split())
a=[-int(x) for x in input().split()]
hq.heapify(a)
for i in range(m):
    x=hq.heappop(a)
    x=-x//2
    hq.heappush(a,-x)
 
print(sum(a)*-1)
### BUGGY CODE ###

import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[float('inf')]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[float("inf")]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == float('inf'):
        print(-1)
    else:
        print(o-1)
    


### FIXED CODE ###

import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)
### BUGGY CODE ###

def calc0(K, xyc):
    rmax = 0
    for i in range(K * 2):
        for j in range(K * 2):
            rcount = 0
            for x, y, c in xyc:
                rcount += ((x + j) // K + (y + i) // K) % 2 == c
            rmax = max(rmax, rcount)
    return rmax

def calc1(K, xyc):
    rmax = 0
    for i in range(K * 2):
        xs = [(x + c * K + (y + i) // K * K) % (2 * K) for x, y, c in xyc]
        for j in range(K * 2):
            rcount = 0
            for x in xs:
                rcount += ((x + j) // K)  % 2 == 1
            rmax = max(rmax, rcount)
    return rmax

def calc(K, xyc):
    rmax = 0
    for i in range(K):
        ts = [0 for x in range(K * 2)]
        for x, y, c in xyc:
            a = (x + c * K + (y + i) // K * K) % (2 * K)
            ts[a] += 1
        rcount = sum(ts[0:K])
        for j in range(K):
            rcount += -ts[j] + ts[j+K]
            rmax = max(rmax, rcount, N - rcount)
    return rmax

#import random
#N = 10000
#K = 20
#xyc = [(random.randint(0, 10000), random.randint(0, 10000), random.randint(0, 10000) % 2) for i in range(N)]

N, K = [int(e) for e in input().split()]
xyc = [input().split() for i in range(N)]
xyc = [(int(x), int(y), c == "W") for x, y, c in xyc]

#print(calc0(K, xyc))
#print(calc1(K, xyc))
print(calc(K, xyc))



### FIXED CODE ###

def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    p = [[0] * K2 for i in range(K2)]
    for x, y, c in xyc:
        y += c * K
        p[x % K2][y % K2] += 1
        p[(x + K) % K2][(y + K) % K2] += 1

    def isum(xs):
        r = 0
        yield r
        for x in xs:
            r += x
            yield r

    psum = [list(isum(row)) for row in p]
    pksum = [[b - a for a, b in zip(row, row[K:])] for row in psum]

    rmax = N / 2
    for y in range(K):
        rcount = sum(row[y] for row in pksum[:K])
        for x in range(K):
            rmax = max(rmax, rcount, N - rcount)
            rcount += -pksum[x][y] + pksum[x + K][y]

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()

judge = 0
AC_list = []
for i in range(len(S)):
    if S[i] == "A":
        judge = 1
    elif S[i] =="C":
        if judge == 1:
            judge = 0
            AC_list.append(i-1)
        else:
            pass
    else:
        judge = 0
        
for i in range(Q):
    l, r = map(int,input().split())
    ans = sum(l-1 <= j <= r-2 for j in AC_list)
    print(ans)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()

AC_list = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == "AC":
        AC_list[i+1] = AC_list[i]+1
    else:
        AC_list[i+1] = AC_list[i]

for i in range(Q):
    l, r = map(int,input().split())
    print(AC_list[r-1]-AC_list[l-1])
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10000000)
readline = sys.stdin.readline

def solve():
    H, W, K = map(int, readline().split())
    x1, y1, x2, y2 = map(int,readline().split())
    x1, y1, x2, y2 = (v - 1 for v in (x1, y1, x2, y2))
    C = [readline().rstrip() for i in range(H)]

    visited = [[False] * W for i in range(H)]
    dist = [[0] * W for i in range(H)]

    dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    q = deque()

    q.append((x1, y1, 0))
    visited[x1][y1] = True
    dist[x1][y1] = 0

    def aa(_i, _j, y, x, d):
        i, j = _i, _j
        for k in range(K):
            i += y
            j += x
            if not (0 <= i < H and 0 <= j < W):
                break
            if C[i][j] == '@':
                break
            if visited[i][j]:
                continue
            visited[i][j] = True
            dist[i][j] = d
            q.append((i, j, d))

    while q:
        i, j, d = q.popleft()
        for y,x in dirs:
            aa(i, j, y, x, d+1)
    
    if not visited[x2][y2]:
        print(-1)
    else:
        print(dist[x2][y2])
    
solve()


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10000000)
readline = sys.stdin.readline

def solve():
    H, W, K = map(int, readline().split())
    x1, y1, x2, y2 = map(int,readline().split())
    x1, y1, x2, y2 = (v - 1 for v in (x1, y1, x2, y2))
    C = [readline().rstrip() for i in range(H)]

    INF = 10 ** 10
    visited = [[INF] * W for i in range(H)]
    dist = [[0] * W for i in range(H)]

    dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    q = deque()

    q.append((x1, y1, 0))
    visited[x1][y1] = 0
    dist[x1][y1] = 0

    def aa(_i, _j, y, x, d):
        i, j = _i, _j
        for k in range(K):
            i += y
            j += x
            if not (0 <= i < H and 0 <= j < W):
                break
            if C[i][j] == '@':
                break
            if d > visited[i][j]:
                break
            if d == visited[i][j]:
                continue
            visited[i][j] = d
            dist[i][j] = d
            q.append((i, j, d))

    while q:
        i, j, d = q.popleft()
        for y,x in dirs:
            aa(i, j, y, x, d+1)
    
    if visited[x2][y2] == INF:
        print(-1)
    else:
        print(dist[x2][y2])
    
solve()