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

import sys
sys.setrecursionlimit(10**5) #再帰関数の呼び出し制限

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


dic = {}
for i in range(n-1):
    aa, bb = map(int,input().split())

    if aa not in dic:
        dic[aa] = set()
        dic[aa].add(bb)
    else:
        dic[aa].add(bb)

    if bb not in dic:
        dic[bb] = set()
        dic[bb].add(aa)
    else:
        dic[bb].add(aa)


p = []
x = []
for _ in range(q):
    s, t = map(int,input().split())
    p.append(s)
    x.append(t)

res = [0]*n
for i in range(q):
    res[p[i]-1] += x[i]

visited = set()

# 深さが一つ前のやつのresの値を足す
def dfs(node, prev):
    visited.add(node)
    if prev != 0:
        res[node-1] += res[prev-1]
    for i in dic[node]:
        if i not in visited:
            prev = node
            dfs(i, prev)

dfs(1, 0)
print(*res, sep=" ")

### FIXED CODE ###

# 早くなるおまじない
import sys
input = sys.stdin.buffer.readline

# 再帰関数の呼び出し制限
sys.setrecursionlimit(3 * 10 ** 5)

# 深さが一つ前のやつのresの値を足す
# dfsはおk，ここで累積和を使う発想が出てこなかった
# def dfs(node, prev):
#     visited.add(node)
#     if prev != 0:
#         res[node-1] += res[prev-1]
#     for i in dic[node]:
#         if i not in visited:
#             prev = node
#             dfs(i, prev)

def dfs(node, prev, visited, res, dic):
    visited.add(node)
    if prev != 0:
        res[node-1] += res[prev-1]
    for i in dic[node]:
        if i not in visited:
            prev = node
            dfs(i, prev, visited, res, dic)


def main():
    n,q = map(int,input().split())

    dic = {}
    for i in range(n-1):
        aa, bb = map(int,input().split())

        if aa not in dic:
            dic[aa] = set()
            dic[aa].add(bb)
        else:
            dic[aa].add(bb)

        if bb not in dic:
            dic[bb] = set()
            dic[bb].add(aa)
        else:
            dic[bb].add(aa)


    p = []
    x = []
    for _ in range(q):
        s, t = map(int,input().split())
        p.append(s)
        x.append(t)

    res = [0]*n
    for i in range(q):
        res[p[i]-1] += x[i]

    visited = set()

    dfs(1, 0, visited, res, dic)
    print(*res, sep=" ")

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

def main(s,x,q):
    res = s
    for op in q:
        if int(op[0]) == 1:
            res = res[::-1]
        elif int(op[0]) == 2:
            if int(op[1]) == 1:
                res = op[2] + res
            if int(op[1]) == 2:
                res = res + op[2]
    return res

s = input()
x = int(input())
q = [input().split() for _ in range(x)]
print(main(s,x,q))

### FIXED CODE ###

def main2(s,x,q):
    res = s
    rev = 1 #-1なら反転中
    lstA = []
    lstB = []
    for op in q:
        if int(op[0]) == 1:
            rev = rev * -1
        elif int(op[1])*rev == 1 or int(op[1])*rev == -2:
            lstA.append(op[2])
        elif int(op[1])*rev == -1 or int(op[1])*rev == 2:
            lstB.append(op[2])
    if rev == 1:
        res = "".join(lstA[::-1])+res+"".join(lstB)
    else :
        res = "".join(lstB[::-1])+res[::-1]+"".join(lstA)
    return res

s = input()
x = int(input())
q = [input().split() for _ in range(x)]
print(main2(s,x,q))
### BUGGY CODE ###

N, X, Y = map(int, input().split())

dis = []

for i in range(1, N):
    for j in range(i + 1, N + 1):
        d1 = abs(i - j)
        d2 = abs(i - X) + 1 + abs(j - Y)
        d3 = abs(i - Y) + 1 + abs(j - X)
        d = min(d1, d2, d3)

        dis.append(d)

for k in range(1, N):
    print(dis.count(k))

### FIXED CODE ###

N, X, Y = map(int, input().split())

dis = [0 for _ in range(N)]
for i in range(1, N):
    for j in range(i + 1, N + 1):
        d = min(abs(i - j),
                abs(i - X) + 1 + abs(j - Y),
                abs(i - Y) + 1 + abs(j - X))
        dis[d] += 1

