Harryxun/stf_run huggingface dataset:
import numpy as np
N ,K = list(map(int, input().split()))
p = list(map(lambda x: (1+int(x))/2, input().split()))
s = [0]*N
s[0]=p[0]
sum = 0
for i in range(1,N):
  s[i] = s[i-1]+p[i]

l = []
for i in range(N-K):
  l.append(s[i+K]-s[i])
  
print(max(l))

### FIXED CODE ###

N ,K = list(map(int, input().split()))
p = list(map(lambda x: (1+int(x))/2, input().split()))
s = [0]*N
s[0]=p[0]
for i in range(1,N):
  s[i] = s[i-1]+p[i]

l = [s[K-1]]
for i in range(N-K):
  l.append(s[i+K]-s[i])

print(max(l))
n = int(input())
a,b,c = [],[],[]
for i in range(n):
    line = input()
    line = line.strip("\n").split(" ")
    a.append(int(line[0]))
    b.append(int(line[1]))
    c.append(int(line[2]))

def helper(i, prev=None, memo={}):

    if (i,prev) in memo: return memo[(i,prev)]

    if i == n:
        return 0

    happ1, happ2, happ3 = 0,0,0
    if prev != 'a':
        happ1 = a[i] + helper(i+1, 'a', memo)
    if prev != 'b':
        happ2 = b[i] + helper(i+1, 'b', memo)
    if prev != 'c':
        happ3 = c[i] + helper(i+1, 'c', memo)

    ret = max(happ1, happ2, happ3)
    memo[(i,prev)] = ret
    return ret

print(helper(0))

### FIXED CODE ###

n = int(input())
a,b,c = [],[],[]
for i in range(n):
    line = input()
    line = line.strip("\n").split(" ")
    a.append(int(line[0]))
    b.append(int(line[1]))
    c.append(int(line[2]))

def bottomup(a, b, c):
    dp = [[0 for _ in range(3)] for _ in range(n)]
    
    dp[(n-1)] = [a[n-1], b[n-1], c[n-1]]

    for i in range(n-2,-1,-1):
        dp[i][0] = a[i] + max(dp[i+1][1:])
        dp[i][1] = b[i] + max(dp[i+1][0], dp[i+1][2])
        dp[i][2] = c[i] + max(dp[i+1][:2])
    
    return max(dp[0])
    
print(bottomup(a,b,c))
import sys
sys.setrecursionlimit(100000000)

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

A = [0]*M

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

A.append(N+1)

# DP version
DP = [0]*N
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

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

if M == 0:
    A = []
else:
    A = [0]*M
    for i in range(M):
        A[i] = int(input())

A.append(N+1)

# DP version
DP = [0]*(N+1)
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
#DP[2] = 2

for i in range(2,N+1):
    DP[i] = DP[i-1] + DP[i-2]

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    if NOW == N:
        break
    
print(total_comb % 1000000007 )
import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
q=0
count=0
for i in range(0,M):
  p.append(list(map(int, input().split())))
for i in range(0,M):
  q+=p[i][0]-p[i][1]
if q%2==1:
  print("NO")
else:
  m=int(M/100)
  for j in range(0,M,m):
    for i in range(0,M):
      if p[i][0]==j or p[i][1]==j:
        count+=1
    if count%2==1:
      print("NO")
      sys.exit()
  else: 
    print("YES")

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
# 整数の入力
A, B, C= map(int, input().split())
# 出力
if A==B and B==C:
 if A%2 ==0 and B%2==0 and C%2==0:
  print(-1)
  sys.exit()
count=0
while True:
 if A%2 ==1 or B%2==1 or C%2==1:
  print(count)
  sys.exit()
 else:
  A_a=B/2+C/2
  B_a=A/2+C/2
  C_a=A/2+B/2
  A=A_a
  B=B_a
  C=C_a
  count+=1
n=int(input())
a=list(map(int, input().split()))

money=1000

chart=[a[0]]
flag=0

for i in range(n):
    if flag==0:
        if a[i]>chart[-1]:
            chart.append(a[i])
            flag=1

    else:
        if a[i]<chart[-1]:
            cnt=0
            M=0
            for j in range(i, n+1):
                if a[i]<a[j]:
                    cnt+=1
                    if M<a[j]:
                        M=a[j]
            
            if cnt==0:
                break
            elif cnt==1:
                chart.append(M)
                break
            else:
                flag=0

days=len(chart)

