Harryxun/stf_run huggingface dataset:
N = int(input())
graph = [[] for  _ in range(N)]
now = 0
for _ in range(N-1):
    x,y,w = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append((y,w))
    graph[y].append((x,w))
    now = x
    
vis = [0 for _ in range(N)]

even = set()
odd = set()

def dfs(now):
 #   print(now)
    for nv in graph[now]:
        if vis[nv[0]]: continue
        if nv[1] % 2 == 0:
            if now in even:
                even.add(nv[0])
            else:
                odd.add(nv[0])
        else:
            if now in even:
                odd.add(nv[0])
            else:
                even.add(nv[0])
        vis[nv[0]] = 1
        dfs(nv[0])
vis[x] = 1
even.add(x)
dfs(x)

for i in range(N):
    if i in even:
        print(1)
    else:
        print(0)



### FIXED CODE ###

N = int(input())
graph = [[] for  _ in range(N)]
now = 0
for _ in range(N-1):
    x,y,w = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append((y,w))
    graph[y].append((x,w))
    now = x
    
vis = [0 for _ in range(N)]

even = set()
odd = set()
import sys
sys.setrecursionlimit(10000000)


def dfs(now):
    #print(now)
    for nv in graph[now]:
        if vis[nv[0]]: continue
        if nv[1] % 2 == 0:
            if now in even:
                even.add(nv[0])
            else:
                odd.add(nv[0])
        else:
            if now in even:
                odd.add(nv[0])
            else:
                even.add(nv[0])
        vis[nv[0]] = 1
        dfs(nv[0])
vis[x] = 1
even.add(x)
dfs(x)

for i in range(N):
    if i in even:
        print(1)
    else:
        print(0)
from bisect import bisect

N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
dp[0] = -INF
ans = [0] * N

def dfs(u, p=-1):
    # Update dp
    i = bisect(dp, A[u])
    old = dp[i]
    dp[i] = A[u]

    # Calc ans
    ans[u] = i
    if p != -1:
        ans[u] = max(ans[u], ans[p])

    # Go to next
    for v in graph[u]:
        if v == p:
            continue
        dfs(v, u)

    # Restore
    dp[i] = old

dfs(0)
print(*ans)


### FIXED CODE ###

from bisect import bisect_left
from collections import deque

N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = max(i, ans[p])

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

print(*ans)
def main():
    n = int(input())
    h = [list(map(int, input().split()))]
    ans = h[0]
    for i in range(n-1):
        if h[i+1] > h[i]:
            ans += h[i + 1]-h[i]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    h = list(map(int, input().split()))
    ans = h[0]
    for i in range(n-1):
        if h[i+1] > h[i]:
            ans += h[i + 1]-h[i]
    print(ans)


if __name__ == '__main__':
    main()
from __future__ import print_function
import numpy as np
import sys

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

cnt=0
S=list(input())
# eprint(S)

L=list()
L.append(S.pop())
while len(S)!=0:
    if S[-1]==L[-1]: # SのfrontとLのfrontが0と0とか一致しちゃった時だから，消せない．次のSのfrontを見よう 
        L.append( S.pop() )
        # eprint("S: " + str(S))
        # eprint("L: " + str(L))
    else: # SのfrontとLのfrontが0と1となっている場合．消す．
        S.pop()
        L.pop()
        if L==[] and S!=[]:
            L.append(S.pop())
        cnt=cnt+2
        # eprint("S: " + str(S))
        # eprint("L: " + str(L))

print(cnt)

#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#


### FIXED CODE ###

from __future__ import print_function
import numpy as np
import sys

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

cnt=0
S=list(input())
# eprint(S)

L=list()
L.append(S.pop())
while len(S)!=0:
    if S[-1]==L[-1]: # SのfrontとLのfrontが0と0とか一致しちゃった時だから，消せない．次のSのfrontを見よう 
        L.append(S.pop())
        # eprint("S: " + str(S))
        # eprint("L: " + str(L))
    else: # SのfrontとLのfrontが0と1となっている場合．消す．
        S.pop()
        L.pop()
        if L==[] and S!=[]:
            L.append(S.pop())
        cnt=cnt+2
        # eprint("S: " + str(S))
        # eprint("L: " + str(L))

print(cnt)

