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

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [[0]*2]*m
for i in range(m):
  bc[i] = list(map(int,input().split()))
  
std = sorted(bc, key=lambda x: x[1], reverse=True)
  
for i in range(m):
  if min(a) >= std[i][1]:
    break
  for j in range(std[i][0]):
    a[a.index(min(a))] = max(std[i][1], min(a))

print(sum(a))


### FIXED CODE ###

#5618213
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
ans = [0]*n
#print(ans)
#[0, 0, 0, 0, 0]
for kkk in range(k):
    if kkk == 0:
        for i,l in enumerate(li):
            if l == 0:
                ans[i]+=1
            else:
                mi = max(0,i - l)
                ma = min(n-1,i + l)
                for x in range(mi,ma+1):
                    ans[x]+=1
    else:
        tmp = [0]*n
        for i,l in enumerate(ans):
            if l == 0:
                tmp[i]+=1
            else:
                mi = max(0,i - l)
                ma = min(n-1,i + l)
                for x in range(mi,ma+1):
                    tmp[x]+=1
        ans = tmp
    #print(*ans)
print(*ans)

### FIXED CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
ans = [0]*(n+1)
tmp = [0]*(n+1)
tmp_sum = []
#print(ans)
#[0, 0, 0, 0, 0]
k = min(k,100)

for kkk in range(k):
    #print(li,'li')
    for i,l in enumerate(li):
        if l != 0:
            start = max(0,i-l)
            end = min(n,i+l+1)
            #print(start,'start',end,'end')
            tmp[start] += 1
            #print(end,len(tmp),'aaa')
            tmp[end] -= 1
    #print(tmp,'tmp')
    last = 0
    for t in tmp:
        last = t+last
        tmp_sum.append(last)
    for i,l in enumerate(li):
        if l == 0:
            tmp_sum[i] += 1
    ans = tmp_sum[:n]
    li = tmp_sum[:n]
    tmp = [0]*(n+1)
    tmp_sum = []
    #if len(set(ans)) == 1:
    #    break
print(*ans)
### BUGGY CODE ###

n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    for f in fl:
        if i+1 in f:
            isContinue = True
            break
    if isContinue:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        new_fl = p[r-1]['T']
        for nf in new_fl:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    for f in fl:
        if i+1 in f:
            for s in f:
                if not s in [i+1]+ dt['T'] + dt['B']:
                    ans[i] += 1

print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M,K = map(int,input().split())
    friend = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

A,B,C,D = list(map(int,input().split()))
integer = (i for i in range(A, B+1))
cnt = 0
for x in integer:
    if x % C != 0:
        if x % D != 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

import fractions
def lcm(C,D):
    return C*D//fractions.gcd(C,D)
