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

import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')

h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)  


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)
### BUGGY CODE ###

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

def culc(L):
    subL=[0]*(n+1)

    for i in range(n):
        temp=L[i]
        bottom=max(i-temp,0)
        top=min(i+temp,n-1)

        subL[bottom]+=1
        subL[top+1]-=1
    
    resL=[0]*n
    resL[0]=subL[0]
    for i in range(1,n):
        resL[i]=resL[i-1]+subL[i]

    return resL

for i in range(min(k,20)):
    A=culc(A)

print(*A)


### FIXED CODE ###

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

def culc(L):
    subL=[0]*(n+1)

    for i in range(n):
        temp=L[i]
        bottom=max(i-temp,0)
        top=min(i+temp,n-1)

        subL[bottom]+=1
        subL[top+1]-=1
    
    resL=[0]*n
    resL[0]=subL[0]
    for i in range(1,n):
        resL[i]=resL[i-1]+subL[i]

    return resL

for i in range(min(k,50)):
    A=culc(A)

print(*A)
### BUGGY CODE ###



def func():
    N, K = map(int, input().split() )
    h = list( map(int,input().split()) )

    dp = [0] * N
    for n in range(1, N):
        cans = []
        for k in range(1,K+1):
            if n-k >= 0 :
                cans.append( dp[n-k] + abs(h[n]-h[n-k]) )
        dp[n] = min(cans)    
    print(dp[N-1])

if __name__=='__main__':
    func()





### FIXED CODE ###



def func():
    N, k = map(int, input().split() )
    h = list( map(int,input().split()) )

    dp = [float('inf')] * N
    dp[0] = 0
    for n in range(1, N):
        # can_min = 10**4
        # for k in range(1,K+1l):
        #     if n-k >= 0 :
        #         can = dp[n-k] + abs(h[n]-h[n-k])
        #         can_min = min(can, can_min)
        # dp[n] = can_min 
        dp[n] = min([ dp[j] + abs(h[n]-h[j]) for j in range(max(n-k,0), n) ])
    print(dp[N-1])

if __name__=='__main__':
    func()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

memo = {0:0, 1:1, 2:1}
def calc(x):
  global memo
  if x in memo:
    return memo[x]
  c = bin(x).count('1')
  y = x % c
  res = calc(y) + 1
  memo[x] = res
  return res

for i in range(3, 2*10**5+1):
  calc(i)

N = int(input())
X = input()
c = X.count('1')
X_int = int(X, 2)
Xmodp = X_int % (c+1)
Xmodm = X_int % (c-1) if c > 1 else 0

ans = []
digit = 1 << (N - 1)
for x in X:
  if x == '0':
    ans.append(
      calc((Xmodp + digit%(c+1)) % (c+1)) + 1
    )
  else:
    if c == 1:
      ans.append(0)
    else:
      ans.append(
        calc((Xmodm - digit%(c-1)) % (c-1)) + 1
      )  
  digit >>= 1

print(*ans, sep='\n')

### FIXED CODE ###

N = int(input())
X = input()
c = X.count('1')
if c == 0:
  for i in range(N):
    print(1)
  quit()
if c == 1:
  if int(X[-1]):
    for i in range(N-1):
      print(2)
    print(0)
  else:
    for i in range(N-1):
      if int(X[i]):
        print(0)
      else:
        print(1)
    print(2)
  quit()

memo = {0:0, 1:1, 2:1}
def calc(x):
  global memo
  if x in memo:
    return memo[x]
  c = bin(x).count('1')
  y = x % c
  res = calc(y) + 1
  memo[x] = res

for i in range(3, 2*10**5+1):
  calc(i)

Xmodp = Xmodm = 0
digit_p = digit_m = 1
digit = {}
for i in range(N):
  if int(X[-i-1]):
    Xmodp += digit_p
    Xmodp %= c + 1
    Xmodm += digit_m
    Xmodm %= c - 1
  digit[i] = [digit_p, digit_m]
  digit_p = (digit_p * 2) % (c+1)
  digit_m = (digit_m * 2) % (c-1)

