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

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

cnt = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  done = [0 for _ in range(W)]
  for j in range(W):
    if S[i][j] == "#":
      continue
    if done[j]:
      continue
    l = 0
    while j + l < W:
      if S[i][j + l] == "#":
        break
      l += 1
    for k in range(l):
      cnt[i][j + k] += l
      done[j + k] = 1

for j in range(W):
  done = [0 for _ in range(H)]
  for i in range(H):
    if S[i][j] == "#":
      continue
    if done[i]:
      continue
    l = 0
    while i + l < H:
      if S[i + l][j] == "#":
        break
      l += 1
    for k in range(l):
      cnt[i + k][j] += l
      done[i + k] = 1

ans = 0
for i in range(H):
  for j in range(W):
    ans = max(ans, cnt[i][j] - 1)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

cnt = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  done = [0 for _ in range(W)]
  for j in range(W):
    if S[i][j] == "#":
      continue
    if done[j]:
      continue
    l = 0
    while j + l < W:
      if S[i][j + l] == "#":
        break
      l += 1
    for k in range(l):
      cnt[i][j + k] += l
      done[j + k] = 1

for j in range(W):
  done = [0 for _ in range(H)]
  for i in range(H):
    if S[i][j] == "#":
      continue
    if done[i]:
      continue
    l = 0
    while i + l < H:
      if S[i + l][j] == "#":
        break
      l += 1
    for k in range(l):
      cnt[i + k][j] += l
      done[i + k] = 1

ans = 0
for i in range(H):
  for j in range(W):
    ans = max(ans, cnt[i][j] - 1)
print(ans)
### BUGGY CODE ###

N = int(input())
arr = [int(x) for x in input().split()]
res = 1
for x in arr:
  res *= x
MAX = 10 ** 18
if res > MAX:
  print("-1")
else:
  print(res)

### FIXED CODE ###

N = int(input())
arr = [int(x) for x in input().split()]
found = False
for x in arr:
  if x == 0:
    found = True
if found:
  print(0)
  exit(0)
res = 1
MAX = 10 ** 18
for x in arr:
  res *= x
  if res > MAX:
    print(-1)
    exit(0)
print(res)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
INF = 1 << 31


