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

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import Counter
def div10(d):
    return d//10
def rem2019(d):
    return d%2019
def resolve():
    S = sr()
    N = len(S)
    # a = ['']
    # for i in range(N):
    #     s = S.pop()
    #     a.append(int(s+str(a[i])))
    # a = a[::-1]
    # a[-1] = 0
    # ans = 0
    # for i in range(N):
    #     t = list(map(rem2019, a))
    #     ans += Counter(t)[0]-1
    #     a = list(map(div10, a))
    #     g = a.pop()
    ans = 0
    for i in range(N-3):
        for j in range(i+3, N):
            if int(S[i:j+1])%2019 == 0:
                ans += 1
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        t %= 2019
        r *= 10
        r %= 2019
        a[t] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

from math import gcd
a,b,n=map(int,input().split())
t=a*b//gcd(a,b)
if a==1:
    print(0)
    exit()

ans=[]
if n%t!=0:
    n%=t

for i in range(1,n+1):
    y=int(a*i/b)-a*int(i/b)
    ans.append(y)


print(max(ans))


### FIXED CODE ###


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

def f(x):
    return a*x//b-a*(x//b)

print(f(min(n,b-1)))
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
# print(a_list)
a_set = set(a_list)
length_dict = {}
for elm in a_set:
    cur_list = [ind for ind in range(n) if a_list[ind] == elm]
    length_dict[elm] = len(cur_list)
num_dict0 = {}
num_dict1 = {}
for elm in a_set:
    num_dict0[elm] = int(length_dict[elm]*(length_dict[elm]-1)/2)
    num_dict1[elm] = int((length_dict[elm]-1)*(length_dict[elm]-2)/2)

# print(num_dict0, num_dict1)
for ind in range(n):
    cur_elm = a_list[ind]
    output = 0
    for elm in a_set:
        if elm == cur_elm:
            output += num_dict1[elm]
        else:
            output += num_dict0[elm]
    print(output)

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
# print(a_list)
a_set = set(a_list)
length_dict = {}
for elm in a_set:
    length_dict[elm] = 0    

for ind in range(n):
    elm = a_list[ind]
    length_dict[elm] += 1

total_num = 0
for elm in a_set:
    total_num += int(length_dict[elm]*(length_dict[elm]-1)/2)
difference = {}
for elm in a_set:
    difference[elm] = int(length_dict[elm]*(length_dict[elm]-1)/2) - int((length_dict[elm]-1)*(length_dict[elm]-2)/2)


# print(num_dict0, num_dict1)
for ind in range(n):
    elm = a_list[ind]
    print(total_num-difference[elm])
### BUGGY CODE ###

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

a = []
pc = "."
pi = 0
for i,c in enumerate(S):
    if pc!=c:
        a.append(i-pi)
        pi = i
        pc = c
else:
    a.append(i+1-pi)