ans = []
for i in range(N):
  x = int(X[-i-1])
  if x:
    ans.append(memo[(Xmodm - digit[i][1]) % (c-1)] + 1)
  else:
    ans.append(memo[(Xmodp + digit[i][0]) % (c+1)] + 1)

ans = ans[::-1]
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
li_A = list(map(int, input().split()))
for i in range(M):
    B, C = map(int, input().split())
    for j in range(B):
        min_A = min(li_A)
        if min_A <C:
            li_A[li_A.index(min_A)] = C
        else:
            break
print(sum(li_A))

### FIXED CODE ###

from heapq import heappop, heappush, heapify
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
heap = list(map(int, input().split()))
heapify(heap)

BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append([B, C])
BC.sort(key=lambda x: -x[1])

for B, C in BC:
    for _ in range(B):
        tmp = heappop(heap)
        if tmp < C:
            heappush(heap, C)
        else:
            heappush(heap, tmp)
            break
print(sum(heap))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append(str(a[i]))
    b.reverse()
b = ' '.join(b)
print(b)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
i=0
while n-1-i>=0:
    b.append(str(a[n - 1 - i]))
    i += 2
if n%2==0:
    for i in range(0,n,2):
        b.append(str(a[i]))
else:
    for i in range(1,n,2):
        b.append(str(a[i]))
b=' '.join(b)
print(b)
### BUGGY CODE ###

#!/usr/bin/env python3

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


