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

import bisect
import sys
input = lambda: sys.stdin.readline().rstrip()

n=int(input())
s= list(input())
q=[]
qq=int(input())
for i in range(qq):
    q.append(list(input().split()))

# アルファベットごとに出現位置を記録
x=[[] for i in range(26)]
for i,j in enumerate(s):
    x[ord(j)-97].append(i)

# 終点対策
for i in range(26):
    x[i].append(float('inf'))


for i,j,k in q:
    if int(i)==1:
        if s[int(j)-1]!=k:
            v=s[int(j)-1]
            s[int(j)-1]=k
            # 変更前の要素を削除
            index=bisect.bisect_right(x[ord(v)-97], int(j)-1) - 1
            x[ord(v)-97].pop(index)
            # 変更後の要素を加える
            bisect.insort_right(x[ord(k)-97],int(j)-1)
    else:
        cnt=0
        j=int(j)-1
        k=int(k)-1
        for l in range(26):
            index=bisect.bisect_left(x[l],j)
            if x[l][index]<=k:
                cnt+=1


        print(cnt)

### FIXED CODE ###

import bisect
import sys
input = lambda: sys.stdin.readline().rstrip()

n=int(input())
s= list(input())
q=[]
qq=int(input())
for i in range(qq):
    q.append(list(input().split()))

# アルファベットごとに出現位置を記録
x=[[] for i in range(26)]
for i,j in enumerate(s):
    x[ord(j)-97].append(i)

# 終点対策
for i in range(26):
    x[i].append(5*10**5)


for i,j,k in q:
    if int(i)==1:
        if s[int(j)-1]!=k:
            v=s[int(j)-1]
            s[int(j)-1]=k
            # 変更前の要素を削除
            index=bisect.bisect_right(x[ord(v)-97], int(j)-1) - 1
            x[ord(v)-97].pop(index)
            # 変更後の要素を加える
            bisect.insort_right(x[ord(k)-97],int(j)-1)
    else:
        cnt=0
        j=int(j)-1
        k=int(k)-1
        for l in range(26):
            index=bisect.bisect_left(x[l],j)
            if x[l][index]<=k:
                cnt+=1


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

def resolve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    ans = 0
    l = [0 for i in range(K)]
    for i in range(K):
        l[i] = (p[i]*(p[i]+1))//2/p[i]
    ans = sum(l)
    for i in range(K, N):
        l[i%K] = (p[i]*(p[i]+1))//2/p[i]
        tmp = sum(l)
        if ans < tmp:
            ans = tmp
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    l = [0]*N
    l[0] = p[0]+1
    for i in range(1, N):
        l[i] = l[i-1]+p[i]+1
    ans = l[K-1]
    for i in range(N-K):
        tmp = l[K+i]-l[i]
        if tmp > ans:
            ans = tmp
    print(ans/2)
resolve()
### BUGGY CODE ###

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

changes = []

wests = tuple([i for i in range(N) if S[i] == 'W'])
easts = tuple([i for i in range(N) if S[i] == 'E'])

# print(wests)
# print(easts)


for leader in range(N):
    change = 0
    change += len([i for i in range(N) if i < leader and S[i] == 'W'])
    change += len([i for i in range(N) if leader < i and S[i] == 'E'])
    changes.append(change)

print(min(changes))

### FIXED CODE ###

import bisect

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

changes = []

wests = [i for i in range(N) if S[i] == 'W']
# print(wests)
easts = [i for i in range(N) if S[i] == 'E']
# print(easts)

for leader in range(N):
    change = 0
    change += bisect.bisect_left(wests, leader)
    change += len(easts) - bisect.bisect_right(easts, leader)
    changes.append(change)

print(min(changes))
### BUGGY CODE ###

n, y = map(int, input().split())
y = y/1000
answer= []

for rep1 in range(n + 1):
    for rep2 in range(n + 1 - rep1):
        for rep3 in range(n + 1 - rep1 - rep2):
            if rep1 + rep2 + rep3 == n and rep1 * 10 + rep2 * 5 + rep3 == y:
                answer = [rep1,rep2, rep3]
                break

