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


from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]


move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[10**8] * W for _ in range(H)]


def bfs(i, j, d):
    visited[i][j] = d
    que = deque([(i, j, d)])

    while que:
        ci, cj, d = que.popleft()

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] <= d:
                continue
            if S[ni][nj] == '.':
                visited[ni][nj] = d
                que.append((ni, nj, d))

        for di in range(-2, 3):
            for dj in range(-2, 3):
                ni, nj = ci+di, cj+dj
                if not (0 <= ni < H and 0 <= nj < W)  \
                        or visited[ni][nj] <= d+1 or abs(ni)+abs(nj) <= 1:
                    continue
                if S[ni][nj] == '.':
                    visited[ni][nj] = d+1
                    que.append((ni, nj, d+1))


bfs(Ch-1, Cw-1, 0)
# print(visited)
if visited[Dh-1][Dw-1] == 10**8:
    print(-1)
else:
    print(visited[Dh-1][Dw-1])


### FIXED CODE ###

from collections import deque

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

visited = [[-1] * W for _ in range(H)]

que = deque([(Ch-1, Cw-1, 0)])
move = ((1, 0), (-1, 0), (0, 1), (0, -1))
while que:
    ci, cj, d = que.popleft()

    if visited[ci][cj] != -1:
        continue
    visited[ci][cj] = d

    for di, dj in move:
        ni, nj = ci + di, cj + dj
        if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] != -1:
            continue
        if S[ni][nj] == '.':
            que.appendleft((ni, nj, d))

    for di in range(-2, 3):
        for dj in range(-2, 3):
            ni, nj = ci+di, cj+dj
            if not (0 <= ni < H and 0 <= nj < W)  \
                    or visited[ni][nj] != -1:
                continue
            if S[ni][nj] == '.':
                que.append((ni, nj, d+1))
    # print(visited)
    # exit()

if visited[Dh-1][Dw-1] == -1:
    print(-1)
else:
    print(visited[Dh-1][Dw-1])
### BUGGY CODE ###

A,B,K=map(int,input().strip().split(" "))
c=[]

if(A==B and K>=1):
    print(A)
    quit()
elif(A==B and K==0):
    quit()

if(B<=K):
    for i in range(A,B+1):
        print(i)
    quit()

else:

    if(K>B):
        K=B

    for i in range(K):
        if(A+i<=B):
            print(A+i)
        c.append(A+i)

    for i in range(0,A):
        c.append(i)

    if(B-K<=0):
        quit()


    for i in range(B-K+1,B+1):
        if(i not in c and i<=B):
            print(i)


### FIXED CODE ###

A,B,K=map(int,input().strip().split(" "))
c=[]

if(A==B and K>=1):
    print(A)
    quit()
elif(A==B and K==0):
    quit()

if(B<=K):
    for i in range(A,B+1):
        print(i)
    quit()

else:

    if(K>B):
        K=B

    for i in range(K):
        if(A+i<=B):
            print(A+i)
        c.append(A+i)


    if(B-K<=0):
        quit()


    for i in range(B-K+1,B+1):
        if(i not in c and i<=B and i>=A):
            print(i)
### BUGGY CODE ###

#200322D
N = int(input())
A = list(map(int,input().split()))
count = 0
for i in range(N):
    for j in range(N):
        if A[i] == A[j]:
            count += 1
All = (count - N) / 2
#print(int(All))

for i in range(N):
    count = 0
    for j in range(N):
        if A[i] == A[j]:
            count += 1
    print(int(All - count + 1))

### FIXED CODE ###

#200322D
from collections import Counter

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

c = Counter(A)
#print(c)
#print(c[1])
#print(c[A[0]])
L = len(c)
#print(L)

def nCm(x):
    return x * (x - 1) / 2

c_list = list(c.keys())

All = 0
for i in range(L):
    All += nCm(c[c_list[i]])

for i in range(N):
    Ans = All - (c[A[i]]) + 1
    print(int(Ans))
### BUGGY CODE ###

import fractions
import collections
import copy

n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

pri_li0 = copy.copy(pri_li[0])

for i in range(n-1):
    pri_li[0] += pri_li[i+1]

b_li = [pri_li[0]-pri_li0]

for i in range(1,n):
    b_li.append(pri_li[0]-pri_li[i])

com = copy.copy(b_li[0])
#print(com)
for i in range(1,n):
    com &= b_li[i]
#print(com)
#exit()
for i in range(n):
    b_li[i] -= com

ans = 0

for i in range(n):
    tmp = 1
    #print(len(b_li[i]))
    keys = b_li[i].keys()
    #print(keys)
    for j in keys:
        #print(b_li[i][j])
        #exit()
        tmp *= j ** b_li[i][j]
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans%mod)
exit()

