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

def lcs(x, y):
    lx = len(x)
    ly = len(y)
    pcsl = [[0 for i in range(ly + 1)] for j in range(lx + 1)]
    for i in range(lx):
        for j in range(ly):
            if x[i] == y[j]:
                pcsl[i][j] = pcsl[i - 1][j - 1] + 1
            elif pcsl[i - 1][j] > pcsl[i][j - 1]:
                pcsl[i][j] = pcsl[i - 1][j]
            else:
                pcsl[i][j] = pcsl[i][j - 1]
    print(pcsl[i][j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs(ax, ay)

### FIXED CODE ###

def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print(len(indices) - 1)


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)
### BUGGY CODE ###

import collections

s = input()
q = int(input())
rev = 0
ans = ['S']

for _ in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    rev += 1
  else:
    if int(query[1]) == 1:      # 先頭
      if rev%2 == 0:
        ans = [query[2]] + ans
      else:
        ans = ans + [query[2]]
    else:                       # 末尾
      if rev%2 == 0:
        ans = ans + [query[2]]
      else:
        ans = [query[2]] + ans

ans = ''.join(ans)
mes = ans.replace("S", s)
if rev%2 == 0:
  print(mes)
else:
  print(mes[::-1])


### FIXED CODE ###

import collections

s = input()
q = int(input())
rev = 0
ans = collections.deque(['S'])

for _ in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    rev += 1
  else:
    if int(query[1]) == 1:      # 先頭
      if rev%2 == 0:
        ans.appendleft(query[2])
      else:
        ans.append(query[2])
    else:                       # 末尾
      if rev%2 == 0:
        ans.append(query[2])
      else:
        ans.appendleft(query[2])

ans = ''.join(ans)
mes = ans.replace("S", s)
if rev%2 == 0:
  print(mes)
else:
  print(mes[::-1])
### BUGGY CODE ###

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

def fac(x):
    ans = 1
    for i in range(1, x + 1):
        ans = ans * i
    return(ans)

if n < m:
    n, m = m, n

if n - m >= 2:
    print(0)
elif n - m == 1:
    print((fac(m)) ** 2 * n % (10 ** 9 + 7) )
else:
    print((fac(n)) ** 2 * 2 % (10 ** 9 + 7))

### FIXED CODE ###

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

def fac(x):
    ans = 1
    for i in range(1, x + 1):
        ans = (ans * i) % (10 ** 9 + 7)
    return(ans)

if n < m:
    n, m = m, n

if n - m >= 2:
    print(0)
elif n - m == 1:
    print((fac(m)) ** 2 * n % (10 ** 9 + 7) )
else:
    print((fac(n)) ** 2 * 2 % (10 ** 9 + 7))
### BUGGY CODE ###

N=int(input())

A=list(map(int,input().split()))
A_max=max(A)
D=[0] *(A_max+1) #xを割り切る最小の素数を格納

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

for i in range(2,A_max+1):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            D[i]=j
            break
    if D[i]==0:
        D[i]=i

def gcdlist(n):
    a=n
    l=[]
    if D[a] == a:
        return [a]
    else:
        while a>1:
            l.append(D[a])
            a //=D[a] 
            if a==D[a]:
                l.append(a)
                break
        return l

pairwise=True
gcds=[]
for i in range(N):
    l=gcdlist(A[i])
    if i==0:
        for j in l:
            gcds.append(j)
        continue
    for j in l:
        if j not in gcds:
            continue
        else:
            pairwise=False
    if pairwise==True:
        for j in l:
            gcds.append(j)
    else:
        break
if pairwise==True:
    print("pairwise coprime")
else:
    if gcd_list(A) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

### FIXED CODE ###

import sys

N=int(input())
A = list(map(int,input().split()))
 
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

if gcd_list(A) > 1:
    print("not coprime")
    sys.exit()

D = [i for i in range(max(A)+1)] #iを割り切る最小の素数を格納
p = 2
 
while(p*p<=max(A)):
    if D[p]==p:
        for i in range(p*p,max(A)+1,p):
            if D[i]==i:
                D[i]=p
 
    p+=1
    
prime = set()
for a in A:
    tmp=D[a]
    L=set()
    while(a>1):
        a=a//tmp
        L.add(tmp)
        tmp=D[a]

    for l in L:
        if l in prime:
            print("setwise coprime")
            sys.exit()
        else:
            prime.add(l)

print("pairwise coprime")
### BUGGY CODE ###

from collections import defaultdict

def readInput():
	return [int(i) for i in input().split(" ")]

(R, C) = readInput()
N = int(input())
rowIdx = set() 
grid = defaultdict(lambda:None)
rowGrid = defaultdict(set)
for i in range(N):
	(r, c, a) = readInput()
	r -= 1
	c -= 1
	rowGrid[r].add(c)
	grid[(r, c)] = a 
	rowIdx.add(r)

pairIdx = rowIdx.copy()
for i in rowIdx:
	pairIdx.remove(i)
	for j in pairIdx:
		tempRow = rowGrid[i]
		tempPair = rowGrid[j]
		mark = 1
		for k in tempRow:
			if (grid[(j, k)] != None):
				diff = grid[(i, k)] - grid[(j, k)]
				mark = 0 
		if (mark is 1):
			continue
		for m in tempRow:
			anchor = grid[(i, m)]
			anchorP = grid[(j, m)]
			if (anchorP is None and anchor < diff):
				print('No')
				exit()
			elif (anchorP is not None and anchor - anchorP != diff):
				print('No')
				exit()
		for n in tempPair:
			anchor = grid[(j, n)]
			anchorP = grid[(i, n)]
			if (anchorP is None and anchor < -diff):
				print('No')
				exit()
print('Yes')

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N,S=map(int, input().split())
    A = list(map(int,input().split()))
    mod = 998244353
    dp = [[0]*(S+1) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        vi = A[i]
        for j in range(S+1):
            if j+vi<=S:
                dp[i+1][j+vi] += dp[i][j]
                dp[i+1][j] += 2 * dp[i][j]
                dp[i+1][j+vi] %= mod
            else:
                dp[i+1][j] += 2 * dp[i][j]
            dp[i+1][j] %= mod

    print(dp[N][S])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N,S=map(int, input().split())
    A = list(map(int,input().split()))
    mod = 998244353
    dp = [[0]*(S+1) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        vi = A[i]
        for j in range(S+1):
            dp[i+1][j] += 2 * dp[i][j]
            dp[i+1][j] %= mod
            if j+vi<=S:
                dp[i+1][j+vi] += dp[i][j]
                dp[i+1][j+vi] %= mod

    print(dp[N][S])

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

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

dp=[float('inf')]*N
dp[0]=0
dp[1]=abs(H[1]-H[0])

for n in range(2,N):
    if n-K>0:
        s=n-K
    else:
        s=0
    l=[]
    for i in range(n-K,n):
        l.append(dp[i]+abs(H[n]-H[i]))
    dp[n]=min(l)

print(dp[N-1])

### FIXED CODE ###

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

dp=[float('inf')]*N
dp[0]=0
dp[1]=abs(H[1]-H[0])

for n in range(2,N):
    if n-K>0:
        dp[n]=min([(dp[i]+abs(H[n]-H[i]))for i in range(n-K,n)])
    else:
        dp[n]=min([dp[i]+abs(H[n]-H[i])for i in range(0,n)])

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

import math
from functools import reduce

k=int(input())
ans=0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=(gcd(a,b,c))
print(ans)

### FIXED CODE ###

import itertools
import math
from functools import reduce

k=int(input())
l=list(range(1,k+1))
ans=0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for i in itertools.product(l,repeat=3):
    ans+=(gcd(i[0],i[1],i[2]))
print(ans)
### BUGGY CODE ###

N = int(input())
l = [-1] * N

def get(v1, v2):
    print(v1, flush=True)
    s = input()
    if s=="Male":
        l[v1] = 0
    elif s=="Female":
        l[v1] = 1
    else:
        print(v1)
        return -1

    print(v2, flush=True)
    s = input()
    if s=="Male":
        l[v2] = 0
    elif s=="Female":
        l[v2] = 1
    else:
        print(v2)
        return -1
    
    return l[v2]==l[v1]


left, right = 0, N-1
while 1:
    mid = (left+right)//2
    v = get(left, mid)
    if v==-1:
        break
        sys.exit()
    elif v==True and (mid-left)%2:
        right = m
    else:
        left = m

    

### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

import numpy as np

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
n = 0
mn = -1
r = [0] * k
for i in range(x):
  for j in range(y):
    for l in range(z):
      s = a[i] + b[j] + c[l]
      if n < k:
        r[n] = s
      else:
        if n == k:
        	mn = np.argmin(r)
        if r[mn] < s:
          r[mn] = s
          mn = np.argmin(r)
      n += 1
r.sort()
for i in range(k):
  print(r[-(i+1)])

### FIXED CODE ###

import numpy as np

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
r = []
for i in range(x):
  for j in range(y):
    if (i + 1) * (j + 1) > k:
        break
    for l in range(z):
      if (i + 1) * (j + 1) * (l + 1) > k:
        break
      r.append(a[i] + b[j] + c[l])
r.sort()
for i in range(k):
  print(r[-(i+1)])
### BUGGY CODE ###

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

result = 1 
for i in multi:
    result = result * i

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

### FIXED CODE ###

n = int(input())
multi = list(map(int,input().split()))
result = 1 

if 0 in multi:
    result = 0
    print(0)
    exit()

for i in range(n):
    result = result * multi[i]
    if (result > 10**18):
        result = -1
        break 
        
print(result)
### BUGGY CODE ###

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[set() for _ in range(w)] for _ in range(h)]

delta = AA[0][0] - BB[0][0]
kouho[0][0].add(delta)
kouho[0][0].add(-delta)
dx = [1, 0]
dy = [0, 1]
for y in range(h):
    for x in range(w):
        for d in range(2):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            delta = AA[ny][nx] - BB[ny][nx]
            for num in kouho[y][x]:
                temp = ((h + w - 2) - (ny + nx) + 1) * 80
                if temp >= abs(num + delta):
                    kouho[ny][nx].add(num + delta)
                if temp >= abs(num - delta):
                    kouho[ny][nx].add(num - delta)
ans = 10 ** 10
for a in kouho[h - 1][w - 1]:
    ans = min(ans, abs(a))
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) & 1:
                    temp |= 1 << (delta - i)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) & 1:
                    temp |= 1 << (delta - i)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) & 1:
        print(i)
        exit()
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())