print(answer[0], answer[1], answer[2]) if answer != [] else print("-1 -1 -1")


### FIXED CODE ###

n, y = map(int, input().split())
y = y/1000
answer= []

for ten in range(n + 1):
    for five in range(n + 1 - ten):
        one = n - ten - five
        if ten * 10 + five * 5 + one == y:
            answer = [ten, five, one]
            break

print(answer[0], answer[1], answer[2]) if answer != [] else print("-1 -1 -1")
### BUGGY CODE ###

n, m = map(int, input().split())
ll = []

for i in range(n):
    l = list(map(int, input().split()))
    ll.append(l)

i = 0
while i < n-1:
    k = i+1
    while k <= n-1:
        if ll[i][0] > ll[k][0]:
            ll[i], ll[k] = ll[k], ll[i]
        k += 1
    i+=1
s = 0
cst = 0
while m > 0:
    cst += ll[s][0] * ll[s][1]
    m -= ll[s][1]
    s += 1
print(cst + m*ll[s-1][0])

### FIXED CODE ###

n, m = map(int, input().split())
ll = []
for i in range(n):
    l = list(map(int, input().split()))
    ll.append(l)

ll.sort()

t = 0
cst = 0
i = 0
while t < m:
    t += ll[i][1]
    cst += ll[i][0]*ll[i][1]
    if t > m:
        cst -= ll[i][0]*(t-m)
    i += 1
print(cst)
### BUGGY CODE ###

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

def getTargetIndex():
    prev = 0
    for i in range(0,n-1):
        left = 0
        right = 0
        left = list[:i+1]
        right = list[i+1:]
        diff = abs(sum(left)- sum(right))
        if(i == 0):
            prev = diff
        else:
            if diff < prev:
                prev = diff
    print(prev)


getTargetIndex()


### FIXED CODE ###

n = int(input())
array = list(map(int,input().split(' ')))

left= array[0]
right = sum(array) - left

prev = 0
for i in range(0,n-1):
    diff = abs(left - right)
    left = left + array[i+1]
    right = right - array[i+1]

    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)
### BUGGY CODE ###

import math
K = int(input())
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      _gcd=math.gcd(math.gcd(i, j), k)
      count += _gcd
print(count)

### FIXED CODE ###

import math
K = int(input())
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    x=math.gcd(i, j)
    for k in range(1, K+1):
      _gcd=math.gcd(x, k)
      count += _gcd
print(count)
### BUGGY CODE ###


H,W,D = map(int,input().split())
A = []

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

dic = {}


for i in range(H):

    for j in range(W):

        dic[A[i][j]] = [i,j]

Q = int(input())


for i in range(Q):

    ans = 0

    L,R = map(int,input().split())

    now = dic[L]

    for j in range((R-L) // D):

        now = dic[L + j * D]
        nex = dic[L + (j+1) * D]

        ans += abs(now[0]-nex[0]) + abs(now[1]-nex[1])

    print(ans)
        


### FIXED CODE ###


H,W,D = map(int,input().split())
A = []

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

dic = {}


for i in range(H):

    for j in range(W):

        dic[A[i][j]] = [i,j]

Q = int(input())

nlis = [0]
for i in range(H * W):

    i += 1

    if i - D < 1:
        nlis.append(0)

    else:
        now = dic[i]
        las = dic[i-D]
        nlis.append(nlis[i-D] + abs(now[0]-las[0]) + abs(now[1]-las[1]))


for i in range(Q):

    L,R = map(int,input().split())

    print(nlis[R] - nlis[L])
### BUGGY CODE ###

N, K = map(int,input().split())
moves = []

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    moves.append((L, R))
moves.sort()

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1
# print(moves)

for n in range(1, N+1):
    for L, R in moves:
        if n - L <= 0 :
            break
        for dis in range(L, R+1):
            if n - dis >= 1:
                dp[n] += dp[n - dis]
            else:
                break

# print(dp)
print(dp[N] % mod)


### FIXED CODE ###

n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
#import collections
#import sys
 
#input=sys.stdin.readline
 
N=int(input())
l=[]
clist=[]
 
for i in range(N):
    l.append(list(input()))
    l[i].sort()
    l[i]="".join(l[i])
    #clist.append(collections.Counter(list(input().replace("\n",""))))#ここは普通に入れてfor文でcounterする
 
count=0
 
for i in range(N):
    for j in range(i+1,N):
        if l[i]==l[j]:
            count+=1
            
print(count)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import collections 
 
N=int(input())
l=[]
 
for i in range(N):
    l.append(list(input()))
    l[i].sort()
    l[i]="".join(l[i])
    
clist=list(collections.Counter(l).values())

count=0
for c in clist:
    count+=int(c*(c-1)//2)
    
print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))

