Harryxun/stf_run huggingface dataset:
from functools import lru_cache

# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))

INF = 10**15
# 各数字の消費マッチ棒
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)


# N=nのときの解に対応するベクトルを返す
@lru_cache(maxsize=None)
def dfs(n):
    return (
        [-INF for _ in range(9)] if n < 0 else
        [0 for _ in range(9)] if n == 0 else
        max(
            (
                [
                    t + 1 if i == a else t
                    for i, t in enumerate(dfs(n - C[a]), start=1)
                ]
                for a in A
            ),
            key=lambda x: [sum(x)] + list(reversed(x))
        )
    )

# 出力
ans = ''.join(str(a) * dfs(N)[a - 1] for a in sorted(A, reverse=True))
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)

dp = [[0 for _ in range(10)] for _ in range(N + 1)]
dp2 = [-100 for _ in range(N + 1)]
dp2[0] = 0

for i in range(2, N+1):
    x = -1
    opt = -1
    for a in A:
        c = C[a]
        if i >= c and (dp2[i - c] > opt or (dp2[i - c] == opt and a > x)):
            x = a
            opt = dp2[i - c]
    if x == -1:
        continue
    dp2[i] = dp2[i - C[x]] + 1
    c = C[x]
    for a in A:
        if x == a:
            dp[i][a] = dp[i - c][a] + 1
        else:
            dp[i][a] = dp[i - c][a]

ans = ''.join(str(a) * dp[N][a] for a in sorted(A, reverse=True))
print(ans)
firstString = input()
secondString = input()
diff = 0
for i in range(len(firstString)):
    if firstString[i] != secondString[i]:
        diff += 1
print(diff)

### FIXED CODE ###

input = int(input())
print (input + input ** 2 + input ** 3)
from collections import Counter
N = int(input())
X = []
for i in range(N):
    x,y = map(int,input().split())
    X.append((x,y))
kouho = []
for i in range(N):
    for j in range(N):
        if i==j:continue
        kouho.append((X[i][0]-X[j][0],X[i][1]-X[j][1]))
C = Counter(kouho)
print(N-max(C.values()))

### FIXED CODE ###

from collections import Counter
N = int(input())
X = []
for i in range(N):
    x,y = map(int,input().split())
    X.append((x,y))
kouho = []
for i in range(N):
    for j in range(N):
        if i==j:continue
        kouho.append((X[i][0]-X[j][0],X[i][1]-X[j][1]))
C = Counter(kouho)
if len(C)==0:print(1)
else:print(N-max(C.values()))
N, K = map(int, input().split())
l = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
for _ in range(K):
    l.remove(int(input()))
n = [int(x) for x in str(N)]
c = len(n)

max = l[0]
min = l[-1]
if N > 1111 * max:
    b = 10000*min([i for i in l if i>0]) + 1111*min
else:
    a = [max] * c
    for j in range(c):
        if a[j] > n[j]:
            a[j] = min([i for i in l if i>=n[j]])
    b = ""
    for j in range(c):
        b += str(a[j])
    b = int(b)

print(b)


### FIXED CODE ###

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

for i in range(N, 100000):
    for j in D:
        if j in str(i):
            break
    else:
        print(i)
        break
n,k=int(input().split())
s=input()
s[k-1]=s[k-1].lower()
print(s)

### FIXED CODE ###

n,k=map(int,input().split())
s=input()
new=s[k-1:k]
news=new.lower()
print(s[:k-1]+news+s[k:])
char=input()

week=("SUN","MON","TUE","WED","THU","FRI","SAT")

print(7-week.index())


### FIXED CODE ###

char=input()

week=("SUN","MON","TUE","WED","THU","FRI","SAT")

print(7-week.index(char))
n=str(input())
print('Yes' if 9 in n else "No")

### FIXED CODE ###

n=str(input())
print('Yes' if "9" in n else "No")
import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7)

### FIXED CODE ###

import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7))
n,m = input().split();
a = input().splite();

a_sum = sum(a);

rest_day = int(n) - a_sum

if rest_day < 0:
    rest_day = -1

return rest_day

### FIXED CODE ###

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

a_sum = sum(a);

if n - a_sum < 0:
    print(-1)
else:
    print(n-a_sum)
import numpy as np

n, m = map(int, input().split())
a = []
b = []
for i in range(n):
    a += [list(map(int, input().split()))]
for i in range(m):
    b += [int(input())]