for k in range(1, N):
    print(dis[k])
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
grid = []

for _ in range(n):
    s = ns()
    s = s+s
    grid.append(s)
    
for i in range(n):
    grid.append(grid[i])
    
vert = []
hrzn = []

for i in range(2*n):
    hrzn.append(grid[i])
    
for j in range(2*n):
    temp = ""
    for i in range(2*n):
        temp += grid[i][j:j+1]
        
    vert.append(temp)
    
    
ans = 0

for a in range(n):
    for b in range(n):
        
        ok = True
        for i in range(n-1):

            if vert[b+i][a+i:a+n] != hrzn[a+i][b+i:b+n]:
                ok = False
                break
                
        if ok:
            ans += 1
            
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())
 
n = ni()
grid = []
 
for _ in range(n):
    s = ns()
    s = s+s
    grid.append(s)
    
for i in range(n):
    grid.append(grid[i])
    
vert = []
hrzn = []
 
for i in range(2*n):
    hrzn.append(grid[i])
    
for j in range(2*n):
    temp = ""
    for i in range(2*n):
        temp += grid[i][j:j+1]
        
    vert.append(temp)
    
    
ans = 0
 
for a in range(n):
    for b in range(1):
        
        ok = True
        for i in range(n-1):
 
            if vert[b+i][a+i:a+n] != hrzn[a+i][b+i:b+n]:
                ok = False
                break
                
        if ok:
            ans += 1
            