b_li = []

seki = 1

for i in range(n):
    seki *= ai[i]
    seki %= mod

print(seki)

for i in range(n):
    tmp = seki/ai[i]
    print(tmp)
    exit()
    #tmp %= mod
    b_li.append(seki/ai[i])

t_gcd = fractions.gcd(b_li[0],b_li[1])

for i in range(n-2):
    t_gcd = int(fractions.gcd(t_gcd,b_li[i+2]))

#print(t_gcd,b_li,seki)
#exit()

ans = 0

for i in range(n):
    ans += int(seki/t_gcd/ai[i])
    
print(ans%mod)

### FIXED CODE ###

import collections
import math
n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
    
# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor


dic = {}
for a in ai:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

kari = 1
for num,count in dic.items():
    kari *= pow(num,count,mod)
    kari %= mod

kari_old = kari
ans = 0

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    #kari = 1
    #for j in range(kosu):
    #kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    kari *= pow(ai[i],mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
    #print(ans)
        
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M=map(int,input().split())
list1=list(map(int,input().split()))
for _ in range(M):
  B,C=map(int,input().split())
  list1+=[C]*B
while len(list1)>=N+1:
  list1.remove(min(list1))
SUM=sum(list1)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().split()))
ans = 0
m = 0

max_index = len(array) - 1

while(True):
    if len(array) == 0:
        break
    m = max(array)
    max_index = array.index(m)

    t = 0
    for x in range(max_index + 1,len(array)):
        t += m - array[x]
    ans += t
    del array[max_index :]

print(ans)


### FIXED CODE ###

N = int(input())
array = list(map(int, input().split()))
ans = 0
next = 1
a = True
while (a):
    a = False
    b = False
    for i in range(next,len(array)):
        if array[i] < array[i-1]:
            ans += array[i-1] - array[i]
            array[i] = array[i - 1]
            a = True
            if b == False:
                b= True
                next = i

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

import io
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)
HOGE = 10 ** 9 + 7


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
2000 3
'''


def MAIN():
  # T_IN()
  A()


def A():
  x = IN_L_I()
  n = x[0]
  k = x[1]

  for i in range(1, k + 1):
    blue = f(k, i)

    # red = 0
    # red += f(n - k, i - 1)
    # red += f(n - k, i)
    # red += f(n - k, i)
    # red += f(n - k, i + 1)
    red = f2(n - k - (i - 1), i + 1)

    res = int((blue * red) % HOGE)
    print(res)
  return None


def f(x: int, y: int):
  if x < y:
    return 0
  if x == y == 0:
    return 1
  if y < 1:
    return 0
  return f2(x - y, y)


def f2(x: int, y: int):
  return c(x + y - 1, y - 1)


def c(a: int, b: int):
  return pascal(a, b)


@lru_cache(maxsize=None)
def pascal(x, y):
  if x < 0 or y < 0:
    return 0
  if x < y:
    return 0

  if x == 0 or y == 0 or x == y:
    return 1
  else:
    return (pascal(x - 1, y - 1) + pascal(x - 1, y)) % HOGE


MAIN()


### FIXED CODE ###

import io
import sys

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
2000 3
'''


def MAIN():
  # T_IN()
  cmb_init(MOD)
  A()


def A():
  x = IN_L_I()
  n = x[0]
  k = x[1]

  res = []
  for i in range(1, k + 1):
    blue = f(k, i)

    # red = 0
    # red += f(n - k, i - 1)
    # red += f(n - k, i)
    # red += f(n - k, i)
    # red += f(n - k, i + 1)
    red = f2(n - k - (i - 1), i + 1)

    res.append((blue * red) % MOD)

  [print(i) for i in res]
  return None


def f(x: int, y: int):
  if x < y:
    return 0
  if x == y == 0:
    return 1
  if y < 1:
    return 0
  return f2(x - y, y)


def f2(x: int, y: int):
  return c(x + y - 1, y - 1)


def c(a: int, b: int):
  return cmb(a, b, MOD)


def track(func):
  def tracked(*args, **kwargs):
    result = func(*args, **kwargs)
    name = func.__name__
    arg_str = ",".join(repr(arg) for arg in args)
    print("%s(%s) -> %r" % (name, arg_str, result))
    return result

  return tracked


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


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


N = 10 ** 4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

### CMB ###############################


MAIN()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if j-i==a[i]+a[j]:
      ans=ans+1
print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
l=[]
r=[]
for i in range(n):
  l.append(i+a[i]+1)
  r.append(i-a[i]+1)