a = np.array(a)
b = np.array(b)
b.reshape(m, 1)

c = np.dot(a, b)
for i in range(len(c)):
    print(c[i])



### FIXED CODE ###

n, m = map(int, input().split())
A = [input().split() for _ in range(n)]
b = [input()for _ in range(m)]
for a in A:
    print(sum(int(x)*int(y) for x, y in zip(a,b)))
#import sys
#input = sys.stdin.readline
from collections import Counter
def func(x):
    cnt = 0
    y = x
    while x > 0:
        if x%2 == 1:
            cnt += 1
        x //= 2
    return y%cnt
        
def main():
    N = int( input())
    X = list( map( int, list( input())))
    base_plus = 0
    base_minus = 0
    r = 1
    one = Counter(X)[1]
    for x in X[::-1]:
        base_plus += r*x
        base_plus %= one+1
        r *= 2
        r %= one+1
    r = 1
    for x in X[::-1]:
        base_minus += r*x
        base_minus %= one-1
        r *= 2
        r %= one-1

    ANS = [0]*N
    # print(base)
    # print(bin(base))
    for i in range(N):
        if one == 1:
            if X[i] == 1:
                ANS[i] = 0
                continue
        if X[i] == 1:
            xi = (base_minus -  pow(2,N-1-i,one-1))%(one-1)
            # print(i, bin(base -  pow(2,N-1-i)), one-1)
        else:
            xi = (base_plus +  pow(2,N-1-i,one+1))%(one+1)
            # print(i, bin(base +  pow(2,N-1-i)), one+1)
        # print(i,xi)
        if xi == 0:
            ANS[i] = 1
            continue
        ans = 1
        while xi > 0:
            ans += 1
            xi = func(xi)
        ANS[i] = ans
    print("\n".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

#import sys
#input = sys.stdin.readline
from collections import Counter
def func(x):
    cnt = 0
    y = x
    while x > 0:
        if x%2 == 1:
            cnt += 1
        x //= 2
    return y%cnt
        
def main():
    N = int( input())
    X = list( map( int, list( input())))
    base_plus = 0
    base_minus = 0
    r = 1
    one = Counter(X)[1]
    for x in X[::-1]:
        base_plus += r*x
        base_plus %= one+1
        r *= 2
        r %= one+1
    r = 1
    if one > 1:
        for x in X[::-1]:
            base_minus += r*x
            base_minus %= one-1
            r *= 2
            r %= one-1

    ANS = [0]*N
    # print(base)
    # print(bin(base))
    for i in range(N):
        if one == 1:
            if X[i] == 1:
                ANS[i] = 0
                continue
        if X[i] == 1:
            xi = (base_minus -  pow(2,N-1-i,one-1))%(one-1)
            # print(i, bin(base -  pow(2,N-1-i)), one-1)
        else:
            xi = (base_plus +  pow(2,N-1-i,one+1))%(one+1)
            # print(i, bin(base +  pow(2,N-1-i)), one+1)
        # print(i,xi)
        if xi == 0:
            ANS[i] = 1
            continue
        ans = 1
        while xi > 0:
            ans += 1
            xi = func(xi)
        ANS[i] = ans
    print("\n".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()
def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    if (l[1]-weight)%2 == 0:
      color[l[0]] = color[node]
    else:
      color[l[0]] = int(not color[node])
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)
color[1] = 0
for i in range(1,N+1):
  tree[i] = []
  
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
dfs(1,0)
print('\n'.join(map(str,color[1:])))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)

def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    if l[1]%2 == 0:
      color[l[0]] = color[node]
    else:
      color[l[0]] = int(not color[node])
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)

for i in range(1,N+1):
  tree[i] = []
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
  
color[1] = 0
dfs(1,0)
color = [c  if c>-1 else 0 for c in color]
print('\n'.join(map(str,color[1:])))
n,k = map(int,input().split())
a = [int(i)-1 for i in input().split()]
loc = 0
cnt1 = 0
seen = [False]*n
seen[0] = True
while not seen[loc]:
    loc = a[loc]
    cnt1 += 1
    if cnt1 == k:
        print(loc+1)
        exit()
cnt2 = 0
x = loc
while loc != x:
    loc = a[loc]
    cnt2 += 1
cnt1 -= cnt2
k = (k-cnt1)%cnt2
loc = 0
while k > 0:
    loc = a[loc]
    k -= 1
print(loc+1)

### FIXED CODE ###

