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

from itertools import product
N, M = map(int, input().split())
x, y, z = zip(*(map(int, input().split()) for _ in range(N)))


def f(a, b, c, p, q, r):
    dp = [(0, 0, 0) for _ in range(M + 1)]
    for t in zip(a, b, c):
        for i in range(M, 0, -1):
            u = (dp[i - 1][0] + p * t[0], dp[i - 1][1] + q * t[1], dp[i - 1][2] + r * t[2])
            if sum(u) > sum(dp[i]):
                dp[i] = u
    return sum(map(abs, dp[M]))


ans = max(
    f(x, y, z, p, q, r)
    for p, q, r in product((-1, 1), repeat=3)
)
print(ans)


### FIXED CODE ###

from itertools import product
N, M = map(int, input().split())
x, y, z = zip(*(map(int, input().split()) for _ in range(N)))


def f(a, b, c):
    return sum(sorted(map(sum, zip(a, b, c)), reverse=True)[:M])


def g(k, a):
    return [k * e for e in a]


ans = max(
    f(g(p, x), g(q, y), g(r, z))
    for p, q, r in product((-1, 1), repeat=3)
)
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
#print(S[1])
cnt=0
for k in range(1,N+1):
  for j in range(1,k):
    for i in range(1,j):
      if S[i-1]!=S[j-1] and S[i-1]!=S[k-1] and S[j-1]!=S[k-1]:
        if (j-i)!=(k-j):
          cnt += 1
          #print(i,j,k,j-i,k-j, S[i-1],S[j-1],S[k-1])
print(cnt)

### FIXED CODE ###

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

r=S.count('R')
g=S.count('G')
b=S.count('B')
al_num=r*g*b

#全体からj-i=k-jの場合を引く
sub=0
for i in range(0,N):
  for j in range(i+1,N):
    if S[i]==S[j]:
      continue

    k = 2*j -i
    #i,j,kは等差数列なのでkは決まる, k>=Nは不適なのでスキップ
    if k>=N or S[k]==S[i] or S[k]==S[j]:
      continue
    
    sub += 1
print(al_num - sub)
# O(N^2)
### BUGGY CODE ###

num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []

for i in range(num):
    c.append(a[i] ^ a[(i+1)%num])
    d.append(b[i] ^ b[(i+1)%num])
    
c += c

for k in range(num):
    if d == c[k:num+k]:
        print(k, a[k] ^ b[0])

### FIXED CODE ###

num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []

for i in range(num):
    c.append(a[i] ^ a[(i+1)%num])
    d.append(b[i] ^ b[(i+1)%num])
    
c += c

# print(c)
# print(d)

# テーブル作成
table = [0]
k = 0
for i in range(1, num+1):
    table.append(k)
    if i == num:
        continue
    
    if d[i] == d[k]:
        k += 1
    else:
        k = 0

# print(table)

i = 0 # 探索される文字列の位置
j = 0 # 探索する文字列の位置
k = 0 # kの初期値
while k < num:
    
    while True:
        # print(i, j, k)
        if c[i] == d[j]:
            if j == num - 1:
                print(k, a[k] ^ b[0])
                i += 1
                j = table[num]
                k = i - j
                break
            
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:    
            i += 1
            j = table[j]
            break
    
    k = i - j
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from copy import copy


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    for i in range(N):
        tmp = copy(A)
        tmp[i] = 0
        print(max(tmp))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from copy import copy


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A_max = copy(A)
    A_max.sort(reverse=True)

    for a in A:
        if a == A_max[0]:
            print(A_max[1])
        else:
            print(A_max[0])


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

s = input()
k = int(input())

set_ = set()

for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        set_.add(s[i:j])

res = sorted(list(set_))[k-1]
print(res)

### FIXED CODE ###

s = input()
k = int(input())

s_head = sorted(list(set(s)), reverse=True)
res = [s_head.pop()]
while len(res) < k:
    tmp = res[-1]
    tmp_list = []
    for i in range(len(s)-len(tmp)):
        if s[i:i+len(tmp)] == tmp:
            tmp_list.append(s[i:i+len(tmp)+1])
    if len(tmp_list) == 0:
        res.append(s_head.pop())
    elif min(tmp_list) == tmp:
        res.append(s_head.pop())
    else:
        res.append(min(tmp_list))

print(res[k-1])
### BUGGY CODE ###

s1 = input()
s2 = input()
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
prev = dp[0]
for i in range(1,n+1):
    dpi = dp[i]
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dpi[j] = 1 + prev[j-1]
        else:
            dpi[j] = max(prev[j], dpi[j-1])
    prev = dpi
