Harryxun/stf_run huggingface dataset:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())

adj = [set() for _ in range(N)] #adj[i] = (i_adj, 距離0or1)
for _ in range(N-1):
  u, v, w = mi()
  #0スタートに
  u -= 1
  v -= 1
  adj[u].add((v, w%2))
  adj[v].add((u, w%2))

from collections import deque
q = deque([])

seen = [0] * N
bw = [0] * N

#とりあえずノード0から探索をスタートすることにする
#0の距離は0としておく
q.append(0)
bw[0] = 0 #必要無いが、分かりやすくするために
seen[0] = 1


def solve(): #前のノードまでの色（0or1）を引き継ぐ
  try: nownode = q.popleft()
  except: return
  nowcolor = bw[nownode]

  #今のノードから隣接しているものを探索
  for adjidx, w in adj[nownode]:
    if seen[adjidx]!=1:
      q.append(adjidx)
      seen[adjidx]=1
      bw[adjidx] = (nowcolor+w)%2

  solve()

solve()

for color in bw:
  print(color)



### FIXED CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###
import sys
sys.setrecursionlimit(10000000)

N = int(input())

adj = [set() for _ in range(N)] #adj[i] = (i_adj, 距離0or1)
for _ in range(N-1):
  u, v, w = mi()
  #0スタートに
  u -= 1
  v -= 1
  adj[u].add((v, w%2))
  adj[v].add((u, w%2))

from collections import deque
q = deque([])

seen = [0] * N
bw = [0] * N

#とりあえずノード0から探索をスタートすることにする
#0の距離は0としておく
q.append(0)
bw[0] = 0 #必要無いが、分かりやすくするために
seen[0] = 1


def solve(): #前のノードまでの色（0or1）を引き継ぐ
  try: nownode = q.popleft()
  except: return
  nowcolor = bw[nownode]

  #今のノードから隣接しているものを探索
  for adjidx, w in adj[nownode]:
    if seen[adjidx]!=1:
      q.append(adjidx)
      seen[adjidx]=1
      bw[adjidx] = (nowcolor+w)%2

  solve()

solve()

for color in bw:
  print(color)
import sys
from math import gcd

# sys.stdin = open('b1.in')

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

d = gcd(a, b)
if c % d == 0:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

import sys

# sys.stdin=open('b1.in')

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

res = 'NO'
for k in range(1, b + 1):
    if k * a % b == c:
        res = 'YES'
        break
print(res)
import math
N=int(input())
a = list(map(int, input().split()))

#------------最小公倍数---------------------
lcm = a[0]
for i in range(1, N):
    lcm = lcm * a[i] // math.gcd(lcm, a[i])
#------------------------------------------
b= []
for i in range(N):
    b.append(lcm //a[i])
ans=0


for j in range(len(b)):
    ans +=b[j]%1000000007



print(ans)


### FIXED CODE ###

import fractions
N=int(input())
a = list(map(int, input().split()))

#------------最小公倍数---------------------
lcm = a[0]
for i in range(1, N):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])
#------------------------------------------
ans=0
for j in a:
    ans += lcm // j
print(ans % 1000000007)
N = int(input())

lis = []

for n in range(N):
  s = input()
  if not s in lis:
    s.append(s)

print(len(lis))

### FIXED CODE ###

N = int(input())

lis = []

for n in range(N):
  lis.append(input())

s = set(lis)
print(len(s))
a, b = map(int, input().split())
print(a%2==0 or b%2==0 ? 'No' : 'Yes')


### FIXED CODE ###

a, b = map(int, input().split())
print('No' if a%2==0 or b%2==0 else 'Yes')
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue

        c=deque()    
        s=0
        c+=[i,j]
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        m = c.popleft()
                        n = c.popleft()
                        T[m][n]=s
                        if m != H-1:
                                if T[m+1][n]==0:
                                        c.append(m+1)
                                        c.append(n)
                        if m != 0:
                                if T[m-1][n]==0:
                                        c.append(m-1)
                                        c.append(n)
 
                        if n != W-1:
                                if T[m][n+1]==0:
                                        c.append(m)
                                        c.append(n+1)
                                        
                        if n != 0:
                                if T[m][n-1]==0:
                                        c.append(m)
                                        c.append(n-1)

        #print(T)
        d = max(d,s)
        T=B.copy()
        
print(d-2)

### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
n,m=map(int,input().split())
a=0
b=n*10**9
A=True
for i in range(m):
  x,y=map(int,input().split())
    a=max(a,x)
    b=min(b,y)
