Harryxun/stf_run huggingface dataset:
import sys


def acinput():
    return list(map(int, input().split(" ")))


class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x+y, default=0):
        self.size = 2**(size-1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                # モノイドでは可換律は保証されていないので演算の方向に注意
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


def acinput():
    return list(map(int, input()[:-1].split(" ")))


N, K = acinput()

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

st = SegmentTree(30000+10, f=max)

res = 0
for sa in A:
    L = max(sa-K, 0)
    R = min(sa+K+1, 300000)

    tmp = st.query(L, R+1)+1
    st.update(sa, tmp)
    res = max(tmp, res)

print(res)


### FIXED CODE ###



class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x+y, default=0):
        self.size = 2**(size-1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                # モノイドでは可換律は保証されていないので演算の方向に注意
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


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

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

st = SegmentTree(300000+10, f=max)

res = 0
for sa in A:
    L = max(sa-K, 0)
    R = min(sa+K, 300001)

    tmp = st.query(L, R+1)+1
    st.update(sa, tmp)
    res = max(tmp, res)

print(res)
N = input()
A = [int(a) for a in input().split()]

ans = 1

if 0 in A:
    print(0)
    exit():

for i in range(len(A)):
    if ans > 10 ** 18:
        print(-1)
        exit()
    ans *= A[i]


if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in A:
    print(0)
    exit()

for i in range(len(A)):
    if ans > 10 ** 18:
        print(-1)
        exit()
    ans *= A[i]


if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)
n,m=map(int,input().split())

if n>=3 and m>=3:
  a=n*m
  b=n*2+m*2-4
  ans=a-b
elif n==1 and b==1:
  ans=1
elif n==1 or m==1:
  a=n*m
  b=2
  ans=a-b
elif n==2 or m==2:
  ans=0
  
print(ans)


### FIXED CODE ###

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

if n>=3 and m>=3:
  a=n*m
  b=n*2+m*2-4
  ans=a-b
elif n==1 and m==1:
  ans=1
elif n==1 or m==1:
  a=n*m
  b=2
  ans=a-b
elif n==2 or m==2:
  ans=0
  
print(ans)
a, b = int(input())

d = a * b
if d % 2 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

d = a * b
if d % 2 == 0:
    print('No')
else:
    print('Yes')
from collections import defaultdict

def per(a, b):
    re = 1
    for i in range(b):
        re *= a - i
    return re

def dfs(i, oi):
    cnt_ko = len(to[i])
    if i == 1:
        re = k * per(k - 1, cnt_ko)
    elif cnt_ko == 1:
        return 1
    else:
        re = per(k - 2, cnt_ko - 1)
    for ki in to[i]:
        if ki == oi: continue
        re *= dfs(ki, i)
    return re%md

md = 10 ** 9 + 7
n, k = map(int, input().split())
to = defaultdict(list)
for _ in range(n - 1):
    a, b = map(int, input().split())
    to[a] += [b]
    to[b] += [a]
print(dfs(1, 0))


### FIXED CODE ###

from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)

def per(a, b):
    t = (a, b)
    if t in memo:
        return memo[t]
    re = 1
    for i in range(b):
        re = re * (a - i) % md
    memo[t] = re
    return re

def dfs(i, oi):
    cnt_ko = len(to[i])
    if i == 1:
        re = k * per(k - 1, cnt_ko) % md
    elif cnt_ko == 1:
        return 1
    else:
        re = per(k - 2, cnt_ko - 1)
    for ki in to[i]:
        if ki == oi: continue
        re = re * dfs(ki, i) % md
    return re

md = 10 ** 9 + 7
memo = {}
n, k = map(int, input().split())
to = defaultdict(list)
for _ in range(n - 1):
    a, b = map(int, input().split())
    to[a] += [b]
    to[b] += [a]
print(dfs(1, 0))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 
p= int(readline())
if p % 2 == 1:
    print(0)
else:
    p //= 2
    ans = 0
    while n:
        p //= 5
        ans += p
    print(ans)

### FIXED CODE ###