def main(n, k, heights):
    heights.extend([INF] * k)
    costs = [INF] * (n + k)
    costs[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            costs[i + j] = min(costs[i + j], abs(heights[i] - heights[i + j]) + costs[i])
    return costs[n - 1]


if __name__ == '__main__':
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    print(main(N, K, H))


### FIXED CODE ###

import numpy as np


def main(n, k, heights):
    heights = np.array(heights, dtype=int)
    costs = np.zeros(n, dtype=int)
    for i in range(1, n):
        start = max(0, i - k)
        costs[i] = np.min(costs[start:i] + np.abs(heights[i] - heights[start:i]))
    return costs[-1]


if __name__ == '__main__':
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    print(main(N, K, H))
### BUGGY CODE ###

import re
S = input()
count = 0
Olength = len(S)
previousCount = 0

while(1) :
    S = re.sub("(01|10)", "", S)
    count = count + (Olength - len(S))
    Olength = len(S)
    
    if previousCount == count :
        break
    previousCount = count
print(count)

### FIXED CODE ###

S = input()
C1 = S.count("0")
C2 = S.count("1")

print(min(C1,C2)*2)
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()
x = {0:1}
ans = 0
if p in [2,5]:
  for i in range(n):
    if int(s[i])%p==0:
      ans += i+1
else:
  for i in range(n-1,-1,-1):
    u = int(s[i:])%p
    ans += x.get(u,0)
    x[u] = x.get(u,0) + 1
print(ans)

### FIXED CODE ###

n, p = map(int, input().split())
s = input()
x = [1] + [0]*(p-1)
ans = 0
u = 0
if p in [2,5]:
  for i in range(n):
    if int(s[i])%p==0:
      ans += i+1
else:
  for i in range(n-1,-1,-1):
    u = (int(s[i])*pow(10,n-1-i,p)+u)%p
    ans += x[u]
    x[u] += 1
print(ans)
### BUGGY CODE ###

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

res = 'Yes'

a_dict = dict()

for a in a_list:
    if a not in a_dict.keys():
        a_dict[a] = 1
    else:
        a_dict[a] += 1

a_keys = list(a_dict.keys())
if len(a_keys) > 3:
    res = 'No'
elif len(a_keys) == 3:
    a, b, c = a_keys
    if a_dict[a] != a_dict[b]:
        res = 'No'
    if a_dict[a] != a_dict[c]:
        res = 'No'
    if a ^ b != c:
        res = 'No'
    if b ^ c != a:
        res = 'No'
    if c ^ a != b:
        res = 'No'
elif len(a_keys) == 2:
    a, b = a_keys
    if a_dict[a] == 2 * a_dict[b]:
        if b != 0:
            res = 'No'
    elif 2 * a_dict[a] == a_dict[b]:
        if a != 0:
            res = 'No'
    else:
        res = 'No'
else:
    a = a_keys[0]
    if a != 0:
        res = 'No'
print(res)


### FIXED CODE ###

from collections import Counter

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

res = 'Yes'

a_dict = Counter(a_list)


a_keys = list(a_dict.keys())
if len(a_keys) > 3:
    res = 'No'
elif len(a_keys) == 3:
    a, b, c = a_keys
    if a_dict[a] != a_dict[b]:
        res = 'No'
    if a_dict[a] != a_dict[c]:
        res = 'No'
    if a ^ b != c:
        res = 'No'
    if b ^ c != a:
        res = 'No'
    if c ^ a != b:
        res = 'No'
elif len(a_keys) == 2:
    a, b = a_keys
    if a_dict[a] == 2 * a_dict[b]:
        if b != 0:
            res = 'No'
    elif 2 * a_dict[a] == a_dict[b]:
        if a != 0:
            res = 'No'
    else:
        res = 'No'
else:
    a = a_keys[0]
    if a != 0:
        res = 'No'
print(res)
### BUGGY CODE ###

import itertools

ans_list = []

while 1:
    try:
        a, b= map(int, raw_input().split())
        GCD = a * b
        LCM = 0
        # GCD
        for i, j in itertools.product(range((a if a > b else b) / 2), repeat=2):
            if a * (i+1) == b * (j+1) and GCD > a * (i+1):
                GCD = a * (i+1)
        # LCM
        for i in range(a if a > b else b, 1, -1):
            if a % i == 0 and b % i == 0:
                LCM = i
                break
        ans_list.append(str(GCD) + " " + str(LCM))
    except:
        for s in ans_list:
            print s
        break

### FIXED CODE ###

def get_gcd(a,b):
	if a > b: a, b = b, a
	if b % a == 0:
		return a
	else:
		return get_gcd(a, b % a)

def get_lcm(a,b,g):
	return a * b / g

while True:
	try:
		a,b = map(int, sorted(raw_input().split()))
		GCD = get_gcd(a,b)
		LCM = get_lcm(a,b,GCD)
		print "{} {}".format(GCD, LCM)
	except EOFError:
		break
### BUGGY CODE ###

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

for c in range(Q):
  con = 0
  l,r = map(int,input().split())
  l = l - 1
  part = S[l:r]
  for i in range(len(part) - 1):
    if part[i] + part[i + 1] == "AC":
      con += 1
  print(con)
  

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cons = [0] * (N + 1)

for i in range(N - 1):
  #隣り合う2文字(S[i] + S[i + 1])が"AC"である数の累積和を予め記録しておく
  #愚直に計算すると最悪でN * Q = 10 ** 6となるため、下準備をして再計算を防ぐ
  ##ACACTACGなら[0,1,1,2,2,2,3,3]
  cons[i + 1] = cons[i] + (1 if S[i] + S[i + 1] == 'AC' else 0)

for i in range(Q):
  l,r = map(int, input().split())
  #予め記録してあるACの累積数を引けば範囲内のACの数が求められる
  #ACと単位が2文字であるためrを1つ左にずらしておく(1引かないとCがはみ出てしまう)
  print(cons[r - 1] - cons[l - 1])
### BUGGY CODE ###

S = input()
Q = int(input())
queries = []
for _ in range(Q):
  q = list(input().split())
  queries.append(q)

for query in queries:
  t = query[0]
  if (t == '1'):
    new_S = S[::-1]
    S = new_S
  elif (t == '2'):
    f = query[1]
    if(f == '1'):
      new_S = query[2] + S
      S = new_S
    elif(f == '2'):
      new_S = S + query[2]
      S = new_S

print(S)


### FIXED CODE ###

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

r_count = 0
for query in range(Q):
  query = deque(list(input().split()))
  t = query[0]
  if (t == '1'):
    r_count += 1
  elif (t == '2'):
    f = query[1]
    if(f == '1' and (r_count % 2 == 0)):
      S.appendleft(query[2])
    elif(f == '1' and (r_count % 2 == 1)):
      S.append(query[2])
    elif(f == '2' and (r_count % 2 == 0)):
      S.append(query[2])
    elif(f == '2' and (r_count % 2 == 1)):
      S.appendleft(query[2])

if (r_count % 2 == 1):
  for i, s in enumerate(reversed(S)):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
else:
  for i, s in enumerate(S):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
### BUGGY CODE ###

N = int(input())
a = input()
number =1
for i in a.split():
    number *= int(i)


if number>10**18:
    number = -1

print(number)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
number =1

if 0 in a:
    print(0)
    exit()

for i in a:
    number *= i
    if number > 10**18:
            print(-1)
            exit()

print(number)
### BUGGY CODE ###

import itertools

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

num_list = []
for n in range(0, N + 1):
    num_list.append(n)

ans_list = []
for k in range(K, N + 2):
    for i in itertools.combinations(num_list, k):
        if not (len(i), sum(i)) in ans_list:
            ans_list.append((len(i), sum(i)))

print(len(ans_list))

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10**9+7
ans= 0
for k in range(K, N + 2):
    min_num = ((k-1) * k) / 2
    max_num = (N * (N+1)) / 2 - ((N-k) * (N-k+1)) / 2
    ans +=  max_num - min_num + 1
print(int(ans % mod))
### BUGGY CODE ###

n=int(input())

X=list(map(int,input().split()))
sort_X=sorted(X)
for i in range(n):
    if sort_X.index(X[i])<int(n/2):
        print(sort_X[int(n/2)])
    else:
        print(sort_X[int(n/2)-1])

### FIXED CODE ###

n=int(input())

X=list(map(int,input().split()))
sort_X=sorted(X)
for i in range(n):
    if X[i]<sort_X[int(n/2)]:
        print(sort_X[int(n/2)])
    else:
        print(sort_X[int(n/2)-1])
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra

H, W = map(int, input().split())
s = [input() for _ in range(H)]

graph = [[0 for _ in range(H*W)] for _ in range(H*W)]

for i in range(H):
    for j in range(W-1):
        if s[i][j] == s[i][j+1] == ".":
            graph[j+(W*i)][j+(W*i)+1] = 1
            graph[j+(W*i)+1][j+(W*i)] = 1

for i in range(H-1):        
    for j in range(W):
        if s[i][j] == s[i+1][j] == ".":
            graph[j+(W*i)][j+(W*(i+1))] = 1
            graph[j+(W*(i+1))][j+(W*i)] = 1
            
d = dijkstra(graph)

cnt = 0
for i in s:
    for j in range(W):
        if i[j] == ".":
            cnt += 1
      
if d[0][H*W-1] == float("inf"):
    print(-1)
else:
    print(int(cnt-d[0][H*W-1]-1))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
S = [input() for i in range(H)]
C = sum(i.count('.') for i in S)

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(0, 0, 0)])
used = {(0, 0)}