for day in range(days):
    if day%2==0:
        contact=money//chart[i]
        money-=contact*chart[i]
    
    else:
        money+=contact*chart[i]

print(money)

### FIXED CODE ###

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

money=1000

chart=[a[0]]

for kabuka in a:
    if kabuka==chart[-1]:
        continue
    else:
        chart.append(kabuka)

days=len(chart)
kabu=0

if days==1:
    print(money)
    exit()

for i in range(days):
    if i==0:
        if chart[0]<chart[1]:
            kabu=money//chart[0]
            money%=chart[0]

    elif i==days-1:
        money+=kabu*chart[i]
        kanu=0
    
    else:
        if chart[i-1]<chart[i] and chart[i]>chart[i+1]:
            money+=kabu*chart[i]
            kabu=0

        if chart[i-1]>chart[i] and chart[i]<chart[i+1]:
            kabu=money//chart[i]
            money%=chart[i]

print(money)
import functools
import math

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

num = 1

for i in range(N):
    B = A[:]
    B.pop(i)

    gcd = functools.reduce(math.gcd, B)
    if num < gcd:
        num = gcd

print(num)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
gcd_list=[]
reverse_gcd_list = []


def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

gcd_list.append(A[0])
reverse_gcd_list.append(A[-1])

for i in range(1,N):
    gcd_list.append(gcd(gcd_list[i-1], A[i]))
    # reverse_gcd_list.insert(0,gcd(reverse_gcd_list[0], A[-1-i]))
    reverse_gcd_list.append(gcd(reverse_gcd_list[-1], A[-1-i]))

reverse_gcd_list.reverse()
num = [gcd_list[-2], reverse_gcd_list[1]]
for i in range(N-2):
    num.append(gcd(gcd_list[i], reverse_gcd_list[i+2]))

print(max(num))
from scipy.special import comb
N,P=map(int,input().split())
A=list(map(lambda x:int(x)%2,input().split()))
A0,A1=A.count(0),A.count(1)
if P==1:
    if not A1:
        print(0)
        exit()
value0=0
for i in range(0,A0+1):
    #print(value0)
    value0+=comb(A0, i, exact=True)
value1=0
for i in range(2-P,A1+1,2):
    #print(value1,i)
    #print(comb(A1, i, exact=True))
    value1+=comb(A1, i, exact=True)
print(value0*value1+(1 if not P else 0))


### FIXED CODE ###

from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N,P=map(int,input().split())
A=list(map(lambda x:int(x)%2,input().split()))
A0,A1=A.count(0),A.count(1)
if P==1:
    if not A1:
        print(0)
        exit()
value0=0
for i in range(0,A0+1):
    value0+=comb(A0, i)
value1=(1 if not P else 0)
for i in range(2-P,A1+1,2):
    value1+=comb(A1, i)
print(value0*value1)
N = int(input())
A = list(map(int, input().split()))
         
import math
from functools import reduce

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

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

print(gcd_list(A))


### FIXED CODE ###

import functools
import math
import fractions

N = int(input())
A = list(map(int, input().split()))
         
a = functools.reduce(fractions.gcd, A)
print(a)
import math
b = list(map(int,input().split()))
ans=0
check=0
A=0
C=b[1]
max = b[2]//b[1]

for i in range(max+1):
    A=b[1]-1
    if A>0:
        check = math.floor((b[0]*A)/C) - b[0]*math.floor(A/C)
        if check > ans:
            ans=check
    b[1]+=b[1]
print(ans)

### FIXED CODE ###

import math
b = list(map(int,input().split()))
ans=0
check=0
if b[2]>b[1]-1:
    check = math.floor((b[0]*(b[1]-1))/b[1]) - b[0]*math.floor((b[1]-1)/b[1])
else:
    check = math.floor((b[0]*b[2])/b[1]) - b[0]*math.floor(b[2]/b[1])
if check>ans:
    ans=check
print(ans)
import numpy as np

n, m = list(map(int, input().split()))
mat = np.zeros((m, 2))
for i in range(m):
	mat[i, 0], mat[i, 1] = list(map(int, input().split()))
mat = np.c_[mat, np.array(range(m))]
mat = mat[mat[:, 1].argsort()]
cnt = np.zeros(m)
res = []
for i, j in mat[:, :2]:
	i = int(i)
	cnt[i] += 1
	res.append('{0:06d}{1:06d}'.format(i, int(cnt[i])))

for i in np.argsort(mat[:, 2]):
	print(res[int(i)])