#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
def hoge(lst,i):
    if lst[i]==lst[i+1]:
        return hoge(lst,i+1)
    if lst[i]>lst[i+1]:return True
    if lst[i]<lst[i+1]:return False

N = int(input())
H = list(map(int,input().split()))
det=0

for i in range(N-1):
    if H[i]-1>H[i+1]:
        det+=1
        print("No")
        break
    if i+2<=N-1:
        if H[i]>H[i+1] and H[i+1] > H[i+2]:
            det+=1
            print("No")
            break
        if H[i]>H[i+1] and hoge(H,i+1):
            det+=1
            print("No")
            break
if det==0:print("Yes")

### FIXED CODE ###


def hoge(lst,i):
    if lst[i]==lst[i+1] and len(lst)>i+2:
        return hoge(lst,i+1)
    if lst[i]>lst[i+1]:return True
    if lst[i]<lst[i+1]:return False

N = int(input())
H = list(map(int,input().split()))
det=0

for i in range(N-1):
    if H[i]-1>H[i+1]:
        det+=1
        print("No")
        break
    if i+2<=N-1:
        if H[i]>H[i+1] and H[i+1] > H[i+2]:
            det+=1
            print("No")
            break
        if H[i]>H[i+1] and hoge(H,i+1):
            det+=1
            print("No")
            break
if det==0:print("Yes")
from collections import Counter
from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
same, diff, zero_a, zero_b = 0, 0, 0, 0
same_cnt = Counter()
diff_cnt = Counter()

for _ in range(n):
    a, b = map(int, input().split())
    x = gcd(a, b)
    a, b = a // x, b // x
    if a == b == 0:
        continue
    elif a == 0:
        zero_a += 1
    elif b == 0:
        zero_b += 1
    elif a * b > 0:
        same += 1
        same_cnt[(abs(a), abs(b))] += 1
    else:
        diff += 1
        diff_cnt[(abs(a), -abs(b))] += 1


ans = 1
mod = 10 ** 9 + 7

for (a, b) in diff_cnt.keys():
    s = same_cnt[(-b, a)]
    d = diff_cnt[(a, b)]
    if s > 0:
        same -= s
        diff -= d
        ans = ans * (pow(2, s, mod) + pow(2, d, mod) - 1) % mod

ans = ans * pow(2, same + diff, mod) % mod

ans = ans * (pow(2, zero_a, mod) + pow(2, zero_b, mod) - 1) - 1
print(ans % mod)

### FIXED CODE ###

from collections import Counter
from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
same, diff, zero_a, zero_b, zero_zero = 0, 0, 0, 0, 0
same_cnt = Counter()
diff_cnt = Counter()

for i in range(n):
    a, b = map(int, input().split())
    if a == b == 0:
        zero_zero += 1
    elif a == 0:
        zero_a += 1
    elif b == 0:
        zero_b += 1
    elif a * b > 0:
        x = gcd(a, b)
        a, b = a // x, b // x
        same += 1
        same_cnt[(abs(a), abs(b))] += 1
    else:
        x = gcd(a, b)
        a, b = a // x, b // x
        diff += 1
        diff_cnt[(abs(a), -abs(b))] += 1


ans = 1
mod = 10 ** 9 + 7

for (a, b) in diff_cnt.keys():
    s = same_cnt[(-b, a)]
    d = diff_cnt[(a, b)]
    if s > 0:
        same -= s
        diff -= d
        ans = ans * (pow(2, s, mod) + pow(2, d, mod) - 1) % mod

ans = ans * pow(2, same + diff, mod) % mod

ans = ans * (pow(2, zero_a, mod) + pow(2, zero_b, mod) - 1) - 1
print((ans + zero_zero) % mod)
S = input()
S_list = [S]
if S_list[1] == S_list[2] == S_list[3] :
  print("No")
else :
  print("Yes")
	

### FIXED CODE ###

S = input()
if S[0] == S[1] == S[2] :
  print("No")
else :
  print("Yes")
import collections

cnt = 0

N = int(input())
string_counters = []

cnt = dict()
for i in range(N):
    string = collections.Counter(input())
    if string not in string_counters:
        string_counters.append(string)
        cnt[i] = 1
    else :
        cnt[string_counters.index(string)] += 1

output = 0
for k, v in cnt.items():
    output += v - 1
print(output)

### FIXED CODE ###

N = int(input())
cnt = dict()
output = 0