n,k = map(int,input().split())
a = [int(i)-1 for i in input().split()]
loc = 0
lst = [False]*n
lst[0] = True
while True:
    if lst[a[loc]]:
        x = a[loc]
        break
    loc = a[loc]
    lst[loc] = True
cnt = 0
loc = 0
if x != 0:
    while True:
        loc = a[loc]
        cnt += 1
        if loc == x: break
cnt2 = 0
while True:
    loc = a[loc]
    cnt2 += 1
    if loc == x: break
if k >= cnt:
    k -= cnt
    k %= cnt2
    loc = x
    while k > 0:
        loc = a[loc]
        k -= 1
else:
    loc = 0
    while k > 0:
        loc = a[loc]
        k -= 1
print(loc+1)
for i in range(int(raw_input())):
&#160;&#160;&#160;&#160;sides = map(int, raw_input().split())
&#160;&#160;&#160;&#160;if sides[0]**2 == sides[1]**2 + sides[2]**2 or\
&#160;&#160;&#160;&#160;&#160;&#160;&#160;sides[1]**2 == sides[2]**2 + sides[0]**2 or\
&#160;&#160;&#160;&#160;&#160;&#160;&#160;sides[2]**2 == sides[0]**2 + sides[1]**2:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;print "YES"
&#160;&#160;&#160;&#160;else:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;print "NO"

### FIXED CODE ###

x = int(input())
for a in range(x):
 y = map(int,raw_input().split())
 y.sort()
 if y[2]**2-y[1]**2 == y[0]**2:
  print "YES"
 else:
  print "NO"
#import sys
#sys.setrecursionlimit(20000)

def solve(i,m):
    if m==0:
        return True
    if m<0:
        return False
    if i>=n:
        return False
    res=solve(i+1,m) or solve(i+1,m-A[i])
    return res

n=int(input())
A=[]*n
A=list(input().split())
for i in range(n):
    A[i]=int(A[i])
m=int(input())
B=list(input().split())
ans=[]
for i in range(m):
    B[i]=int(B[i])
    ans=solve(0,B[i])
    if ans==True:
        print("yes")
    else:
        print("no")



### FIXED CODE ###

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

T = [[0]*2001 for i in range(n)]

T[0][0] = 1
T[0][A[0]] = 1
for i in range(1,n):
    for j in range(2001):
        T[i][j] = T[i-1][j]
        if (j - A[i] >=0) and (T[i-1][j-A[i]] == 1):
            T[i][j] = 1
    
for i in range(m):
    if T[n-1][B[i]] == 1: print("yes")
    else: print("no")
N = int(input())
A = list(map(int, input().split()))
chinpo = 0

for i in range(N-1):

    if A[i+1] > A[i+2]:
        A[i+1] -= 1
        if A[i+2] >= A[i+1]:
            chinpo += 1
    else:
        chinpo += 1

if chinpo == N-1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
H = []
H = input().split(" ")
for i in range(N):
    H[i] = int(H[i])-1

ochinchin = True
for i in range(1, N):
    if H[i] < H[i-1]:
        H[i] += 1
        if H[i] < H[i-1]:
            ochinchin = False
            break
            

if ochinchin:
    print("Yes")
else:
    print("No")
import sys
sys.setrecursionlimit(40000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))



### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)
import sys
 
def main():
  N, W = map(int, input().split())
  w = [0]*N
  v = [0]*N
  for i in range(N):
          w[i], v[i] = map(int, sys.stdin.readline().split())
 
  #WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
 
 
  dp = [[0]*(N+1) for j in range(W+1)]
 
  for i in range(1, W+1):
          for j in range(1, N+1):
                  if i - w[j-1]>=0:
                  #if i - WV[j-1][0]>=0:
                          dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1], dp[i][j-1])
                          #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                  else:
                          dp[i][j] = dp[i][j-1]
 
  print(dp[W][N])
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

N = int(input())

dp = [[0]*3  for i in range(N)]

dp[0][0], dp[0][1], dp[0][2] = map(int, sys.stdin.readline().split())

tmp = [0, 0, 0]

for i in range(1, N):
    tmp[0], tmp[1], tmp[2] = map(int, sys.stdin.readline().split())
    for j in range(3):
        dp[i][j] = max(dp[i-1][(j+1)%3]+tmp[j], dp[i-1][(j+2)%3]+tmp[j])

print(max(dp[N-1]))
import math

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

mod = 10**9 + 7

f = math.factorial(n-1)