res = []
while que:
    s, t, cost = que.popleft()
    if s == H-1 and t == W-1:
        res = cost
        break
    for di, dj in dd:
        xi = s + di; yj = t + dj
        if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
            continue
        used.add((xi, yj))
        que.append((xi, yj, cost + 1))
if res:
    print(C - 1 - res)
else:
    print(-1)
### BUGGY CODE ###

N, M = map(int, input().split(" "))
stores = dict()
p = 10000000000

for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    if Ai in stores:
        stores[Ai] += Bi
    else:
        stores[Ai] = Bi
    p = min(p, Ai)


price = 0
while True:
    if p in stores:
        if M <= stores[p]:
            price += p * M
            break
        else:
            price += p * stores[p]
            M -= stores[p]
    p += 1
print(price)

### FIXED CODE ###

N, M = map(int, input().split(" "))
stores = []

for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    stores.append((Ai, Bi))    

price = 0
for a, b in sorted(stores, key=lambda x: x[0]):
    if M <= b:
        price += a * M
        break
    else:
        price += a * b
        M -= b
print(price)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N,K=list(map(int,sys.stdin.readline().split()))
H=list(map(int,sys.stdin.readline().split()))

dp=[0]*N
def rec(i):
    if dp[i]:
        return dp[i]
    if i==N-1:
        return 0
    L=[]
    for k in range(i+1,min(i+K+1,N)):
        L.append(rec(k)+abs(H[i]-H[k]))

    dp[i]=min(L)
    return min(L)