ans = 0
for x in range(1, n+1):
    ans = max((a*x//b)-a*(x//b), ans)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

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

if b-1 <= n:
    x = b-1
    ans = math.floor(a*x/b) - a * math.floor(x/b)
else:
    x = n
    ans = math.floor(a*x/b) - a * math.floor(x/b)
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
S = []

res = []
for i in range(N):
    S.append(input())

SS = collections.Counter(S)
for i in SS.keys():
    if(SS[i]== max(SS.values())):
        res.append(i)
res.sort()
for i in range(len(res)):
    print(res[i])
    

### FIXED CODE ###

import collections
N = int(input())
S = []

res = []
for i in range(N):
    S.append(input())

SS = collections.Counter(S)
m = max(SS.values())
for i in SS.keys():
    if(SS[i]== m):
        res.append(i)
res.sort()
for i in range(len(res)):
    print(res[i])
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split()))
    hs = [int(input()) for i in range(N)]
    hs.sort()
    i = 0
    r = 10 ** 9
    while True:
        if i + K > N:
            break
        th = hs[i:i + K]
        r = min(r, th[-1] - th[0])
        i += 1
    print(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = list(map(int, input().split()))
    hs = [int(input()) for i in range(N)]
    hs.sort()
    i = 0
    r = 10 ** 9
    while True:
        if i + K > N:
            break
        r = min(r, hs[i + K - 1] - hs[i])
        i += 1
    print(r)


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

N = int(input())
S = input().strip()
kmax = 0
for k in range(1,N//2+1):
    C = {}
    for i in range(N-k+1):
        if S[i:i+k] not in C:
            C[S[i:i+k]] = []
        C[S[i:i+k]].append(i)
    for a in C:
        if len(C[a])>=2:
            flag = 0
            for i in range(1,len(C[a])):
                if C[a][i]-C[a][i-1]>=k:
                    flag = 1
                    break
            if flag==1:
                kmax = k
                break
print(kmax)

### FIXED CODE ###

N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N):
    X = S[:N-k]
    Y = S[k:]
    cur = 0
    cnt = 0
    for i in range(N-k):
        if X[i]!=Y[i]:
            cmax = max(cmax,min(cnt,k))
            cur = i
            cnt = 0
        else:
            cnt += 1
    cmax = max(cmax,min(cnt,k))
print(cmax)
### BUGGY CODE ###

import numpy as np
S = input()

MOD = 10 ** 9 + 7
n = len(S)

dp = np.zeros((100005, 13), dtype=np.uint64)

dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    # print(c)
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
    res = dp[n][5]
    
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
# import numpy as np

S = input().rstrip()

MOD = 10 ** 9 + 7
n = len(S)

# dp = np.zeros((100005, 13), dtype=np.uint64)

dp = [[0 for i in range(13)] for j in range(100005)]

dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
        
    res = dp[n][5]
    
print(res)
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
  s = h[i]
  t = 0
  for j in range(i+1,n):
    if s >= h[j]:
      t += 1
      s = h[j]
    else:
      ans = max(ans, t)
      break
    ans = max(ans, t)
print(ans)

### FIXED CODE ###

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

x = 0
y = 0
z = 0
for i in h:
  if x < i:
    x = i
    y = 0
    continue
    
  y += 1
  x = i
  if z < y:
    z = y
print(z)
### BUGGY CODE ###

N = int(input())
T = 1
A = 1


for i in range(N):
    t,a = map(int, input().split())

    if max(t,a)%min(t,a) == 0:
        if t > a:
            t = t//a
            a = a
        else:
            t = t
            a = a//t

    j = 0
    while T > t*j or A > a*j:
        j += 1

    T = t*j
    A = a*j

print(T+A)


### FIXED CODE ###

N = int(input())
T = 1
A = 1


for i in range(N):
    t,a = map(int, input().split())

    if max(t,a)%min(t,a) == 0:
        if t > a:
            t = t//a
            a = a
        else:
            t = t
            a = a//t

    j = max(T//t,A//a)
    while T > t*j or A > a*j:
        j += 1

    T = t*j
    A = a*j

print(T+A)
### BUGGY CODE ###

def rec(digit, flag, k):
    limit = int(N[digit])
    if k > K:
        return 0
    if digit == len(N) - 1:
        if k == K:
            return 1
        elif k == K - 1:
            return limit if flag else 9
        else:
            return 0
    if flag:
        if limit == 0:
            return rec(digit + 1, 1, k)
        else:
            return rec(digit + 1, 0, k + 1) * (limit - 1) + rec(digit + 1, 1, k + 1) + rec(digit + 1, 0, k)
    else:
        return rec(digit + 1, 0, k + 1) * 9 + rec(digit + 1, 0, k)

N = input()
K = int(input())
print(rec(0, 1, 0))

### FIXED CODE ###

def rec(digit, flag, k):
    limit = int(N[digit])
    if k > K:
        return 0
    if digit == len(N) - 1:
        if k == K:
            return 1
        elif k == K - 1:
            return limit if flag else 9
        else:
            return 0
    if flag:
        if limit == 0:
            return rec(digit + 1, 1, k)
        else:
            return rec(digit + 1, 0, k + 1) * (limit - 1) + rec(digit + 1, 1, k + 1) + rec(digit + 1, 0, k)
    else:
        return rec(digit + 1, 0, k + 1) * 9 + rec(digit + 1, 0, k)

N = input()
K = int(input())
print(rec(0, 1, 0))
### BUGGY CODE ###

from collections import Counter
from operator import mul
from functools import reduce

def combinations_count2(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
#
N=int(input())
A=list(map(int,input().split()))
#
hoge=Counter(A)
ans1=0
for i in hoge.values():
    if i==1:
        continue
    else:
        ans1+=combinations_count2(i,2)

ans2=[]
for i in A:
    ans2.append(A.count(i)-1)

for k in range(N):
    print(ans1-ans2[k])

### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce
def combinations_count2(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

#
N=int(input())
A=list(map(int,input().split()))
#
hoge=Counter(A)
ans=0
for i in hoge.values():
    if i>=2:
        ans += combinations_count2(i, 2)
for i in range(N):
    print(ans-hoge[A[i]]+1)
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    from collections import deque
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    d=[[1,0],[-1,0],[0,1],[0,-1]]
    INF=10**12
    path=[[INF]*w for _ in range(h)]
    ans=0
    st=[]
    st=deque()
    st.append((ch,cw,0))
    wp=[]
    wp=deque()
    while st:
      nx,ny,ncost=st.popleft()
      wp.append((nx,ny,ncost))
      path[nx][ny]=ncost
      for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if (0<=x<=h-1) and (0<=y<=w-1):
          if s[x][y]!='#' and path[x][y]>ncost:
            path[x][y]=ncost
            st.append((x,y,ncost))
      if len(st)==0:
        while wp:
          nx,ny,ncost=wp.popleft()
          for i in range(-2,3):
            for j in range(-2,3):
              if (i,j)==(0,0) or (i,j)==(1,0) or (i,j)==(0,1) or (i,j)==(-1,0) or (i,j)==(0,-1):
                continue
              x,y=i+nx,j+ny
              if (0<=x<=h-1) and (0<=y<=w-1):
                if s[x][y]!='#' and path[x][y]>ncost+1:
                  path[x][y]=ncost+1
                  st.append((x,y,ncost+1))
    if path[dh][dw]==INF:
      print(-1)
    else:
      print(path[dh][dw])

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def solve(h,w,ch,cw,dh,hw,s):
    d=[[1,0],[-1,0],[0,1],[0,-1]]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + d]
    INF=10**12
    path=[[INF]*w for _ in range(h)]
    ans=0
    st=[]
    st=deque()
    st.append((ch,cw,0))
    wp=[]
    wp=deque()
    while st:
      nx,ny,ncost=st.popleft()
      wp.append((nx,ny,ncost))
      path[nx][ny]=ncost
      for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if (0<=x<=h-1) and (0<=y<=w-1):
          if s[x][y]!='#' and path[x][y]>ncost:
            path[x][y]=ncost
            st.append((x,y,ncost))
      if len(st)==0:
        while wp:
          nx,ny,ncost=wp.popleft()
          for dx,dy in warp:
              x,y=nx+dx,ny+dy
              if (0<=x<=h-1) and (0<=y<=w-1):
                if s[x][y]!='#' and path[x][y]>ncost+1:
                  path[x][y]=ncost+1
                  st.append((x,y,ncost+1))
    if path[dh][dw]==INF:
      print(-1)
    else:
      print(path[dh][dw])

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    from collections import deque
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    solve(h,w,ch,cw,dh,dw,s)
### BUGGY CODE ###

import sys
args = sys.stdin.readlines()
n, m = map(int, args[0].split(' '))
gates = []
for gate in args[1:]:
  l, r = map(int, gate.split(' '))
  gates.append((l, r))
  
ids = set(range(1, n+1))
for gate in gates:
  l, r = gate
  ids = ids & set(range(l, r+1))
  
print(len(ids))


### FIXED CODE ###

import sys
args = sys.stdin.readlines()
n, m = map(int, args[0].split(' '))
l_1 = 1
r_1 = n

for gate in args[1:]:
  l, r = map(int, gate.split(' '))  
  if l > l_1:
    l_1 = l
  if r < r_1:
    r_1 = r

ids = r_1 - l_1 + 1
if ids < 0:
  print(0)
else:
  print(ids)
### BUGGY CODE ###

import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from copy import deepcopy 

def main():
    n = int(input())
    a = []
    for _ in range(n):
        b = [int(i) - 1 for i in input().split()]
        a.append(b[::-1])
    
    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if a[j][-1] == i:
            if i > j:
                i,j = j,i
            q.add((i,j))
    
    for i in range(n):
        check(i)
        
    day = 0
    while len(q):
        day += 1
        prevQ = deepcopy(q)
        q.clear()
        for i,j in prevQ:
            a[i].pop()
            a[j].pop()
        for i,j in prevQ:
            check(i)
            check(j)
    
    ans = day
    for i in range(n):
        if len(a[i]) != 0:
            ans = -1
    
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from copy import deepcopy 

MAXN = 1005
MAXV = MAXN * (MAXN - 1)//2
G = [[] for _ in range(MAXV)]

id = [[-1] * MAXN for _ in range(MAXN)]
def toId(i,j):
    if i > j:
        i,j = j,i
    return id[i][j]


finished = [0] * MAXV
dp = [-1] * MAXV
def dfs(v):
    if dp[v] != -1:
        if finished[v] == 0:
            return -1
        return dp[v]
    dp[v] = 0
    for e in G[v]:
        res = dfs(e)
        if res == -1:
            return -1
        dp[v] = max(dp[v],res + 1)
    finished[v] = 1
    return dp[v]


def main():
    n = int(input())
    a = [[int(i) - 1 for i in input().split()] for _ in range(n)]

    v = 0
    for i in range(n):
        for j in range(i + 1,n):
            id[i][j] = v
            v += 1
    
    for i in range(n):
        for j in range(n - 1):
            a[i][j] = toId(i,a[i][j])
        for j in range(n - 2):
            G[a[i][j]].append(a[i][j + 1])
    
    ans = 0
    for i in range(v):
        res = dfs(i)
        if res == -1:
            ans = -1
            break
        ans = max(ans,dfs(i) + 1)
    
    print(ans)

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

import math
from functools import reduce

n = int(input())
ans = 0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for a in range(1,n+1):
    for b in range(1,n+1):
        for c in range(1,n+1):
            ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce

n = int(input())
ans = 0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for a in range(1,n+1):
    for b in range(1,n+1):
        for c in range(1,n+1):
            ans += gcd(a,b,c)
print(ans)
### BUGGY CODE ###

import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
b = np.abs(a)
b = sorted(a,reverse = True)
b_k = b[k-1] 
a_new = [a[_] for _ in range(len(a)) if np.abs(a)[_] >= b_k]
 
comb = itertools.combinations(a_new,k)  
l = [list(_) for _ in comb]  
A = (functools.reduce(operator.mul,l[_]) for _ in range(len(l)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

from itertools import permutations

N, M, r = map(int, input().split())
R = list(map(int, input().split()))

INF = 10 ** 9

G = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    G[i][i] = 0

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

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])

ans = INF
for tmp in permutations(R):
    score = 0
    for i in range(r - 1):
        score += G[tmp[i]][tmp[i + 1]]
    ans = min(ans, score)

print (ans)


### FIXED CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

N, M, R = map(int, input().split())
r = list(input().split())
edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))

lst = floyd_warshall(graph, directed = False)
# print (lst)
def calc(path):
    cost = 0
    s = int(path[0]) - 1
    for i in range(1, R):
        g = int(path[i]) - 1
        cost += lst[s, g]
        s = g
    return cost

ans = 10 ** 18
for tmp in permutations(r):
    # print (tmp)
    ans = min(ans, calc(tmp))

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

s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=ab*3+a
    a=(a*3+q)%m
    q=q*3
print(abc)


### FIXED CODE ###

s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=(ab+a)%m
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)
### BUGGY CODE ###

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

cont = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if s == (x + y + z):
                cont += 1
print(cont)

### FIXED CODE ###

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

cont = 0
for x in range(k+1):
    for y in range(k+1):
        if x + y <= s:
            if s - (x+y) <= k:
                cont += 1
print(cont)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
c = 0
while True:
  for i in range(n):
    if a[i] / 2 == a[i] // 2:
      a[i] = a[i] // 2
    else:
      print(c)
      break
  c += 1

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
c = 0
while True:
  for i in range(n):
    if a[i] / 2 == a[i] // 2:
      a[i] = a[i] // 2
    else:
      print(c)
      exit()
  c += 1