if b>=a:
  ans=b-a+1
  print(ans)
else:
  print(0)

### FIXED CODE ###

n,m=map(int,input().split())
a=0
b=n*10**9
for i in range(m):
  x,y=map(int,input().split())  
  a=max(a,x)
  b=min(b,y)
if b>=a:
  ans=b-a+1
  print(ans)
else:
  print(0)
def BinarySearchLowerBound(_arr, _ele): # arr is strictly increasing
    low_ind = 0
    up_ind = len(_arr) - 1
    if _arr[low_ind] >= _ele:
        return low_ind
    if _arr[up_ind] <= _ele:
        return up_ind
    found = None
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        it = BinarySearchLowerBound(D, (Li, -1))
        while it < len(D):
            if D[it][0]>= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()
aaa


### FIXED CODE ###

input = int(input())
print(input ** 3)
#_N = 5
#A = [10, -4, -8, -11, 3]
_N = int(input())
A = map(int, input().split(" "))

n = len([*filter(lambda a:a<=-1, A)])
a = [*map(abs, A)]
res = sum(a)
if n % 2 == 1:
    res -= min(a) * 2
print(res)


### FIXED CODE ###


#_N = 5
#A = [10, -4, -8, -11, 3]
_N = int(input())
A = list(map(int, input().split(" ")))

n = len(list(filter(lambda a:a<=-1, A)))
a = list(map(abs, A))
res = sum(a)
if n % 2 == 1:
    res -= min(a) * 2
print(res)
n=int(input())
r=input().split()
for i in range(r):
    r[i]=int(r[i])
s=sum(r)
m=min(r)
ma=max(r)
print(m ma s)


### FIXED CODE ###

n=int(input())
r=input().split()
for i in range(len(r)):
    r[i]=int(r[i])
s=sum(r)
m=min(r)
ma=max(r)
print(m,ma,s)
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2


if 1 in hoal:
    dp[0] = 0
    dp[1] = 1

if 2 in hoal:
    dp[1] = 0
    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1 and dp_check[i]==0:
        dp[i]=dp[i-1]+dp[i-2]

    dp[i]=dp[i]%1000000007

print(dp)
    

### FIXED CODE ###

"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N

    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

if N==1:
    if M==1:
        dp[0]=0
    else:
        dp[0]=1
    print(dp[N-1])
else:
    if dp_check[0]==1:
        dp[0]=0
        dp[1]=1
    elif dp_check[1]==1:
        dp[0]=1
        dp[1]=0
    else:
        dp[0] = 1
        dp[1] = 2
    #実際に求める
    #dp[i]<-i段までの移動方法の和
    for i in range(N):
        if i>1 and dp_check[i]==0:
            dp[i]=dp[i-1]+dp[i-2]

        dp[i]=dp[i]%1000000007

    print(dp[N-1])
#coding: utf-8
import sys

class Queue:
    class Cell:
        def __init__(self, x, y = None):
            self.data = x
            self.next = y

    def __init__(self):
        self.size = 0
        self.rear = None

    def enqueue(self, x):
        if self.size == 0:
            self.rear = Queue.Cell(x)
            self.rear.next = self.rear
        else:
            new_cell = Queue.Cell(x, self.rear.next)
            self.rear.next = new_cell
            self.rear = new_cell
        self.size += 1

    def dequeue(self):
        if self.size == 0: raise IndexError
        front = self.rear.next
        self.rear.next = front.next
        self.size -= 1
        if self.size == 0: self.rear = None
        return front.data

    def isEmpty(self):
        return self.size == 0

def generator(n1, n2, step=1):
    n = n1
    while n<n2:
        yield n
        n+= step

n, q = map(int, raw_input().split())
 
A = Queue()
for i in generator(0,n):
    name, time = raw_input().split()
    A.enqueue([name, int(time)])

stime = 0
while not A.isEmpty():
    job = A.dequeue()
    if q>=job[1]:
        stime += job[1]
        print job[0], stime
    else:
        stime += q
        job[1] -= tmp
        A.enqueue(job)

### FIXED CODE ###

import sys