res = ''
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res = s1[i-1] + res
        i -= 1
        j -= 1
print(res)

### FIXED CODE ###

s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
res = []
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res.append(s1[i-1])
        i -= 1
        j -= 1
print(''.join(res[::-1]))
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())

    cnt = 0
    for i in range(Q):
        query = input().split()
        if(query[0] == "1"):
            cnt += 1
        else:
            if(query[1] == "1"):
                if(cnt%2 == 0):
                    S = query[2]+S
                else:
                    S = S+query[2]
            else:
                if(cnt%2 == 0):
                    S = S+query[2]
                else:
                    S = query[2]+S
        
    if(cnt%2 == 0):
        print(S)
    else:
        print(S[::-1])
main()

### FIXED CODE ###

from collections import deque

def main():
    S = input()
    Q = int(input())
    
    SS = deque()
    for s in S:
        SS.append(s)
    
    cnt = 0
    for i in range(Q):
        query = input().split()
        if(query[0] == "1"):
            cnt += 1
        else:
            if(query[1] == "1"):
                if(cnt%2 == 0):
                    SS.appendleft(query[2])
                else:
                    SS.append(query[2])
            else:
                if(cnt%2 == 0):
                    SS.append(query[2])
                else:
                    SS.appendleft(query[2])
    
    ans = list(SS)
    if(cnt%2 == 0):
        print(''.join(ans))
    else:
        print(''.join(ans[::-1]))
main()
### BUGGY CODE ###


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

#Aは小さい順に並べる
A_list = list(map(int,input().split()))
A_list = sorted(A_list)
BC_list = []

ans = 0

for i in range(M):
    bi,ci = map(int,input().split())
    BC_list.append([bi,ci])

#BC_listからCの配列を作成する(大きい順)
C_list=[]
for i in range(M):
    for j in range(BC_list[i][0]):
        C_list.append(BC_list[i][1])
C_list=sorted(C_list,reverse=True)

#NにたりないばあいはNまで1で埋める、Nより大きい場合はNまでを使う
if len(C_list) > N:
    C_list = C_list[0:N]
else:
    for i in range(N-len(C_list)):
        C_list.append(1)

#どこの添字からAとCが逆転するか調べる
for i in range(N):
    #Aは昇順、Cは降順
    if C_list[i] > A_list[i]:
        A_list[i] = C_list[i]
    else:
        break

print(sum(A_list))


### FIXED CODE ###


#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める
N,M = map(int,input().split())

#Aの入力
A_list = list(map(int,input().split()))

C_list = []

#Cのリストに追加する
for i in range(M):
    bi,ci = map(int,input().split())
    C_list.append([bi,ci])

#C_listをCの値でソート
C_list=sorted(C_list, reverse=True, key=lambda x:x[1])

count = 0
for bi,ci in C_list:
    count += bi
    if count > N:
        #countがNより大きくなったらNより大きくなった分だけ使う
        bi = N - count + bi
    A_list.extend([ci]*bi)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print(sum(A_list[0:N]))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

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


def gcd_list(lst):
    return reduce(gcd, lst)


ans = 0
for i in range(N):
    ans = max(ans, gcd_list(A[:i] + A[i+1:]))
print(ans)


### FIXED CODE ###

from fractions import gcd

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


def gcd2(x, y):
    if not x:
        return y
    if not y:
        return x
    return gcd(x, y)


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

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

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

n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

ans=0
for i in range(0,n,2):
    ans=max(ans,sum(A[i:2*k+1+i]))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
S=input()+"*"

A=[0] if S[0]=="1" else []
cnt,fig=0,S[0]
for i in range(n+1):
    if fig!=S[i]:
        A.append(cnt)
        fig=S[i]
        cnt=1
    else:cnt +=1

if S[-2]=="0":A.append(0)
num=2*(k+1)
B=[[0,0]] if S[0]=="0" else []
for i in range(1,len(A)):
    A[i]=A[i]+A[i-1]
for i in range(0,len(A),2):
    B.append([A[i],A[i+1]])

C=[]
left=0
for i in range(max(0,len(B)-k)):
    C.append(B[k+i][1]-B[left+i][0])
print(max(C) if len(B)-k>0 else B[-1][1])
### BUGGY CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += cmb(i+n-1, n-1, mod) * pow(25, i) * pow(26, (K-i))
print(ans%mod)

### FIXED CODE ###

# F - Strivore
import sys
MOD = 10**9+7
K = int(input())
S = input()
l = len(S)
ans = 0
 
tmp = pow(26,K,MOD)
ans = tmp
waru = pow(26,-1,MOD)
 