ans = N
l = len(a)
for i in range(0,(l+1)//2):
    ans = min(ans,sum(a[1:1+i*2:2])+sum(a[2+i*2::2]))
print(ans)

### FIXED CODE ###

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

a = []
pc = "."
pi = 0
for i,c in enumerate(S):
    if pc!=c:
        a.append(i-pi)
        pi = i
        pc = c
else:
    a.append(i+1-pi)

l = len(a)
w = 0
b = sum(a[2::2])
ans = w+b
for i in range(1,(l+1)//2):
    #ans = min(ans,sum(a[1:1+i*2:2])+sum(a[2+i*2::2]))
    if -1+i*2 < l:
        w += a[-1+i*2]
    if i*2 < l:
        b -= a[i*2]
    ans = min(ans,w+b)
print(ans)
### BUGGY CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if 4*h*n != N*(n+h):
            x = N*h*n
            y = 4*h*n - N*(n+h)
            w = x // y
            if x % y == 0 and 1 <= w <= 3500:
                print(h, n, w)
                exit()



### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if 4*h*n != N*(n+h):
            x = N*h*n
            y = 4*h*n - N*(n+h)
            w = x // y
            if x % y == 0 and 1 <= w <= 3500:
                print(h, n, w)
                exit()
### BUGGY CODE ###

import math

H, W, N = map(int, input().split())
count = [0]*10
count[0] = (H-2)*(W-2)
rectmap=[]

#print(board)
for i in range(0,N):
    a, b = list(map(int, input().split()))
    for j in range(a-1, a+2):
        for k in range(b-1, b+2):
            if j>1 and j<H and k>1 and k<W:
                rectmap.append([j-1, k-1])
#print(rectmap)
rectmap.sort()
rectmap.append([])
while len(rectmap)!=1 :
#    print(rectmap[0])
#    print(rectmap)
    c=0
#    print(rectmap)
    while rectmap[0]==rectmap[1]:
        c+=1
        rectmap.pop(0)
    c+=1
    rectmap.pop(0)
#    print(rectmap)
#    input()
    count[c]+=1
    count[0]-=1
for i in range(0, 10):
    print(count[i])    
#print(H,W,N)
#print(ab)


### FIXED CODE ###

import math

H, W, N = map(int, input().split())
count = [0]*10
count[0] = (H-2)*(W-2)
rectmap={}

#print(board)
for i in range(0,N):
    a, b = input().split()
    a = int(a)
    b = int(b)
    ab = (a, b)
    al = max(a-1, 2)
    au = min(a+2, H)
    bl = max(b-1, 2)
    bu = min(b+2, W)

    for j in range(al, au):
        for k in range(bl, bu):
            if (j,k) in rectmap:
                rectmap[(j,k)] +=1
            else:
                rectmap[(j,k)] = 1
#            print(rectmap)
##    for j in range(a-1, a+2):
##        for k in range(b-1, b+2):
##            if j>1 and j<H and k>1 and k<W:
##                rectmap.append([j-1, k-1])
#print(rectmap)
for i in rectmap.values():
    count[i]+=1
    count[0]-=1
for c in count:
    print(c)
#print(H,W,N)
#print(ab)
### BUGGY CODE ###

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    vi = v[i]
    for j in range(T+1):
        vt[j] = min(vt[j],vi+max(0,-(j-ts)/2,(j-te)/2))
    ts = te
print(sum(vt)/2)

### FIXED CODE ###

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    for j in range(T+1):
        vt[j] = min(vt[j],v[i]+max(0,-(j-ts)/2,(j-te)/2))
    ts = te
print(sum(vt)/2)
### BUGGY CODE ###

A, B = map(int, input().split())
a = A
for i in range(B,A,-1):
    a = a^i
print(a)

### FIXED CODE ###

A, B = map(int, input().split())
sa = B-A
if (A%2==0 and B%2 ==1):
    if(sa%4==1):
        ans = 1
    else:
        ans = 0
elif(A%2==0 and B%2==0):
    if(sa%4==2):
        ans = B+1
    else:
        ans = B
elif(A%2==1 and B%2 ==1):
    if(sa%4==2):
        ans = A-1
    else:
        ans = A
elif(A%2==1 and B%2 ==0):
    if(sa%4==1):
        ans = A^0^B
    else:
        ans = A^1^B
print(ans)
### BUGGY CODE ###

def main() :
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]

    ans = 0
    for i in range(n) :
        for j in range(i+1, n) :
            cost = A[i][j]
            for k in range(n) :
                if i == k or j == k:
                    continue

                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    cost = 0
                elif d < A[i][j] :
                    print(-1)
                    exit()
            ans += cost
    print(ans)

main()

### FIXED CODE ###

def main() :
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]

    ans = 0
    for i in range(n) :
        for j in range(i+1, n) :
            cost = A[i][j]
            for k in range(n) :
                if i == k or j == k:
                    continue

                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    cost = 0
                elif d < A[i][j] :
                    print(-1)
                    exit()
            ans += cost
    print(ans)

main()
### BUGGY CODE ###

s = input()
K = int(input())
S = []
ss = ''
w = []
for i in range(len(s)):
    if s[i] in w:
        pass
    else:
        S.append(s[i])
        w.append(s[i])
    for j in range(i+1, K+i+1):
        ss = ''
        if j >= len(s):
            continue
        ss = s[i] + s[i+1:j+1]
        if ss in w:
            continue
        S.append(ss)
        w.append(ss)

S.sort()

print(S[K-1])

### FIXED CODE ###

s = input()
K = int(input())
S = set()

for i in range(len(s)):
    S.add(s[i])
    for j in range(i+1, K+i+1):
        ss = ''
        if j >= len(s):
            continue
        ss = s[i] + s[i+1:j+1]
        S.add(ss)
        
S = list(S)
S.sort()

print(S[K-1])
### BUGGY CODE ###

S=input()
l=[0 for x in range(len(list(S)))]
s_r=S.count("R")
s_l=S.count("L")