def findTrailingZeros(n): 
      
    if (n%2!=0): 
        return 0

    else: 
        ans = 0
        n //= 2
        while (n): 
            ans += n // 5
            n //= 5
  
        return ans 
  
n = int(input())
  
print(findTrailingZeros(n))
from functools import reduce
n = (int)(input())
a = (list)(map(int, input().split()))


def calcMod(a, m):
  return sum([m % v for v in a])


def mul(a, b):
  return a*b


#print(calcMod(a, reduce(mul, a)-1))
print(sum(a)-N)


### FIXED CODE ###

from functools import reduce
n = (int)(input())
a = (list)(map(int, input().split()))


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


def calcMod(a, m):
  return sum([m % v for v in a])


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


def lcm_list(l):
  g = reduce(lcm, l)
  return g


def mul(a, b):
  return a*b


#print(calcMod(a, (int)(lcm_list(a)-1)))
print(calcMod(a, reduce(mul, a)-1))
nums = [input() for i in range(2)]
A,B,C = map(int,nums)
x = int(input())
  
count = 0
for i in range(A):
  if i*500 == x:
  	count += 1
  	break
  else:
    x -= i*500
    for j in range(B):
		if j*100 == x:
		  count += 1    		
		  break
        else:
          x -= j*100
          for k in range(C):
            if k*50 == x:
    		  count += 1
      		  break
print(count)

### FIXED CODE ###

nums = [input() for i in range(3)]
A,B,C = map(int,nums)
x = int(input())
count = 0
for i in range(A+1):
  for j in range(B+1):
    for k in range(C+1):
      if 500*i+100*j+50*k == x:
        count +=1
print(count)
import numpy as np

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

def f(i):
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = [f(i) for i in range(N)]

print(*B)

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[3] // 2
# A[3] = B[3] // 2 + B[4] // 2
# A[4] = B[4] // 2 + B[0] // 2

# A[0] - A[1] = (B[0] - B[2]) // 2
# A[1] - A[2] = (B[1] - B[3]) // 2
# A[2] - A[3] = (B[2] - B[4]) // 2
# A[3] - A[4] = (B[3] - B[0]) // 2
# A[4] - A[0] - (B[4] - B[1]) // 2

# A[0] - A[1] + A[2] - A[3] + A[4] = B[0]
# A[1] - A[2] + A[3] - A[4] + A[0] = B[1]
# A[2] - A[3] + A[4] - A[0] + A[1] = B[2]
# A[3] - A[4] + A[0] - A[1] + A[2] = B[3]


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=N)
def f(i):
    if i >= 2:
        return f(i - 2) + 2 * A[i - 1] - 2 * A[i - 2]
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = (f(i) for i in range(N))

print(*B)
import math
A, B, H, M = map(int, input(), split())
 
H_degree = (30 * H) + (0.5 * M)
M_degree = 6 * M
diff = math.abs(H_degree - M_degree)
if diff > 180:
  diff = 360 - diff
else:
  diff = diff
 
length = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(diff)))
 
print(length)

### FIXED CODE ###

import math
A, B, H, M = map(int, input().split())
 
H_degree = (30 * H) + (0.5 * M)
M_degree = 6 * M
diff = abs(H_degree - M_degree)
if diff > 180:
  diff = 360 - diff
else:
  diff = diff
 
length = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(diff)))
 
print(length)
n,m = map(int,input().split())

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

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

ma = [0]*n


for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    ma[a] = max(ma[a],h[b])
    ma[b] = max(ma[b],h[a])

int ans = 0    
for i in range(n):
    if h[i] > ma[i]:
        ans += 1
        

print(ans)

### FIXED CODE ###



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

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

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

ma = [0]*n


for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    ma[a] = max(ma[a],h[b])
    ma[b] = max(ma[b],h[a])

ans = 0    
for i in range(n):
    if h[i] > ma[i]:
        ans += 1
        

print(ans)
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1, initial=False
            ), args[2::2])
    ))

    return str(
        search_min_cost(keys, np.array([False for _ in range(n)], dtype=bool))
    )


cache = {}