for i in range(1,K+1):
    tmp = (tmp*25*waru)%MOD
    tmp = (tmp*(l-1+i)*pow(i,-1,MOD))%MOD
    ans = (ans+tmp)%MOD
 
print(ans)
### BUGGY CODE ###

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

L.sort()
cnt = 0
for i in range(N-1):
    for j in range(i):
        a, b = L[i], L[j] 
        k = i + 1
        l = 0
        r = 0
        for k in range(i+1, N):
            if L[k] > a - b:
                l = k
                break
        for k in range(N-1, i, -1):
            if L[k] < a + b:
                r = k
                break
        
        cnt += max(r - l + 1, 0)
            
print(cnt)            

### FIXED CODE ###

from bisect import bisect, bisect_left
N = int(input())
L = list(map(int, input().split()))

L.sort()
cnt = 0
for i in range(N-1):
    for j in range(i):
        a, b = L[i], L[j] 
        r = bisect_left(L[i+1:], a+b) + i+1
        cnt += max(r - i - 1, 0)
            
print(cnt)
### BUGGY CODE ###

from collections import Counter

def ngram(text, n):
    return [text[i:i+n] for i in range(len(text) - n + 1)]

text = input()
k = int(input())
candidates = set()
for n in range(1,len(text) + 1):
    #_ = filter(lambda x:x[1] == 1,Counter(ngram(text,n)).items())
    candidates |= set(ngram(text,n))

print(sorted(list(candidates))[k-1])

### FIXED CODE ###

from collections import Counter

def ngram(text, n):
    return [text[i:i+n] for i in range(len(text) - n + 1)]

text = input()
k = int(input())
candidates = set()
for n in range(1,6):
    #_ = filter(lambda x:x[1] == 1,Counter(ngram(text,n)).items())
    candidates |= set(ngram(text,n))

print(sorted(list(candidates))[k-1])
### BUGGY CODE ###

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

for i in range(n):
    if a_lst.count(a_lst[i])!=1:
        print('NO')
        break
else:
    print('YES')

### FIXED CODE ###

n = int(input())
a_lst = list(map(int,input().split()))
new_lst = list(set(a_lst))

if len(a_lst)==len(new_lst):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import math 

INF = 1e9+7
n,m = map(int, input().split())
ans = 0
n,m = max(n,m),min(m,n)
a = math.factorial(n)
if n==m:
    ans = 2*(a**2)
elif n==m-1 or n-1 ==m:
    ans = a*a//n
else:
    ans = 0
print(ans)

### FIXED CODE ###

import math 

INF = 10**9 + 7
n,m = map(int, input().split())
ans = 0
n,m = max(n,m),min(m,n)
a = math.factorial(n)%INF
b = math.factorial(m)%INF
ans = a*b
if n==m:
    ans = ans*2
    ans = ans%INF
elif n ==m+1:
    ans = ans%INF
else:
    ans = 0
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    heap = []
    ans = 0
    for a in map(int, input().split()):
        heappush(heap, a)
        ans += a

    for _ in range(M):
        B, C = map(int, input().split())
        for _ in range(B):
            a = heappop(heap)
            if a < C:
                heappush(heap, C)
                ans += C - a
            else:
                heappush(heap, a)
                break

    return ans


if __name__ == '__main__':
    print(main())



### FIXED CODE ###

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    heap = []
    ans = 0
    for a in map(int, input().split()):
        heappush(heap, a)
        ans += a

    BC = []
    for _ in range(M):
        B, C = map(int, input().split())
        BC.append((B, C))

    BC = sorted(BC, key=lambda x: -x[1])
    for B, C in BC:
        for _ in range(B):
            a = heappop(heap)
            if a < C:
                heappush(heap, C)
                ans += C - a
            else:
                heappush(heap, a)
                break

    return ans


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

import collections
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

Q, K = map(int, input().split())
xy = [map(int, input().split()) for i in range(Q)]
k = [set() for i in range(N)]
g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c
    k[a-1].add(b-1)
    k[b-1].add(a-1)
c = [10**9*N]*N
c[K-1] = 0
q = collections.deque([K])
while(len(q) > 0):
    x = q.popleft()

    for y in k[x-1]:
        if c[y] == (10**9*N):
            q.append(y+1)
        c[y] = min(c[x-1]+g[x-1][y], c[y])

for x, y in xy:
    print(c[x-1] + c[y-1])


### FIXED CODE ###

N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[-1]*N

Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
memo[K-1]=0
while(q):
  
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[x-1]+memo[y-1])
### BUGGY CODE ###

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