class Queue:
    class Cell:
        def __init__(self, x, y = None):
            self.data = x
            self.next = y

    def __init__(self):
        self.size = 0
        self.rear = None

    def enqueue(self, x):
        if self.size == 0:
            self.rear = Queue.Cell(x)
            self.rear.next = self.rear
        else:
            new_cell = Queue.Cell(x, self.rear.next)
            self.rear.next = new_cell
            self.rear = new_cell
        self.size += 1

    def dequeue(self):
        if self.size == 0: raise IndexError
        front = self.rear.next
        self.rear.next = front.next
        self.size -= 1
        if self.size == 0: self.rear = None
        return front.data

    def isEmpty(self):
        return self.size == 0

def generator(n1, n2, step=1):
    n = n1
    while n<n2:
        yield n
        n+= step

n, q = map(int, raw_input().split())
TASK=[]
A = Queue()
for i in generator(0,n):
    name, time = raw_input().split()
    TASK.append([name, int(time)])
    A.enqueue(i)

stime = 0
while not A.isEmpty():
    p = A.dequeue()
    if q>= TASK[p][1]:
        stime += TASK[p][1]
        print TASK[p][0], stime
    else:
        stime += q
        TASK[p][1] -= q
        A.enqueue(p)
A, B = map(int, input().split())
print(max(A+B, A−B, A×B))

### FIXED CODE ###

A, B = map(int, input().split())
print(max(A+B, A-B, A*B))
n = int(input())
a = list(map(int, input().split()))

if len(a) % 2 == 0:
    print(*list(reversed(a[1::2])), *a[0::2])
else:
    print(*list(reversed(a[0::2])), *a[1::2])


### FIXED CODE ###

from collections import deque

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

d = deque()
for i in range(n):
    if i % 2 != 0:
        d.append(a[i])
    else:
        d.appendleft(a[i])

if n % 2 == 0:
    print(*list(reversed(d)))
else:
    print(*d)
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()

def f(k):
    return chr(97+k)

c = 0
i = 1
while True:
    d = c+pow(26,i)
    if c < n <= d:
        break
    c = d
    i+=1

m = n-c-1
ans = ''
for _ in range(i)
    ans = f(m%26) + ans
    m = m//26
ans = f(m%26) + ans

# ans = 'a'*(i-len(ans)) + ans

print(ans)


### FIXED CODE ###

n = int(input())
i = 1
while pow(26,i) < n:
    n -= pow(26,i)
    i += 1
ans = ''
n -= 1
for _ in range(i):
    ans += chr(ord('a') + n%26)
    n //= 26
print(ans[::-1])
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]

xl.sort(key=lambda x:x[1])

cnt = [0 for _ in range(10**7)]
ans = [0 for _ in range(n)]

for i in range(n):
    for j in range(xl[i][0] - xl[i][1] + 1, xl[i][0] + xl[i][1]):
        if cnt[j] == 0:
            cnt[j] = 1
        else:
            break
        if j == xl[i][0] + xl[i][1]-1:
            ans[i] = 1

print(sum(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl2 = sorted([[x + l, x - l] for x, l in xl])

ans = 0
mr = xl2[0][1]
for r, l in xl2:
    if l >= mr:
        ans += 1
        mr = r
print(ans)
import sys
import operator

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

a = [int(x) for x in sys.stdin.readline().rstrip().split()]
a.sort()

cards = [[int(x) for x in sys.stdin.readline().rstrip().split()] for _ in range(m)]
cards.sort(key=operator.itemgetter(1), reverse=True)

a_idx = 0
a_len = len(a)

for b, c in cards:
    if c <= a[a_idx] or a_idx == a_len:
        break
    for b_idx in range(b):
        if c <= a[a_idx] or a_idx == a_len:
            break
        else:
            a[a_idx] = c
            a_idx += 1

print(a)

### FIXED CODE ###

import sys
import operator

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

a = [int(x) for x in sys.stdin.readline().rstrip().split()]
a.sort()

cards = [[int(x) for x in sys.stdin.readline().rstrip().split()] for _ in range(m)]
cards.sort(key=operator.itemgetter(1), reverse=True)

a_idx = 0
a_len = len(a)

for i in range(len(cards)):
    for j in range(cards[i][0]):
        if a_idx == a_len or a[a_idx] >= cards[i][1]:
            break
        else:
            a[a_idx] = cards[i][1]
            a_idx += 1

print(sum(a))
import math
import sys
a,b,c = int(input().split())
if a < c and c < b:
    print("Yes")
elif b < c and c < a:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import math
import sys
a,b,c = map(int,input().split())
if a < c and c < b:
    print("Yes")
elif a > c and c > b:
    print("Yes")
else:
    print("No")
N, K = int(input())
A = list(map(int, input().split()))

A_neg = []
A_pos = []

for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])

