Harryxun/sft_time huggingface dataset:
### 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)


def main():
    n,m = LI()
    a = LI()
    p = LI()
    fm = {}
    def f(k):
        if k in fm:
            return fm[k]
        g = 1
        for i in range(n):
            if k & (1 << i):
                g *= a[i] // fractions.gcd(g, a[i])
        fm[k] = m // g
        return fm[k]

    r = 0
    for k in range(1,1<<n):
        t = []
        b = 1.0
        for i in range(n):
            if k & (1 << i):
                t.append(1 << i)
                b *= p[i]
            else:
                b *= 100 - p[i]
            b /= 100

        c = 0
        tl = len(t)
        for l in range(1,1<<tl):
            o = 0
            lc = 0
            for j in range(tl):
                if l & (1 << j):
                    o |= t[j]
                    lc += 1
            if lc % 2 == 1:
                c += f(o)
            else:
                c -= f(o)
        r += b * c
    # print(fm)

    return '{:0.8f}'.format(r)


print(main())



### 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)


def main():
    n,m = LI()
    a = LI()
    p = [c / 100.0 for c in LI()]
    d = collections.defaultdict(lambda: 1.0)
    e = collections.defaultdict(lambda: 1)

    r = 0
    for k in range(1,1<<n):
        t = [i for i in range(n) if k & (1 << i)]
        l = k & (k-1)
        d[k] = d[l] * p[t[0]]
        e[k] = e[l] * a[t[0]] // fractions.gcd(a[t[0]], e[l])
        o = m // e[k]
        if len(t) % 2 == 1:
            r += o * d[k]
        else:
            r -= o * d[k]


    return '{:0.8f}'.format(r)


print(main())
### BUGGY CODE ###

import itertools
k, n = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.append(k)
a.reverse()
l = []
for i in range(n):
  l.append(a[i]-a[i+1])
k = []
for i in itertools.permutations(l, r=n-1):
  k.append(sum(i))
print(min(k))

### FIXED CODE ###

K,N = map(int,input().split())	
A = list(map(int,input().split()))
D=[A[0]-A[-1]+K]
for i in range(N-1):
    D.append(A[i+1]-A[i])
print(K-max(D))
### BUGGY CODE ###

n=int(input())
for h in range(1,(3*n)//4+1):
  for j in range(1,3501):
    if (4*h*j-j*n-n*h)>0 and 3500>=(n*h*j)/(4*h*j-j*n-n*h)>0 and ((n*h*j)/(4*h*j-j*n-n*h)).is_integer():
      print(h,j,(n*h*j)//(4*h*j-j*n-n*h))
      exit()

### FIXED CODE ###

n=int(input())
for h in range(1,(3*n)//4+1):
  for j in range(1,3501):
    if (4*h*j-j*n-n*h)>0 and 3500>=(n*h*j)/(4*h*j-j*n-n*h)>0 and ((n*h*j)/(4*h*j-j*n-n*h)).is_integer():
      print(h,j,(n*h*j)//(4*h*j-j*n-n*h))
      exit()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
import bisect
 
def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    pos = [-1 for _ in range(N)]
    for i,num in enumerate(a):
        pos[num-1] = i

    ins,count = [-1,N],0
    for i,num in enumerate(pos):
        ind = bisect.bisect_left(ins,num)
        bisect.insort(ins,num)
        l,r = ins[ind]-ins[ind-1],ins[ind+1]-ins[ind]
        count += (i+1)*(r*l)
    
    print(count)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
	
	class BinaryIndexedTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = size
			self.default = default
			self.BIT = [default]*(self.size+1)

		# function(max, min, plus, minus, etc...)
		def BIT_segfunc(self, x, y):
			return max(x, y)

		def BIT_query(self, idx):
			ret = self.default
			while idx > 0:
				ret = self.BIT_segfunc(ret, self.BIT[idx])
				idx -= idx&(-idx)
			return ret

		# update
		def BIT_update(self, idx, x):
			while idx <= self.size:
				self.BIT[idx] = self.BIT_segfunc(self.BIT[idx], x)
				idx += idx&(-idx)
			return

		def BIT_range(self, x, y):
			return self.BIT_query(y)-self.BIT_query(x)

		# seg確認用
		def BIT_print(self):
			print(self.BIT)
		
	N = int(input())
	a = list(map(int,input().split()))
	l = [0]*N;r = [0]*N
	left_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a):
	    l[num-1] = i + 1 - left_bit.BIT_query(num)
	    left_bit.BIT_update(num, i+1)
	right_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a[::-1]):
	    r[num-1] = i + 1 - right_bit.BIT_query(num)
	    right_bit.BIT_update(num, i+1)
	
	print(sum(l[i]*r[i]*(i+1) for i in range(N)))

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

def into_ruiseki(a):
	n = len(a)
	ret = [0 for i in range(n + 1)]
	for i in range(n):
		ret[i + 1] = ret[i] + a[i]
	return ret

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

left = into_ruiseki(a)
right = into_ruiseki(a[::-1])

total = sum(a)
ans = 0
for i in range(n):
	for j in range(n - i):
		if total - left[i] - right[j] == 0:
			ans += 1
print(ans)


### FIXED CODE ###

def into_ruiseki(a):
	n = len(a)
	ret = [0 for i in range(n + 1)]
	for i in range(n):
		ret[i + 1] = ret[i] + a[i]
	return ret

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

b = sorted(into_ruiseki(a))
# print("b =", b)
ans = 0
cnt = 1
for i in range(1, n + 1):
	if b[i] == b[i - 1]:
		cnt += 1
	else:
		ans += cnt * (cnt - 1) // 2
		cnt = 1
ans += cnt * (cnt - 1) // 2
print(ans)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):

      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append((i,j))
        while q:
          y,x=q.popleft()
          if visited[y][x]:
            continue
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx

            if 0<=ny<h and 0<=nx<w:
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='#':
                continue
              visited[ny][nx]=True #忘れがち
              # print(i,j,ny,nx)
              ans+=1
              for ddy,ddx in dd:
                nny=ny+ddy
                nnx=nx+ddx
                if 0<=nny<h and 0<=nnx<w:
                  if visited[nny][nnx]:
                    continue
                  if field[nny][nnx]=='.':
                    continue
                  q.append((nny,nnx))

      # print(ans)
  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[False]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if visited[i][j]:
        continue
      if field[i][j]!='#':
        continue
      q=collections.deque()
      q.append((i,j))
      b=0
      wh=0
      while q:
        y,x=q.popleft()
        if visited[y][x]:
          continue
        if field[y][x]=='#':
          b+=1
        else:
          wh+=1
        visited[y][x]=True
        for dy,dx in dd:
          ny=y+dy
          nx=x+dx
          if not (0<=ny<h and 0<=nx<w):
            continue
          if field[y][x]==field[ny][nx]:
            continue
          if visited[ny][nx]:
            continue
          q.append((ny,nx))
      ans+=b*wh
      # print(i,j,b,wh,ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    a = sorted(a, reverse=False)
    a[-1] = a[-1] // 2
print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)
for _ in range(m):
    tmp = (heapq.heappop(a) * (-1)) // 2
    heapq.heappush(a, -tmp)