A,B,C,D = map(int, input().split())
b = (B - B//C - B//D + B//lcm(C,D))
a = ((A-1) - (A-1)//C- (A-1)//D + (A-1)//lcm(C,D))
print(b-a)
### BUGGY CODE ###

def resolve():
        n = int(input())
        s = input()
        r = [0] * n
        g = [0] * n
        b = [0] * n
        for i in range(n):
            if s[i] == "R":
                r[i] = 1
            elif s[i] == "G":
                g[i] = 1
            else:
                b[i] = 1
        ans = 0
        a = [r, g, b]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])
        a = [r, b, g]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])
        a = [g, r, b]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])
        a = [g, b, r]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])

        a = [b, r, g]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])

        a = [b, g, r]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])

        for i in range(1, n // 2+1):
            j = 0
            while j + 2 * i <= n - 1:
                if {s[j], s[j + i], s[j + 2 * i]} == {"R", "G", "B"}:
                    ans -= 1
                j += 1
        print(ans)
resolve()


### FIXED CODE ###

def resolve():
    n = int(input())
    s = input()
    r = [0] * n
    g = [0] * n
    b = [0] * n
    for i in range(n):
        if s[i] == "R":
            r[i] = 1
        elif s[i] == "G":
            g[i] = 1
        else:
            b[i] = 1
    ans = sum(r)*sum(g)*sum(b)

    for i in range(1, n // 2 + 1):
        j = 0
        while j + 2 * i <= n - 1:
            if {s[j], s[j + i], s[j + 2 * i]} == {"R", "G", "B"}:
                ans -= 1
            j += 1
    print(ans)
resolve()
### BUGGY CODE ###

import itertools
import collections
n,k=map(int,input().split())
candle=list(map(int,input().split()))
com=list(itertools.product([1,0], repeat=n))
ans=200000000
for i in range(2**n):
  count=collections.Counter(com[i])
  if count[1]==k:
    begin=0
    end=0
    cnt=0
    temp=0
    for j in range(n):
      if com[i][j]==1:
        cnt+=1
        if cnt==1:
          start=candle[j]
        elif cnt==k:
          end=candle[j]
    if start>=0:
      temp=abs(end)
      if temp<ans:
        ans=temp
    if end<=0:
      temp=abs(start)
      if temp<ans:
        ans=temp
    else:
      temp=min(abs(start), end)*2+max(abs(start), end)
      if temp<ans:
        ans=temp
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
candle=list(map(int,input().split()))
ans=2000000000
for i in range(n-k+1):
  if candle[i]<0 and candle[i+k-1]>0:
    temp=min(abs(candle[i]), candle[i+k-1])*2+max(abs(candle[i]), candle[i+k-1])
  elif candle[i+k-1]<=0:
    temp=abs(candle[i])
  elif candle[i]>=0:
    temp=candle[i+k-1]
  ans=min(temp, ans)
print(ans)
### BUGGY CODE ###

N, K = [int(n) for n in input().split()]
P =  [int(n) for n in input().split()]
o = {}
q =[]
ans = 0

def e(x):
    if x in o: return o[x]
    o[x] = sum([(j/x) for j in range(1,x+1)])
    return o[x]

for p in P:
    if len(q) < K:
        q.append(e(p))
    else:
        m = sum(q)
        if m > ans:
            ans = m
        q.append(e(p))
        q.pop(0)
print(ans if ans>sum(q) else sum(q))

### FIXED CODE ###

N, K = [int(n) for n in input().split()]
P = [(int(n)+1)/2 for n in input().split()]
ans = sum(P[:K])
e = ans
for p,x in zip(P, P[K:]):
    e = e-p+x
    if ans < e:
        ans = e
print(ans)
### BUGGY CODE ###

if __name__ == "__main__":
    N, M = map(int, input().split())
    city_list = []
    for i in range(M):
        city_list.append(list(map(int, input().split())))
    pref = {}
    pref_sort = {}
    for i in range(N):
        pref[str(i+1)] = []
        pref_sort[str(i+1)] = []
    for i in range(M):
        pref[str(city_list[i][0])].append(city_list[i][1])
    for i in range(N):
        pref[str(i+1)].sort()
    for i in range(M):
        key = city_list[i][0]
        val = city_list[i][1]
        output = str(key).zfill(6) + str(pref[str(key)].index(val)+1).zfill(6)
        print(output)

### FIXED CODE ###

# AtCoder Beginner Contest 113-C
if __name__ == "__main__":
    N, M = map(int, input().split())
    city_list = []
    for i in range(M):
        city_list.append(list(map(int, input().split())))
    pref = {}
    pref_sort = {}
    for i in range(M):
        key = city_list[i][0]
        val = city_list[i][1]
        if str(key) in pref:
            pref[str(key)].append(val)
        else:
            pref[str(key)] = [val]
    ans = {}
    for key, val in pref.items():
        val.sort()
        for i in range(len(val)):
            ans[(key, val[i])] = str(key).zfill(6) + str(i+1).zfill(6)
    for key, val in city_list:
        print(ans[str(key), val])
### BUGGY CODE ###

from sys import stdin
import bisect

a,b = [int(x) for x in stdin.readline().rstrip().split()]

while True:
    if a*2 < b:
        a += 1
        b -= 2
    else:
        break
print(min(a,b//2))

### FIXED CODE ###

from sys import stdin

a,b = [int(x) for x in stdin.readline().rstrip().split()]

if a > b//2:
    print(b//2)
else:
    print((b+2*a)//4)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
p = list(map(int, input().split()))
swappair= [list(map(int, input().split())) for _ in range(M)]

union_list = [-1 for _ in range(N+1)]

def find(a): # get root
    while not union_list[a] == -1:
        a = union_list[a]
    return a

def merge(a,b): 
    ia = find(a)
    ib = find(b)
    union_list[ib] = ia

def is_same_grp(a,b):
    ia = find(a)
    ib = find(b)
    return ia == ib

for i in range(M):
    merge(*swappair[i])

ans = 0
for i in range(1,N+1):
    ans += int( is_same_grp(i, p[i-1]))

print(ans)




### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
p = list(map(int, input().split()))
swappair= [list(map(int, input().split())) for _ in range(M)]

union_list = [-1 for _ in range(N+1)]

def find(a): # get root
    while not union_list[a] == -1:
        a = union_list[a]
    return a

def merge(a,b): 
    ia = find(a)
    ib = find(b)
    if ia == ib:
        return 
        
    if ia < ib:
        union_list[ib] = ia
    elif ia > ib:
        union_list[ia] = ib
    


def is_same_grp(a,b):
    ia = find(a)
    ib = find(b)
    return ia == ib

for i in range(M):
    merge(*swappair[i])

ans = 0
for i in range(1,N+1):
    ans += int( is_same_grp(i, p[i-1]))

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

n,m = map(int,input().split())
H = [int(i) for i in input().split()]

a = [0] * m
b = [0] * m

ans = [1]* n



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

for i in range(n):

    for j in range(m):
        if a[j] == i+1 and H[i] <= H[b[j]-1]:
            ans[i] = 0
        elif b[j] == i+1 and H[i] <=  H[a[j]-1]:
            ans[i] = 0
    #for k in range(m):
        #print(i)
        #print(a[k])
        #if b[k] == i and H[i-1] > H[a[k]-1]:
        #    ans[i-1] = 0





print(ans.count(1))


### FIXED CODE ###

n,m = map(int,input().split())
H = [int(i) for i in input().split()]

a = [0] * m
b = [0] * m
ans = [1]* n



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


for j in range(m):
    if H[a[j]-1] < H[b[j]-1]:
        ans[a[j]-1] = 0
    elif H[a[j]-1] > H[b[j]-1]:
        ans[b[j]-1] = 0
    elif H[a[j]-1] == H[b[j]-1]:
        ans[a[j]-1] = 0
        ans[b[j]-1] = 0


print(ans.count(1))
### BUGGY CODE ###

s = list(input().strip())
n = len(s)
end = n - 2

count = 0

if n >= 3:
  i = 0
  while i < end:
    if s[i] == 'A' and s[i + 1] == 'B' and s[i + 2] == 'C':
      s[i] = 'B'
      s[i + 2] = 'A'
      count = count + 1

      j = i - 1
      while j >= 0 and s[j] == 'A':
        s[j] = 'B'
        s[j + 2] = 'A'
        count = count + 1
        j = j - 1

      i = i + 2
    else:
      i = i + 1

print(count)

### FIXED CODE ###

s = input().strip().replace('BC', 'D')
n = len(s)

count = 0
a_count = 0
for i in range(n):
  if s[i] == 'A':
    a_count += 1
  elif a_count > 0 and s[i] == 'D':
    count += a_count
  else:
    a_count = 0

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

import sys
input = sys.stdin.readline

def min_cost_flow(E, s, t, f):
    NN = 2 * N + 6
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    while f > 0:
        dist = [1<<100] * NN
        dist[s] = 0
        update = 1
        while update:
            update = 0
            for v in range(NN):
                if dist[v] == 1<<100: continue
                for i, (b, _cap, c, r) in enumerate(G[v]):
                    if _cap > 0 and dist[b] > dist[v] + c:
                        dist[b] = dist[v] + c
                        prevv[b] = v
                        preve[b] = i
                        update = 1
        if dist[t] == 1<<100:
            return -1
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
N = int(input())
su = 0
INF = 1 << 31
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + INF))
    E.append((i, 2*N+1, cnt, x - y + INF))
    E.append((i, 2*N+2, cnt, - x + y + INF))
    E.append((i, 2*N+3, cnt, - x - y + INF))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + INF))
    E.append((2*N+1, i+N, cnt, - x + y + INF))
    E.append((2*N+2, i+N, cnt, x - y + INF))
    E.append((2*N+3, i+N, cnt, x + y + INF))

print(su * INF * 2 - min_cost_flow(E, 2*N+4, 2*N+5, su))

### FIXED CODE ###

from networkx import*
N = int(input())
G = MultiDiGraph()
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(i, demand = -c)
    G.add_weighted_edges_from([(i, -1, x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -2, x - y)], capacity = c)
    G.add_weighted_edges_from([(i, -3, -x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -4, -x - y)], capacity = c)
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(N + i, demand = c)
    G.add_weighted_edges_from([(-1, N + i, -x - y)], capacity = c)
    G.add_weighted_edges_from([(-2, N + i, -x + y)], capacity = c)
    G.add_weighted_edges_from([(-3, N + i, x - y)], capacity = c)
    G.add_weighted_edges_from([(-4, N + i, x + y)], capacity = c)

print(-min_cost_flow_cost(G))
### BUGGY CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    field = "#"*(W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#"*(W+2)

    INF = 10**9
    cost = [INF]*len(field)
    move = [-1, 1, -(W+2), W+2]
    def bfs(s):
        q = deque()

        cost[s] = 0
        q.append(s)

        while q:
            now = q.popleft()
            now_cost = cost[now]
            for dx in move:
                nv = now + dx

                if field[nv] == "#" or cost[nv] < INF:
                    continue
                else:
                    cost[nv] = now_cost + 1
                    q.append(nv)
    
    ans = 0
    for si in range(H):
        for sj in range(W):
            for gi in range(H):
                for gj in range(W):
                    start = (si+1)*(W+2)+sj+1
                    goal = (gi+1)*(W+2)+gj+1
                    if start == goal or "#" in [field[start], field[goal]]:
                        continue
                    cost = [INF] * len(field)
                    bfs(start)
                    ans = max(ans, cost[goal])
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    field = "#"*(W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#"*(W+2)

    INF = 10**9
    cost = [INF]*len(field)
    move = [-1, 1, -(W+2), W+2]
    def bfs(s, g):
        q = deque()
        dequeue = q.popleft
        enqueue = q.append
        cost[s] = 0
        enqueue(s)

        while q:
            now = dequeue()
            now_cost = cost[now]
            for dx in move:
                nv = now + dx
                if nv == g:
                    cost[g] = now_cost + 1
                    return
                if field[nv] == "#" or cost[nv] < INF:
                    continue
                else:
                    cost[nv] = now_cost + 1
                    q.append(nv)
    
    ans = 0
    for si in range(H):
        for sj in range(W):
            for gi in range(H):
                for gj in range(W):
                    start = (si+1)*(W+2)+sj+1
                    goal = (gi+1)*(W+2)+gj+1
                    if field[start] == "#" or  field[goal] == "#" or start == goal:
                        continue
                    cost = [INF] * len(field)
                    bfs(start, goal)
                    ans = max(ans, cost[goal])
    print(ans)

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

n = int(input())

a = {i+1: list(map(int, input().split())) for i in range(n)}

ret = 1
while True:
    pair = []
    for k,v in a.items():
        if v and v[0] in a and a[v[0]][0] == k:
            pair.append(k)
    for p in pair:
        if len(a[p]) > 1:
            a[p] = a[p][1:]
        else:
            a.pop(p)
    if len(a) == 0:
        break
    if len(pair) == 0:
        ret = -1
        break
    ret = ret + 1

print(ret)

### FIXED CODE ###

n = int(input())
 
a = {i+1: list(map(int, input().split())) for i in range(n)}
ret = 1
pair = []
keys = a.keys()
while True:
    for k in keys:
        v = a[k][0]
        if a[v][0] == k:
            pair.append(k)
            if v not in keys:
                pair.append(v)
    for p in pair:
        if len(a[p]) > 1:
            a[p] = a[p][1:]
        else:
            a.pop(p)
    if len(a) == 0:
        break
    if len(pair) == 0:
        ret = -1
        break
    ret = ret + 1
    keys = [k for k in pair if k in a]
    pair = []
 
print(ret)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
  for y in range(x,k+1):
    for z in range(y,k+1):
      if x+y+z==s:
        if x==y and y==z:
          ans+=1
        elif x==y or y==z or x==z:
          ans+=3
        else:
          ans+=6
print(ans)


### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
  for y in range(x,k+1):
    z=s-(x+y)
    if z>k or z<y:
      continue
    if x==y and y==z:
      ans+=1
    elif x==y or y==z or x==z:
      ans+=3
    else:
      ans+=6
print(ans)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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())


def choose_abc_range(s):
    ranges = []
    cur = 0
    while cur < len(s):
        if s[cur:cur+3] == "ABC":
            st = cur
            j = cur

            while s[j:j+3] == "ABC":
                j += 3

            ed = j

            ranges.append([st, ed])
            cur = j

        else:
            cur += 1

    return ranges

def get_a(sa):
    a = 0
    for sai in sa:
        if sai == "A":
            a += 1
        else:
            break

    return a

def get_bc(sb):
    b = 0
    for sbi in sb[::2]:
        if sbi == "bc":
            b += 1
        else:
            break

    return b

s = ns()
ans = 0
while "ABC" in s:

    ranges = choose_abc_range(s)

    for l, r in ranges:
        k = (r-l+1)//3

        ans += k

        s = s[:l] + "BCA"*k + s[r:]

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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())


s = ns()

cur = 0
anum = 0
bcnum = 0
ans = 0

while cur < len(s):
    if s[cur:cur+1] == "A":
        anum += 1
        cur += 1

    elif s[cur:cur+2] == "BC":
        bcnum += 1
        ans += anum
        cur += 2

    else:
        anum = 0
        bcnum = 0
        cur += 1

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

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

lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい

for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)

lis[0].sort()

for i in lis[-1]:
  if i in lis[0]:
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])):
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')
### BUGGY CODE ###

N=int(input())

for h in range(1,3501):
    for n in range(h,3501):
        if (4*h*n-N*n-N*h)==0:
            pass
        elif (N*h*n)/(4*h*n-N*n-N*h)==int((N*h*n)/(4*h*n-N*n-N*h)):
            if int((N*h*n)/(4*h*n-N*n-N*h))>0:
                print(h,n,int((N*h*n)/(4*h*n-N*n-N*h)))
                exit()

### FIXED CODE ###

N=int(input())

for a in range(1,3501):
    for b in range(1,3501):
        if (4*a*b-N*a-N*b)>0:
            c=N*a*b/(4*a*b-N*a-N*b)
            if c==int(c):
                if 4*a*b*c==N*(a*b+b*c+c*a):
                    print(a,b,int(c))
                    exit()