A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

ans = 1

if K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= (A_neg[-i]%1000000007)
    ans %= 1000000007
  print(-ans)

else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  for i in range(len(A_pos)//2):
    buf.append(A_pos[2*i]*A_pos[2*i+1])
  for i in range(len(A_neg)//2):
    buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)

### FIXED CODE ###

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

A_neg = []
A_pos = []

for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])

A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

ans = 1

if K == N:
  for i in range(N):
    ans *= (A[i]%1000000007)
    ans %= 1000000007
  print(ans)

elif K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= ((-A_neg[-i])%1000000007)
    ans %= 1000000007
  print(ans)

else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  for i in range(len(A_pos)//2):
    buf.append(A_pos[2*i]*A_pos[2*i+1])
  for i in range(len(A_neg)//2):
    buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)
# 入力 : 数字2つ
N, A = map(int, input().split())

# 出力　N^2-A
print(N*N-A)


### FIXED CODE ###

# 入力 : 数字2つ
N = int(input())
A = int(input())

# 出力　N^2-A
ans = N * N - A
print(ans)
print(-(-eval(input().replace(" ","+")//2))

### FIXED CODE ###

print(-(-eval(input().replace(" ","+"))//2))
# C - Special Trains
import math

N = int(raw_input())
C, S, F = [0]*(N-1), [0]*(N-1), [0]*(N-1)
for i in range(N-1):
  C[i], S[i], F[i] = map(int, raw_input().split())
result = [0] * N

for station in range(N):
  now = station
  time = 0
  while now != N-1:
    time = S[now] + C[now] if time <= S[now] else int(math.floor(time/F[now])*F[now] + C[now]
    now += 1
  result[station] = time

for i in result: print i

### FIXED CODE ###

# C - Special Trains
import math

N = int(raw_input())
C, S, F = [0]*(N-1), [0]*(N-1), [0]*(N-1)
for i in range(N-1):
  C[i], S[i], F[i] = map(int, raw_input().split())
result = [0] * N

for station in range(N):
  now = station
  time = 0
  while now != N-1:
    time = S[now] + C[now] if time <= S[now] else int(math.ceil(float(time)/float(F[now])))*F[now] + C[now]
    now += 1
  result[station] = time

for i in result: print i
def lcs(x,y):
    x = " " + x
    y = " " + y    
    c = [[0]*(len(x)+1)]*(len(y)+1)
    for i in xrange (len(x)):
        for j in xrange (len(y)):
            if i >= 1 and j >= 1 and x[i] == y[j]:
                c[i][j] = c[i-1][j-1] + 1
            elif i >= 1 and j >= 1 and x[i] != y[j]:
                c[i][j] = max(c[i][j-1],c[i-1][j])
    return max(max(c))

n = input()

for i in xrange (n):

 x = raw_input()
 y = raw_input()

 print lcs(x,y)

### FIXED CODE ###

def lcs():
    x, y = raw_input(), raw_input()
    b1 = [0 for k in range(len(y)+1)]
    for i in xrange(len(x)):
        a = x[i]
        b2 = b1 + []
        for j in xrange(len(y)):
            if a == y[j]:
                b1[j+1] = b2[j] + 1
            elif b1[j+1] < b1[j]:
                b1[j+1] = b1[j]
    print max(b1)
 
n = input()
for i in xrange(n):
    lcs()
a = []
while True:
	b = list(map(int,input().split()))
	if b[0] == "0" and b[1]=="0":
		break
	b.sort()
	a.append(b)


for i in a:
	print(i[0],i[1])

### FIXED CODE ###

a = []
while True:
	b = list(map(int,input().split()))
	if b[0] == 0 and b[1]==0:
		break
	b.sort()
	a.append(b)

for i in a:
	print(i[0],i[1])
#input
N, M = map(int, input().split())
x = []
y = []
z = []
for i in range(N):
    x_temp, y_temp, z_temp = map(int, input().split())
    x.append(x_temp)
    y.append(y_temp)
    z.append(z_temp)

#output
#+++
a1 = [p+q+r for p, q, r in zip(x, y, z)]
a1.sort(reverse = True)
b1 = np.sum(a1[:M])

#++-
a2 = [p+q-r for p, q, r in zip(x, y, z)]
a2.sort(reverse = True)
b2 = np.sum(a2[:M])

#+-+
a3 = [p-q+r for p, q, r in zip(x, y, z)]
a3.sort(reverse = True)
b3 = np.sum(a3[:M])

#-++
a4 = [-p+q+r for p, q, r in zip(x, y, z)]
a4.sort(reverse = True)
b4 = np.sum(a4[:M])

#+--
a5 = [p-q-r for p, q, r in zip(x, y, z)]
a5.sort(reverse = True)
b5 = np.sum(a5[:M])

#-+-
a6 = [-p+q-r for p, q, r in zip(x, y, z)]
a6.sort(reverse = True)
b6 = np.sum(a6[:M])

#--+
a7 = [-p-q+r for p, q, r in zip(x, y, z)]
a7.sort(reverse = True)
b7 = np.sum(a7[:M])

#---
a8 = [-p-q-r for p, q, r in zip(x, y, z)]
a8.sort(reverse = True)
b8 = np.sum(a8[:M])

print(max(b1, b2, b3, b4, b5, b6, b7, b8))

### FIXED CODE ###

#input
N, M = map(int, input().split())
x = []
y = []
z = []
for i in range(N):
    x_temp, y_temp, z_temp = map(int, input().split())
    x.append(x_temp)
    y.append(y_temp)
    z.append(z_temp)

#output
#+++
a1 = [p+q+r for p, q, r in zip(x, y, z)]
a1.sort(reverse = True)
b1 = sum(a1[:M])

#++-
a2 = [p+q-r for p, q, r in zip(x, y, z)]
a2.sort(reverse = True)
b2 = sum(a2[:M])

#+-+
a3 = [p-q+r for p, q, r in zip(x, y, z)]
a3.sort(reverse = True)
b3 = sum(a3[:M])

#-++
a4 = [-p+q+r for p, q, r in zip(x, y, z)]
a4.sort(reverse = True)
b4 = sum(a4[:M])

#+--
a5 = [p-q-r for p, q, r in zip(x, y, z)]
a5.sort(reverse = True)
b5 = sum(a5[:M])

#-+-
a6 = [-p+q-r for p, q, r in zip(x, y, z)]
a6.sort(reverse = True)
b6 = sum(a6[:M])

#--+
a7 = [-p-q+r for p, q, r in zip(x, y, z)]
a7.sort(reverse = True)
b7 = sum(a7[:M])

#---
a8 = [-p-q-r for p, q, r in zip(x, y, z)]
a8.sort(reverse = True)
b8 = sum(a8[:M])

print(max(b1, b2, b3, b4, b5, b6, b7, b8))
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
n = int(stdin.readline())
dll = []
while n:
    n -= 1
    cmd = stdin.readline().rstrip()
    if cmd.startswith('insert '):
        dll.insert(0, cmd[7:])
    elif cmd.startswith('delete '):
        dll.remove(cmd[7:])
    elif cmd.startswith('deleteFirst'):
        del dll[0]
    elif cmd.startswith('deleteLast'):
        del dll[-1]
print(*dll)

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
from collections import deque

n = int(stdin.readline())
dll = deque()
fcode = ord('F')
lcode = ord('L')
while n:
    n -= 1
    cmd = stdin.readline().rstrip()
    if cmd.startswith('i'):
        dll.appendleft(int(cmd[7:]))
    elif cmd.startswith('d'):
        c = ord(cmd[6])
        if c == fcode:
            dll.popleft()
        elif c == lcode:
            dll.pop()
        else:
            try:
                dll.remove(int(cmd[7:]))
            except ValueError:
                pass
print(*dll)
N,K,X,Y = map(int,input().split())

result = 0
if N > K:
  result = K * X + (N - K) * Y
else:
  result = N * X

print(result)


### FIXED CODE ###

N = int(input())
K = int(input())
X = int(input())
Y = int(input())
if(N<=K):
  print(X*N)
else:
  print(X*K+(N-K)*Y)
import numpy as np
X = int(input())
ans = 1
for b in range(int(np.ceil(np.sqrt(X)))):
    p = 0
    while np.pow(b, p) <= X:
        p += 1
    p -= 1
    ans = max(ans, np.pow(b, p))
print(ans)


### FIXED CODE ###

import numpy as np
X = int(input())
ans = 1
for b in range(2, 1+int(np.ceil(np.sqrt(X)))):
    p = 0
    while np.power(b, p) <= X:
        p += 1
    p -= 1
    ans = max(ans, np.power(b, p))
print(ans)