print(rec(0))

### FIXED CODE ###

import sys
N,K=list(map(int,sys.stdin.readline().split()))
H=list(map(int,sys.stdin.readline().split()))

dp=[0]*N

for i in range(1,N):
    mn=10**9
    for j in range(max(0,i-K),i):
        mn=min(mn,dp[j]+abs(H[j]-H[i]))

    dp[i]=mn

print(dp[-1])
### BUGGY CODE ###

num, capacity = map(int, input().split())
dp = [0]*(capacity+1)

for i in range(num):
    weight, value = map(int, input().split())
    for w in range(capacity,weight - 1,-1):
        if w < weight:
            continue
        else:
            dp[w] = max( dp[w - weight] + value,  dp[w] )
print(dp[capacity])

### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
c = 0
for i in range(n):
    for j in range(i - 1):
        if i - j == a[i] + a[j]:
            c += 1
print(c)


### FIXED CODE ###

n = int(input())
l = {}
r = {}
xc = 0
for x in input().split():
    xi = int(x)
    lx = xc + xi
    if lx in l:
        l[lx] += 1
    else:
        l[lx] = 1
    rx = xc - xi
    if rx in r:
        r[rx] += 1
    else:
        r[rx] = 1
    xc += 1
c = 0
for x in l:
    if x in r:
        c += l[x] * r[x]
print(c)
### BUGGY CODE ###

n,m = map(int, input().split( ))
mod = 10**9+7

fct = [1]
fct2 = [m]

m_sq = int(m**(1/2)) + 10


