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

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

light = [[[0, 0, 0, 0] for _ in range(W + 1)] for _ in range(H + 1)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = light[h][w]
            light[h + 1][w][1] = here[1] + 1
            light[h][w + 1][3] = here[3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = light[h][w]
            light[h - 1][w][0] = here[0] + 1
            light[h][w - 1][2] = here[2] + 1
            ans = max(ans, sum(here) + 1)

print(ans)


### FIXED CODE ###

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

light = [0] * 4 * (W + 1) * (H + 1)

row = 4 * (W + 1)
col = 4

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = row * h + col * w
            light[row * (h + 1) + col * w + 1] = light[here + 1] + 1
            light[row * h + col * (w + 1) + 3] = light[here + 3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = row * h + col * w
            light[row * (h - 1) + col * w + 0] = light[here + 0] + 1
            light[row * h + col * (w - 1) + 2] = light[here + 2] + 1
            ans = max(ans, sum(light[here: here + 4]) + 1)

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

n = int(input())
def Lucas(i):
    if i == 0:
        return 2
    if i == 1:
        return 1
    return Lucas(i-1) + Lucas(i-2)
print(Lucas(n))

### FIXED CODE ###

n = int(input())
L0 = 2
L1 = 1
for i in range(n):
    L0,L1 = L1,L0+L1
print(L0)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[None]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = [i,j]
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[None]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = (i,j)
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
s=list(input())
q=int(input())

for _ in range(q):
    m,l,r=input().split()
    
    if m=='1':
        s[int(l)-1]=r
    else:
        print(len(set(s[int(l)-1:int(r)])))

### FIXED CODE ###

import bisect
n = int(input())
s = list(input())
alp = 'abcdefghijklmnopqrstuvwxyz'
cnt = {c: [] for c in alp}

for i, c in enumerate(s):
    cnt[c].append(i)

q = int(input())
for _ in range(q):
    t, x, y = input().split()
    ans = 0
    if t == '1':
        i, c = int(x) - 1, y
        if s[i] == c:
            continue
        a = bisect.bisect_left(cnt[s[i]], i)
        cnt[s[i]].pop(a)
        s[i] = c
        b = bisect.bisect_left(cnt[c], i)
        cnt[c].insert(b, i)
    else:
        l, r = int(x) - 1, int(y) - 1
        for c in alp:
            a = bisect.bisect_left(cnt[c], l)
            if a < len(cnt[c]) and cnt[c][a] <= r:
                ans += 1

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

import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
A.sort(reverse=True)

mod=10**9+7
keta=[0]*60

for i in range(N):
    for j in range(60):    
        keta[j]+=((A[i]>>j)&1)

ans=0

mod_div2=[0]*60
mod_div2[0]=1
for i in range(1,60):
    mod_div2[i]=(2*mod_div2[i-1])%mod
    
for i in range(len(A)):
    keta_max=0
    for j in range(60):
        if(1<=(A[i]//(2**j))):
            keta_max=j+1
    for j in range(keta_max):
            if((A[i]>>j)&1):
                keta[j]-=1
                ans+=mod_div2[j]*(len(A)-i-1-keta[j])
            else:
                ans+=mod_div2[j]*keta[j]
            ans%=mod


print(ans%mod)

### FIXED CODE ###

import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
A.sort(reverse=True)

mod=10**9+7
keta=[0]*60

for i in range(N):
    for j in range(60):    
        keta[j]+=((A[i]>>j)&1)

ans=0

mod_div2=[0]*60
mod_div2[0]=1
for i in range(1,60):
    mod_div2[i]=(2*mod_div2[i-1])%mod
    
for i in range(len(A)):
    keta_max=0
    for j in range(60):
        if((A[i]>>j)&1):
            keta_max=j+1
    for j in range(keta_max):
            if((A[i]>>j)&1):
                keta[j]-=1
                ans+=mod_div2[j]*(len(A)-i-1-keta[j])
            else:
                ans+=mod_div2[j]*keta[j]
            ans%=mod


print(ans%mod)
### BUGGY CODE ###

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)

n = readInt()
a = readInts()

d = defaultdict(int)

ans = 0

for i in a:
	d[i]+=1

for k in range(0,n):
	e = d.copy()
	e[a[k]]-=1
	ans = 0
	for j in e:
		ans+=comb(e[j],2)
	print(ans)

### FIXED CODE ###

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)

n = readInt()
a = readInts()

d = defaultdict(int)

ans = 0

for i in a:
	d[i]+=1

maxv = 0
for i in d:
	maxv+=comb(d[i],2)

for k in range(0,n):
	b = d[a[k]]
	delta = comb(b,2)-comb(b-1,2)
	ans = maxv-delta
	print(ans)
### 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):
        ans = (a[i] * a[j] + ans) % (10**9+7)

print(ans)


### FIXED CODE ###

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

ans = 0
b = [0] * n
c = 0

for i in range(n):
    c = c + a[i]
    b[i] = c

for j in range(n-1):
    ans = (a[j] * (b[n-1] - b[j]) + ans) % (10**9+7)

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

n,w = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n)]
knap = {(0,0)}
for weight,value in lis:
    gone = set()
    for num,now in knap:
        if num + weight <= w:gone.add((num+weight,now+value))
    for nn,nu in gone:
        knap.add((nn,nu))
ans = 0

for num,value in knap:
    ans = max(ans,value)
print(ans)

### FIXED CODE ###

def dp():
    n,w = map(int,input().split())
    lis = (map(int,input().split()) for i in range(n))
    
    dpp = [0] * (w + 1)
    for weight, value in lis:
        for j in range(w,weight-1,-1):
            dp = dpp[j-weight] + value
            if dpp[j] < dp:
                dpp[j] = dp
    return max(dpp)
print(dp())
### BUGGY CODE ###

s = input().strip()
K = int(input())
C = {}
for i in range(len(s)):
    if s[i] not in C:
        C[s[i]] = []
    C[s[i]].append(i)
D = {}
for a in C:
    for i in C[a]:
        for j in range(i+1,len(s)+1):
            if s[i:j] not in D:
                D[s[i:j]] = 0
            D[s[i:j]] += 1
D = sorted(list(D.keys()))
print(D[K-1])

### FIXED CODE ###

S = input().strip()
N = len(S)
K = int(input())
A = []
for k in range(1,min(6,N+1)):
    for i in range(N-k+1):
        x = S[i:i+k]
        if x not in A:
            A.append(x)
A = sorted(A)
print(A[K-1])
### BUGGY CODE ###

from functools import reduce
from operator import mul
import math
import copy

def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

n = int(input())
l = list(map(int, input().split()))
d = {}
s_sum = {}
s = list(set(l))
m = 0
for i in range(len(s)):
    d[s[i]] = l.count(s[i])
for v in d.values():
    if v > 1:
        m += cmb(v, 2)
for i in range(len(l)):
    if not l[i] in d:
        print(m)
    elif l[i] in s_sum:
        print(s_sum[l[i]])
    else:
        ans = 0
        e = copy.deepcopy(d)
        e[l[i]] -= 1
        for v in e.values():
            if v > 1:
                ans += cmb(v, 2)
        s_sum[l[i]] = ans
        print(ans)

### FIXED CODE ###

import collections

def count_defaultdict(it):
    counter = collections.defaultdict(int)
    for x in it:
        counter[x] += 1
    return dict(counter)

_ = int(input())
l = list(map(int, input().split()))
all_sum = 0
count = count_defaultdict(l)
for _, v in count.items():
    all_sum += v * (v - 1) // 2
for i in range(len(l)):
    if count[l[i]] > 1:
        v = count[l[i]]
        print(all_sum - v * (v-1) // 2 + (v-1) * (v-2)//2)
    else:
        print(all_sum)
### BUGGY CODE ###

N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [1]
K = 0
visited = [False]*(N+1)

while que != []:
    now = que.pop()
    visited[now]=True
    K = max(K, len(G[now]))
    used = [False]*(K+1)
    for i in G[now]:
        if visited[i]:
            used[ans[EdaNum[(min(now,i),max(now,i))]]] = True
    nowcolor = 1
    for i in G[now]:
        if not visited[i]:
            while used[nowcolor] == True:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            que.append(i)

print(K)
for i in ans:
    print(i)

### FIXED CODE ###

N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [[1,-1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent,parentcolor = que.pop()
    visited[now]=True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            if nowcolor == parentcolor:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now, nowcolor-1])
    #print(que)

print(K)
for i in ans:
    print(i)
### BUGGY CODE ###

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

def bina(x,ok,ng):
    global da
    while ng-ok!=1:
        mi=(ok+ng)//2
        if da[mi]<x:
            ok=0
            ok+=mi
        else:
            ng=0
            ng+=mi
    return ok


ans=0
da=sorted(da)
for i in range(1,n-1):
    for j in range(i):
        ans+=bina(da[i]+da[j],i,n)-i
print(ans)

### FIXED CODE ###

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

def bina(x,ok,ng):
    global da
    while ng-ok!=1:
        mi=(ok+ng)//2
        if da[mi]<x:
            ok=0
            ok+=mi
        else:
            ng=0
            ng+=mi
    return ok


ans=0
da=sorted(da)
for i in range(1,n-1):
    for j in range(i):
        ans+=bina(da[i]+da[j],i,n)-i
print(ans)
### BUGGY CODE ###

import numpy as np

def cal_ans(x):
    ans = (x*(x+1)/2)/x
    return ans
n,k = map(int,input().split())
p = np.array(list(map(int,input().split())))
p = np.array(list(map(cal_ans,p)))

ans_temp = 0
ans_list = []
for i in range(n):
    try:
        if ans_temp < np.sum(p[i:i+k]):
            ans_temp = np.sum(p[i:i+k])
    except:
        pass
print(ans_temp)

### FIXED CODE ###

# import numpy as np

def cal_ans(x):
    ans = (x+1)/2
    return ans
n,k = map(int,input().split())
p = list(map(int,input().split()))
p = list(map(cal_ans,p))

ans_temp = 0
ans_list = []
S = [0]
for i in range(n):
    S.append(S[i]+p[i])
# print(p)
# print(S)
# for i in range(n-k+1):
#     ans_list.append(sum(p[i:i+k]))
t_len = len(S)
ans1 = 0
for i in range(t_len - k):
    if ans1 < S[i+k]-S[i]:
        ans1 = S[i+k]-S[i]
print(ans1)
# ans = 0
# for i in range(k):
#     ans += (ans_list[i]*(ans_list[i]+1)/2)/ans_list[i]
#     # print((ans_list[i]*(ans_list[i]+1)/2))
# print(ans)
### BUGGY CODE ###

n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
noww=now
matc=list(0 for i in range(n+2*now))
mat2=list(0 for i in range(n+2*now))
for i in range(n):
  matc[now-a[i]]+=1
  mat2[now+a[i]]+=1
  now+=1
#print(matc)
for j in range(n+2*noww):
  ans+=matc[j]*mat2[j]
print(ans)
       
       



### FIXED CODE ###

import numpy as np
n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
noww=now
k=n+2*now
matc=[0]*(n+2)
mat2=[0]*(n+2)
for i in range(n):
  neg=i-a[i]
  pos=i+a[i]
  if neg>=0:
    matc[neg]+=1
  if pos<=n:
    mat2[pos]+=1
  now+=1
#print(matc)
for j in range(n+2):
  ans+=matc[j]*mat2[j]
print(ans)
### BUGGY CODE ###

"""
atcoder workspace
"""
from itertools import permutations

N, M, R = map(int, input().split())
Rlist = list(map(int, input().split()))

Dmat = [[1e9] * N for i in range(N)]

for i in range(N):
    Dmat[i][i] = 0

for i in range(M):
    f, t, c = map(int, input().split())
    Dmat[f-1][t-1] = c
    Dmat[t-1][f-1] = c

for i in range(N): #mid
    for j in range(N): #from
        for k in range(N): #to
            Dmat[j][k] = min(Dmat[j][k], Dmat[j][i] + Dmat[i][k])

ans = 1e9
for p in permutations(Rlist):
    temp = 0
    for i in range(R-1):
        temp += Dmat[p[i]-1][p[i+1]-1]
    ans = min(ans, temp)

print(ans)


### FIXED CODE ###

"""
atcoder workspace
"""
from itertools import permutations

N, M, R = map(int, input().split())
Rlist = list(map(int, input().split()))

Dmat = [[1e9] * N for i in range(N)]

for i in range(N):
    Dmat[i][i] = 0

for i in range(M):
    f, t, c = map(int, input().split())
    Dmat[f-1][t-1] = c
    Dmat[t-1][f-1] = c

for i in range(N): #mid
    for j in range(N): #from
        for k in range(N): #to
            Dmat[j][k] = min(Dmat[j][k], Dmat[j][i] + Dmat[i][k])

ans = 1e9
for p in permutations(Rlist):
    ans = min(ans, sum([Dmat[p[i]-1][p[i+1]-1] for i in range(R-1)]))

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

s=input()
q=int(input())

rev=0

for _ in range(q):
    temp=input().split(" ")
    
    if temp[0]=="1":
        if rev==0:
            rev=1
        else:
            rev=0
    else:
        if rev==0:
            if temp[1]=="1":
                s=temp[2]+s
            else:
                s=s+temp[2]
        else:
            if temp[1]=="2":
                s=temp[2]+s
            else:
                s=s+temp[2]

if rev==0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s=input()
q=int(input())

rev=0

sento=[]
matsubi=[]

for _ in range(q):
    temp=input().split(" ")
    
    if temp[0]=="1":
        if rev==0:
            rev=1
        else:
            rev=0
    else:
        if rev==0:
            if temp[1]=="1":
                sento.append(temp[2])
            else:
                matsubi.append(temp[2])
        else:
            if temp[1]=="2":
                sento.append(temp[2])
            else:
                matsubi.append(temp[2])

sento_s="".join(sento)
sento_s=sento_s[::-1]
matsubi_s="".join(matsubi)

s=sento_s+s+matsubi_s

if rev==0:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
  S.append(str(input()))
C = []
for i in range(N):
  C.append(S.count(S[i]))
S_new = sorted(set(S))
for s in S_new:
  if S.count(s) == max(C):
    print(s)


### FIXED CODE ###

import collections
N = int(input())
S = []
for i in range(N):
  S.append(str(input()))
A = collections.Counter(S)
m = max(A.values())
for s in sorted(set(S)):
  if A[s] == m:
    print(s)
### BUGGY CODE ###

from itertools import product

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

max_ans = M // N

tmpM = M
insu = {}
tmp = 2
while tmpM != 1:
    if tmpM % tmp == 0:
        insu[tmp] = insu.get(tmp, 0) + 1
        tmpM = tmpM // tmp
        continue
    else:
        if tmp == 2:
            tmp = 3
        elif tmpM // tmp == 1:
            tmp = tmpM
        else:
            tmp += 2

ins = []
for k, v in insu.items():
    tmp = 1
    k_list = set()
    k_list.add(1)
    for i in range(v):
        tmp *= k
        k_list.add(tmp)
    ins.append(k_list)

ans = 1
for ins_set in product(*ins):
    tmp_ans = 1
    for a in ins_set:
        tmp_ans *= a
        if tmp_ans > max_ans:
            break
    else:
        # print(ins_set, tmp_ans)
        ans = max(ans, tmp_ans)

print(ans)

### FIXED CODE ###

from itertools import product

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

max_ans = M // N

ans = 1
tmp = 2
tmpM = M
max_prime = int(M ** 0.5)
all_list = []
i = -1
k = 0
div = 2
while tmpM != 1:
    if tmpM % div == 0:
        tmpM = tmpM // div
        if k == 0:
            i += 1
            all_list.append(set())
            all_list[i].add(div ** k)
            k += 1
        all_list[i].add(div ** k)
        k += 1

    else:
        k = 0
        if div == 2:
            div = 3
        elif div > max_prime:
            div = tmpM
        else:
            div += 2

if all_list == []:
    print(1)
    exit()

# print(all_list)
ans = 1

for div_tuple in product(*all_list):
    tmp = 1
    for k in div_tuple:
        tmp *= k
        if tmp > max_ans:
            break
    else:
        ans = max(ans, tmp)

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

n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
  if b==n:
    tempb.append(a)
if len(temp)>=1 and ans==0:
  c = [x for x in temp if x in tempb]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  """
else:
  print("IMPOSSIBLE")            
    

### FIXED CODE ###

n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
  if b==n:
    tempb.append(a)
if len(temp)>=1 and ans==0:
  temp=set(temp)
  tempb=set(tempb)
  c = temp&tempb
  #c = [x for x in temp if x in tempb]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  """
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

H,N = list(map(int, input().split()))
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]
 
# dp[damage] := モンスターに damage を与えるために必要な最小コスト
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
print(dp[-1])

### FIXED CODE ###

H,N = list(map(int, input().split()))
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]
 
# dp[damage] := モンスターに damage を与えるために必要な最小コスト
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
print(dp[-1])
### BUGGY CODE ###

import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[float("inf") for _ in range(N)]
dp[0]=0
for i in range(N-1):
	for j in range(1,min(K+1,N-i)):
		dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
print(dp[N - 1])

### FIXED CODE ###

import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[float("inf") for _ in range(N)]
dp[0]=0
for i in range(N-1):
	for j in range(1,min(K+1,N-i)):
		dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
print(dp[N - 1])
### BUGGY CODE ###

import bisect

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

L.sort()

ans = 0
for i in range(N-2):
    for j in range(N-i-1):
        a = L[i]
        b = L[i+j+1]
        c_left = bisect.bisect_right(L[i+j+2:], b - a)
        c_right = bisect.bisect_left(L[i+j+2:], b + a)
        ans += c_right - c_left
print(ans)


### FIXED CODE ###

import bisect

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

L.sort()

ans = 0
for i in range(N-2):
    for j in range(N-i-1):
        a = L[i]
        b = L[i+j+1]
        c_right = bisect.bisect_left(L[i+j+2:], b + a)
        ans += c_right
print(ans)