### FIXED CODE ###

import numpy as np

n, m = list(map(int, input().split()))
mat = np.zeros((m, 3))
for i in range(m):
	mat[i, 0], mat[i, 1] = list(map(int, input().split()))
	mat[i, 2] = i
mat = mat[mat[:, 1].argsort()]
cnt = np.zeros(n+1)
res = []
for i in mat[:, 0]:
	i = int(i)
	cnt[i-1] += 1
	res.append('{0:06d}{1:06d}'.format(i, int(cnt[i-1])))

for idx in np.argsort(mat[:, 2]):
	print(res[int(idx)])
"""D."""

import sys

#def input() -> str:  # noqa: A001
#    """Input."""
#    return sys.stdin.readline()[:-1]


class UnionFindTree:
    """Union-find."""

    def __init__(self, n: int) -> None:
        """Init."""
        self.n = n
        self.parent = [-1] * n

    def find_root(self, x: int) -> int:
        """Find root."""
        parent = self.parent[x]
        if parent < 0:
            return x
        return self.parent[self.find_root(parent)]

    def union(self, x: int, y: int) -> None:
        """Unite two trees."""
        x_root = self.find_root(x)
        y_root = self.find_root(y)

        if x_root == y_root:
            return

        if x_root > y_root:
            x_root, y_root = y_root, x_root

        self.parent[x_root] += self.parent[y_root]
        self.parent[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.parent[self.find_root(x)] * -1

    def is_same(self, x: int, y: int) -> bool:
        """Is same group."""
        return self.find_root(x) == self.find_root(y)


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

tree = UnionFindTree(n)

for _ in range(m):
    a, b = map(int, input().split(' '))
    tree.union(a - 1, b - 1)

ans = 0

for i in range(n):
    ans = max(ans, tree.get_size(i))

print(ans)


### FIXED CODE ###

"""D."""

import sys

#def input() -> str:  # noqa: A001
#    """Input."""
#    return sys.stdin.readline()[:-1]


class UnionFindTree:
    """Union-find."""

    def __init__(self, n: int) -> None:
        """Init."""
        self.n = n
        self.rank = [-1] * n

    def find_root(self, x: int) -> int:
        """Find root."""

        if self.rank[x] < 0:
            return x

        self.rank[x] = self.find_root(self.rank[x])
        return self.rank[x]

    def union(self, x: int, y: int) -> None:
        """Unite two trees."""
        x_root = self.find_root(x)
        y_root = self.find_root(y)

        if x_root == y_root:
            return

        if x_root > y_root:
            x_root, y_root = y_root, x_root

        self.rank[x_root] += self.rank[y_root]
        self.rank[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.rank[self.find_root(x)] * -1

    def is_same(self, x: int, y: int) -> bool:
        """Is same group."""
        return self.find_root(x) == self.find_root(y)


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

tree = UnionFindTree(n)

for _ in range(m):
    a, b = map(int, input().split(' '))
    tree.union(a - 1, b - 1)

ans = 0

for i in range(n):
    ans = max(ans, tree.get_size(i))

print(ans)
import collections
mod = 1000000007

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

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * collections.Counter(n_colors)[x]) % mod
	n_colors[n_colors.index(x)] += 1

print(cnt)

### FIXED CODE ###

mod = 10 ** 9 + 7
n = int(input())
nums = list(map(int, input().split()))

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * len([y for y in n_colors if x == y])) % mod
	if cnt == 0:
		break
	n_colors[n_colors.index(x)] += 1

print(cnt)
from collections import defaultdict

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]

sushi = sorted(sushi, key = lambda x: x[1], reverse = True)
types = set()
max_vals = [0]
other_vals = [0]

for typ, val in sushi:
    if typ not in types:
        max_vals.append(max_vals[-1] + val)
        types.add(typ)
    else:
        other_vals.append(other_vals[-1] + val)

max_score = 0
for k in range(1, K + 1):
    if K - k < len(other_vals):
        score = max_vals[k] + other_vals[K - k] + k ** 2
        max_score = max(max_score, score)

print(max_score)


### FIXED CODE ###

from collections import defaultdict

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]

sushi = sorted(sushi, key = lambda x: x[1], reverse = True)
types = set()
max_vals = [0]
other_vals = [0]

for typ, val in sushi:
    if typ not in types:
        max_vals.append(max_vals[-1] + val)
        types.add(typ)
    else:
        other_vals.append(other_vals[-1] + val)