pos = -1
seen = [False] * n
hist = []
cycle = []
i = 0
while(seen[i] == False):
    seen[i] = True
    hist.insert(0, i)
    ne = a[i]-1
    i = ne
    if (seen[i] == True):
        pos = i

preCircle = len(hist)

cnt = 0
while(len(hist) != 0):
    b = hist[0]
    cycle.append(b)
    cnt += 1
    hist.pop(0)
    if (b == pos):
        break

preCircle -= cnt

cycle = list(reversed(cycle))

if (k < preCircle):
    print(hist[-k-1] + 1)
else:
    k -= preCircle
    ans = k % len(cycle)
    print(cycle[ans] + 1)



### FIXED CODE ###

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

pos = -1
seen = [False] * n
last = [-1] * n
hist = []
i = 0
cnt = 0

while(seen[i] == False):
    seen[i] = True
    last[i] = cnt
    cnt += 1
    hist.append(i)
    ne = a[i]-1
    i = ne
    if (seen[i] == True):
        pos = i

cycle = hist[last[pos]:]
preCircle = last[pos]

if (k <= preCircle):
    print(hist[k] + 1)
else:
    k -= preCircle
    ans = k % len(cycle)
    print(cycle[ans] + 1)
### BUGGY CODE ###

import bisect

N = int(input())

ans = [-1]
for _ in range(N):
    a = int(input())
    i = bisect.bisect_left(ans, a)
    if i == 0:
        ans.append(a)
    else:
        ans[i-1] = a
    ans.sort()
print(len(ans))


### FIXED CODE ###

import bisect
import collections

N = int(input())
A = [int(input()) for _ in range(N)]

ans = collections.deque([A[0]])

for a in A[1:]:
    if a <= ans[0]:  # 色を増やすしかない
        ans.appendleft(a)
    else:  # 既存の色のどこかに追加
        idx = bisect.bisect_left(ans, a)
        ans[idx-1] = a
    # print(a, ans)

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

n=int(input())
sump=1

for i in range(n):
  sump=sump*(i+1)
  
print(sump%(10**9+7))

### FIXED CODE ###

n=int(input())
sump=1

for i in range(n):
  sump*=i+1
  sump%=1000000007
  
print(sump)
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z == s:
        ans += 1

print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z <= k:
      ans += 1

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b