a = []
now = 0
for i in range(len(S)):
  if S[i]=='?':
    b = []
    for j in range(10):
      b.append((j*10**(len(S)-i-1) %13))
    a.append(b)
  else:
    now = (now+10**(len(S)-i-1)*int(S[i])) %13

if len(a)==0:
  if now==5:
    print(1)
  else:
    print(0)
  exit()

dp=[[0 for j in range(13)] for i in range(len(a))]
for i in range(len(a)):
  if i==0:
    for k in range(10):
      dp[i][(now+a[i][k])%13] = 1
  else:
    for k in range(10):
      temp = a[i][k]
      for l in range(13):
        dp[i][(l+temp)%13] += dp[i-1][l]
  for j in range(13):
    dp[i][j] = dp[i][j]%mod
print(dp[len(a)-1][5])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

dp=[[0]*13 for i in range(n)]
for i in range(n):
  if i==0:
    if S[i]!='?':
      dp[i][int(S[i])] += 1
    else:
      for j in range(10):
        dp[i][j] += 1
  else:
    if S[i]!='?':
      for k in range(13):
        dp[i][(k*10+int(S[i]))%13] += dp[i-1][k]
    else:
      for j in range(10):
        for k in range(13):
          dp[i][(k*10+j)%13] += dp[i-1][k]
    for k in range(13):
      dp[i][k] %= mod
