Harryxun/stf_run huggingface dataset:
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    sys.exit()

A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if len(A_neg) == N:
    if K % 2 == 1:
        A = sorted(A, key=lambda x: abs(x))
    else:
        A = sorted(A, key=lambda x: -abs(x))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    sys.exit()

A_pos = sorted(A_pos, key=lambda x: -abs(x))
A_neg = sorted(A_neg, key=lambda x: -abs(x))
ans = 1
r = K
if r % 2 == 1:
    ans *= A_pos[0]
    ans %= MOD
    A_pos = A_pos[1:]
    r -= 1

while r > 0:
    if len(A_pos) <= 1:
        ans *= A_neg[0] * A_neg[1]
        ans %= MOD
    elif len(A_neg) <= 1:
        ans *= A_pos[0] * A_pos[1]
        ans %= MOD
    else:
        acc_pos = A_pos[0] * A_pos[1]
        acc_neg = A_neg[0] * A_neg[1]

    if acc_pos > acc_neg:
        ans *= acc_pos
        ans %= MOD
    else:
        ans *= acc_neg
        ans %= MOD
    r -= 2
print(ans % MOD)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())

if K == N:
    ans = 1
    for a in A:
        ans = ans * a % MOD
    print(ans)
    sys.exit()

A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if len(A_pos) == 0:
    if K % 2 == 1:
        A_neg.sort(reverse=True)
    else:
        A_neg.sort()
    ans = 1
    for a in A_neg[:K]:
        ans = ans * a % MOD
    print(ans)
    sys.exit()

A_pos.sort()
A_neg.sort(reverse=True)
ans = 1
r = K
if r % 2 == 1:
    ans = ans * A_pos.pop() % MOD
    r -= 1

while r > 0:
    if len(A_pos) <= 1:
        ans = ans * A_neg.pop() * A_neg.pop() % MOD
    elif len(A_neg) <= 1:
        ans = ans * A_pos.pop() * A_pos.pop() % MOD

    else:
        acc_pos = A_pos[-1] * A_pos[-2]
        acc_neg = A_neg[-1] * A_neg[-2]

        if acc_pos > acc_neg:
            ans = ans * A_pos.pop() * A_pos.pop() % MOD
        else:
            ans = ans * A_neg.pop() * A_neg.pop() % MOD
    r -= 2
print(ans % MOD)
N = int(input())
X_bin = input()
#N = 2 * 10**4
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int
# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1
dp = {0: 0, 1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    #if next_int in bin_cnt.keys():
    #    cnt = bin_cnt[next_int]
    #else:
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    key = next_int
    #if key in dp.keys():
    #    ans = dp[key]
    #else:
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    #else:
    #    bin_cnt[key] = cnt
    #bin_cnt[next_int] = cnt
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    #dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))


### FIXED CODE ###

N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)
a, b = map(int, input().split())
c = a+b
d = a-b
e = a*b
print(max([c, d. e]))

### FIXED CODE ###

a, b = map(int, input().split())
print(max(a+b,a-b,a*b))
Num = 10 ** 9 + 7
N, M = map(int, input().split())
if M != 0
  danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)

### FIXED CODE ###

Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = -1
if M != 0:
  danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)
b=input()
if b=='A':
	print('T')
if b=='T':
	print('A')
if b=='C':
	print('G'):
if b=='G':
	print('C')

### FIXED CODE ###

b=input()
if b=='A':
	print('T')
if b=='T':
	print('A')
if b=='C':
	print('G')
if b=='G':
	print('C')
i = [int(input()) for i in range(3)]

print(len(set(i)))

### FIXED CODE ###

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

l=[a,b,c]

print(len(set(l)))
n = int(input())

ntmp = n
sum = 0

while ntmp >= 10:
    sum += ntmp % 10
    ntmp = (int)(ntmp / 10)

if n % sum == 0:
    print("Yes")

else:
    print("No")


### FIXED CODE ###

n = int(input())

ntmp = n
sum = 0

while True:
    sum += ntmp % 10
    ntmp = ntmp // 10
    if ntmp == 0:
        break

if n % sum == 0:
    print("Yes")

else:
    print("No")
p = list((input().split()))
s = []
for i in range(1, int(p[0])):
    s.append(p[i])
print(len(list(set(s))))

### FIXED CODE ###

n = int(input())
p = [input() for i in range(n)]
s = set()
for i in range(n):
    s.add(p[i])