for i in range(len(list(S))):
    p_i=i
    p_l=[]
    for j in range(10**100):
        if S[p_i]=="R":
            p_i+=1
            p_l.append(p_i)
        elif S[p_i]=="L":
            p_i-=1
            p_l.append(p_i)
        if j>max(s_r,s_l) and j%2==1:
            if p_l[j]==p_l[j-2]:
                break
            else:
                continue
    l[p_i]+=1

print(*l)

### FIXED CODE ###

s=input()
s="L"+s+"R"
N=len(s)
a=[1]*N
for i in range(1,N-1):
    if s[i]=="R" and s[i+1]=="R":
        a[i+2]+=a[i]
        a[i]=0
for i in range(N-1,1,-1):
    if s[i]=="L" and s[i-1]=="L":
        a[i-2]+=a[i]
        a[i]=0
print(*a[1:-1])
### BUGGY CODE ###

import math

A,B=map(int, input().split())

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def primelist(n):
    P = [2]
    flag = 0
    for i in range(3,n+1,2):
        for j in range(len(P)):
            if math.sqrt(i) < P[j]:
                break
            else:
                if i%P[j] == 0:
                    flag += 1
                    break
        if flag == 0:
            P.append(i)
        flag = 0
    P.append(1)
    return(P)

def maxsoin(n):
    x = n
    i = 2
    prime_factors = []
    while x > 1:
      if x % i == 0:
        prime_factors.append(i)
        x = x / i
      else:
        i += 1
    result = max(prime_factors)
    return(result)

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = maxsoin(N)
    pl = primelist(ms)
    ans=0
    for i in range(len(pl)):
        if N%pl[i]==0:
            ans+=1
    print(ans)

### FIXED CODE ###

import collections

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

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

A,B=map(int, input().split())
N=gcd(A,B)
c = collections.Counter(prime_factorize(N))
print(len(list(c.keys()))+1)
### BUGGY CODE ###

#Coding:Utf-8

N=int(input())
s=[list(input()) for i in range(N)]
total=num=0
for l in range(N):
    s[l].sort()
s.sort()
for m in range(N):
    if m==0:
        dupl=s[m+1:N+1].count(s[m])
        for o in range(1,dupl+1):
            total+=o
        num+=dupl+1
    elif num!=N:
        dupl=s[num+1:N+1].count(s[num])
        for o in range(1,dupl+1):
            total+=o
        num+=dupl+1
    else:
        break

print(total)

### FIXED CODE ###

#Coding:Utf-8

N=int(input())
s=[list(input()) for i in range(N)]
total=num=0
dic={}
for l in range(N):
    s[l].sort()
    if dic.get(str(s[l]))==None:
        dic[str(s[l])]=0
    else:
        dic[str(s[l])]+=1
        total+=int(dic[str(s[l])])
print(total)
### BUGGY CODE ###

n=int(input())
arr = list(map(int, input().split()))
z=1
for i in range(n):
    z=z*arr[i]
if(z>1000000000000000000):
    print("-1")
else:
    print(z)
    



### FIXED CODE ###

n=int(input())
arr = list(map(int, input().split()))
z=1
flag=0
zero=1
for i in range(n):
    z=z*arr[i]
    if(z>1000000000000000000):
        flag=1
        break
for i in range(n):
    if(arr[i]==0):
        zero=0
if(flag==0 or zero==0):
    print(z*zero)
else:
    print("-1")
### BUGGY CODE ###

N,M=map(int,input().split())
m=M//N
for i in range(m,0,-1):
    if M%i==0:
        print(i)
        break

### FIXED CODE ###

N,M=map(int,input().split())
a=1
for i in range(1,4*10000):
    if M%i:
        continue
    if M//i>=N and i>a:
        a=i
    if i>=N and M//i>a:
        a=M//i
print(a)
### BUGGY CODE ###

p = 10 ** 9 + 7
n,a,b = map(int,input().split())
k=max(a,b)
com=[0]*(k+1)
com[0]=1
def ma():
  for i in list(range(1, k+1)):
    dm=(com[i-1]*(n-i+1))%p
    com[i]=(dm*pow(i,p-2,p))%p
  print((2**n-1-com[a]-com[b])%p)
ma()

### FIXED CODE ###

p = 10 ** 9 + 7
n,a,b = map(int,input().split())
k=max(a,b)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
com=[0]*(k+1)
com[0]=1
for i in range(1, k+1):
  com[i]=((com[i-1]*(n-i+1))*modinv(i,p))%p
print((pow(2,n,p)-1-com[a]-com[b])%p)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ca = [A[0]] + [0]*(N-1)

for i in range(1,N):
    ca[i] = ca[i-1] + A[i]