l = []
for i in range(n-1):
    d = x[i+1] - x[i]
    l.append(d)

# print(l)

count = 0
k = f
plus = 0
for i in range(1,n):
    # print(k)
    k = f + plus
    count += l[i-1] * k
    plus += f / (i+1)

print(int(count)%mod)

### FIXED CODE ###

import math

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

mod = 10**9 + 7

f = math.factorial(n-1)
f %= mod

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

l = []
for i in range(n-1):
    d = x[i+1] - x[i]
    l.append(d)

# print(l)

count = 0
k = f
plus = 0
for i in range(1,n):
    # print(k)
    k = f + plus
    count += l[i-1] * k
    plus += f * modinv(i+1,mod)

print(int(count)%mod)
l=[]
for i in range(3):
    l.append(list(map(int, input().split())))
n = int(input())
for i in range(n):
    m = int(input())

    for j in range(3):
        for k in range(3):
            if l[j][k] == m:
                l[j][k] = -1
o=0
p=0
for j in range(3):
    for k in range(3):
        o+=l[j][k]
        p+=l[k][j]
    if o==-3 or p==-3:
        print('Yes')
        exit()
    o=0
    p=0
if l[0][0]+l[1][1]+l[2][2]==-3 or l[0][2]+l[1][1]+l[2][0]==-3:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

q, mod = divmod(int(input()), 2)
if mod == 1:
  q+=1