for i in range(N):
    string = ''.join(sorted(input()))
    cnt.setdefault(string, 0)
    output += cnt[string]
    cnt[string] += 1

print(output)
import math

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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(a, b))


### FIXED CODE ###

#バージョン的にfractionsにある
import fractions

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

print((a * b) // fractions.gcd(a, b))
MOD = 10**9+7 # p=MOD
n, a, b = map(int, input().split())
whole = pow(2, n, MOD)-1 # 2^n-1(mod p)を計算。
# nCaの計算
comb1=1
for i in range(n-a+1,n+1): # n*(n-1)*(n-2)*...*(n-a+1)(mod p)を計算
  comb1 *= i
  comb1 %= mod
for i in range(1,a+1): # 1/a!(mod p)を計算 フェルマーの小定理:1/a = a^p-2(mod p)を利用
  comb1 *= pow(i,mod-2,mod)
  comb1 %= mod
comb2=1
for i in range(n-b+1,n+1): # n*(n-1)*(n-2)*...*(n-b+1)(mod p)を計算
  comb2 *= i
  comb2 %= mod
for i in range(1,b+1):
  comb2 *= pow(i,mod-2,mod)
  comb2 %= mod
ans -= (comb1+comb2)
ans %= mod
print(ans)

### FIXED CODE ###

mod = 10**9+7 
n, a, b = map(int, input().split())
whole = pow(2, n, mod)-1 # 2^n-1(mod p)を計算。
# nCaの計算
comb1=1
for i in range(n-a+1,n+1): # n*(n-1)*(n-2)*...*(n-a+1)(mod p)を計算
  comb1 *= i
  comb1 %= mod
for i in range(1,a+1): # 1/a!(mod p)を計算 フェルマーの小定理:1/a = a^p-2(mod p)を利用
  comb1 *= pow(i,mod-2,mod)
  comb1 %= mod
comb2=1
for i in range(n-b+1,n+1): # n*(n-1)*(n-2)*...*(n-b+1)(mod p)を計算
  comb2 *= i
  comb2 %= mod
for i in range(1,b+1):
  comb2 *= pow(i,mod-2,mod)
  comb2 %= mod
whole -= (comb1+comb2)
whole %= mod
print(whole)
H , W = input().split()
W = (W)
H = int(H)
ans = int(0)

#Wが偶数なら(W//2)*H
#W.Hが奇数なら((W+1)//2)*((H+1)//2) + ((W - 1)//2*(H - 1)//2)
#Wが奇数Hが偶数(W+1)//2*(H//2) + ((W - 1)//2)*(H//2)

if(W == H == 1):
    ans =1
elif(W%2 == 0):
    ans = (W//2)*H
elif(W%2 == 1 and H%2==1):
    ans = (((W+1)//2)*((H+1)//2)) + (((W - 1)//2)*((H - 1)//2))
elif(W%2 == 1 and H%2 ==0):
    ans = (((W+1)//2)*(H//2)) + (((W - 1)//2)*(H//2))
print(ans)

### FIXED CODE ###


H , W = input().split()
W = int(W)
H = int(H)
ans = int(0)

#Wが偶数なら(W//2)*H
#W.Hが奇数なら((W+1)//2)*((H+1)//2) + ((W - 1)//2*(H - 1)//2)
#Wが奇数Hが偶数(W+1)//2*(H//2) + ((W - 1)//2)*(H//2)

if(W == 1 or H == 1):
    ans = 1
elif(W%2 == 0):
    ans = (W//2)*H
elif(W%2 == 1 and H%2==1):
    ans = (((W+1)//2)*((H+1)//2)) + (((W - 1)//2)*((H - 1)//2))
elif(W%2 == 1 and H%2 ==0):
    ans = (((W+1)//2)*(H//2)) + (((W - 1)//2)*(H//2))
print(ans)
N = int(input())

for i in range(N):
  S.append(str(input()))

cnt_ar = list(set(S))
cnt_ar.sort()

length = len(cnt_ar)

ar = [0]*length

for i in range(length):
  ar[i] = S.count(cnt_ar[i])

max_num = max(ar)

for i in range(length):
  if ar[i] == max_num:
    print(cnt_ar[i])


### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
    S = input()
    if S in d:
        d[S] += 1
    else:
        d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
    print(s)
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
if 1 in a and 2 in a:
    print(0)
    exit()
ans = 1
k = 0
if a[-1]!=n:
    a.append(n)

mod = 10**9+7
max = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, max + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
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

for i in a:
    if i+1 in a:
        print(0)
        exit()
    else:
        if i-k<=2:
            m = 1
        elif i-k==3:
            m = 2
        else:
            m = 0
            f = i-k-1
            for j in range(f//2,-1,-1):
                m += cmb(f-j,j,mod)
        ans *= m
        ans %= mod
        k = i
print(ans%mod)

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
for i in range(2,n+1):
    if i not in a:
        dp[i] = dp[i-1]+dp[i-2]
print(dp[-1]%mod)
# DP(配るDP)
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')] * N
dp[0] = 0
for i in range(N - 1):
  for j in range(K):
    if i + j > N - 1:
      break
    dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N -1)]


### FIXED CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
cost = [0] * n
cost[1] = abs(h[1] - h[0])
for i in range(1, n):
  cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
print(cost[n - 1])
N, T = map(int, input().split())
r = [tuple(map(int, input().split())) for _ in range(n)]
f = [(c, t) for c, t in r if t <= T]
print(min(f, key=lambda x: x[0]))

### FIXED CODE ###

N, T = map(int, input().split())
r = [tuple(map(int, input().split())) for _ in range(N)]
f = [(c, t) for c, t in r if t <= T]
if len(f)==0:
  print('TLE')
else:
  print(min(f, key=lambda x: x[0])[0])
R = int(input())
G = int(input())
print(2G - R)

### FIXED CODE ###

R = int(input())
G = int(input())
print(2*G-R)
# -*- coding: utf-8 -*-
"""
Created on Sun May 20 20:55:50 2018
AGC024B
@author: maezawa
"""

n = int(input())
q = [None for _ in range(n)]
for i in range(n):
    p = int(input())
    q[p-1] = i+1

max_cnt = 0
cnt = 1
qpre = q[0]
 
for i in range(1,n):
    if q[i] > qpre:
        cnt += 1
    else:
        if max_cnt < cnt:
            max_cnt = cnt
        cnt = 1
    qpre = q[i]
if max_cnt < cnt:
    max_cnt = cnt

print(n-max_cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 20 20:55:50 2018
AGC024A
@author: maezawa
"""

a, b, c, k = list(map(int, input().split()))
if a-b > 10**18 or b-a > 10**18:
    print('Unfair')
elif k%2 == 0:
    print(a-b)
else:
    print(b-a)
a, b, c = map(int,input().split())
d = 0
for i in(range(a,b+1))
 if c % i == 0:
  d+=1
 else:
  pass
print(d)

### FIXED CODE ###

a, b, c = map(int,input().split())
d = 0
for i in(range(a,b+1)):
 if c % i == 0:
  d+=1
print(d)
import numpy as np
n,m,c = map(int,input().split())
b = np.array(list(map(int,input().split())))
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
a = np.array(a)
ans = list(a @ b)
cnt = 0
for i in range(n):
    if ans[i] + c > 0: cnt += 1
print(cnt)

### FIXED CODE ###

n,m,c = map(int,input().split())
b = list(map(int,input().split()))
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
cnt = 0
for i in range(n):
    mat = 0
    for j in range(m):
        mat += a[i][j]*b[j]
    if mat + c > 0: cnt += 1
print(cnt)
from collections import Counter
N = int(input())
dic = Counter()
for _ in range(N):
  dic[input()] += 1
M = int(input())
for _ in range(N):
  dic[input()] -= 1
 
if dic.most_common():
  freq = dic.most_common()[0][1]
  print(max(freq, 0))
else:
  print(0)

### FIXED CODE ###

from collections import Counter
N = int(input())
dic = Counter()
for _ in range(N):
  dic[input()] += 1
M = int(input())
for _ in range(M):
  dic[input()] -= 1
 
if dic.most_common():
  freq = dic.most_common()[0][1]
  print(max(freq, 0))
else:
  print(0)
H, W = map(int, input().split())
a = [[x for x in input()] for _ in range(H)]

ans = []
ans.append(['#'*(W+2)])
for row in a:
    row.insert(0, '#')
    row.append('#')
    ans.append(row)
ans.append(['#'*(W+2)])
for i in range(W+2):
    print(*ans[i], sep='')

### FIXED CODE ###

H, W = map(int, input().split())
a = [[x for x in input()] for _ in range(H)]

ans = []
ans.append(['#'*(W+2)])
for row in a:
    row.insert(0, '#')
    row.append('#')
    ans.append(row)
ans.append(['#'*(W+2)])
for i in range(H+2):
    print(*ans[i], sep='')
inf = 10**9
 
S = int(input())
 
if S == 10 ** 18:
    print(0, 0, inf, 0, M, inf)
else:
    S1 = S // inf + 1
    S2 = inf - (S % inf)
 
    print(0, 0, S1, 1, S2, inf)

### FIXED CODE ###

inf = 10**9
 
S = int(input())
 
if S == 10 ** 18:
    print(0, 0, inf, 0, inf, inf)
else:
    S1 = S // inf + 1
    S2 = inf - (S % inf)
 
    print(0, 0, S1, 1, S2, inf)
from functools import reduce
import fractions

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

sum = 0

for num in As:
    sum = sum + cand / num

print(int(sum %  (10 ** 9 + 7)))


### FIXED CODE ###

from functools import reduce
import fractions

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

sum = 0

for num in As:
    sum = sum + cand // num

print(sum % int(1e9+7) )
# E - Colorful Blocks
import sys
sys.setrecursionlimit(10**7)
MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD)
ans = 0
tmp = pow(M-1,N-1,MOD)
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
print(ans)

### FIXED CODE ###

# E - Colorful Blocks
import sys
sys.setrecursionlimit(10**8)

MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD) if M>1 else 0
ans = 0
tmp = pow(M-1,N-1,MOD) if M>1 else 0
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
if M==1 and K==N-1:
    ans += 1
print(ans)
X = input()
X = list(X)
prev = ""
for i in range(len(X) - 1):
    if X[i] + X[i + 1] == "ST":
        a = X.pop(i + 1)
        b = X.pop(i)
        X = [b,a].extend(X)

for i in range(0, len(X)):
    if X[len(X) - (i+1)] == "T":
        print(i * 2)
        break

### FIXED CODE ###

X = input()
Y = []
for i in X:
    Y.append(i)
    if len(Y) > 1:
        if Y[-2] + Y[-1] == "ST":
            Y.pop()
            Y.pop()
print(len(Y))
S, T ＝ map(str, input().split())
A, B ＝ map(int, input().split())
U ＝ input()

if S ＝＝ U：
    A ＝ A － 1
else：
    B ＝ B － 1
print(str(A)＋str(B))

### FIXED CODE ###

S, T = map(str, input().split())
A, B = map(int, input().split())
U = input()

if S == U:
    A = A - 1 
else:
    B = B - 1 

print(str(A) + " " + str(B))
N,K = map(int,input().split())
x = list(map(int,input().split()))

xp = []
xn = []
for i in x:
    if i >= 0:
        xp += [i]
    else:
        xn += [abs(i)]
    
xn.sort()
pl = len(xp)
pn = len(xn)

ans = 2 ** 31 - 1

for i in range(K):
    if i < pl and K-2-i < pn :
        if K-2-i >= 0:
            tmp = xp[i] * 2 + xn[K-2-i]
        else:
            tmp = xp[i] 
    ans = min(ans,tmp)


for i in range(K):
    if i < pn and K-2-i < pl and K-2-i >= 0:        
        if K-2-i >= 0:
            tmp = xn[i] * 2 + xp[K-2-i]
        else:
            tmp = xn[i]
        
    ans = min(ans,tmp)

print(ans)

### FIXED CODE ###

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

xp = []
xn = []
for i in x:
    if i >= 0:
        xp += [i]
    else:
        xn += [abs(i)]
    
xn.sort()
pl = len(xp)
pn = len(xn)

ans = 2 ** 30

for i in range(pl):
    if K-2-i < pn:
        if K-2-i >= 0:
            tmp = xp[i] * 2 + xn[K-2-i]
        elif i == K-1:
            tmp = xp[i] 
    else:
        continue
    ans = min(ans,tmp)


for i in range(pn):
    if K-2-i < pl:        
        if K-2-i >= 0:
            tmp = xn[i] * 2 + xp[K-2-i]
        elif i == K-1:
            tmp = xn[i]
    else:
        continue
    ans = min(ans,tmp)

print(ans)
a,_,b=input();s=int(a)+int(b);print(s//2+int(bin(s)[-1]))

### FIXED CODE ###

s=sum(map(int,input().split()));print(s//2+int(bin(s)[-1]))
from collections import Counter
M=10**7
_,*l=map(int,open(0).read().split())
d=[1]*(sorted(M))
C=Counter(l)
s=0
for a,b in C.items():
    if b != 1:d[a]=0
    elif d[a]:s+=1
    for j in range(a,M,a):d[j]=0
print(s)


### FIXED CODE ###

from collections import Counter
def i(): return int(input())
def l(): return list(map(int,input().split()))
N = i();A = l();A.sort();dp = [1]*(10**6+1);C = Counter(A);ans = 0
for a,b in C.items():
    if b != 1:dp[a] = 0
    elif dp[a]:ans += 1
    for j in range(a,10**6+1,a):dp[j] = 0
print(ans)
S = input()
K = int(input())
List = []
ans = 1
for i in range(len(S)):
    List.append(int(S[i]))
for j in range(len(S)):
    if List[j] != 1:
        ans = List[j]
        num = j+1
        break
if K < num:
    print(1)
else:
    print(ans)

### FIXED CODE ###

S = input()
K = int(input())
List = []
ans = 1
num = 0
for i in range(len(S)):
    List.append(int(S[i]))
for j in range(len(S)):
    if List[j] != 1:
        ans = List[j]
        num = j+1
        break
if K < num:
    print(1)
else:
    print(ans)
a,b,c,k = map(int,input().split())

ans=0

if a>= k:
  print(k)

elif a+b >= k:
  print(a)
  
else:
  print(a-((k-a-b))


### FIXED CODE ###

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

ans=0

if a>= k:
  print(k)

elif a+b >= k:
  print(a)
  
else:
  print(a-((k-a-b)))
s=list(map(int,input().split()))
c=0
if s[0]==1:
    c+=1
if s[1]==1:
    c+=1
if s[2]==1:
    c+=1

print(c)


### FIXED CODE ###

import re

s=re.findall(r"1",input())
print(len(s))
#!/usr/bin/env python3
import sys, math, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0


ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL, AR = A[:n], A[2*n:]
al,ar=AL.copy(),AR.copy()
AN = A[n:2*n]
LS, RS = sum(AL), sum(AR)
AR = list(map(lambda ddd: -ddd, AR))
heapq.heapify(AL)
heapq.heapify(AR)
tmp=LS
ANSR=[0]*n
ANSL=[0]*n

for i in range(n):
    if AN[i]-AL[0] >0:
        LS = LS-heapq.heappop(AL)+AN[i]
        heapq.heappush(AL,AN[i])
    ANSL[i] = LS

LS=tmp
for j in range(n-1,-1,-1):
    if 0 < -AR[0]-AN[j]:
        RS = RS+heapq.heappop(AR)+AN[j]
        heapq.heappush(AR,-AN[j])
    ANSR[j] = RS
ANSR=ANSR+[sum(ar)]
ANSL=[sum(al)]+ANSL
for i in range(n+1):
    ans=max(ans,ANSL[i]-ANSR[i])
print(ans)
# print(ANSL,ANSR)

### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, heapq,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0


ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL, AR = A[:n], A[2*n:]
al,ar=copy.copy(AL),copy.copy(AR)
AN = A[n:2*n]
LS, RS = sum(AL), sum(AR)
AR = list(map(lambda ddd: -ddd, AR))
heapq.heapify(AL)
heapq.heapify(AR)
tmp=LS
ANSR=[0]*n
ANSL=[0]*n

for i in range(n):
    if AN[i]-AL[0] >0:
        LS = LS-heapq.heappop(AL)+AN[i]
        heapq.heappush(AL,AN[i])
    ANSL[i] = LS

LS=tmp
for j in range(n-1,-1,-1):
    if 0 < -AR[0]-AN[j]:
        RS = RS+heapq.heappop(AR)+AN[j]
        heapq.heappush(AR,-AN[j])
    ANSR[j] = RS
ANSR=ANSR+[sum(ar)]
ANSL=[sum(al)]+ANSL
for i in range(n+1):
    ans=max(ans,ANSL[i]-ANSR[i])
print(ans)
# print(ANSL,ANSR)