def search_min_cost(keys: list, unlocked: list) -> int:
    ret = 0
    args = str((len(keys), unlocked))

    if args in cache.keys():
        ret = cache[args]

    elif len(keys) == 0:
        if not all(unlocked):
            ret = -1

    else:
        a, C = keys[0]
        take = search_min_cost(keys[1:], C | unlocked)
        skip = search_min_cost(keys[1:], unlocked)

        if take == -1 and skip == -1:
            ret = -1
        elif take == -1:
            ret = skip
        elif skip == -1:
            ret = a + take
        else:
            ret = min(a+take, skip)

    cache[args] = ret
    return ret


def set2bin(S: set, n: int, start: int = 0, initial: bool = True):
    ret = np.array([initial for _ in range(n)], dtype=bool)
    for s in S:
        ret[s-start] = not initial
    return ret


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))


### FIXED CODE ###

# coding: utf-8
from functools import reduce


def solve(*args: str) -> str:
    a_max = 1+12*10**5
    n, m = map(int, args[0].split())
    cache = {}

    for i in range(1, 1+2*m, 2):
        a, _ = map(int, args[i].split())
        c = reduce(
            lambda x, y: x | 1 << y-1,
            [0] + list(map(int, args[i+1].split()))
        )
        cache[c] = min(cache.get(c, a_max), a)

    for C in tuple(cache.items()):
        unlocked, cost = C
        for E in tuple(cache.items()):
            c, a = E
            cache[unlocked | c] = min(
                cache.get(unlocked | c, a_max),
                a + cost
            )

    return str(cache.get(2**n-1, -1))


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))
x, y, z, k = map(int, input().split())
LA = list(map(int, input().split()))
LB = list(map(int, input().split()))
LC = list(map(int, input().split()))
LAB = []
L = []

for i in range(x):
    for j in range(y):
        LAB.append(LA[i]+LB[j])
LAB.sort(reverse=True)
LAB = LAB[:k]

for i in range(k):
    for j in range(z):
        L.append(LAB[i]+LC[j])
L.sort(reverse=True)