print(sum(a) * -1)
### BUGGY CODE ###

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

for i in numl:
  i.sort()
  
for i in l:
  print(str(i[0]).zfill(6) + str((numl[i[0]].index(i[1]))+1).zfill(6))

### FIXED CODE ###

n,m = map(int,input().split())
L = [[] for i in range(n)]
ans = [None]*m
l = [list(map(int,input().split())) for i in range(m)]

for i in range(len(l)):
  L[l[i][0]-1].append([l[i][1],i+1])
  
for ind,lis in enumerate(L):
  lis.sort()
  for j in range(len(lis)):
    ans[lis[j][1] - 1] = str(ind+1).zfill(6) + str(j+1).zfill(6)
    
print(*ans,sep = '\n')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = max(i for i in range(n+1) if dp[i] < float("inf"))
    for i in range(n):
        if dp[i] == "inf":
            ansl[pos] = i
            break
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])
### BUGGY CODE ###

ma = lambda :map(int,input().split())
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,k = ma()
A = list(ma())
s = 1
zeros = [0 for i in range(n+1)]
for i in range(k):
    s*=A[i]
    if A[i] ==0:
        zeros[i] +=1
        zeros[min(n,i+k)] -=1
for i in range(1,n+1):
    zeros[i] += zeros[i-1]
for i in range(k,n):
    if zeros[i] >0:
        f = False
        yn(f)
        continue
    if A[i] > A[i-k]:
        f =True
    else:
        f=False
    yn(f)


### FIXED CODE ###

ma = lambda :map(int,input().split())
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,k = ma()
A = list(ma())
s = 1
zeros = [0 for i in range(n+1)]
for i in range(k):
    if A[i] ==0:
        zeros[i] +=1
        zeros[min(n,i+k)] -=1
for i in range(1,n+1):
    zeros[i] += zeros[i-1]
for i in range(k,n):
    if zeros[i] >0:
        f = False
        yn(f)
        continue
    if A[i] > A[i-k]:
        f =True
    else:
        f=False
    yn(f)
### BUGGY CODE ###

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

v = [[0, 0] for _ in range(N)]
s = []
ans = 500