print(len(s))
import numpy as np
import sys
N, M = [int(x) for x in input().split()]
s = []
c = []
for i in range(M):
  a, b = [int(x) for x in input().split()]
  s.append(a)
  c.append(b)

ans = np.full(N+1, -1)
for i in range(M):
  if(ans[s[i]]==-1):
    ans[s[i]] = c[i]
  elif(ans[s[i]]!=c[i]):
    print(-1)
    sys.exit()
if(ans[1]==-1)and(n>1):
  ans[1] = 1
ans = np.where(ans==-1, 0, ans)

if(ans[1]==0)and(N!=1):
  print(-1)
  sys.exit()
Ans = 0
for i in range(1, N+1):
  Ans += 10**(N-i)*ans[i]
print(int(Ans))

### FIXED CODE ###

import numpy as np
import sys
N, M = [int(x) for x in input().split()]
s = []
c = []
for i in range(M):
  a, b = [int(x) for x in input().split()]
  s.append(a)
  c.append(b)
  
ans = np.full(N+1, -1)
for i in range(M):
  if(ans[s[i]]==-1):
    ans[s[i]] = c[i]
  elif(ans[s[i]]!=c[i]):
    print(-1)
    sys.exit()
if(ans[1]==-1)and(N>1):
  ans[1] = 1
ans = np.where(ans==-1, 0, ans)
 
if(ans[1]==0)and(N!=1):
  print(-1)
  sys.exit()
Ans = 0
for i in range(1, N+1):
  Ans += 10**(N-i)*ans[i]
print(int(Ans))
T,Y,x,y=map(int,input().split())
a='0'
if T/2==x & Y/2==y:
  a='1'
print(T*Y/2,a)


### FIXED CODE ###

T,Y,x,y=map(int,input().split())
a='0'
if T/2==x and Y/2==y:
  a='1'
print(T*Y/2,a)
n = int(input())
s = input()

ans = 1
current = s[0]
for i in range(n):
  if current != s[i]:
    ans += 1 
    current = s[i]
print ans
  
  

### FIXED CODE ###

n = int(input())
s = input()

ans = 1
current = s[0]
for i in range(n):
  if current != s[i]:
    ans += 1 
    current = s[i]
print(str(ans))
a,b=input().split()
d=0
n=1
l=input().split( )
while True:
  d+=int(l[n])
  if d<=int(b):
    n+=1
  else:
    break
print(n)

### FIXED CODE ###

a,b=input().split()
d=0
n=1
l=input().split( )
for p in range(int(a)):
  d+=int(l[p])
  if d<=int(b):
    n+=1
print(n)
N,X,M = map(int,input().split())

d = {X:0}
l = [X]