count = 0
numbers = [ca.count(j) for j in list(set(ca)) if ca.count(j) > 1]
count += ca.count(0)
count += sum([int(i * (i-1) /2) for i in numbers])

print(count)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ca = [A[0]] + [0]*(N-1)

for i in range(1,N):
    ca[i] = ca[i-1] + A[i]

count = 1
number = 0
number += ca.count(0)
sca = sorted(ca) + ['hoge']
for i in range(1,N+1):
    if sca[i] == sca[i-1]:
        count += 1
    else:
        number += count*(count - 1)/2
        count = 1


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

s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

for i in range(n):
  S[i+1]=(S[i]+(10**(i)*int(s[i]))%p)%p
  ans[S[i+1]]+=1

cnt=ans[0]
for i, a in enumerate(ans):
  cnt+=(a*(a-1))//2
  
print(cnt)


### FIXED CODE ###

s=input()[::-1]
p=2019
ans=[0]*p

x10, S=1, 0
for i in s:
  S+=x10*int(i)
  S%=p
  x10*=10
  x10%=p
  ans[S]+=1

cnt=ans[0]
for a in ans:
  cnt+=(a*(a-1))//2
  
print(cnt)
### BUGGY CODE ###

N = int(input())

count = 0
for A in range(1, N):
  for B in range ((A + 1), N):
    if (A*B) < N:
      count += 1

count = count * 2

for x in range(1, N):
  if x**2 < N:
    count += 1

print(count)

### FIXED CODE ###

N = int(input())

count = 0
for A in range(1, N):
  N_ = (N - 1) // A
  count += N_

print(count)
### BUGGY CODE ###

import copy
import bisect
N = int(input())
L = list(map(int,input().split()))
count = 0
L.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        #print(L[i])
        #print(L[j])
        maxi = L[i] + L[j] -1
        mini = abs(L[i] - L[j]) +1
        #print("maxi"+str(maxi)+"mini"+str(mini))
        #cL = copy.copy(L)
        #del cL[:j+1]
        #print(cL)
        mi = bisect.bisect_left(L[j+1:],mini)
        ma = bisect.bisect_right(L[j+1:], maxi)
        #print("mi"+str(mi)+"ma"+str(ma))
        if ma >= mi:
            count += ma-mi
print(count)


### FIXED CODE ###


import bisect
N = int(input())
L = list(map(int,input().split()))
count = 0
L.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        count += bisect.bisect(L,L[i]+L[j]-1)-j-1
print(count)
### BUGGY CODE ###

N,*X=map(int,open(0).read().split());M,g,r,h,i=10**9+7,1,0,[1],N;exec("i-=1;h+=[h[-1]*i%M];"*N+"r,g=(r+g*h[N-2-i]*(X[-1]-X[i]))%M,g*-~i%M;i+=1;"*N);print(r)

### FIXED CODE ###

N = int(input())
Xs = list(map(int, input().split()))
mod = 10**9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
g1 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

mxx = Xs[-1]
r = 0
r2 = 0
for i in range(N-1):
    r = (r+mul(mul(g1[N-1],inverse[i+1]),Xs[N-1]-Xs[i]))%mod
print(r)
### BUGGY CODE ###

import itertools

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

n = int(input())

cnt = 0
i = 2
a = prime_factorize(n)
if len(a) == 1:
    a.append(1)
b = []
for i in range(1,len(a)+1):
    b.append(list(itertools.combinations(a, i)))


m1 = 10**12
m2 = 10**12
for i in range(len(b)):
    for j in range(len(b[i])):
        c = 1
        d = 1
        for k in range(len(b[i][j])):
            c *= b[i][j][k]
        d = n // c
        if m1+m2 > c+d:
            m1 = c
            m2 = d

print(m1+m2-2)

### FIXED CODE ###

import sys

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