for i in range(1, 100):
  imos = [0] * (n + 1)
  for j in range(n):
    imos[max(0, j - A[j])] += 1
    imos[min(n, j + A[j] + 1)] -= 1
  
  nA = [0] * n
  nA[0] = imos[0]
  for j in range(1, n):
    nA[j] = nA[j - 1] + imos[j]

  A = nA[:]
  if i >= k:
    break

print(*A)

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))

for i in range(1, 100):
  imos = [0] * (n + 1)
  for j in range(n):
    imos[max(0, j - A[j])] += 1
    imos[min(n, j + A[j] + 1)] -= 1
  
  nA = [0] * n
  nA[0] = imos[0]
  for j in range(1, n):
    nA[j] = nA[j - 1] + imos[j]

  A = nA[:]
  if i >= k:
    break

print(*A)
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

def is_ok(x, A, N, K):
    s = 0
    for i in range(N):
        if A[i] >= 0:
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        if A[i] < 0:
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[N-1-jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
    t = 0
    for i in range(N):
        if A[i] * A[i] <= x:
            t += 1
    total = (s - t) / 2
    return total >= K

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
ok, ng = 10**18, -10**18

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif mid >= 0:
            s += N
        if A[i] * A[i] <= mid:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) // 2
    # それがK個以上あるかを判定する
    if total >= K:
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

h, w = map(int, input().split())
hw = h * w
if hw == 1:
    print(0)
    exit()
a = ''.join(input() for _ in range(h))
a = ''.join(map(lambda c: '0' if c == '#' else '1', a))
bits = int(a, 2)
count = 0

line_b = (1 << w) - 1
line_t = line_b << w * (h - 1)
line_r = sum(1 << b for b in range(0, hw, w))
line_l = line_r << w - 1
while bits:
    mask_t = (bits << w) | line_b
    mask_b = (bits >> w) | line_t
    mask_l = (bits << 1) | line_r
    mask_r = (bits >> 1) | line_l
    bits &= mask_t & mask_b & mask_l & mask_r
    count += 1
print(count)


### FIXED CODE ###

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

a = ''.join(input() + '#' for _ in range(h))
a = a.replace('.', '1').replace('#', '0')

bits = int(a, 2)

w1 = w + 1
h1 = h + 1
bits <<= w1

frame = (1 << w1) - 1
frame |= frame << h1 * w1
frame |= sum(1 << b for b in range(w1, h1 * w1, w1))

count = 0
while bits:
    count += 1
    mask = bits | frame
    #       up             down           left          right
    bits &= (mask << w1) & (mask >> w1) & (mask << 1) & (mask >> 1)
print(count)
### BUGGY CODE ###

import sys

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

def main():

    N = int(input())
    A = sorted(list(map(int,input().split())))
    check = [0] * N
    ans = 0

    for i in range(N):
        if check[i] == 1:
            continue
        elif check[i] == 0 and A.count(A[i]) == 1:
            ans += 1
        for j in range(i+1,N):
            if A[j] % A[i] == 0:
                check[j] = 1
            else:
                continue
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

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

def main():

    N = int(input())
    A = sorted(list(map(int,input().split())))
    A_max = A[-1] + 1
    dp = [0] * A_max

    for i in A:
        dp[i] += 1
        if dp[i] == 1:
            for j in range(i*2,A_max,i):
                dp[j] = 2
    print(dp.count(1))

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

N = int(input())
cnt = 0
number = 1