for i in range(k):
    print(L[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

Q = []
Q.append([A[0]+B[0]+C[0], 0, 0, 0])
M = {(0, 0, 0):True}

def search():
    global Q
    q = Q.pop()
    a = q[1]
    b = q[2]
    c = q[3]
    if a+1 < x and (a+1, b, c) not in M:
        Q.append([A[a+1]+B[b]+C[c], a+1, b, c])
        M[(a+1, b, c)] = True
    if b+1 < y and (a, b+1, c) not in M:
        Q.append([A[a]+B[b+1]+C[c], a, b+1, c])
        M[(a, b+1, c)] = True
    if c+1 < z and (a, b, c+1) not in M:
        Q.append([A[a]+B[b]+C[c+1], a, b, c+1])
        M[(a, b, c+1)] = True
    Q.sort()
    return q[0]

for _ in range(k):
    print(search())
A = int(input())
B = int(input())
C = int(input())
a = 10*A + B
b = 10*B + C
c = 10*C + A
d = 10*A + C
e = 10*B + A
f = 10*C +B
print(max([a+C ,b+A, c+B, d+B, e+C, f+A]))


### FIXED CODE ###

suuji = list(map(int, input().split()))
saidai = max(suuji)
suuji.remove(saidai)
print(saidai*10+suuji[0]+suuji[1])
N, W = map(int, input().split())
    dp = [0] + [-1]*(W+1)
    for i in range(N):
        v, w = map(int, input().split())
        for j in range(0, W-w+1):
            if dp[j] > -1 and dp[j+w] < dp[j] + v:
                dp[j+w] = dp[j] + v

    print(max(dp))

### FIXED CODE ###

N, W = map(int, input().split())
dp = [0] + [-1]*(W+1)
for i in range(N):
    v, w = map(int, input().split())
    for j in range(0, W-w+1):
        if dp[j] > -1 and dp[j+w] < dp[j] + v:
            dp[j+w] = dp[j] + v

print(max(dp))
n, m = map(int, input().split())
data = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    data[a - 1].append(b - 1)
    data[b - 1].append(a - 1)

ans = [0] * (n - 1)

def bfs(i, queue, p):
    q = []
    if len(queue) == 0:
        return 
    while len(queue) > 0:
        x = queue.pop(0)
        pre = p.pop(0)
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                q.append(data[x[j]])
                p.append(x[j])
        bfs(x[j], q, p)

queue = []
pre = [0]
queue.append(data[0])
bfs(0, queue, pre)

if 0 not in ans:
    print("Yes")
    for i in range(len(ans)):
        print(ans[i])
else:
    print("No")

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
data = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    data[a - 1].append(b - 1)
    data[b - 1].append(a - 1)

ans = [0] * (n - 1)

def bfs(i, queue, p):
    while len(queue) > 0:
        x = queue.popleft()
        pre = p.popleft()
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                queue.append(data[x[j]])
                p.append(x[j])

queue = deque()
pre = deque()
pre.append(0)
queue.append(data[0])
bfs(0, queue, pre)

if 0 not in ans:
    print("Yes")
    for i in range(len(ans)):
        print(ans[i])
else:
    print("No")
taka, aoki, action = map(int, input().split())
 
if taka >= action:
  print(taka-action, aoki)
  
else:
  print(0, max(taka+aoki-action, 0))

### FIXED CODE ###

s, t = input().split()

print(t+s)
a = int(input())
b = int(input())

if a*b%2 == 0:
    print("Even")
else:
    print("Odd")

### FIXED CODE ###

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

if a*b%2 == 0:
    print("Even")
else:
    print("Odd")
s = input()
s = s.replace("RL", "*")
i = 0
rls = []
n = 0
m = 0
for c in s:
  if c == "R":
    n += 1
  if c == "*":
    r = (n + 1) // 2
    l = n + 1 - r
    rls.append([l, r])
    n = 0
m = 0
i = 1
for c in reversed(s):
  if c == "L":
    m += 1
  if c == "*":
    l = (m + 1) // 2
    r = m + 1 - l
    rls[-i][0] += l
    rls[-i][1] += r
    i += 1
    m = 0
ans = []
i = 0
for c in s:
  if c == "*":
    ans = ans.extend(rls[i])
    i += 1
  else:
    ans.append(0)
print(" ".join([str(c) for c in ans]))


### FIXED CODE ###

s = input()
s = s.replace("RL", "*")
i = 0
rls = []
n = 0
m = 0
for c in s:
  if c == "R":
    n += 1
  if c == "*":
    r = (n + 1) // 2
    l = n + 1 - r
    rls.append([l, r])
    n = 0
m = 0
i = 1
for c in reversed(s):
  if c == "L":
    m += 1
  if c == "*":
    l = (m + 1) // 2
    r = m + 1 - l
    rls[-i][0] += l
    rls[-i][1] += r
    i += 1
    m = 0
ans = []
i = 0
for c in s:
  if c == "*":
    ans.extend(rls[i])
    i += 1
  else:
    ans.append(0)
print(" ".join([str(c) for c in ans]))
A,B,N = map(int,input().split())

if B > N:
  ans = (A * N) // B - A * (N // B)
else:
  ans = (A * (B - 1)) // B - A * (N // (B - 1))
  
print(ans)

### FIXED CODE ###

import math
A,B,N = map(int,input().split())

if B > N:
  ans = math.floor(A * N / B)
else:
  ans = math.floor(A * (B - 1) / B)
  
print(ans)
S, W = map(int, input().split())
if S <= w:
	print("unsafe")
else:
    print("safe")

### FIXED CODE ###

S, W = map(int, input().split())
if S > W:
    print('safe')
else:
    print('unsafe')
n=int(input())
l=list(input().split())
sum_m=0
for i in l:
	sum_m+=1/i
print(1/sum_m)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
sum_m=0
for i in l:
	sum_m+=1/i
print(1/sum_m)
n = int(input())
an = list(map(int, input().split()))
import sys
sys.setrecursionlimit(100000) 

from fractions import gcd
from functools import reduce

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

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

lcma = lcm_list(an)
bn = []
for a in an:
    bn.append(lcma / a)

sumbn = int(sum(bn) % 1000000007)

print(sumbn)

### FIXED CODE ###

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

from fractions import gcd
from functools import reduce

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

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

lcma = lcm_list(an)
ans = 0
for i in range(n):
    ans += (lcma//an[i])
mod=10**9+7
print(ans%mod)
S = list(input())
K = int(input())

if S[0] == 1:
    if K >= 2:
        print(S[1])
    else:
        print(1)
else:
    print)S[1]

### FIXED CODE ###

S = input()
K = int(input())

for i in range(K):
    if S[i] != "1":
        print(S[i])
        break
else:
    print(1)
import sys
def Ii():return int(sys.stdin.readline())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))