n = int(input())
a = make_divisors(n)
#print(a)
ans = sys.maxsize
for x in a:
    y = n // x
    #print(x, y, x+y)
    ans = min(ans, x + y - 2)
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 隣接行列
route = [[0 for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = route[b - 1][a - 1] = 1

# # 隣接リスト
# route2 = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for i, node in enumerate(route[now]):
        if node == 0:
            continue

        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1

            room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

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

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

n = int(input())
list_in = list(map(int, input().split()))
q = int(input())
for i in range(q):
    bc = list(map(int, input().split()))
    list_in = [bc[1] if list_in[l] == bc[0] else list_in[l] for l in range(n)]
    print(sum(list_in))

### FIXED CODE ###

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

counter = collections.Counter(list_in)
sum = sum(list_in)

for i in range(q):
    bc = list(map(int, input().split()))
#    list_in = [bc[1] if list_in[l] == bc[0] else list_in[l] for l in range(n)]
    sum_diff = (bc[1] - bc[0]) * counter[bc[0]]
    counter[bc[1]] = counter[bc[1]] + counter[bc[0]]
    counter[bc[0]] = 0
    print(sum+sum_diff)
    sum = sum + sum_diff
### BUGGY CODE ###

N,M=map(int,raw_input().split(' '))

m_1=[]
m_N=[]
for _ in range(M):
    a,b=map(int,raw_input().split(' '))
    if a==1 and not a in m_1:
        m_1.append(b)
    if b==N and not a in m_N:
        m_N.append(a)

if len(set(m_1)-set(m_N))==len(set(m_1)):
    print 'IMPOSSIBLE'
else:
    print 'POSSIBLE'

### FIXED CODE ###

N,M=map(int,raw_input().split(' '))

m_1=[0]*(N+1)
m_N=[0]*(N+1)
for _ in range(M):
    a,b=map(int,raw_input().split(' '))
    if a==1:
        m_1[b]=1
    if b==N:
        m_N[a]=1

a=''.join(map(str,m_1))
b=''.join(map(str,m_N))

c=int(a,2)
d=int(b,2)


if c&d==0:
    print 'IMPOSSIBLE'
else:
    print 'POSSIBLE'
### BUGGY CODE ###

n = int(input())
a = tuple(int(x) for x in input().split())

def hoge(n, r):
 return n * (min(n-r, r))
ans = sorted(a[:2])[::-1]
for i in a:
 for j in a:
  if i <= j: continue
  ans = (i, j) if hoge(*ans) < hoge(i, j) else ans
print(*ans)


### FIXED CODE ###

N = int(input())
a = sorted(int(x) for x in input().split())

def hoge(n, r):
 return n * (min(n-r, r))

n = max(a)
ans = (n, a[0])
for i in a[1:]:
 ans = (n, i) if hoge(*ans) < hoge(n, i) else ans
print(*ans)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

idx = [s[i:i+2] == "AC" for i in range(n-1)]
idx2 = [sum(idx[:i]) for i in range(n)]

for i in range(q):
    print(idx2[lr[i][1]-1]-idx2[lr[i][0]-1])



### FIXED CODE ###

n,q = map(int, input().split())
s = input()
# lr = [list(map(int, input().split())) for i in range(q)]

idx = [0] * n

# idx = [idx[i-1]+int(s[i-1:i+1] == "AC") for i in range(1, n)]
for i in range(1,n):
    idx[i] = idx[i-1] + (s[i-1:i+1] == "AC")


for i in range(q):
    l,r = map(int, input().split())
    print(idx[r-1]-idx[l-1])
### BUGGY CODE ###

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

A_i = [int(input()) for _ in range(Q)]

for i in range(N):
    a = len(list(filter(lambda x: x == (i+1), A_i)))
    if (K-Q+a) > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

S_i = [0] * N
for i in range(Q):
    S_i[int(input())-1] += 1

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

n=int(input())
li=list(map(int,input().split()))
if 0 in li:
    print(0)
    exit()
ans=1

for i in li:
    ans=ans*i

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

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
if 0 in li:
    print(0)
    exit()
ans=1

for i in li:
    ans=ans*i
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

N,A = map(int,input().split())
x = list(map(int,input().split()))
X = N*max(max(x),A)
dp = [[[0 for i in range(X+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1
for k in range(1,N+1):
    for j in range(k+1):
        for i in range(X+1):
            if i - x[k-1] >= 0 and k >= 1:
                dp[k][j][i] = dp[k-1][j-1][i-x[k-1]] + dp[k-1][j][i]
            else:
                dp[k][j][i] = dp[k-1][j][i]
ans = 0
for j in range(1,N+1):
    for i in range(X+1):
        if i%j == 0 and i//j == A:
            ans += dp[-1][j][i]
print(ans)

### FIXED CODE ###

N,A = map(int,input().split())
x2 = list(map(int,input().split()))
x = [i-A for i in x2]
maxx = max(max(x2),A)
dp = [[0 for i in range(2*N*maxx+1)] for j in range(N+1)]
start = N*maxx
dp[0][start] = 1
for i in range(1,N+1):
    for j in range(2*start+1):
        if 2*start >= j - x[i-1] >= 0:
            dp[i][j] = dp[i-1][j-x[i-1]] + dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][start]-1)