for i in range(1,N):
  l+=[(l[i-1]**2)%M]
  if l[i] in d:
    dl = l[d[l[i]]+1:]
    print(dl)
    l += dl*((N-i-1)//len(dl))
    if (N-i-1)%len(dl) != 0:
      l += dl[0:(N-i-1)%len(dl)]
    break
  d[l[i]] = i
print(l)
print(sum(l))

### FIXED CODE ###

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

d = {X:0}
l = [X]
s = X

for i in range(1,N):
  l+=[(l[i-1]**2)%M]
  s += l[i]
  if l[i] in d:
    dl = l[d[l[i]]+1:]
    s += sum(dl)*((N-i-1)//len(dl))
    if (N-i-1)%len(dl) != 0:
      s += sum(dl[0:(N-i-1)%len(dl)])
    break
  d[l[i]] = i
print(s)
x,y=map(int,raw_input().split())


print x*y,(x+y)*2


### FIXED CODE ###

x,y=map(int, input().split())


print(x*y,(x+y)*2)
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == 1:
    a_list.append(X[i][0])
  elif X[i][0] == n:
    b_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_set = set(a_list) & set(b_list)
if len(c_set) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

### FIXED CODE ###

n,m = map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_set = set(a_list) & set(b_list)
if len(c_set) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")
import numpy as np
from sys import stdin
sys.setrecursionlimit(10**6) 

def main(args):
    a = int(args[0])
    b = int(args[1])
    if 6 <= a and a <= 12:
        v = b//2
    elif a <= 5:
        v = 0
    else:
        v = b
    print(v)

main(stdin.readline().rstrip().split(" "))

### FIXED CODE ###

import numpy as np
from sys import stdin
#sys.setrecursionlimit(10**6) 

def main():
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    if 6 <= a and a <= 12:
        v = b//2
    elif a <= 5:
        v = 0
    else:
        v = b
    print(v)

if __name__ == "__main__":
    main()
k = list(map(int,input().split()))
print(-(-(k[0]+k[1])//2)

### FIXED CODE ###

k = list(map(int,input().split()))
print(-(-(k[0]+k[1])//2))
import bisect
#import numpy as np
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
#A = np.array([int(_) for _ in input().split()],dtype=int)
#A.sort()
A=sorted([int(_) for _ in input().split()])

#target以下の積がK個以上ある最小のtarget

def check(target):
    cnt=0
    for i, a in enumerate(A):
        if a < 0:
            il = bisect.bisect_left(A,  target / a)
            #il = np.searchsorted(A,target/a,side='left')
            #ilからiまで、ただしilがiを超えたら0
            d = max(i - il, 0)
        elif a > 0:
            ir = bisect.bisect_right(A, target / a)
            #ir = np.searchsorted(A,target/a,side='right')
            #0からirまで、ただしirがiを超えたらi
            d = min(ir, i)
        else:
            d = i if target >= 0 else 0
        #print(target,a,d)
        cnt+=d
    return cnt>=K

lb = -10**18-1
rb = 10 ** 18 + 1
# Min x for check(x) == True
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(mid):
        rb = mid
    else:
        lb = mid
print(rb)



### FIXED CODE ###

import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))
n = str(input())
lis = [0 for i in range(26)]
ans = 1
for i in range(1,len(n)+1):
  ans += i
  lis[ord(n[i])-"a"] += 1
for i in range(26):
  for k in range(lis[i]-1):
    ans -= (k+1)
print(ans)

### FIXED CODE ###

n = str(input())
lis = [0 for i in range(26)]
ans = 1
for i in range(len(n)):
  ans += i
  lis[ord(n[i])-ord("a")] += 1
for i in range(26):
  for k in range(lis[i]-1):
    ans -= (k+1)
print(ans)
a = int(input())
b = int(input())
print(a*b)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
    dist = [-1]*N
    dist[s] = 0
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

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

for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

dist = bfs(0)
M = 0

for i in range(N):
    if dist[i]>M:
        M = dist[i]
        s = i

d = max(bfs(s))+1
dp = [False]*(d+1)
dp[1] = True

for i in range(3, d+1):
    dp[i] |= not dp[i-1]
    dp[i] |= not dp[i-2]

if dp[d]:
    print('First')
else:
    print('Second')

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
    dist = [-1]*N
    dist[s] = 0
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

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

for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

dist = bfs(0)
M = -1

for i in range(N):
    if dist[i]>M:
        M = dist[i]
        s = i

d = max(bfs(s))+1
dp = [False]*(d+1)
dp[1] = True

for i in range(3, d+1):
    dp[i] |= not dp[i-1]
    dp[i] |= not dp[i-2]

if dp[d]:
    print('First')
else:
    print('Second')
i = list(map(int, input().split()))
A = i[0]
B = i[1]

count = 0
for i in range (A-1,B+1,1):
    I = str(i)
    if int(I[-1]) == int(I[-5]) and int(I[-2]) == int(I[-4]):
        count = count + 1
    else :
        pass

print(count)

### FIXED CODE ###

i = list(map(int, input().split()))
A = i[0]
B = i[1]

count = 0
for i in range (A,B+1,1):
    I = str(i)
    if int(I[-1]) == int(I[-5]) and int(I[-2]) == int(I[-4]):
        count = count + 1
    else :
        pass

print(count)
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
unique = {a[0] % m: 1}
for i in range(1, n):
    a[i] += a[i - 1]
    a[i] %= m
    if a[i] in unique:
        unique[a[i]] += 1
    else:
        unique[a[i]] = 1
count = unique[0]
for k in unique:
    count += unique[k] * (unique[k] - 1) // 2
print(count)

### FIXED CODE ###

import numpy as np
(n, m) = list(map(int, input().split()))
a = np.array(list(map(int, input().split()))).astype("int64") 
a = np.cumsum(a)
a %= m
count = np.sum(a == 0)
a.sort()
tc = 1
for i in range(1, n):
    if a[i - 1] == a[i]:
        tc += 1
    else:
        count += tc * (tc - 1) // 2
        tc = 1
else:
    count += tc * (tc - 1) // 2
print(count)
temp = raw_input()
temp_list = temp.split()
a = temp_list[0]
b = temp_list[1]
c = temp_list[2]

count = 0
for i in range(a,b):
  if c/i == 0:
    count += 1

print(count)


### FIXED CODE ###

temp = raw_input()
temp_list = temp.split()
a = int(temp_list[0])
b = int(temp_list[1])
c = int(temp_list[2])

count = 0
for i in range(a,b+1):
  if c%i == 0:
    count += 1

print(count)
a, b = [int(item) for item in input().split()]

if b > a:
    c = a
    a = b
    b = c


# 最大公約数を求める
def gcd(a, b):
    while b > 1:
        a, b = b, a%b
    return a

# 公約数でかつ素数の_listを求める
prime_devisor_list = [1, 2]

import math

def is_prime(num):
    if num in [1, 2]:
        return True
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

for i in range(3, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        # i can be ans
        # check pirme

        if is_prime(i):
            prime_devisor_list.append(i)

# 数をこたえる
len(prime_devisor_list)


### FIXED CODE ###

num = int(input())
odd_num = num // 2 + num % 2
print(odd_num / num)
N = int(input())
A = list(map(int, input().split(' ')))

answer = 'YES'
max_val = max(A) + 1
check = [False] * max_val
for a in A:
    if check[a] == True:
        answer = 'NO'
        break
    else:
        check[a] = True
print(answer)

### FIXED CODE ###

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

answer = 'YES'
check_dic = {}
for a in A:
    if a in check_dic:
        answer = 'NO'
        break
    else:
        check_dic[a] = True
print(answer)
a, b, n = map(int, input().split())
c = max(b-1, n)
parint(int(a*c/b))

### FIXED CODE ###

a, b, n = map(int, input().split())
c = min(b-1, n)
print(int(a*c/b))
N,M,K=map(int, input().split())
#最初しろ
#行、列ごとに反転
L=[0]*(10*7)
if K==0 or K==N*M:
    print("Yes")
else:
    for h in range(N):
        for w in range(M):
            now=h*w+(N-h)*(M-w)
            L[now]+=1
    if L[K]>0:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

N,M,K=map(int, input().split())
#最初しろ
#行、列ごとに反転
L=[0]*(10**7)
if K==0 or K==N*M:
    print("Yes")
else:
    for h in range(N+1):
        for w in range(M+1):
            now=h*w+(N-h)*(M-w)
            L[now]+=1
    if L[K]>0:
        print("Yes")
    else:
        print("No")
N,A=map(int,input().split())
if N%500<=A:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N=int(input())
A=int(input())
if N%500<=A:
    print("Yes")
else:
    print("No")
A,B,C = map(int,input().split())

if B+C <= A:
print(0)

else B+C > A:
print(C-A+B)

### FIXED CODE ###

A,B,C = map(int,input().split())

answer = C-A+B

if answer >= 0:
	print(answer)

else :
	print(0)
h = 2R*3.14

### FIXED CODE ###

R = int(input())
h = 2*R*3.14

print(h)
n = int( input() )
A = [ int( val ) for val in input().split( ' ' ) ]
q = int( input() )
M = [ int( val ) for val in input().split( ' ' ) ]
for i in range( 0, q ):
	print( "yes" )

### FIXED CODE ###

def solve( p, t ):
	global isExist, n, A
	isExist[ t ] = True
	if p < n:
		solve( p+1, t-A[p] )
		solve( p+1, t )
	else:
		return

isExist = [False]*2001 
n = int( input() )
A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int( input() )
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]
s = sum( A )
solve( 0, s )
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )
import math
a,b=map(int,input().split())
c=int(a*b//math.gcd(a,b))
print(c)

### FIXED CODE ###

from fractions import gcd
a,b=map(int,input().split())
c=int(a*b//gcd(a,b))
print(c)
def pc(x):
    cnt = 0
    for i in range(len(x)):
        if x[i]=="1":
            cnt += 1
    return cnt
def f(n,j):
    if n==0:
        return 0
    cnt = 1
    n = n%j
    y = bin(n)[2:]
    while n%pc(y)!=0:
        cnt += 1
        n = n%pc(y)
        y = bin(n)[2:]
    return cnt+1
N = int(input())
X = input().strip()
k = 0
for i in range(N):
    if X[i]=="1":
        k += 1
n = int(X,2)
for i in range(N):
    if X[i]=="0":
        m = n+2**(N-1-i)
        j = k+1
    else:
        m = n-2**(N-1-i)
        j = k-1
    print(f(m,j))

### FIXED CODE ###

memo = {}
def f(x):
    if x==0:
        return 0
    if x==1:
        return 1
    if x in memo:
        return memo[x]
    k = sum(list(map(int,list(bin(x)[2:]))))
    memo[x] = 1+f(x%k)
    return memo[x]
    
N = int(input())
X = input().strip()
n = sum(list(map(int,list(X))))
if n==0:
    for i in range(N):
        print(1)
elif n==1:
    D = {i:0 for i in range(N)} # mod n+1
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            print(0)
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))
else:
    C = {i:0 for i in range(N)}  # mod n-1
    C[0] = 1
    for i in range(1,N):
        C[i] = (C[i-1]*2)%(n-1)
    D = {i:0 for i in range(N)} # mod n+1
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt0 = 0
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            cnt0 = (cnt0+C[N-1-i])%(n-1)
            cnt1 = (cnt1+D[N-1-i])%(n+1)
    for i in range(N):
        if X[i]=="1":
            a = (cnt0-C[N-1-i])%(n-1)
            print(1+f(a))
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))
# -*- coding: utf-8 -*-
from collections import Counter
from collections import deque

H,W = list(map(int, input().rstrip().split()))
S_list = [list(input().rstrip()) for i in range(H)]
#-----

def checkRoute(matrix):
    # queue = [ ( (row, column),step ) ]
    # deque = [ ( (int, int   ),int ) ]
    queue = deque([  ( (1,1),1 )  ])

    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    visited = set()
    
    while queue:
        (r,c),step = queue.popleft()
        
        for d in delta:
            next_r = r + d[0]
            next_c = c + d[1]
            
            if (next_r == H) and (next_c == W):
                return step+1
            
            if (1 <= next_r <= H) and (1 <= next_c <= W) and \
               (next_r, next_c) not in visited  and \
               matrix[next_r][next_c] == ".":
            
                queue.append( ( (next_r, next_c), step+1 ) )
                visited.add( (next_r, next_c) )


#-----
# add dummy node(Black area) around the original data
for i in range(len(S_list)):
    S_list[i] = ["#"] + S_list[i][:] + ["#"]
    
S_list = [["#"]*(W+2)] + S_list[:] + [["#"]*(W+2)]
#-----

cnt_dic = Counter( sum(S_list,[]) )
min_step = checkRoute(S_list)
print( cnt_dic["."] - min_step )


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
from collections import deque

H,W = list(map(int, input().rstrip().split()))
S_list = [list(input().rstrip()) for i in range(H)]
#-----

def checkRoute(matrix):
    # queue = [ ( (row, column),step ) ]
    # deque = [ ( (int, int   ),int ) ]
    queue = deque([  ( (1,1),1 )  ])

    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    visited = set()
    
    while queue:
        (r,c),step = queue.popleft()
        
        for d in delta:
            next_r = r + d[0]
            next_c = c + d[1]
            
            if (next_r == H) and (next_c == W):
                return step+1
            
            if (1 <= next_r <= H) and (1 <= next_c <= W) and \
               (next_r, next_c) not in visited  and \
               matrix[next_r][next_c] == ".":
            
                queue.append( ( (next_r, next_c), step+1 ) )
                visited.add( (next_r, next_c) )

    return -1

#-----
# add dummy node(Black area) around the original data
for i in range(len(S_list)):
    S_list[i] = ["#"] + S_list[i][:] + ["#"]
    
S_list = [["#"]*(W+2)] + S_list[:] + [["#"]*(W+2)]
#-----

cnt_dic = Counter( sum(S_list,[]) )
min_step = checkRoute(S_list)

if min_step != -1:
    print( cnt_dic["."] - min_step )
else:
    print(-1)
N = int(input())
p = []
for i in range(N):
    p.append(int(input()))

ans = sum(p) - max(p)/2

print(int(ans))


### FIXED CODE ###

def main():
    #a,b = list(map(int, input().split()))
        
    #print(int(a + (b/2)))
    n = int(input())
    if n == 25:
        print('Christmas')
    if n == 24:
        print('Christmas Eve')
    if n == 23:
        print('Christmas Eve Eve')
    if n == 22:
        print('Christmas Eve Eve Eve')

if __name__ == '__main__':

    main()
a=[]
while True:
 n=input()
 if n==0: break
 a.append(n)
for i in range(len(a)):
 print(f'Case {i+1}: {a[i]}')

### FIXED CODE ###

import sys
i=1
for e in sys.stdin:
 if'0\n'==e:break
 print(f'Case {i}: {e[:-1]}');i+=1