while number <= N:
    
    for i in range(1,N+1):
        for j in range(1,N+1):
            for k in range(1,N+1):
                if i**2 + j**2 + k**2 + i*j + j*k + k*i == number:
                    cnt += 1
                else:
                    continue
    print(cnt)
    cnt = 0
    number += 1

### FIXED CODE ###

N = int(input())
ans_list = [0 for _ in range(1,10100)]

for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            value = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if value <= 10000:
                ans_list[value] += 1

for i in range(1, N+1):
    print(ans_list[i])
### BUGGY CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=0
l=[0]
for i in range(n):
  l.append(l[i]+a[i])
l.sort()
L=collections.Counter(l)
for j in range(len(L)):
  x=L.most_common()[j][1]
  c+=int(x*(x-1)/2)
print(c)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=0
l=[0]
for i in range(n):
  l.append(l[i]+a[i])
L=collections.Counter(l)
for j in L.values():
  c+=int(j*(j-1)/2)
print(c)
### BUGGY CODE ###

N = int(input())
S = list(input())
f=0
ijk = [[i+1,j+1,k+1] for i in range(N) for j in range(N) for k in range(N) 
        if i<j<k 
        if S[i]!=S[j] and
           S[i]!=S[k] and
           S[j]!=S[k]]
# print(ijk)
for i in range(len(ijk)):
    if(ijk[i][1]-ijk[i][0] != ijk[i][2]-ijk[i][1]):
        f+=1
print(f)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in s:
  if i=="R":r+=1
  elif i=="G":g+=1
  else:b+=1

ans=r*g*b
for i in range(n):
  for j in range(i+1,n):
    k_ = j+(j-i)
    if(k_ >=n):
      break
    ans -= int(s[i]!= s[j] and s[i] != s[k_] and s[j] != s[k_])

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

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = sorted([[i+1, d] for i, d in enumerate(lr())], key=lambda x: x[1])[::-1]
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0] = 0
    for s in range(1, N+1):
        for x in range(s):
            for y in range(s-x):
                i, d = A[x+y]
                dp[x+1, y] = max(dp[x, y]+d*(i-x-1), dp[x+1, y])
                dp[x, y+1] = max(dp[x, y]+d*(N-y-i), dp[x, y+1])
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i, N-i])
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = sorted([[i+1, d] for i, d in enumerate(lr())], key=lambda x: x[1])[::-1]
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0] = 0
    for x in range(N):
        for y in range(N-x):
            i, d = A[x+y]
            dp[x+1, y] = max(dp[x, y]+d*(i-x-1), dp[x+1, y])
            dp[x, y+1] = max(dp[x, y]+d*(N-y-i), dp[x, y+1])
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i, N-i])
    print(ans)
resolve()
### BUGGY CODE ###

A = [1] * (1<<18)
B = [1] * (1<<18)
def convolve(a, b):
    def fft(f, w, p):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    x = f[j]
                    y = f[j+d]
                    f[j] = (x + y) % p
                    f[j+d] = u * (x - y) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f, w, p):
        d = 1
        while d < n:
            v = pow(w, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    x = f[j]
                    y = f[j+d] * u
                    f[j] = (x + y) % p
                    f[j+d] = (x - y) % p
                u = u * v % p
            d *= 2
 
    p, g = (81 << 27) + 1, 7
    n0, n1 = len(a), len(b)
    n = 1 << ((max(n0, n1) - 1).bit_length() + 1)
    a = a[:] + [0] * (n-n0)
    b = b[:] + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    fft(a, w, p)
    fft(b, w, p)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a, pow(w, p - 2, p), p)
    invn = pow(n, p - 2, p)
    for i in range(n0 + n1 - 1):
        a[i] = a[i] * invn % p
    return a

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
    B[a] += 1
C = convolve(B, B)
ans = 0
for i in range(200001)[::-1]:
    a = min(M, C[i])
    M -= a
    ans += a * i
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])
C = [0] * 101010
S = [0] * 101010

for a in A[::-1]:
    C[a] += 1
    S[a] += a
for i in range(101000)[::-1]:
    C[i] += C[i+1]
    S[i] += S[i+1]