print(dp[n-1][5])
### BUGGY CODE ###

lists=[0 for j in range(1000)]
n=int(input())
nums=0
while nums!=n+1:
    
    
    if nums<6:
        lists[nums]==nums
        nums=+1
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7726 or nums==46656:
        lists[nums]==1
        nums+=1
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists[nums]==1
        nums+=1
    else:
        order6=0
        order9=0
        for k in range(6):
            if 6**(k+1)< nums <6**(k+2):
                order6=k+1
                # nums は6のκ＋1乗までならば考慮に入れても良い
                
                break
            else:
                continue
        for j in range(5):
            if 9**(j+1) <nums< 9**(j+2):
                order9=j+1
                #numsは9のｊ＋1乗までならば考慮に入れてもいい
                
                break
            else:
                continue
        lists[nums]=min(min(lists[nums-6**(k)] for k in range(0,order6+1)),min(lists[nums-9**(j)] for j in range(0,order9+1)))
        nums+=1
        
print(lists[n])

### FIXED CODE ###

lists=[]
emptylists=[]
numbers=int(input())

for nums in range(numbers+3):
    
    if nums<6:
        lists.append(int(nums))
         
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7776 or nums==46656:
        lists.append(1)
        
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists.append(1)
        
    else:
        power6=0
        power9=0
        for k in range(7):
            if 6**(k)< nums <6**(k+1):
                power6=k
                break   
                
        for j in range(6):
            if 9**(j) <nums< 9**(j+1):
                power9=j
                break
        add=min(min(lists[nums-6**(k)]+1 for k in range(0,power6+1)),min(lists[nums-9**(j)]+1 for j in range(0,power9+1)))
        lists.append(add)
print(lists[numbers])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = [int(i) for i in input().split()]
l.sort(reverse=True)
ans = 0
for i in range(n-2):
  c = l[i]
  for j in range(i+1, n-1):
    b = l[j]
    k_max = n-1
    k_min = j
    while k_min!=k_max:
      k = (k_max+k_min)//2+1
      a = l[k]
      if c < a + b:
        k_min = k
      else:
        k_max = k-1
    ans += k_min - j
print(ans)


### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    ans += bisect_left(l, l[i]+l[j]) - j - 1
print(ans)
### BUGGY CODE ###