max_score = 0
for k in range(1, K + 1):
    if K - k < len(other_vals) and k < len(max_vals):
        score = max_vals[k] + other_vals[K - k] + k ** 2
        max_score = max(max_score, score)

print(max_score)
N, K = map(int, raw_input().split())

if K<=(N-1)*(N-2)/2:
  exit(-1)
else:
  print "-1"


### FIXED CODE ###

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

if K<=(N-1)*(N-2)/2:
  E = []
  for i in range(N-1):
    for j in range(i):
      E += [(j, i)]
  E = E[:(N-1)*(N-2)/2-K]
  for i in range(N-1):
    E += [(i, N-1)]
  print len(E)
  for e in E:
    print e[0]+1, e[1]+1
else:
  print "-1"
def main():
	    str = input()
	    YY = []
	    MM = []
	    YYMM_flg = False
	    MMYY_flg = False
	    AMB_flg = False
	    NA_flg = False

	    for i in range(2):
	    	YY.append(str[i])

	    for i in range(2, 4):
	    	MM.append(str[i])

	    yy = int(''.join(YY))
	    mm = int(''.join(MM))

	    if (yy >= 1 and yy <= 12) and (mm >= 1 and mm <= 12):
	    	AMB_flg = True
	    elif (mm >= 1 and mm <= 12) and (yy != 0 or mm != 0):
	    	YYMM_flg = True
	    elif (yy >= 1 and yy <= 12) and (yy != 0 or mm != 0):
	    	MMYY_flg = True
	    else:
	    	NA_flg = True

	    if AMB_flg:
	    	print("AMBIGUOUS")
	    elif YYMM_flg:
	    	print("YYMM")
	    elif MMYY_flg:
	    	print("MMYY")
	    elif NA_flg:
	    	print("NA")


	if __name__ == "__main__":
	    main()


### FIXED CODE ###

def main():
    str = input()
    YY = []
    MM = []
    YYMM_flg = False
    MMYY_flg = False
    AMB_flg = False
    NA_flg = False

    for i in range(2):
    	YY.append(str[i])

    for i in range(2, 4):
    	MM.append(str[i])

    yy = int(''.join(YY))
    mm = int(''.join(MM))

    if (yy >= 1 and yy <= 12) and (mm >= 1 and mm <= 12):
    	AMB_flg = True
    elif (mm >= 1 and mm <= 12) and (yy != 0 or mm != 0):
    	YYMM_flg = True
    elif (yy >= 1 and yy <= 12) and (yy != 0 or mm != 0):
    	MMYY_flg = True
    else:
    	NA_flg = True

    if AMB_flg:
    	print("AMBIGUOUS")
    elif YYMM_flg:
    	print("YYMM")
    elif MMYY_flg:
    	print("MMYY")
    elif NA_flg:
    	print("NA")


if __name__ == "__main__":
    main()
N = int(input())
d = []
for i in N:
    d.append(int(input()))
print(len(set(d)))

### FIXED CODE ###

N = int(input())
d = []
for i in range(N):
    d.append(int(input()))
print(len(set(d)))
import numpy as np

n = int(input())
b = [[int(i)] for i in input().split()]

diag = [.5 for i in range(n)]

A = np.diag(diag)
for i in range(n-1):
  A[i][i+1] = .5

A[n-1][0] = .5

x = np.linalg.solve(A, b)
tmp = [str(int(round(i[0], 0))) for i in x]
print(' '.join(tmp))


### FIXED CODE ###

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

all_ = sum(a)

x1 = all_ - 2 * (sum([a[i] for i in range(1, n, 2)]))
x = [x1]

for i in range(1, n):
  x_i = 2 * a[i-1] - x[i-1]
  x.append(x_i)

print(' '.join(list(map(str, x))))
n=int(input());
f=0;
while n>=0:
  if n%7<1:f+=1;
  n-=4;
print(["No","Yes"][f])

### FIXED CODE ###

n=int(input());
f=0;
while n>=0:
  if n%7<1:f+=1;
  n-=4;
print("Yes"if f>0 else"No")
import sys
input = sys.stdin.readline

S = list(map(int, input().split()))
N = S[0]
M = S[1]
A = list(map(int, input().split()))


for _ in range(M):
    A[A.index(max(A))] //= 2

print(sum(A))


### FIXED CODE ###

S = input()


if S == 'Sunny':
    print('Cloudy')
elif S == 'Cloudy':
    print('Rainy')