print(q)
import math
try:
    a,b,c,d=map(int,input().split())

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

    def ans_cnt(i,y,z):
        return i - (i//y + i//z - i//lcm(y,z))
    
except EOFError:
    pass

print(ans_cnt(b,c,d)-ans_cnt(a-1,c,d))

### FIXED CODE ###

from fractions import gcd
a,b,c,d=map(int,input().split())

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

def ans_cnt(i,y,z):
    return i - (i//y + i//z - i//lcm(y,z))

print(ans_cnt(b,c,d)-ans_cnt(a-1,c,d))
s=list(input())
x,y = map(int, input().split())
s.append('T')
x1=[]
y1=[]

count=0
u=0
for i in range(len(s)):
    if s[i]=='F':
        count+=1
    else:
        if u%2==0:
            x1.append(count)
            u+=1
            count=0
        else:
            y1.append(count)
            u+=1
            count=0


dpx=[[0 for i in range(sum(x1)*2+2)] for j in range(len(x1)+1)]
if len(x1)<=2:
    dpx.append(0)
dpx[1][0]=1
for i in range(1,len(x1)):
    for j in range(-(sum(x1))-1,sum(x1)+1):
        if j-x1[i]>=-sum(x1)-1 and j+x1[i]<sum(x1)+1:
            dpx[i + 1][j] = dpx[i][j + x1[i]] or dpx[i][j-x1[i]] or dpx[i][j]
        elif j-x1[i]<-sum(x1)-1:
            dpx[i + 1][j] =  dpx[i][j+x1[i]] or dpx[i][j]
        elif j+x1[i]>=sum(x1)+1:
            dpx[i + 1][j] = dpx[i][j-x1[i]] or dpx[i][j]
        else:
            dpx[i + 1][j] = dpx[i][j]





dpy=[[0 for i in range(sum(y1)*2+2)] for j in range(len(y1)+1)]
if len(y1)==0:
    dpy.append(0)
dpy[0][0]=1

for i in range(len(y1)):
    for j in range(-sum(y1)-1,sum(y1)+1):
        if j-y1[i]>=-sum(y1)-1 and j+y1[i]<sum(y1)+1:
            dpy[i + 1][j] = dpy[i][j - y1[i]] or dpy[i][j+y1[i]] or dpy[i][j]
        elif j-y1[i]<-sum(y1)-1:
            dpy[i + 1][j] = dpy[i][j + y1[i]] or dpy[i][j]
        elif j+y1[i]>=sum(y1)+1:
            dpy[i + 1][j] = dpy[i][j - y1[i]] or dpy[i][j]
        else:
            dpy[i + 1][j] =  dpy[i][j]




if dpy[len(y1)][y]==1 and dpx[len(x1)][x-x1[0]]==1:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys
input = sys.stdin.readline
s=list(input())
x,y = map(int, input().split())
y=abs(y)
s.append('T')
x1=[]
y1=[]

count=0
u=0
for i in range(len(s)):
    if s[i]=='F':
        count+=1
    else:
        if u%2==0:
            x1.append(count)
            u+=1
            count=0
        else:
            y1.append(count)
            u+=1
            count=0
v=sum(x1)
w=sum(y1)
v-=x1[0]
x-=x1[0]
x1.pop(0)
x=abs(x)
if v<x or w<y:
    print('No')
    exit()

dpx=[[0 for i in range(v+1)] for j in range(len(x1)+1)]
dpx[0][-1]=1

for i in range(len(x1)):
    for j in range(v+1):
        if dpx[i][j]==1:
            if j-2*x1[i]>=0:
                dpx[i+1][j-2*x1[i]]=1
            dpx[i+1][j]=1

if len(y1)==0:
    y1.append(0)
dpy=[[0 for i in range(w+1)] for j in range(len(y1)+1)]
dpy[0][-1]=1

for i in range(len(y1)):
    for j in range(w+1):
        if dpy[i][j]==1:
            if j-2*y1[i]>=0:
                dpy[i+1][j-2*y1[i]]=1
            dpy[i+1][j]=1

if dpy[-1][y]==1 and dpx[-1][x]==1:
    print('Yes')
else:
    print('No')
N = int(input())
ls = [int(i) for i in input().split()]
if len(ls) == 1:
  print(ls[0]*2)
else:
  als = [ls[0]]
  for n in range(1, N-1):
    als.append(min(ls[n-1], ls[n]))
  als.append(ls[-1])
  print(sum(als))

### FIXED CODE ###

n = int(input())
print(n*n*n)
import sys
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  A = []
  for _ in [0]*h:
    A.append(map(int, list(raw_input().replace(".", "1").replace("*", "0"))))
  B = A[:]
  C = []
  for j in range(1,h):
    m=[]
    for i in range(j,h):
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x
      m.append(max("".join(map(str, x)).split("0")))
    C.append(len(max(m))*(j+1))
  print max(C)

### FIXED CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, range(h+1))])
  print s
h,w=map(int,input().split())
n=int(input())
c=list(map(int,input().split()))
d=[]
for i in range(1,n+1):
  for j in c[i-1]:
    d.append(i)
ansl=[[0]*w for i in range(h)]
for i in range(h):
  if i%2==0:
    for j in range(w):
      ansl[i][j]=str(d[i*w+j])
  else:
    for j in range(w):
      ansl[i][w-j-1]=str(d[i*w+j])
for j in ansl:
  print(" ".join(j))

### FIXED CODE ###

h,w=map(int,input().split())
n=int(input())
c=list(map(int,input().split()))
d=[]
for i in range(1,n+1):
  for j in range(c[i-1]):
    d.append(i)
ansl=[[0]*w for i in range(h)]
for i in range(h):
  if i%2==0:
    for j in range(w):
      ansl[i][j]=str(d[i*w+j])
  else:
    for j in range(w):
      ansl[i][w-j-1]=str(d[i*w+j])
for j in ansl:
  print(" ".join(j))
if ("hi" in S):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import re
index = re.fullmatch(r'(hi)+', input())
if index:
    print("Yes")
else:
    print("No")
inf = pow(10, 9)+7

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
    return int(result)


n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()

ans = 0
key = nCr(n-1, k-1)
for i in range(n-k+1):
    ans += ((a[-i-1] - a[i])%inf)*(key%inf)
    ans %= inf
    if n-i-1 != 0:
	    key = key*(n-k-i)//(n-1-i)
    else:
        break
print(ans)

### FIXED CODE ###

inf = pow(10, 9)+7

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()

ans = 0
comb = 1
for i in range(k, n+1):
    ans += (a[i-1]-a[-i])*comb
    ans %= inf
    comb = (comb * i * pow(i-k+1, inf-2, inf))%inf
print(ans)
a, b = map(int,input().split())
if a > b:
    print 'a > b'
elif a < b:
    print 'a < b'
else:
    print 'a == b'

### FIXED CODE ###

a, b = map(int,input().split())
 
if a > b:
    print('a > b')
elif a < b:
    print('a < b')
else:
    print('a == b')
n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n):
    minj=i
    for j in range(i+1,n-1):
        if a[minj]>a[j]:
            minj=j
    if i!=minj:
        a[i],a[minj]=a[minj],a[i]
            b+=1
print(*a)
print(b)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n):
    minj=i
    for j in range(i,n):
        if a[minj]>a[j]:
            minj=j
    if i!=minj:
        a[i],a[minj]=a[minj],a[i]
        b+=1
print(*a)
print(b)