for i in range(1<<N):
    tmp = 0
    for j in range(N):
        if ((i>>j)&1): v[j] = [B[j], j]
        else:          v[j] = [A[j], j]
    for j in range(N):
        p = j
        while (p and v[p][0] < v[p-1][0]):
            v[p], v[p-1] = v[p-1], v[p]
            tmp += 1
            p -= 1
    for j in range(N):
        if (((i>>v[j][1])+v[j][1]-j)&1):
            s.append(v[j][0]*500+j)
    if (len(s)&1):
        tmp = 500
        s.pop()
    while s:
        p = s.pop()
        q = s.pop()
        if ((p-q)&1): tmp += p-q
        else:         tmp += 500
    ans = min(ans, tmp)

if ans < 500:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

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

v = [[0, 0] for _ in range(N)]
s = []
ans = 500

for i in range(1<<N):
    tmp = 0
    for j in range(N):
        if ((i>>j)&1): v[j] = [B[j], j]
        else:          v[j] = [A[j], j]
    for j in range(N):
        p = j
        while (p and v[p][0] < v[p-1][0]):
            v[p], v[p-1] = v[p-1], v[p]
            tmp += 1
            p -= 1
    for j in range(N):
        if (((i>>v[j][1])+v[j][1]-j)&1):
            s.append(v[j][0]*500+j)
    if (len(s)&1):
        tmp = 500
        s.pop()
    while s:
        p = s.pop()
        q = s.pop()
        if ((p-q)&1): tmp += p-q
        else:         tmp += 500
    ans = min(ans, tmp)

if ans < 500:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

s = input()
counter = 0
for i in range(3, len(s)+1):
    for j in range(len(s)-i+1):
        num = int(s[j:j + i])
        if num % 2019 == 0:
            counter += 1
print(counter)


### FIXED CODE ###

import collections


def comb(n):
    return n * (n-1)/2


s = input()
ans = 0
lst_mod = [0]*2019  # O(N)で回した連続値のmod(2019)の値
lst_mod[0] += 1
num, dim = 0, 1
for char in reversed(s):
    num += int(char)*dim
    num %= 2019
    dim *= 10
    dim %= 2019  # サイズを大きくしたくないからmod(2019)を使う
    lst_mod[num] += 1

for mod in lst_mod:
    ans += comb(mod)
print(int(ans))
### BUGGY CODE ###

n, k = map(int, input().split())
s = list(input())
s = list((map(int, s)))
tipS = []
cnt = 1
ans = 0

for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
    else:
        tipS.append([s[i], cnt])
        cnt = 1
tipS.append([s[-1], cnt])

for i in range(len(tipS)):
    tmp = tipS[i][1]
    if tipS[i][0] == 0:
        cnt_tmp = 1
    else:
        cnt_tmp = 0

    for j in range(i + 1,len(tipS)):

        if tipS[j][0] == 1:
            tmp += tipS[j][1]

        else:
            if cnt_tmp < k:
                cnt_tmp += 1
                tmp += tipS[j][1]
            else:
                break
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
s = list(input())
s = list((map(int, s)))
tipS = []
cnt = 1
ans = 0
zeroInd = []
for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
    else:
        tipS.append([s[i], cnt])
        cnt = 1
tipS.append([s[-1], cnt])
total_sum = [0] * len(tipS)
total_sum[0] += tipS[0][1]
for i in range(len(tipS)):
    if tipS[i][0] == 0:
        zeroInd.append(i)
    if i != 0:
        total_sum[i] += tipS[i][1] + total_sum[i-1]
if len(zeroInd) != 0:
    start = zeroInd[0]
tmp_cnt = 0
tmp = 0
tmp2 = 0
before = 0
#print(total_sum)
for i in range(len(tipS)):

    if tipS[i][0] == 0:
        tmp_cnt += 1


        if tmp_cnt > k:
            ans = max(tmp, ans)
            #print("ans: {}".format(ans))
            tmp -= (total_sum[start] - before)
            before = total_sum[start]
            #print("minus{}".format(tmp))
            tmp += tipS[i][1]
            tmp_cnt -= 1
            tmp2 += 1
            start = zeroInd[tmp2]

        else:
            tmp += tipS[i][1]


    else:
        tmp += tipS[i][1]
    #print("tmp_cnt: {}".format(tmp_cnt))
    #print("tmp: {}".format(tmp))

ans = max(ans, tmp)

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
for i in range(n):
    while m > 0:
        a[i] = a[i] // 2
        a.sort(reverse = True)
        m -= 1
print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
A = list(map(int, input().split()))

pq = []
for a in A:
    heapq.heappush(pq, -a)#'-'にすることで最大値を考えることができる！
#print(pq)
for _ in range(m):
    a = (-heapq.heappop(pq)) // 2
    heapq.heappush(pq, -a)
print(-sum(pq))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mn_list = []
for i in range(1,n):
    sunuke = sum(a[:i])
    araiguma = sum(a[i:])
    mn_list.append(abs(sunuke-araiguma))