def cnt(n):
    re = 0
    for a in A:
        b = min(max(n-a, 0), 101000)
        re += C[b]
    return re
def calc(n):
    re = 0
    for a in A:
        b = min(max(n-a, 0), 101000)
        re += S[b]  + C[b] * a
    return re

l, r = 0, 200001
while r - l > 1:
    m = (l+r) // 2
    if cnt(m) >= M:
        l = m
    else:
        r = m

print(calc(l) - (cnt(l) - M) * l)
### BUGGY CODE ###

#!/usr/bin/env python3
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 40:
    K = 40

for k in range(K):
    D = [0]*N

    for i in range(N):
        D[i] += 1
        if A[i] == 0:
            continue

        left = math.ceil(i - A[i] - 0.5)
        right = math.floor(i + A[i] + 0.5)
        if left < 0: left = 0
        if right > N-1: right = N-1
    
        for j in range(left, right+1):
            if i == j: continue
            D[j] += 1

    A = D


print(' '.join(map(str,A)))

    


### FIXED CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 41:
    K = 41

for k in range(K):
    D = [0]*N

    for i in range(N):
        left = max(i - A[i], 0)
        right = min(i + A[i], N-1)
        D[left] += 1
        if right + 1 < N: D[right+1] -= 1
    

    for i in range(1, N):
        D[i] += D[i-1]
    A = D


print(' '.join(map(str,A)))
### BUGGY CODE ###

n = int(input())
x = 1
ans = 0
while x < n:
    if ((n-x) % x) == 0:
        m = (n-x) // x
        if m <= x:
            break
        ans += m
    x += 1
print(ans)

### FIXED CODE ###

n = int(input())
x = 1
ans = 0
while x < n:
    m = (n - x) // x
    if m <= x:
        break
    if ((n-x) % x) == 0:
        ans += m
    x += 1
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c = [tuple(input()) for _ in range(h)]
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7
dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]

q = [((1, 0, x1, y1, i)) for i in range(4)]

while q:
    c1, c2, x, y, d = heappop(q)
    # print(x, y, d, c1, c2)
    if c1 > dp[x][y][d][0]:
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny] == '@':
            continue
        if i == d and c2 < k:
            if dp[nx][ny][i] > (c1, c2 + 1):
                dp[nx][ny][i] = (c1, c2 + 1)
                heappush(q, (c1, c2 + 1, nx, ny, i))
        else:
            if dp[nx][ny][i] > (c1 + 1, 1):
                dp[nx][ny][i] = (c1 + 1, 1)
                heappush(q, (c1 + 1, 1, nx, ny, i))

ans = min(dp[x2][y2][i][0] for i in range(4))
if ans == MAX:
    ans = -1
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c_ = [tuple(input()) for _ in range(h)]
c = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if c_[i][j] == '@':
            c[i][j] = True
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7


def convert(x, y, d):
    return (x * w + y) * 4 + d


# dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]
dp = [MAX * (k + 1) + k] * (h * w * 4)

# q = [((1, 0, x1, y1, i)) for i in range(4)]
q = [((k + 1, convert(x1, y1, i))) for i in range(4)]

while q:
    c0, xyd = heappop(q)
    c1 = c0 // (k + 1)
    c2 = c0 % (k + 1)
    # print(x, y, d, c1, c2)
    d = xyd % 4
    y = (xyd // 4) % w
    x = (xyd // 4) // w
    if c1 > dp[xyd] // (k + 1):
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nxyi = convert(nx, ny, i)
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny]:
            continue
        if i == d and c2 < k:
            if dp[nxyi] > c1 * (k + 1) + c2 + 1:
                dp[nxyi] = c1 * (k + 1) + c2 + 1
                heappush(q, (dp[nxyi], nxyi))
        else:
            if dp[nxyi] > (c1 + 1) * (k + 1) + 1:
                dp[nxyi] = (c1 + 1) * (k + 1) + 1
                heappush(q, (dp[nxyi], nxyi))

ans = min(dp[convert(x2, y2, i)] // (k + 1) for i in range(4))
if ans == MAX:
    ans = -1
print(ans)