cl=collections.Counter(l)
cr=collections.Counter(r)
ans=0
for k,v in cl.items():
  ans+=v*cr[k]
print(ans)
### BUGGY CODE ###

n, k, q = map(int, input().split())
alist = [int(input()) for i in range(q)]
pts = [k for i in range(n)]

for a in alist:
    for j in range(n):
        if not j == (a-1):
        	pts[j] -= 1

for b in range(n):
    if pts[b] < 1:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

n, k, q = map(int, input().split())
nlist = [0 for i in range(n)]

for i in range(q):
    nlist[int(input())-1] += 1

for n in nlist:
    if q - n < k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

MOD = 10**9 + 7

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

# i段目にたどり着く方法
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

for i in range(2, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if i not in a else 0

print(dp[-1])

### FIXED CODE ###

MOD = 10**9 + 7

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [0] * (n + 1)
for _ in range(m):
    a[int(input())] = 1

# i段目にたどり着く方法
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if a[1] == 0 else 0

for i in range(2, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if a[i] == 0 else 0

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

def solve():
    N = int(input())
    Ss = input()

    for k in reversed(range(1, N//2+1)):
        strs = []
        for L in range(N-k+1):
            R = L+k-1
            ss = Ss[L:R+1]
            strs.append((ss, L, R))

        ds = dict()
        for ss, L, R in strs:
            if ss not in ds:
                ds[ss] = [(L, R)]
            else:
                ds[ss] += [(L, R)]

        for ss, LRs in ds.items():
            maxL = -1
            minR = N
            for L, R in LRs:
                if L > maxL:
                    maxL = L
                if R < minR:
                    minR = R
            if minR+1 <= maxL:
                return k

    return 0

print(solve())


### FIXED CODE ###

N = int(input())
Ss = input()

def isOK(k):
    strAs = ['' for _ in range(N)]
    strBs = ['' for _ in range(N)]
    for L in range(N-k+1):
        R = L+k-1
        ss = Ss[L:R+1]
        strAs[R] = ss
        strBs[L] = ss

    strCands = set()
    for iEn in range(N-1):
        if strAs[iEn] != '':
            strCands.add(strAs[iEn])
        if strBs[iEn+1] != '' and strBs[iEn+1] in strCands:
            return True

    return False


ng, ok = N//2 + 1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

N, M = map(int, input().split())
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
mod = 10**9 + 7

dp = [[0] * (M+1) for i in range(N+1)]
dp_sum = [[0] * (M+1) for i in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i] == T[j]:
            dp_sum[i][j] = dp_sum[i][j-1] + dp_sum[i-1][j] + 1
        else:
            dp_sum[i][j] = dp_sum[i][j-1] + dp_sum[i-1][j] - dp_sum[i-1][j-1]

print((dp_sum[N][M]+1) % mod)


### FIXED CODE ###

from collections import defaultdict

N, M = map(int, input().split())
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
mod = 10 ** 9 + 7
sum_dp = []
for i in range(N+1):
    sum_dp.append([0] * (M+1))

temp = 0
for i in range(1, N+1):
    for j in range(1, M+1):
        temp = 0
        if(S[i] == T[j]):
            temp = sum_dp[i-1][j-1] + 1
        sum_dp[i][j] = (sum_dp[i-1][j] + sum_dp[i][j-1] - sum_dp[i-1][j-1] + temp) % mod

print(sum_dp[N][M] + 1)
### BUGGY CODE ###

from bisect import bisect_left

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

change=[tuple(map(int,input().split())) for _ in range(M)]
change=sorted(change,key=lambda x: x[1])
change2=[]
for i in range(M):
  b,c=change[i]
  change2.extend([c]*b)

change2 = change2[max(len(change2)-N,0):]

A.extend(change2)
A = sorted(A)
print(sum(A[len(A)-N:]))

### FIXED CODE ###

from bisect import bisect_left

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

change=[tuple(map(int,input().split())) for _ in range(M)]
change=sorted(change,key=lambda x: x[1],reverse=True)
change2=[]
count=0
for i in range(M):
  b,c=change[i]
  change2.extend([c]*b)
  count += b
  if count >= N:break

A.extend(change2)
A = sorted(A)
print(sum(A[len(A)-N:]))
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
flag = True

for i in range(N):
  flag = True
  for j in range(i):
    if(P[i] > P[j]):
      flag = False
      break
  if(flag):
    ans += 1

print(ans)

### FIXED CODE ###

from sys import stdin
N=int(input())
P=[int(x) for x in stdin.readline().rstrip().split()]
ans=1
min=P[0]

for i in range(1,N):
  if(P[i] < min):
    ans+=1
    min=P[i]
print(ans)
### BUGGY CODE ###

from collections import Counter


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            if self.table[i] == -1:
                self.table[i] = i
                for k in range(i*i, maximum+1, i):
                    if self.table[k] == -1:
                        self.table[k] = i

    def factorize(self, n):
        res = Counter()
        b = n
        while self.table[b] != -1:
            res[self.table[b]] += 1
            b //= self.table[b]
        return res


def solve():
    N = int(input())
    ins = Osa_k(N)
    ans = 0

    for i in range(1, N+1):
        cnt = i
        for j in ins.factorize(i).values():
            cnt *= (j+1)
        ans += cnt

    print(ans)


solve()


### FIXED CODE ###

def solve():
    N = int(input())
    cnt = [1]*(N+1)

    for i in range(2, N+1):
        j = 1
        while i*j<=N:
            cnt[i*j] += 1
            j += 1

    ans = 0
    for i in range(1, N+1):
        ans += i*cnt[i]
    print(ans)

solve()
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#    c[i] = pow(10,i,M)
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1




dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        dp[0][l*c%M] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(13):
            for l in range(10):
                dp[i][j] += dp[i-1][(j-l*c)%13]
    else:
        st = int(s)
        for j in range(13):
            dp[i][j] = dp[i-1][(j-st*c)%13]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]%mod
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
    for j in range(M):
        dp[i][j] %=mod

#print(dp)
print(dp[-1][5]%mod)

### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]

T = [S[i] * 2 for i in range(N)]
T = T + T

def check(i, j) :
    for x in range(N) :
        for y in range(x, N) :
            if T[i+y][j+x] != T[i+x][j+y] :
                return False
    return True

ret = 0
for i in range(N) :
    for j in range(N) :
        if check(i, j) :
            ret += 1
            
print(ret)

### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]

def check(a) :
    for i in range(N) :
        for j in range(i, N) :
            if S[(a+i)%N][j] != S[(a+j)%N][i] :
                return False
                
    return True

ret = 0
for a in range(N) :
    if check(a) :
        ret += N
            
print(ret)
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    S_tmp = str(input())
    S_tmp = list(S_tmp)
    S_tmp.sort()
    S.append(S_tmp)

count=0
for i in range(len(S) - 1):
    for j in range(i+1, len(S)):
        if S[i]==S[j]:
            count+=1
print(count)

### FIXED CODE ###

import math

N = int(input())
S = []
for i in range(N):
    S_tmp = str(input())
    S_tmp = list(S_tmp)
    S_tmp.sort()
    S.append("".join(S_tmp))
S.sort()

count=0
x = 0
tmp = S[0]
count_all = []
for i in S[1:]:
    if tmp==i:
        count+=1
    else:
        if count>0:
            x += math.factorial(count+1)//(math.factorial(count+1-2) * math.factorial(2))
        count = 0
    tmp = i
if count>0:
    x += math.factorial(count+1)//(math.factorial(count+1-2) * math.factorial(2))
        
    tmp = i
print(x)
### BUGGY CODE ###

m=2018
L,R=map(int,input().split())
for i in range(L,R):
  for j in range(i+1,R+1):
    m=min(m,i*j%2019)
print(m)

### FIXED CODE ###

L,R=map(int, input().split())
m=2019
for i in range(L,min(R+1,L+2019)):
  for j in range(i+1,min(R+1,L+2019)):
    m=min(m,i*j%2019)
print(m)
### BUGGY CODE ###

line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]
times = int(input())
memo=[0]*90001
for i in range(0, times):
    temp = list(map(int, input().split(" ")))
    nowloc = temp[0]
    ans = 0
    while nowloc != temp[1]:
        if memo[nowloc]==0:
            memo[nowloc]=abs(data[nowloc][0] - data[nowloc + a[2]][0]) + abs(data[nowloc][1] - data[nowloc + a[2]][1])
        ans += memo[nowloc]
        nowloc += a[2]
    print(ans)

### FIXED CODE ###

line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(1, a[0] * a[1]+1):
    if i < a[2]+1:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]] - memo[line[0]])
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
a = [None for i in range(2 * M)]
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a[2*i] = [A, B]
    a[2*i+1] = [B, A]

a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        break

for i in range(len(one)):
    for j in range(len(two)):
        if one[i] == two[j]:
            flag = 1
            print("POSSIBLE")
            break

if flag == 0:
    print("IMPOSSIBLE")


### FIXED CODE ###

import sys

N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    ship[a].append(b)
    ship[b].append(a)

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")