print(ans*n)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < n and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)
def insert(S, k):
    S.append(k)
    i = n - 1
    while i > 0 and S[i] > S[(i - 1) // 2]:
        S[i], S[(i - 1) // 2] = S[(i - 1) // 2], S[i]
        i = (i - 1) // 2
def extractMax(S):
    if len(S) == 1:
        return S.pop()
    ans = S[0]
    S[0] = S.pop()
    maxHeapify(S, 0)
    return ans
A = []
n = 0
while True:
    s = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        n -= 1
        print(extractMax(A))
    else:
        n += 1
        insert(A, int(s[7:]))



### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))
### BUGGY CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))
b = [0]*N
for i in range(N):
    b[i] = format(A[i],"b")
one = [[0]*20 for _ in range(N)]
for i in range(N):
    for j in range(20):
        if j < len(list(b[i])):
            one[i][j] = int(b[i][-(j+1)])

sumone = [[0]*20 for _ in range(N+1)]
for j in range(20):
    for i in range(1,N+1):
        sumone[i][j] = sumone[i-1][j] + one[i-1][j]
sumone.append([2]*20)

def ok(l,r):
    for j in range(20):
        if sumone[r][j] - sumone[l][j] >= 2:
            return False
    else:
        return True

ans = 0
r = 0
for l in range(N+1):
    flag = 0
    while r < N+2 and ok(l,r) and flag == 0:
        if r != N+1:
            r += 1
        else:
            flag = 1
            break
    ans += r-l-1

print(ans)

### FIXED CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

ans = 0
r = 0
sum = 0
xor = 0
for l in range(N):
    while r < N and sum+A[r] == xor^A[r]:
        sum += A[r]
        xor ^= A[r]
        r += 1
    sum -= A[l]
    xor ^= A[l]
    ans += r-l

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

# YouTubeの通り
from operator import itemgetter

def f(n, xy):
    def update(i, x):
        i += 1
        while i < n + 1:
            bit[i] += x
            i += i & -i

    def get_sum(i):
        i += 1
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    # yの座標圧縮
    xy.sort(key=itemgetter(1))
    for i in range(n):
        xy[i][1] = i

    xy.sort()
    cy = [[0] * 4 for _ in range(n)]
    bit = [0] * (n + 1)
    for i in range(n):
        x, y = xy[i]
        s = get_sum(y)
        cy[i][3] = pow(2, s, md)
        cy[i][2] = pow(2, i - s, md)
        update(y, 1)
    bit = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        x, y = xy[i]
        s = get_sum(y)
        cy[i][0] = pow(2, s, md)
        cy[i][1] = pow(2, n - 1 - i - s, md)
        update(y, 1)
    ans = pow(2, n - 1, md) * n % md
    for i in range(n):
        c0, c1, c2, c3 = cy[i]
        ans = (ans + (c0 - 1) * (c2 - 1) * c1 * c3 + (c1 - 1) * (c3 - 1) * c0 * c2
               - (c0 - 1) * (c1 - 1) * (c2 - 1) * (c3 - 1)) % md
    print(ans)

md = 998244353
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
f(n, xy)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    md=998244353
    n=II()
    xy=LLI(n)
    yy=set()
    for x,y in xy:yy.add(y)
    ytoj={y:j for j,y in enumerate(sorted(yy))}

    ans=n*(pow(2,n,md)-1)-4*(pow(2,n,md)-1-n)
    ans%=md

    xy.sort()
    bit=BitSum(200005)
    for i,[x,y] in enumerate(xy):
        j=ytoj[y]
        c=bit.sum(j-1)
        ans+=pow(2,c,md)-1
        ans+=pow(2,i-c,md)-1
        ans%=md
        bit.add(j,1)

    bit=BitSum(200005)
    for i,[x,y] in enumerate(xy[::-1]):
        j=ytoj[y]
        c=bit.sum(j-1)
        ans+=pow(2,c,md)-1
        ans+=pow(2,i-c,md)-1
        ans%=md
        bit.add(j,1)

    print(ans)

main()
### BUGGY CODE ###

import copy
import fractions
from functools import reduce

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

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

ans = 0
for i in range(N):
    tmp = copy.copy(A)
    pop = A.pop(0)
    ans = max(ans, gcd(*A))
    A.append(pop)

print(ans)

### FIXED CODE ###

def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

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

L = [0]*(N+1)
R = [0]*(N+1)
for i in range(1, N+1):
    L[i] = gcd(L[i-1], A[i-1])
    R[N-i] = gcd(R[N-i+1], A[N-i])

ans = 0
for i in range(N):
    ans = max(ans, gcd(L[i],R[i+1]))

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

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

counter = Counter(A)

for i in range(Q):
    if B[i] in counter:
        counter[C[i]] = counter[C[i]] + counter.pop(B[i])
    ans = 0
    for num, count in counter.items():
        ans += num * count
    print(ans)


### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

counter = Counter(A)
ans = 0
for num, count in counter.items():
    ans += num * count

for i in range(Q):
    if B[i] in counter:
        ans += counter[B[i]] * C[i] - counter[B[i]] * B[i]
        counter[C[i]] = counter[C[i]] + counter.pop(B[i])
    print(ans)
### BUGGY CODE ###

n = int(input())
luk = input()

keys = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
a = 0
for key in keys:
  s = 0
  for st in luk:
    if st == key[s]:
      s += 1
    if s == 3:
      a += 1
      s = 0
      break
print(a)

### FIXED CODE ###

n = int(input())
luk = input()

keys = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
a = 0
for key in keys:
  s = 0
  for st in luk:
    if st == key[s]:
      s += 1
    if s == 3:
      a += 1
      s = 0
      break
print(a)
### BUGGY CODE ###

#! /usr/bin/env python3

N = int(input())
A = [int(i) for i in input().split()]

def gcd(a, b):
    # return a if b == 0 else gcd(b, a % b)
    while b > 0:
        c = a % b
        a = b
        b = c
    return int(a)

def lcm(a, b):
    return a // gcd(a, b) * b

l = 1
for i in range(N):
    l = lcm(l, A[i])

ans = 0
MOD = int(1e9 + 7)
for i in range(N):
    ans += int(l // A[i])
    ans %= MOD

print(ans)

### FIXED CODE ###

#! /usr/bin/env python3
N = int(input())
A = [int(i) for i in input().split()]

def gcd(a, b):
    while b > 0:
        c = a % b
        a = b
        b = c
    return int(a)

def lcm(a, b):
    return a // gcd(a, b) * b

l = 1
for i in range(N):
    l = lcm(l, A[i])

ans = 0
MOD = int(1e9 + 7)
for a in A:
    ans += int(l // a)
    # ans %= MOD

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

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

DP = [0]
for i in range(N - 1):
    act = float("inf")
    for k in range(K):
        if i - k < 0: continue
        act = min(DP[-1 - k] + abs(h[i - k] - h[i + 1]), act)
    DP += [act]

print(DP[-1])

### FIXED CODE ###

import sys
import numpy as np
# inputを高速化する。
input = sys.stdin.readline
n, k = map(int, input().split())
h = [int(i) for i in input().split()]
# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)
for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))
print(dp[n-1])
### BUGGY CODE ###

def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    n,k=mdata()
    A=mdata()
    dp=[1 if A[0]>=i else 0 for i in range(k+1)]
    for i in range(1,n):
        for j in range(1,k+1):
            dp[j]+=dp[j-1]
        for j in range(k+1):
            if A[i]<j:
                dp[j]-=dp[j-A[i]-1]
    print(dp[-1]%mod)



if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

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

    for i in range(n):
        dpsum = [0] * (k + 2)
        for l in range(k + 1):
            dpsum[l + 1] = dpsum[l] + dp[i][l]
            dpsum[l + 1] %= mod
        for j in range(k + 1):
            dp[i + 1][j] = (dpsum[j + 1] - dpsum[max(0, j - a[i])]) % mod
    print(dp[n][k])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from itertools import accumulate
n, k, *A = map(int, open(0).read().split())
for _ in range(min(k, 50)):
    B = [0] * (n+1)
    for i in range(n):
        B[max(0, i-A[i])] += 1
        B[min(n, i+A[i]+1)] -= 1
    A = list(accumulate(B))[:n]
print(*A)

### FIXED CODE ###

from itertools import accumulate
n, k, *A = map(int, open(0).read().split())
for _ in range(min(k, 50)):
    B = [0] * (n+1)
    for i in range(n):
        B[max(0, i-A[i])] += 1
        B[min(n, i+A[i]+1)] -= 1
    *A, = accumulate(B)
print(*A[:n])
### BUGGY CODE ###

from collections import  defaultdict
s = input()
K = int(input())

idx_dict = defaultdict(list)

for i, c in enumerate(s):
    idx_dict[c].append(i)
results = set()
abc = "abcdefghijklmnopqrstuvwxyz"

for al in abc:
    idxs = idx_dict[al]
    count = len(idxs)
    if count == 0:
        continue

    lens = [1 for i in range(count)]
    while len(results) < K:
        useIdx = -1
        useStr = "あああ"
        for i in range(count):
            i1 = idxs[i]
            i2 = idxs[i] + lens[i]
            if i2 <= len(s):
                ss = s[i1:i2]
                if useStr > ss:
                    useStr = ss
                    useIdx = i
        if useIdx < 0:
            break
        lens[useIdx] += 1
        results.add(useStr)
sorted = list(results)
sorted.sort()
print(sorted[K - 1])


### FIXED CODE ###

s = input()
sLen = len(s)
K = int(input())

result = set()
for i in range(sLen):
    for j in range(1, K + 1):
        if i + j > sLen:
            break
        ss = s[i:i+j]
        result.add(ss)
print(sorted(result)[K - 1])
### BUGGY CODE ###

from collections import  deque
h,w = map(int,input().split())
mp = []
for _ in range(h):
    row = list(input())
    mp.append(row)

q = deque()
dist = [[-1] * w for _ in range(h)]

for col in range(h):
    for row in range(w):
        if mp[col][row] == '#':
            q.append((col,row))
            dist[col][row] = 0
ans = 0
while q:
    now_x,now_y = q.popleft()
    ans = dist[now_x][now_y]
    for x,y in ((1,0), (0,1), (-1,0), (0,-1)):
        next_x = now_x + x
        next_y = now_y + y
        if 0 <= next_x < h and 0 <= next_y < w :
            if dist[next_x][next_y] < 0:
                q.append((next_x, next_y))
                dist[next_x][next_y] = ans + 1

print(ans)


### FIXED CODE ###

from collections import  deque
h,w = map(int,input().split())
mp = []
for _ in range(h):
    row = list(input())
    mp.append(row)

q = deque()
dist = [[-1] * w for _ in range(h)]

for col in range(h):
    for row in range(w):
        if mp[col][row] == '#':
            q.append((col,row))
            dist[col][row] = 0
ans = 0
while q:
    now_x,now_y = q.popleft()
    ans = dist[now_x][now_y]
    for x,y in ((1,0), (0,1), (-1,0), (0,-1)):
        next_x = now_x + x
        next_y = now_y + y
        if 0 <= next_x < h and 0 <= next_y < w :
            if dist[next_x][next_y] < 0:
                q.append((next_x, next_y))
                dist[next_x][next_y] = ans + 1

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

import numpy as np
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h = np.array(sorted(h))
diff = np.diff(h)
low_score = np.inf
for i in range(n - k + 1):
    cost = diff[i: i + k - 1].sum()
    low_score = min(low_score, cost)
print(low_score)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array(sorted([int(input()) for _ in range(n)]))
h_roll = np.roll(h, -k + 1)
x = h_roll - h
print(int(x[:-k + 1].min()))
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]
Array = list()
a = 0
b = 0
for i in range(N):
	a, b = [int(x) for x in input().split()]
	Array.extend([a]*b)

Array.sort()
print(Array[K - 1])

### FIXED CODE ###

from operator import itemgetter

N, K = [int(x) for x in input().split()]
Array = list()
A = list()
count = 0
ans = 0
for i in range(N):
	A.append([int(x) for x in input().split()])

A.sort(key=itemgetter(0))
for i in range(N):
	count += A[i][1]
	if count >= K:
		ans = A[i][0]
		break
		
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
for a in range(N):
  newA = [A[a]%n for n in A]
  newA.pop(a)
  if 0 in newA:
    ans = ans
  else:
    ans += 1
  
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
Amax = A[-1]
dp = [1]*(Amax+1)
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:
    for q in range(Amax//p+1):
      dp[p*q] = 0
    if A[i] != A[i+1]: 
      ans += 1
if dp[Amax] == 1:
  ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import copy

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

a_list = sorted(a_list)


def judge(w_list, k):
    w_list = sorted(w_list)

    for i in range(len(w_list) - 1):
        w_list += [abs(w_list[i] - w_list[i + 1])]

    w_list = sorted(list(set(w_list)))

    if k in w_list:
        return True, w_list
    elif 1 in w_list:
        return True, w_list
    elif abs(w_list[0] - w_list[-1]) < K:
        return False, w_list
    elif k % 2 == 0 and 2 in w_list:
        return True, w_list
    else:
        for w in w_list:
            if w + K in w_list:
                return True, w_list

        return False, w_list


w_list = a_list

while True:
    org_w_list = copy.copy(w_list)
    is_ok, w_list = judge(w_list, K)
    if is_ok:
        break
    else:
        if abs(w_list[0] - w_list[-1]) < K:
            break
        if w_list == org_w_list:
            break

ans = "POSSIBLE" if is_ok else "IMPOSSIBLE"

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import copy

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

a_list = sorted(a_list)


def judge(w_list, k):
    w_list = sorted(w_list)

    for i in range(len(w_list) - 1):
        w_list += [abs(w_list[i] - w_list[i + 1])]

    w_list = sorted(list(set(w_list)))

    if k in w_list:
        return True, w_list
    elif 1 in w_list:
        return True, w_list
    elif abs(w_list[0] - w_list[-1]) < K:
        return False, w_list
    elif k % 2 == 0 and 2 in w_list:
        return True, w_list
    else:
        ww_list = set([w + K for w in w_list])
        if ww_list & set(w_list):
            return True, w_list
        else:
            return False, w_list


w_list = a_list

while True:
    org_w_list = copy.copy(w_list)
    is_ok, w_list = judge(w_list, K)
    if is_ok:
        break
    else:
        if abs(w_list[0] - w_list[-1]) < K:
            break
        if w_list == org_w_list:
            break

ans = "POSSIBLE" if is_ok else "IMPOSSIBLE"

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

import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
start = a[0][0]
goal = n
tmp,ans = [],[]
for i in range(m):
	if a[i][1] == goal:
		tmp.append(a[i][0])
#print(tmp)
for j in range(m):
		if a[j][0] == start:
			if a[j][1] in tmp:
				print('POSSIBLE')
				sys.exit()
print('IMPOSSIBLE')

### FIXED CODE ###

import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
start = a[0][0]
goal = n
tmp,ans = [],[]
for i in range(m):
	if a[i][1] == goal:
		tmp.append(a[i][0])
#print(tmp)
for j in range(m):
		if a[j][0] == start:
			ans.append(a[j][1])
if len(set(tmp)&set(ans)) > 0:
	print('POSSIBLE')
	sys.exit()
print('IMPOSSIBLE')