for i in range(2,m_sq):
    if m%i==0:
        fct.append(i)
        fct2.append(m//i)

fct = list(set(fct+fct2))
fct.sort()

l = len(fct)
d = {f:i for i,f in enumerate(fct)}

dp = [[0 for i in range(l)] for j in range(n)]
dp[0] = [1]*(l)

for i in range(1,n):
    for j in range(l):
        fj = fct[j]
        for k in range(j+1):
            fk = fct[k]
            if fj%fk==0:
                dp[i][j] += dp[i-1][k]
                dp[i][j] %= mod
print(dp[n-1][l-1])



### FIXED CODE ###

n,m = map(int,input().split( ))

fct = {}

for i in range(2,int(m**(1/2))+10):
    if m%i==0:##合成数で割れることはない
        fct[i]=1
        m//=i
        while m%i==0:
            fct[i]+=1
            m//=i
if m>1:
    fct[m]=1
mod = 10**9+7
def h(a,b):
    res = 1
    for i in range(a+b-1,a-1,-1):
        res *= i
        res %= mod
    for i in range(1,b+1):
        res *= pow(i,mod-2,mod)
        res %= mod
    return res
ans = 1
for p in fct:
    ans *= h(n,fct[p])
    ans%=mod
print(ans)
### BUGGY CODE ###

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

ans = 0

sums_A = ["" for _ in range(len(A)+1)]
sums_B = ["" for _ in range(len(B)+1)]


for a in range(len(A)+1):
    sums_A[a] = sum(A[:a])

for b in range(len(B)+1):
    sums_B[b] = sum(B[:b])

for a_max in range(max([k for k, v in enumerate(sums_A) if v <= K])+1):
    b_max = max([k for k, v in enumerate(sums_B) if v <= K-sums_A[a_max]])
    if ans < a_max+b_max:
        ans = a_max+b_max
print(ans)


### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, M, K = NMI()
    A = NLI()
    B = NLI()
    
    cumsum_A = [0 for _ in range(len(A)+1)]
    cumsum_B = [0 for _ in range(len(B)+1)]    
    
    cnt = 0
    
    for n in range(N):
        cnt += A[n]
        cumsum_A[n+1] = cnt
        
    cnt = 0
    
    for m in range(M):
        cnt += B[m]
        cumsum_B[m+1] = cnt
    

    
    ans = 0
    b= M
    
    for n in range(N+1):
        remain_K = K - cumsum_A[n]
        if remain_K < 0:
            break
        else:
            for m in range(b,-1,-1):
                if cumsum_B[m]> remain_K:
                    continue
                else:
                    b = m
                    ans = max(ans,n+m)
                break
    
    print(ans)
            
    


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


#%%
import heapq

N, M = map(int, input().split())
l = [0] * N
for i in range(N):
    l[i] = list(map(int, input().split()))

l.sort()
#print(l)

L = [[] for _ in range(M+1)]
for i in range(N):
    if l[i][0] <= M:
        L[l[i][0]].append(l[i][1]) 

#print(L)


a = []
ans = []
for i in range(M+1):
    for j in range(len(L[i])):
        heapq.heappush(a, -L[i][j])
    heapq.heapify(a)
    if len(a) != 0:
        ans.append(heapq.heappop(a))

print(-sum(ans))

#%%


### FIXED CODE ###


#%%
import heapq

N, M = map(int, input().split())
l = [0] * N
for i in range(N):
    l[i] = list(map(int, input().split()))

l.sort()
#print(l)

L = [[] for _ in range(M+1)]
for i in range(N):
    if l[i][0] <= M:
        L[l[i][0]].append(l[i][1]) 

#print(L)


a = []
ans = 0
for i in range(M+1):
    for j in range(len(L[i])):
        heapq.heappush(a, -L[i][j])
    if len(a) != 0:
        ans += heapq.heappop(a)

print(-ans)

#%%
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
for i in range(n):
    count=0
    for j in range(i+1):
        if p[i]>p[j]:
            break
        else:
            count+=1
    if count==i+1:
        ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
ps=[]
p_min = p[0]
for i in p:
    if p_min>i:
        p_min=i
    
    if p_min>=i:
        ans+=1
print(ans)
### BUGGY CODE ###

import sys

N = int(input())
 
ans = 1
for val in input().split():
    ans = ans * int(val)
    if(int(val) == 0):
        print(0)
        sys.exit()

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

### FIXED CODE ###

import sys

N = int(input())

An = [int(_) for _ in input().split()]
An.sort()

ans = 1

for val in An:
    # 0がきたらすぐに抜ける
    if(int(val) == 0):
        print(0)
        sys.exit()
    ans *= val
    # ansが10^18を超えた時点で-1にする
    if(ans > 10 **18):
        print(-1)
        sys.exit()

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

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

m = 0
s = sorted(a)

d = [0]*(s[-1]+3)

for i in range(0,s[-1]+1):
    d[i+1] = s.count(i)
e = [0]*(s[-1]+3)
for i in range(0,s[-1]+1):
    e[i] = d[i]+d[i+1]+d[i+2]

print(max(e))

### FIXED CODE ###

cnt=[0]*100002
input()
for x in map(int,input().split()):
    cnt[x]+=1
    cnt[x+1]+=1
    cnt[x+2]+=1
print(max(cnt))
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

for i in range(n):
    print(max(a[:i] + a[i+1:]))

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

sorted_a = sorted(a)
first = sorted_a[-1]
second = sorted_a[-2]
first_place = a.index(first)
for i in range(n):
    if first == second:
        print(first)
    else:
        if i == first_place:
            print(second)
        else:
            print(first)
### BUGGY CODE ###

from numba import njit

@njit
def func(N):
  dp = [1 for _ in range(N+1)]
  for i in range(2,N+1):
    for j in range(i, N+1, i):
      dp[j] += 1
  return dp

N = int(input())
dp = func(N)
ans = 0
for i in range(1, N+1):
  ans += i*dp[i]
print(ans)


### FIXED CODE ###

N = int(input())

dp = [1 for _ in range(N+1)]
for i in range(2, N+1):
  for j in range(i, N+1, i):
    dp[j] += 1
ans = 0
for i in range(1, N+1):
  ans += i*dp[i]
print(ans)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
d2 = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    d2.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

n, m = map(int, input().split())
ships = [[int(x) for x in input().split()] for x in range(m)]

judge = False
relay = []
goal = []

for ship in ships:
    if n in ship:
        goal.append(ship[0])
    elif 1 in ship:
        relay.append(ship[1])

res = False
if len(goal) == 0 or len(relay) == 0:
    print("IMPOSSIBLE")
else:
    for i in relay:
        if i in goal:
            res = True
            break
    print("POSSIBLE" if res else "IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
ships = [[int(x) for x in input().split()] for x in range(m)]

judge = False
relay = []
goal = []

for ship in ships:
    if n in ship:
        goal.append(ship[0])
    elif 1 in ship:
        relay.append(ship[1])

res = False
if len(goal) == 0 or len(relay) == 0:
    print("IMPOSSIBLE")

else:
    print("IMPOSSIBLE" if not set(relay) & set(goal) else "POSSIBLE")