import fractions
k = int(input())

l = [[-1 for _ in range(k+1)] for _ in range(k+1)]

sum = 0
for x1 in range(1,k+1):
  for x2 in range(1,k+1):
    for x3 in range(1,k+1):
      for i in range(1, 2):
        if l[x1][x2] == -1:
          ans = fractions.gcd(x1,x2)
          l[x1][x2] = ans
          l[x2][x1] = ans
        else:
          ans = l[x1][x2]
        if l[ans][x3] == -1:
          ans1 = fractions.gcd(ans,x3)
          l[ans][x3] = ans1 
          l[x3][ans] = ans1
        else:
          ans1 = l[ans][x3]
        
        sum += ans1
 
print(sum)

### FIXED CODE ###

import fractions
k = int(input())

l = [[-1 for _ in range(k+1)] for _ in range(k+1)]

for i in range(1,k+1):
  for j in range(1,k+1):
     if l[i][j] == -1:
        ans = fractions.gcd(i,j)
        l[i][j] = ans
        l[i][i] = ans
sum = 0
#1種類
for i in range(1,k+1):
  sum += i
#２種類
for i in range(1,k):
  for j in range(i+1,k+1):
    sum += l[i][j]*6

#3種類
for i in range(1,k-1):
  for j in range(i+1,k):
    for m in range(j+1,k+1):
      sum += l[l[i][j]][m]*6

print(sum)
### BUGGY CODE ###

a = int(input())
b = [int(i) for i in input().split()]

ans =1
for I in b:
  ans = ans*I
if ans>10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

a = int(input())
b = [int(i) for i in input().split()]

ans =1
b = sorted(b)
for I in b:
  ans = ans*I
  if b[0] == 0:
      ans = 0
      print(0)
      break
  elif ans > 10**18:
    print('-1')
    ans = -1
    break
if ans >=1:
    print(ans)
### BUGGY CODE ###

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

inf = 10**9
dp = [inf] * (N+5)

dp[0] = 0

for i in range(1, N):
    # 後ろを見ていく
    h = A[i]
    dp[i] = min(dp[i-k]+abs(h-A[i-k]) for k in range(1, min(K, i)+1))

print(dp[N - 1])


### FIXED CODE ###

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

dp=[100000 for i in range(N)]
dp[0]=0

for i,h_now in enumerate(h):
    if i==0:
        continue
    x=max(0,i-K)
    dp[i]=min([dp_i+abs(h_now-h_i) for dp_i,h_i in zip(dp[x:i],h[x:i])])

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

N, M = map(int, input().split())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
c = []
for i in range(M):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        c.append(b[i])

flag = 0
for k in c:
    if k == N:
        flag = 1
        break
    else:
        for i in range(M):
            if a[i] == k and b[i] == N:
                flag = 1
                break
    if flag == 1:
        break

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


### FIXED CODE ###

N, M = map(int, input().split())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
c = []
d = []
flag = 0
for i in range(M):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        c.append(b[i])
        if b[i] == N:
            flag = 1
    if b[i] == N:
        d.append(a[i])
        if a[i] == 1:
            flag = 1
e = set(c) | set(d)
if len(c) + len(d) == len(e):
    flag = 0
else:
    flag = 1

if flag == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

import numpy as np

# input
n = int(input())
inp_ls = input().split(" ")
a_ls = np.array([int(e) for e in inp_ls[:n]])

cnt = 0
for i in range(n-1):
	abs_val = i+1
	l0 = a_ls[:-abs_val]
	l1 = a_ls[abs_val:]
	h_sum_ls = l0+l1
	cnt += np.count_nonzero(h_sum_ls == abs_val)

# result
print(cnt)


### FIXED CODE ###

def count_j(arg_ls, th, b_idx, e_idx):
	if b_idx-1 == e_idx: return 0
	if b_idx == e_idx: return int(arg_ls[b_idx] > th)
	cent_idx = (e_idx+1 - b_idx) // 2 + b_idx
	cent_j = arg_ls[cent_idx]
	if cent_j > th:
		return count_j(arg_ls, th, b_idx, cent_idx-1) + (e_idx+1 - cent_idx)
	else:
		return count_j(arg_ls, th, cent_idx, e_idx)

n = int(input())
inp_ls = input().split(" ")
a_ls = [int(e) for e in inp_ls[:n]]

i_dic = {}
for i,a in enumerate(a_ls):
	val = -a+(i+1)
	if val not in i_dic: i_dic[val] = []
	i_dic[val].append(i+1)

cnt = 0
for i in range(len(a_ls)):
	val = a_ls[i] + (i+1)
	cand_ls = i_dic.get(val, [])
	result = count_j(cand_ls, (i+1), 0, len(cand_ls)-1)
	cnt += result

print(cnt)