else:
    print('Sunny')
while True:
    try:
        n = int(raw_input())
        filter = [1 for i in range(n)]
        filter[0] = 0
        for i in range(2,n//2):
　　　　　　　if filter[i] == 1:
                j = 2
                k = i*j
                while k < n:
                    filter[k-1] = 0
                    j += 1
                    k = i*j
        print filter
        sum = 0
        for i in filter:
            sum += i
        print sum
    except:
        break

### FIXED CODE ###

import math
n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
  
r = max(n)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
p[3::2] = [0 for x in range(3,r,2)]
for i in range(2,sqrt,2):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)] 
  
for i in n:
     print sum(p[:i])
#coding: utf-8

n = int(input())
color = ["white" for i in range(n)]
d = [[] for i in range(n)]
global t
t = 0
M = [[False for i in range(n)] for j in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    u = data[0]
    k = data[1]
    if i == 0:
        start = u
    for v in data[2:2+k]:
        M[u-1][v-1] = True


def search(u,t):
    t += 1
    color[u-1] = "gray"
    d[u-1].append(t)
    for v in range(n):
        if M[u-1][v-1] and color[v-1] == "white":
            t = search(v,t)
    color[u-1] = "black"
    t += 1
    d[u-1].append(t)
    return t

search(start, t)
for i in range(n):
    print(i+1, d[i][0], d[i][1])



### FIXED CODE ###

#coding:utf-8
from copy import deepcopy

n = int(input())
c = ["white" for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
S = []
class DFS:
    def __init__(self, key, color="white",nex=None):
        self.color = color
        self.nex = nex
        self.key = key

objList = [DFS(i+1) for i in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    times = data[1]
    obj = objList[i]
    for j in range(times):
        index = data[2+j] - 1
        nextobj = DFS(index+1)
        obj.nex = nextobj
        obj = obj.nex


time = 1
def check(first,time):
    obj = objList[first]
    c[first] = "gray"
    d[first] = time
    f[first] = time
    S.append(first+1)
    
    while S != []:
        index = S[-1] - 1
        u = objList[index]
        v = u.nex
    
        if v != None:
            objList[index] = v
            if c[v.key - 1] == "white":
                index = v.key - 1
                v = objList[index]
                c[v.key-1] = "gray"
                time += 1
                d[index] = time
                S.append(v.key)

           
                
        else:
            S.pop()
            c[u.key-1] = "black"
            time += 1
            f[index] = time
    return time


for i in range(n):
    if f[i] == 0:
        time = check(i,time) + 1
        

k = 1
for i,j in zip(d,f):
    print(k,i,j)
    k += 1
K=int(input())
A=[1,2,3,4,5,6,7,8,9]
B=[]
C=[]
D=[]
E=[]
F=[]
G=[]
H=[]
I=[]

def henkan(A):
    a=len(A)
    B=[]
    for i in range(a):
        if A[i]%10==0:
            B.append(10*A[i])
            B.append(10*A[i]+1)
        elif A[i]%10==9:
            B.append(10*A[i]+9)
            B.append(10*A[i]+8)
        else:
            x=A[i]%10
            B.append(10*A[i]+x)
            B.append(10*A[i]+x+1)
            B.append(10*A[i]+x-1)
    return B

B=henkan(A)
C=henkan(B)
D=henkan(C)
E=henkan(D)
F=henkan(E)
G=henkan(F)
H=henkan(G)
I=henkan(H)
ans=A+B+C+D+E+F+G+H+I
ans=sorted(ans)

print(ans[K-1])


### FIXED CODE ###

K=int(input())
A=[1,2,3,4,5,6,7,8,9]
B=[]
C=[]
D=[]
E=[]
F=[]
G=[]
H=[]
I=[]
J=[]
def henkan(A):
    a=len(A)
    B=[]
    for i in range(a):
        if A[i]%10==0:
            B.append(10*A[i])
            B.append(10*A[i]+1)
        elif A[i]%10==9:
            B.append(10*A[i]+9)
            B.append(10*A[i]+8)
        else:
            x=A[i]%10
            B.append(10*A[i]+x)
            B.append(10*A[i]+x+1)
            B.append(10*A[i]+x-1)
    return B

B=henkan(A)
C=henkan(B)
D=henkan(C)
E=henkan(D)
F=henkan(E)
G=henkan(F)
H=henkan(G)
I=henkan(H)
J=henkan(I)
ans=A+B+C+D+E+F+G+H+I+J
ans=sorted(ans)

print(ans[K-1])
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  z2 = [0 for in range(b+1)]
  for i in range(a):
    z1 = z2 + []
    for j in range(b):
      if X[i] == Y[j]:
        z2[j+1] = z1[j] + 1
      else:
        z2[j+1] = z2[j]
  
  return z2[-1]

q = input()

for i in range(q):
  print lcs_siz()

### FIXED CODE ###

def lcs_size():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  z2 = [0 for i in range(b+1)]

  for i in range(a):
    ch = X[i]
    z1 = z2 + []
    for j in range(b):
      if ch == Y[j]:
        z2[j+1] = z1[j] + 1
      elif z2[j+1] < z2[j]:
        z2[j+1] = z2[j]

  return z2[-1]

q = input()
for k in range(q):
  print lcs_size()
n = int(input())
A = list(map(int,input().split()))

law_ans = 0
absminA = float('inf')
for a in A:
    law_ans += abs(a)
    absminA = min(absminA, a)


cnt_neg = 0

for a in A:
    if a < 0:
        cnt_neg += 1

cnt_0 = A.count(0)

if cnt_0 == 0:
    if cnt_neg%2 == 0:
        print(law_ans)
    else:
        print(law_ans-2*absminA)
else:
    pritn(law_ans)


### FIXED CODE ###

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

law_ans = 0
absminA = float('inf')
for a in A:
    law_ans += abs(a)
    absminA = min(absminA, abs(a))


cnt_neg = 0

for a in A:
    if a < 0:
        cnt_neg += 1

cnt_0 = A.count(0)

if cnt_0 == 0:
    if cnt_neg%2 == 0:
        print(law_ans)
    else:
        print(law_ans-2*absminA)
else:
    print(law_ans)
N=int(input())
ld=list(map(int,input().split()))
def modpow(a,n,p):#a^n mod p
    res=1
    while n>0:
        if n&1:#１とのビット論理積が１、つまり奇数
            res=res*a%p
        a=a*a%p
        n>>=1
        #ビットの右シフト_2進数表記のnを小数点を固定して右に１桁ずらす_１桁小さくなる
    return res
if ld[0]!=0:
    print(0)

else:
    dd={}
    for i in range(N):
        if ld[i] in dd:
            dd[ld[i]]+=1
        else:
            dd[ld[i]]=1
    if dd[0]!=1:
        print(0)
    else:
        DV=998244353
        ans=1
        for i in range(0,len(dd)-1):
            #mul=dd[i]**dd[i+1]%DV
            mul=modpow(dd[i],dd[i+1],DV)
            #ans*=dd[i]**dd[i+1]
            ans*=mul
            ans%=DV
        print(ans)


### FIXED CODE ###

N=int(input())
ld=list(map(int,input().split()))
def modpow(a,n,p):#a^n mod p
    res=1
    while n>0:
        if n&1:#１とのビット論理積が１、つまり奇数
            res=res*a%p
        a=a*a%p
        n>>=1
        #ビットの右シフト_2進数表記のnを小数点を固定して右に１桁ずらす_１桁小さくなる
    return res
if ld[0]!=0:
    print(0)

else:
    dd={}
    for i in range(N):
        if ld[i] in dd:
            dd[ld[i]]+=1
        else:
            dd[ld[i]]=1

    if dd[0]!=1:
        print(0)
    else:
        DV=998244353
        ans=1
        for i in range(0,len(dd)-1):
            #mul=dd[i]**dd[i+1]%DV
            if i in dd and i+1 in dd:
                mul=modpow(dd[i],dd[i+1],DV)
                #ans*=dd[i]**dd[i+1]
                ans*=mul
                ans%=DV
            else:
                print(0)
                break
        else:
            print(ans)
import copy

ab = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

n = int(input())

# 最初はaで確定

value = ['a']
for i in range(10):
    if len(value[0]) == n:
        break
    tmp_value = copy.copy(value)
    value = []
    for v in tmp_value:
        for j in range(n):
            value.append(v + ab[j])
            if ab[j] not in v:
                break
    for v in value:
    print(v)


### FIXED CODE ###

import copy

ab = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

n = int(input())

value = ['a']
for i in range(10):
    if len(value[0]) == n:
        break
    tmp_value = copy.copy(value)
    value = []
    for v in tmp_value:
        for j in range(n):
            value.append(v + ab[j])
            if ab[j] not in v:
                break
for v in value:
    print(v)