n = Ii()
a = Li()
sa = sum(a)
af = [0]*(10**5)
for i in a: 
  af[i]+=1
q = Ii()
for i in range(q):
  b,c = Mi()
  sa = sa + (c-b)*af[b]
  af[c] += af[b]
  af[b] = 0;
  print(sa)
  

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int,sys.stdin.readline().split()))
q = int(input())
s = sum(a)
cnt = [0]*(10**5+5)
for c in a:
  cnt[c] +=1
for i in range(q):
  b,c = map(int,sys.stdin.readline().split())
  bdif = c-b
  s += cnt[b]*bdif
  cnt[c] += cnt[b]
  cnt[b] = 0
  print(s)
import math
a,b,x=map(int,input().split())
if a**2*b>=2*x:
  ans=math.degrees(math.atan(2*x/(a*b**2)))
  print(90-ans)
else:
  ans=math.degrees(math.atan(a**2/(2*a*b-2*x/a)))
  print(90-ans)
  

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
A,B=a**2,b**2
print(math.degrees(math.asin((B/((2*x/(a*b))**2+B))**0.5) if 2*x<=a*a*b else math.acos((A/((2*(a*a*b-x)/A)**2+A))**0.5)))
import numpy as np

N,M = map(int,input().split())
vector = np.zeros((N, N))

for i in range(0, M):
	A,B = map(int,input().split())
	vector[A-1:A,B-1:B] = 1
	vector[B-1:B,A-1:A] = 1

depth = np.zeros((1, N))


### FIXED CODE ###

n,m = map(int,input().split())
visited = [-1 for _ in range(n+1)]
visited[1] = 0
will = []
root = [[] for _ in range(n+1)] 
for i in range(m):
    a,b = map(int,input().split())
    root[a].append(b)
    root[b].append(a)

will.append(1)

while will:
    visit = will.pop(0)
    for i in root[visit]:
        if visited[i] != -1:
            continue
        will.append(i)
        visited[i] = visit

if visited[1:] == -1:
    print('No')
else:
    print('Yes')
    for i in range(2,len(visited)):
        print(visited[i])
import sys
N,K = map(int,input().split())
lsx = list(map(int,input().split()))
if 0 in lsx:
    K = K-1
    lsx.remove(0)
if bool(lsx) == False or K == 0:
    print(0)
    sys.exit()
lshu = []
for i in range(len(lsx)):
    if lsx[i] < 0:
        lshu.append(lsx[i])
    else:
        sei = i
        break
lssei = lsx[sei:]
lenhu = len(lshu)
lensei = len(lssei)
lshu2 = [abs(lshu[i]) for i in range(lenhu-1,-1,-1)]
dishu = [0] + lshu2
dissei = [0] + lssei
print(dissei,dishu)
ans = 10*10**8
for i in range(K):
    if i <= lenhu and K-i <= lensei:
        ans = min(ans,2*dishu[i]+dissei[K-i],dishu[i]+2*dissei[K-i])
print(ans)

### FIXED CODE ###

import sys
N,K = map(int,input().split())
lsx = list(map(int,input().split()))
if 0 in lsx:
    K = K-1
    lsx.remove(0)
if bool(lsx) == False or K == 0:
    print(0)
    sys.exit()