print(min(mn_list))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mn_list = []
sunuke = a[0]
araiguma = sum(a[1:])
res = abs(sunuke-araiguma)
for i in range(1,n-1):
    sunuke += a[i]
    araiguma -= a[i]
    res = min(res,abs(sunuke-araiguma))
print(res)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int):
    n = list(map(int,list(str(N))))
    kuriage = 0
    LEN = len(n)
    pay_count = 0
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay_count += 10-(n[i]+kuriage)
                kuriage = 1

    if kuriage == 1:
        pay_count += 1
    print(pay_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: str):
    n = list(map(int,list(N)))
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay_count += 10-(n[i]+kuriage)
                kuriage = 1

    if kuriage == 1:
        pay_count += 1
    print(pay_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)
    solve(N)

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

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
c=[input() for _ in range(h)]
"""
ha=[]
for i in range(h):
  for j in range(w):
    if c[i][j]=='@':
      ha.append([i,j])
"""
from collections import deque
seen=[[0]*w for _ in range(h)]
todo=deque([[0,x1,y1]])
seen[x1][x2]=1
while todo:
  t,x,y=todo.popleft()

  if x==x2 and y==y2:
    print(t)
    exit(0)
  if x>0:
    for xi in range(x-1,max(x-k,0)-1,-1):
      if c[xi][y]=='@':break
      if seen[xi][y]==1:continue
      seen[xi][y]=1
      todo.append([t+1,xi,y])
  if x<h-1:
    for xi in range(x+1,min(x+k,h-1)+1):
      if c[xi][y]=='@':break
      if seen[xi][y]==1:continue
      seen[xi][y]=1
      todo.append([t+1,xi,y])
  if y>0:
    for yi in range(y-1,max(y-k,0)-1,-1):
      if c[x][yi]=='@':break
      if seen[x][yi]==1:continue
      seen[x][yi]=1
      todo.append([t+1,x,yi])
  if y<w-1:
    for yi in range(y+1,min(y+k,w-1)+1):
      if c[x][yi]=='@':break
      if seen[x][yi]==1:continue
      seen[x][yi]=1
      todo.append([t+1,x,yi])
print(-1)

### FIXED CODE ###

from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
inf=float('inf')
seen=[[[(inf,inf)]*4 for _ in range(w)] for _ in range(h)]
D=[(-1,0),(0,1),(1,0),(0,-1)]# 上:0, 右:1, 下:2, 左:3
q=deque()
for d in range(4):
  seen[x1][y1][d]=(1,0)
  q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])
while q:
  x,y,d,c,k_=q.popleft()
  # nx, ny: 次の座標
  # nd: 次の進行方向
  # nc: 次の移動回数
  # nk: 次の進行済マス数
  for nd in range(4):
    if nd==d:
      dx,dy=D[nd]
      nk=1 if k_==k else k_+1
      nc=c+1 if k_==k else c
    else:
      dx,dy=0,0
      nk=0
      nc=c+1
    nx=x+dx;ny=y+dy
    if 0<=nx<h and 0<=ny<w and cmap[nx][ny]!='@' and seen[nx][ny][nd]>(nc,nk):
      seen[nx][ny][nd]=(nc,nk)
      if nc==c: # 同一方向に進むケースは次のループで一番はじめに処理する。
        q.appendleft((nx,ny,nd,nc,nk))
      else:
        q.append((nx,ny,nd,nc,nk))
ans=inf
for d in range(4):
  ans=min(ans,seen[x2][y2][d][0])
ans=-1 if ans==inf else ans
print(ans)
### BUGGY CODE ###

#049_C
import sys
sys.setrecursionlimit(100000)

s = input()

def dfs(x):
    if x == s:
        return True
    if len(x) > len(s):
        return False

    if any (dfs(x + k) for k in ['dream', 'dreamer', 'erase', 'eraser']):
        return True
    
    return False

print('YES' if dfs('') else 'NO')

### FIXED CODE ###

#049_C
s = input()[::-1]
k = ['maerd', 'remaerd', 'esare', 'resare']

tmp = 0
flg = True
while tmp < len(s):
    check = False
    for x in k:
        if s[tmp: tmp + len(x)] == x:
            check = True
            tmp += len(x)
    if check == False:
        flg = False
        break
        
print('YES' if flg else 'NO')
### BUGGY CODE ###

from copy import copy
n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
c = copy(a)
ans = 0
while k:
    if k & 1:
        ans = c[ans]
    t = copy(c)
    for i in range(n):
        t[i] = c[c[i]]
    c = copy(t)
    k >>= 1
print(ans + 1)

### FIXED CODE ###

from copy import copy
n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
ans = 0
while k:
    if k & 1:
        ans = a[ans]
    c = [a[a[i]] for i in range(n)]
    a = copy(c)
    k >>= 1
print(ans + 1)