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

K = list(map(int, input()))
D = int(input())

mod = 10 ** 9 + 7

next_dp = [0] * D
border = 0

for current_digit in K:
    dp, next_dp = next_dp, [0] * D
    for current_mod, cnt in enumerate(dp):
        for next_mod in range(current_mod, current_mod + 10):
            next_dp[next_mod % D] += cnt

    for next_mod in range(border, current_digit + border):
        next_dp[next_mod % D] += 1

    border = (border + current_digit) % D

    for i in range(D):
        next_dp[i] %= mod
print((next_dp[0] + (border == 0) - 1) % mod)


### FIXED CODE ###

K = list(map(int, input()))
D = int(input())

mod = 10 ** 9 + 7

next_dp = [0] * D
border = 0

for current_digit in K:
    dp, next_dp = next_dp, [0] * D
    for current_mod, cnt in enumerate(dp):
        for next_mod in range(current_mod, current_mod + 10):
            next_dp[next_mod % D] += cnt

    for next_mod in range(border, current_digit + border):
        next_dp[next_mod % D] += 1

    border = (border + current_digit) % D

    for i in range(D):
        next_dp[i] %= mod
print((next_dp[0] + (border == 0) - 1) % mod)
### BUGGY CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l


q = deque([(1, 0)])

while(q):
    a, ca = q.popleft()
    bs = PT[a]

    c = list(range(1, cmax+1))
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        if COLOR[(na, nb)] == 0:
            clr = c.pop()
            if clr == ca:
                clr = c.pop()

            COLOR[(na, nb)] = clr
            q.append((b, clr))

print(cmax)

for a, b in PATH:
    print(COLOR[(a, b)])


### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    '''
    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l
    '''

q = deque([(1, -1)])
while(q):
    a, ng = q.popleft()
    bs = PT[a]

    c = 1
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        cab = COLOR[(na, nb)]

        if cab == ng:
            continue

        if cab == 0:
            if c == ng:
                c += 1
            clr = c
            COLOR[(na, nb)] = clr
            q.append((b, clr))
            c += 1

print(max(COLOR.values()))

clr = []
for a, b in PATH:
    clr.append(COLOR[(a, b)])

print("\n".join(map(str, clr)))
### BUGGY CODE ###

n=input()
b=list(map(int,input(). split ()))
c=1
for i in b:
  c=c*i
if c>10**18:
  print(-1)  
else:
  print(c)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split( )))
if 0 in a:
  print(0)
  
else:
    c=1
    for i in a:
        c= c*i
        if c> 10**18:
            c=-1
            break
    print(c)
### BUGGY CODE ###

import collections as col
N=int(input())
A=[ai for ai in map(int,input().split())]
CA=col.Counter(A)
CA_KEYS=sorted(CA.keys())
#print(CA_KEYS)
for Ai in CA_KEYS:
    CA_Tmp={ai:0 for ai in CA_KEYS}
#    print()
    crnt=A[0]
    next=Ai
    CA_Tmp[crnt]=1
#    print(crnt, end=" ")
    if CA_Tmp[next] > CA[next]:
        continue
    Ans=True
    for j in range(1, N):
#        print(next,end=" ")
        if next in CA:
            CA_Tmp[next]+=1
            if CA_Tmp[next] > CA[next]:
                Ans=False
                break
            crnt,next=next,crnt^next
        else:
            Ans=False
            break
    if Ans==True:
        if next!=A[0]:
#            print("No!",next,"!=",A[0])
            Ans=False
        else:
            break


print("Yes" if Ans==True else "No")


### FIXED CODE ###


import collections as col
N=int(input())
A=[ai for ai in map(int,input().split())]
Ans=False
CA=col.Counter(A)
if len(CA)==1 and 0 in CA:
    Ans=True
elif len(A)%3==0:
    if len(CA)==3:
        K=list(CA.keys())
        if (K[0]^K[1]==K[2]) and (CA[K[0]]==CA[K[1]]==CA[K[2]]):
            Ans=True
    elif len(CA)==2:
        K=list(sorted(CA.keys()))
        if CA[K[0]]*2==CA[K[1]]:
            Ans=True

print("Yes" if Ans==True else "No")
### BUGGY CODE ###

L = int(input(),2)

mod = 10**9+7


res = 0
bi = 1

judge = True

for i in range(1000001,0,-1):
    if ((L>>i)&1) == 1:
        res = (res+(pow(3,i,mod))*bi)%mod
        bi = bi*2
if (L&1) == 1:
    res += 3*bi
else:
    res += bi
print(res%mod)


### FIXED CODE ###

L = int(input(),2)

mod = 10**9+7

res = 0
bi = 1

thr = [1]
for i in range(1000002):
    thr.append(thr[-1]*3%mod)

for i in range(1000001,0,-1):
    if ((L>>i)&1) == 1:
        res = (res+(thr[i]*bi)%mod)%mod
        bi = bi*2%mod
if (L&1) == 1:
    res += 3*bi
else:
    res += bi
print(res%mod)
### BUGGY CODE ###

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

# 倍数のやつはTrueに
T = [False]*(10**6+1)
for i in A:
    for j in range(i*2, 10**6, i):
        T[j] = True

# ダブってるやつはTrueに
dbl = []
for i in A:
    if A.count(i) != 1:
        dbl.append(i)

for i in dbl:
    T[i] = True

# Falseの数を数える
ans = 0
for i in A:
    if T[i] == False:
        ans += 1

print(ans)

### FIXED CODE ###

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

cnt = [0] * ((10 ** 6) + 1)

for elem in a:
    cnt[elem] += 1

unique = []

for i in range((10 ** 6) + 1):
    if cnt[i] == 1:
        unique.append(i)

cnt = [0] * ((10 ** 6) + 1)

a = list(set(a))

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0
        
for elem in unique:
    if cnt[elem] == 0:
        ans += 1

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

import sys
import math
import itertools
from functools import reduce
from functools import lru_cache


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

def main():

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

    count =0
    for i in range(N):
        I =S[i]

        for j in range(i+1,N):
            J =S[j]
            if I==J:
                continue
            for k in range(j+1,N):
                K =S[k]
                if I!=K and J!=K and j-i !=k-j:
                    count+=1


    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
import itertools
from functools import reduce
from functools import lru_cache


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

def main():

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

    R=[0]*N
    G=[0]*N
    B=[0]*N
    r=0
    g  =0
    b=0
    count =0
    for i in range(N-1,-1,-1):
        if S[i] =="R":
            r+=1
        elif S[i] =="G":
            g+=1
        else:
            b+=1
        R[i]=r
        G[i]=g
        B[i]=b

    count =0
    for i in range(N):



        for j in range(i+1,N):
            SE = set(["R", "G", "B"])
            I = S[i]
            SE.remove(I)
            J =S[j]
            if I==J:
                continue
            SE.remove(J)
            if "G" in SE:
                count+=G[j]
                if j+j-i <N and S[j+j-i] =="G":
                    count -=1

            elif "R" in SE:
                count+=R[j]
                if j+j-i <N and S[j+j-i] =="R":
                    count -=1
            else:
                count+=B[j]
                if j+j-i <N and S[j+j-i] =="B":
                    count -=1



    print(count)


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

from collections import deque
h,w,k = map(int, input().split())
g = [list(input()) for _ in range(h)]
ans = h*w
for i in range(h):
  if 'S' in g[i]:
    sx = g[i].index('S')
    sy = i
    break
g[sy][sx] = 0
q = deque()
q.append(sy*w+sx)
while q:
  v = q.popleft()
  y,x = v//w, v%w
  cur = min((y-1)//k, (x-1)//k, (h-y-2)//k, (w-x-2)//k) + 2
  if ans > cur:
    ans = cur
  if g[y][x] < k:
    for dx,dy in ((0,1),(1,0),(0,-1),(-1,0)):
      nx = x+dx; ny = y+dy
      if 0 <= nx < w and 0 <= ny < h and g[ny][nx] == '.':
        g[ny][nx] = g[y][x] + 1
        q.append(ny*w+nx)
print(ans)

### FIXED CODE ###

from collections import deque
h,w,k = map(int, input().split())
g = [list(input()) for _ in range(h)]
ans = h*w
for i in range(h):
  if 'S' in g[i]:
    sx = g[i].index('S')
    sy = i
    break
g[sy][sx] = 0
q = deque()
q.append(sy*w+sx)
while q:
  v = q.popleft()
  y,x = v//w, v%w
  cur = min((y-1)//k, (x-1)//k, (h-y-2)//k, (w-x-2)//k) + 2
  if ans > cur:
    ans = cur
  if g[y][x] < k:
    for dx,dy in ((0,1),(1,0),(0,-1),(-1,0)):
      nx = x+dx; ny = y+dy
      if 0 <= nx < w and 0 <= ny < h and g[ny][nx] == '.':
        g[ny][nx] = g[y][x] + 1
        q.append(ny*w+nx)
print(ans)
### BUGGY CODE ###

import numpy as np
N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
if K-Q<=0:
  L=Q-K
  for i in range(N):
    if A.count(i+1)>L:
      print('Yes')
    else:
      print('No')
else:
  for i in range(N):
    print('Yes')

### FIXED CODE ###

import numpy as np
N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]

if K-Q<=0:
  L=[K-Q for i in range(N)]
  for i in range(Q):
    L[A[i]-1]=L[A[i]-1]+1
  for i in range(N):
    if L[i]>0:
      print('Yes')
    else:
      print('No')
else:
  for i in range(N):
    print('Yes')
### BUGGY CODE ###

import fractions

N,M=map(int,input().split())
d=N*M//fractions.gcd(N,M)
a=d//N
b=d//M

S=input()
dS={}
for i in range(N):
    dS[a*i]=S[i]

T=input()
dT={}
for i in range(M):
    dT[b*i]=T[i]

f=True
for i in range(d):
    if i in dS and i in dT and dS[i]!=dT[i]:
        f=False
        break

print(d if f else -1)

### FIXED CODE ###

import fractions

N,M=map(int,input().split())
g=fractions.gcd(N,M)

a=N//g;b=M//g

S=input();T=input()

f=True
for k in range(g):
    if S[k*a]!=T[k*b]:
        f=False
        break

print(a*b*g if f else -1)
### BUGGY CODE ###

def len_LCS(X,Y):
    x_l = len(X)
    y_l = len(Y)
    lcs = [[0 for _ in range(x_l+1)] for _ in range(y_l+1)]
    for j in range(y_l):
        for i in range(x_l):
            if Y[j] == X[i]:
                lcs[j+1][i+1] = lcs[j][i] + 1
            else:
                lcs[j+1][i+1] = lcs[j+1][i] if lcs[j+1][i] > lcs[j][i+1] else lcs[j][i+1]
    return lcs[-1][-1]

if __name__=='__main__':
    q = int(input())
    for _ in range(q):
        X = input()
        Y = input()
        print(len_LCS(X,Y))

### FIXED CODE ###

def len_LCS(X,Y):
    lcs_row = [0 for _ in range(len(X)+1)]
    for yc in Y:
        lcs_row_p = lcs_row[:]
        # lcs_row_p: [i] [i+1]
        # lcs_row  : [i] [i+1]
        for (i,xc) in enumerate(X):
            if xc == yc:
                lcs_row[i+1] = lcs_row_p[i] + 1
            elif lcs_row[i] > lcs_row_p[i+1]:
                lcs_row[i+1] = lcs_row[i]
    return lcs_row[-1]
        
if __name__=='__main__':
    n = int(input())
    for _ in range(n):
        X = input()
        Y = input()
        print(len_LCS(X,Y))
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(R, C, K, M):
    # dp[i][j][k]=(i,j)にいてその行でk個取得済みの場合の価値の最大値
    dp = [[[-1] * 4 for _ in range(C)] for __ in range(R)]
    dp[0][0][0] = 0
    dp[0][0][1] = M[0][0]
    for i in range(R):
        for j in range(C):
            now = dp[i][j]
            for k in range(4):
                if now[k] < 0: continue
                # 下へ
                if i < R - 1:
                    # 取らない
                    dp[i + 1][j][0] = max(dp[i + 1][j][0], now[k])
                    # 取る
                    v = M[i + 1][j]
                    if v > 0:
                        dp[i + 1][j][1] = max(dp[i + 1][j][1], now[k] + v)
                # 右へ
                if j < C - 1:
                    # 取らない
                    dp[i][j + 1][k] = max(dp[i][j + 1][k], now[k])
                    # 取る
                    v = M[i][j + 1]
                    if v > 0 and k < 3:
                        dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], now[k] + v)
    print(max(dp[R - 1][C - 1]))
    # for d in dp:
    #    print(d)

if __name__ == '__main__':
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    M = [[0] * C for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        M[r - 1][c - 1] = v
    main(R, C, K, M)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main():
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    M = [[0] * C for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        M[r - 1][c - 1] = v

    # dp[i][j][k]=(i,j)にいてその行でk個取得済みの場合の価値の最大値
    dp = [[-1] * 4 for _ in range(C)]
    dp[0][0] = 0
    dp[0][1] = M[0][0]
    for i in range(R):
        nxt = [[-1] * 4 for _ in range(C)]
        for j in range(C):
            now = dp[j]
            for k in range(4):
                nowk = now[k]
                if nowk < 0: continue
                # 下へ
                if i < R - 1:
                    down = nxt[j]
                    # 取らない
                    down[0] = max(down[0], nowk)
                    # 取る
                    v = M[i + 1][j]
                    if v > 0:
                        down[1] = max(down[1], nowk + v)
                # 右へ
                if j < C - 1:
                    right = dp[j + 1]
                    # 取らない
                    right[k] = max(right[k], nowk)
                    # 取る
                    v = M[i][j + 1]
                    if v > 0 and k < 3:
                        right[k + 1] = max(right[k + 1], nowk + v)
        if i < R - 1: dp = nxt
    print(max(dp[C - 1]))

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

import sys

primes = [2]
for line in sys.stdin:
  try:
    n = int(line)
    if n > max(primes):
      for i in range(max(primes) + 1, n + 1):
        primes.append(i)
        for p in primes:
          if i % p == 0 and i != p:
            primes.pop()
            break
    ans = [i for i in primes if i <= n]
    print(len(ans))
  except:
    break

### FIXED CODE ###

import sys
import math

# Sieve of Eratosthenes
N = 999999
searchList = list(range(3, N + 1, 2))
primes = [2]
while True:
  top = searchList.pop(0)
  primes.append(top)
  if top > math.sqrt(N):
    break
  searchList = [s for s in searchList if s % top != 0]
primes.extend(searchList)

# solve
for line in sys.stdin:
  try:
    n = int(line)
    ans = [i for i in primes if i <= n]
    print(len(ans))
  except:
    break
### BUGGY CODE ###

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i!=0:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i!=0:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=2048
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

mod=998244353 

N=int(input())
alist=[]
all_num=1
for i in range(N):
  alist.append(int(input()))
  all_num *= 3
  all_num %= mod
  
asum=sum(alist)
#print(alist)
#print(all_num)

dp=[]
dp2=[]
for _ in range(N+1):
  dp.append([0]*(asum+1))
  dp2.append([0]*(asum+1))
  
dp[0][0]=1
dp2[0][0]=1
#print(dp)
for i in range(N):
  a=alist[i]
  for j in range(asum):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    dp2[i+1][j] += dp2[i][j]
    dp2[i+1][j] %= mod
    if dp[i][j] > 0:
      dp[i+1][j+a] += dp[i][j]
      dp[i+1][j+a] %= mod
      dp2[i+1][j+a] += dp2[i][j]
      dp2[i+1][j+a] %= mod
    
#print(dp)
#print(dp2)

invalid_num = sum(dp[N][(asum+1)//2:])%mod 
#print(invalid_num)

if asum%2 == 0:
  print((all_num-3*invalid_num+3*dp2[N][asum//2])%mod)
else:
  print((all_num-3*invalid_num)%mod)

### FIXED CODE ###

mod=998244353 

N=int(input())
alist=[]
all_num=1
for i in range(N):
  alist.append(int(input()))
  all_num *= 3
  all_num %= mod
  
asum=sum(alist)
#print(alist)
#print(all_num)

dp=[]
dp2=[]
for _ in range(N+1):
  dp.append([0]*(asum+1))
  dp2.append([0]*(asum+1))
  
dp[0][0]=1
dp2[0][0]=1
#print(dp)
for i in range(N):
  a=alist[i]
  for j in range(asum):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    dp2[i+1][j] += dp2[i][j]
    dp2[i+1][j] %= mod
    if dp[i][j] > 0:
      dp[i+1][j+a] += dp[i][j]
      dp[i+1][j+a] %= mod
      dp2[i+1][j+a] += dp2[i][j]
      dp2[i+1][j+a] %= mod
    
#print(dp)
#print(dp2)

invalid_num = sum(dp[N][(asum+1)//2:])%mod 
#print(invalid_num)

if asum%2 == 0:
  print((all_num-3*invalid_num+3*dp2[N][asum//2])%mod)
else:
  print((all_num-3*invalid_num)%mod)
### BUGGY CODE ###

#!/usr/bin/env python3
# スペース区切りの整数の入力
n, k = map(int, input().split())
#配列の入力
data = list(map(int, input().split()))
score = []

temp = 1
for i in range(n):
    if i < k-1:
        temp *= data[i]
        score.append(0)
    elif i == k-1:
        temp *= data[i]
        score.append(temp)
    else:
        temp = temp // data[i-k] * data[i]
        score.append(temp)
    #print("i:{}, k:{}".format(i, k))
    #print(score)

for j in range(k, n):
    if score[j] > score[j-1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

#!/usr/bin/env python3
# スペース区切りの整数の入力
n, k = map(int, input().split())
#配列の入力
data = list(map(int, input().split()))

for i in range(n-k):
    if data[i] < data[k+i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###


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

a.sort()
x=0
b=set(a)
b=list(b)
for i in range(len(b)):
    if a.count(b[i])!=1:
        x+=a.count(b[i])-1
        
y=len(b)
if x%2==0:
    print(y)

else:
    print(y-1)
    



    

    
    
    





### FIXED CODE ###

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

a.sort()
x=0
count=0
b=set(a)
b=list(b)

c = collections.Counter(a)
c=c.most_common()
for i in range(len(c)):
    if c[i][1]!=1:
        x+=c[i][1]-1
    else:
        break
y=len(b)
if x%2==0:
    print(y)

else:
    print(y-1)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "@" else 0 for a in input()] + [1]
X += [1] * (W + 2)
X += X[:]
H, W = H+2, W+2
HW = H * W
s, t = x1 * W + y1, x2 * W + y2
ss, tt = s + HW, t + HW
def dijkstra():
    n = 2 * H * W
    h = [[0, s], [0, ss]]
    D = [-1] * n
    done = [0] * n
    D[s] = 0
    D[ss] = 0
    while h:
        d, i = hpop(h)
        done[i] = 1
        if i < HW:
            for j in (i+1, i-1):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, [nd, j])
                        D[j] = nd
        else:
            for j in (i+W, i-W):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, [nd, j])
                        D[j] = nd
            
        j = i + HW if i < HW else i - HW
        nd = (d + K - 1) // K * K
        if X[j]: continue
        if D[j] < 0 or D[j] > nd:
            if done[j] == 0:
                hpush(h, [nd, j])
                D[j] = nd
    return [-(-a//K) for a in (D[t], D[tt]) if a >= 0]

di = dijkstra()
print(min(di) if di else -1)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "@" else 0 for a in input()] + [1]
X += [1] * (W + 2)
H, W = H+2, W+2
s, t = x1 * W + y1, x2 * W + y2

def BFS(i0=0):
    dd = [(), (1, -1), (W, -W), (1, -1, W, -W)]
    Q = deque([(i0, 3)])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x, t = Q.popleft()
        if t & 1:
            for d in (1, -1):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if D[y] == -1:
                        D[y] = D[x] + 1
                        Q.append((y, 2))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
        if t & 2:
            for d in (W, -W):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if D[y] == -1:
                        D[y] = D[x] + 1
                        Q.append((y, 1))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
                        
    return D

print(BFS(s)[t])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,K=map(int,input().split())
l=list(map(int,input().split()))

if max(l)<K:
    print("IMPOSSIBLE")
    exit()

temp=[]
prev_l=[-1]
while prev_l!=l: #temp <=> l <=> prev_l
    temp.clear()
    prev_l.clear()
    prev_l=prev_l+l
    for i in range(len(l)-1):
        for j in range(i+1,len(l)):
            temp.append(abs(l[i]-l[j]))
    l=l+temp
    if 1 in l or K in l:
        print("POSSIBLE")
        exit()
    l=list((set(l)))
    #print(l)
    
print("IMPOSSIBLE")

### FIXED CODE ###

# coding: utf-8
# Your code here!
from fractions import gcd
from functools import reduce

N,K=map(int,input().split())
l=list(map(int,input().split()))

if max(l)<K:
    print("IMPOSSIBLE")
else:
    if K%reduce(gcd, l)==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")