s = [int(input()) for i in range(M)]
broken = []
broken.append(-1)
broken.extend(s)
broken.append(N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に

gaps = []  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps.append(broken[i+1]-broken[i]-1)
    if broken[i+1]-broken[i]-1 == 0:
        flag = 1
        break


fibs = []
if flag == 1:
    print(0)
else:
    for i in range(max(gaps)):
        fibs.append(fib(i))
        
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0
def fib(n):
    a, b = 0, 1
    c = [1]
    for i in range(n):
        a, b = b, a + b
        c.append(b)
    return c


broken = np.array([int(input()) for i in range(M)])
broken = np.append(-1,broken)
broken = np.append(broken,N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に

gaps = np.array([])  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps = np.append(gaps, broken[i+1]-broken[i]-1)
    if broken[i+1]-broken[i]-1 == 0:
        flag = 1
        break

gaps = np.array(gaps, np.int)  # 整数列に変換



if flag == 1:
    print(0)
else:
    fibs = fib(max(gaps))
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)
### BUGGY CODE ###

import numpy as np



N,W = map(int,input().split())
items = [[int(a) for a in input().split()]]
for i in range(N-1):
    items.append([int(a) for a in input().split()])
items = np.array(items)
dp = np.full((N+1,W+1),0,dtype=np.int64)
dp[0][W] = 0
for i in range(N):
    for w in range(W+1):
        if w-items[i][0] >= 0:
            dp[i+1][w] =max(dp[i][w],dp[i][w-items[i][0]]+items[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

### FIXED CODE ###

import numpy as np
 
N,Max_W = map(int,input().split())
 
dp = [0 for _ in range(Max_W + 1)]
dp = np.array(dp)
 
for i in range(N):
    w,v = map(int,input().split())
    a = dp[:-w] + v
    b = dp[w:]
    m = np.maximum(a,b)
    dp[w:] = m
print(dp[-1])
### BUGGY CODE ###

from bisect import bisect_left as b
n=int(input())
a=sorted(list(map(int,input().split())))
s=n-1
c=0
while s>0:
    t=2**(len(bin(a[s]))-2)
    if t-a[s] in a:
        d=b(a,t-a[s])
        if d<s and a[d]==t-a[s]:
            a.pop(d)
            c+=1
            s-=1
    s-=1
print(c)

### FIXED CODE ###

from collections import defaultdict as d
n=int(input())
a=sorted(list(map(int,input().split())))
b=d(int)
for i in a:
    b[i]+=1
s=n-1
c=0
while s>0:
    if b[a[s]]>0:
        t=2**(len(bin(a[s]))-2)
        b[a[s]]-=1
        if b[t-a[s]]>0:
            b[t-a[s]]-=1
            c+=1
    s-=1
print(c)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = []
c = []
for i in range(m):
	a, b = map(int, input().split())
	if b == n:
		c.append(a)
	ab.append([a,b])
ab.sort(key=lambda x: x[0])
for i in range(m):
	if ab[i][0] == 1:
		d = ab[i][1]
		if d in c:
			print ("POSSIBLE")
			exit()
print ("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
#2次元配列
#a=[list(map(int,input().split())) for i in range(m)]

aa = []
bb = []
for i in range (m):
	a, b = map(int, input().split())
	if(a == 1):
		aa.append(b)
	if(b == n):
		bb.append(a)

if( len(set(aa) & set(bb)) == 0):
	print ("IMPOSSIBLE")
else:
	print ("POSSIBLE")
### BUGGY CODE ###

[n,m] = [int(i) for i in input().split()]
dic = {}
for i in range(n):
    [ai,bi] = [int(i) for i in input().split()]
    if ai in dic.keys():
        dic[ai] += bi
    else:
        dic[ai] = bi
sum = 0
while m > 0:
    #print(dic)
    if dic[min(dic.keys())] >= m:
        sum += min(dic.keys()) * m
        m = 0
    else:
        sum += dic[min(dic.keys())]*min(dic.keys())
        m -= dic.pop(min(dic.keys()))
print(sum)


### FIXED CODE ###

[n,m] = [int(i) for i in input().split()]
dic = {}
for i in range(n):
    [ai,bi] = [int(i) for i in input().split()]
    if ai in dic.keys():
        dic[ai] += bi
    else:
        dic[ai] = bi
sum = 0
ls = sorted(list(dic.keys()))
while m > 0:
    for i in range(len(ls)):
    #print(dic)
        if dic[ls[i]] >= m:
            sum += ls[i] * m
            m = 0
            break
        else:
            sum += dic[ls[i]]*ls[i]
            m -= dic[ls[i]]
print(sum)
### BUGGY CODE ###

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

ans=[]

for i in range(q):
    l,r=map(int,lr[i].split())
    #print(int((len(s[l-1:r])-len(s[l-1:r].replace('AC',"")))/2))
    ans.append(str(int((len(s[l-1:r])-len(s[l-1:r].replace('AC',"")))/2)))

print('\n'.join(ans))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
lr=[input() for __ in range(q)]
cs=[0]*(n+1)

#端がACで-1で止まる文字列指定は大丈夫？.
for i in range(n):
    cs[i+1]=cs[i] + (1 if s[i:i+2] == 'AC' else 0)

for num in lr:
    l,r=map(int,num.split())
    print(cs[r-1] - cs[l-1])
### BUGGY CODE ###

from collections import deque
N,K = map(int,input().split())
C = deque(map(int,input().split()))
D = C.copy()
#print(C)
ans = 1
for i in range(K):
  ans *= C.popleft()

for i in range(N-K):
  preans = ans
  ans *= C.popleft()
  ans /= D.popleft()
  if preans < ans:
    print("Yes")
  if preans >= ans:
    print("No")

### FIXED CODE ###

from collections import deque
N,K = map(int,input().split())
C = deque(map(int,input().split()))
D = C.copy()
#print(C)
ans = 1
for i in range(K):
  C.popleft()
  #ans *= C.popleft()

for i in range(N-K):
  preans = D.popleft()
  ans = C.popleft()
  #preans = ans
  #ans *= C.popleft()
  #ans /= D.popleft()
  if preans < ans:
    print("Yes")
  if preans >= ans:
    print("No")
### BUGGY CODE ###

X = int(input())
b = 1
MAX = 1
flag = 0
while b <= X:
    p = 2
    while p <= 10:
        beki = b**p
        if beki <= X:
            if beki >= MAX:
                MAX = beki
            else:
                p+=1
        else:
            if p == 2:
                flag = 1
            break
    if flag == 1:
        break
    b+=1
print(MAX)

### FIXED CODE ###

X = int(input())
beki=[]
for a in range(X):
    A=a+1
    for i in range(32):
        I=i+1
        j=0
        for j in range(9):
            J=j+2
            if A == I**J:
                beki.append(A)
                break
            elif A<I**J:
                break
print(max(beki))