lshu = []
sei = len(lsx)
for i in range(len(lsx)):
    if lsx[i] < 0:
        lshu.append(lsx[i])
    else:
        sei = i
        break
lssei = lsx[sei:]
lenhu = len(lshu)
lensei = len(lssei)
lshu2 = [abs(lshu[i]) for i in range(lenhu-1,-1,-1)]
dishu = [0] + lshu2
dissei = [0] + lssei
ans = 10*10**8
for i in range(K+1):
    if i <= lenhu and K-i <= lensei:
        ans = min(ans,2*dishu[i]+dissei[K-i],dishu[i]+2*dissei[K-i])
print(ans)
S=input()
if S.count(1)>=S.count(0):
  print(S.count(0)*2)
else:
  print(S.count(1)*2)



### FIXED CODE ###

S=input()
if S.count("1")>=S.count("0"):
  print(S.count("0")*2)
else:
  print(S.count("1")*2)
n = int(input()) 
f = [list(map(int, input().split())) for i in range(n)] 
p = [list(map(int, input().split())) for j in range(n)] 

ans = -9999999999

for i in range(1, 1024): 
    bf = 0  
    for j in range(n):  
        cnt = 0 
        for k in range(10): 
            if (i >> k) & 1 == 1 and f[j][k] == 1: 
                cnt += 1 
        bf += p[j][cnt] 
    ans =max(ans, bf)  　
    
print(ans)

### FIXED CODE ###

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
arm = [list(map(int, input().split())) for j in range(n)]  # 入力

ans = -9999999999  # 最小
for item in range(1, 1024):  # 2 ** 10 == 1024
    fund = 0
    for i in range(n):  # 店の数
        cou = 0  # かぶる数
        for x in range(10):  # 月-金(5) * 2
            if (item >> x) % 2 == 1 and arr[i][x] == 1:  # その時間で被るかどうか
                cou += 1
        fund += arm[i][cou]
    ans = max(ans, fund)  # 最大値更新

print(ans)
from math import gcd
A,B,K=map(int,input().split())
g=gcd(A,B)
li=[]
for i in range(1,g+1):
    if(g%i==0):
        li.append(i)
print(li[-K])

### FIXED CODE ###

A,B,K=map(int,input().split())
A,B=min(A,B),max(A,B)
cnt=0
for i in reversed(range(1,A+1)):
    if A%i==0 and B%i==0:
        cnt+=1
    if(cnt==K):
        print(i)
        exit()
N,M = map(int,input().split())

a = [int(input()) for i in range(M)]

wa = (10**9) + 7

def Fib(n):
    if n==0:
        return 0 #F0
    elif n==1:
        return 1 #F1
    elif n==2:
        return 1
    else:
        fibo_minus1 = 1 #Fn-1
        fibo_minus2 = 0 #Fn-2
        for i in range(2,n):
            fibo = fibo_minus1 + fibo_minus2 #Fn = Fn-1 + Fn-2
            fibo_minus2 = fibo_minus1 # Fn-2の値を更新
            fibo_minus1 = fibo # Fn-1の値を更新
        return fibo





ans = 1



if M!= 1:
    length = a[0]
    ans *= Fib(length+1)

    for i in range(0,M-1):
        length = a[i+1]-a[i]-1
        # print(length)
        if length == 0:
            ans *= 0
        else:
            ans *= Fib(length+1)
        # print(ans)


    
if M==1:
    length = a[0]
    ans *= Fib(length+1)




length = N-a[-1]


ans *= Fib(length+1)

print(ans%wa)




### FIXED CODE ###

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

a = [int(input()) for i in range(M)]

wa = (10**9) + 7

#dpを使う

dp = [0]*(N+1)
dp[0]=1
now_a = 0
if len(a)==0:
    now_a = -1
if len(a)!=0:
    a.reverse()
    now_a = a.pop()

for i in range(1,N+1):
    # print(now_a)
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i == now_a:
        dp[i]=0
        if len(a)!=0:
            now_a = a.pop()
        else:
            now_a = -1

# print(dp)

print(dp[N]%wa)