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

import sys
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
a = [LI() for _ in range(N)]
dp = [[0] * (2**N) for _ in range(N)]

q = [[] for _ in range(N)]
b = 1
for i in range(N):
    if a[0][i]:
        dp[0][b] = 1
        q[0].append(b)
    b <<= 1

for i in range(1,N):
    for k in q[i-1]:
        v = dp[i-1][k]
        b = 1
        for l in a[i]:
            if l and k & b == 0:
                m = k | b
                if dp[i][m] == 0: q[i].append(m)
                dp[i][m] = (dp[i][m] + v) % MOD
            b <<= 1

print(dp[-1][2**N-1])

### FIXED CODE ###

import sys

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    N = NI()
    a = [LI() for _ in range(N)]
    dp = [[0] * (2**N) for _ in range(N)]

    q = [[] for _ in range(N)]
    b = 1
    for i in range(N):
        if a[0][i]:
            dp[0][b] = 1
            q[0].append(b)
        b <<= 1

    for i in range(1,N):
        for k in q[i-1]:
            v = dp[i-1][k]
            b = 1
            for l in a[i]:
                if l and k & b == 0:
                    m = k | b
                    if dp[i][m] == 0: q[i].append(m)
                    dp[i][m] = (dp[i][m] + v) % MOD
                b <<= 1

    print(dp[-1][2**N-1])

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

n=int(input())
mod=10**9+7
ans=1
for i in range(1,n+1):
    ans*=i
print(ans%mod)

### FIXED CODE ###

import math
n=int(input())
mod=10**9+7
print(math.factorial(n)%mod)
### BUGGY CODE ###

def ToAscii( str_, digit ) :
	num = 0
	for i in range( digit ) :
		num += 100**(i) * ( ord( str_[i] )-96 )
	return num

n = int( input() )

judge_nums = []
for i in range( n ):
	judge_num = 10**27 # 一桁目はフェイク
	str_list = list( input() )
	for s in str_list :
		judge_num += 10**(ord( s )-97)
	judge_nums.append( judge_num )
judge_nums = sorted( judge_nums )


count = 0
for i in range( n ) :
	bFound = False
	for j in range( i+1, n ) :
		if judge_nums[i] != judge_nums[j] :
			break
		if judge_nums[i] == judge_nums[j] :
			count += 1
			bFound = True

print( count )



### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(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 = int( input() )

dict = {}
for i in range( n ):
	sorted_input = "".join( sorted( list( input() ) ) )
	if dict.get( sorted_input ) == None:
		dict[ sorted_input ] = 1
	else :
		dict[ sorted_input ] += 1

count = 0
for eachValue in dict.values():
	if eachValue == 1 : continue
	count += cmb( eachValue, 2 )
print( count )
### BUGGY CODE ###

from collections import deque

def main():
  n, m = map(int, input().split())
  graph = [[] for _ in range(n)]

  for i in range(m):
    a, b = map(int, input().split())
    if b-1 not in graph[a-1]:
      graph[a-1].append(b-1)
      graph[b-1].append(a-1)
  
  searched = []
  result = 0
  while len(searched) != n:
    for i in range(n):
      if i not in searched:
        s = i
        break
    tmp, cnt = dfs(graph, s)
    searched += tmp
    if cnt > result:
      result = cnt
      
  print(result)

def dfs(graph, s):
  stack = deque([s])
  searched = [s]
  while len(stack):
    cur = stack.pop()
    for i in graph[cur]:
      if i not in searched:
        stack.append(i)
        searched += [i]
  return searched, len(searched)

main()

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

def main():
  n, m = map(int, input().split())
  uf = UnionFind(n)

  for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b-= 1;
    uf.union(a, b)
  
  ans = 0
  for i in range(n):
    ans = max(ans, uf.size(i))
      
  print(ans)
  
main()
### BUGGY CODE ###

import numpy as np
 
n = int(input())
A = np.array(list(map(int, input().split(' '))))
 
A_unique = np.unique(A)
num_dict = {}
total = 0
for a in A_unique:
  tmp = np.count_nonzero(A==a)
  num_dict[a] = (tmp*(tmp-1)/2, (tmp-1)*(tmp-2)/2)
  total += tmp*(tmp-1)/2

ans_dict = {}
for a in A_unique:
  ans_dict[a] = int(total - num_dict[a][0] + num_dict[a][1])

for a in A:
  print(ans_dict[a])

### FIXED CODE ###

import collections

n = int(input())
A = list(map(int, input().split(' ')))
 
c = dict(collections.Counter(A))
num_dict = {}
total = 0
for a, count in c.items():
  num_dict[a] = (count*(count-1)/2, (count-1)*(count-2)/2)
  total += count*(count-1)/2

ans_dict = {}
for a in c.keys():
  ans_dict[a] = total - num_dict[a][0] + num_dict[a][1]

for k in range(n):
  print(int(ans_dict[A[k]]))
### BUGGY CODE ###

import sys
from collections import defaultdict, deque


def dfs(root, links):
    pending = set()
    ans = 0
    q = [(r, 0, 1) for r in root]
    while q:
        node = q.pop()
        if node[1] == 0:
            v, _, d = node
            ans = max(ans, d)
            q.append((v, 1))
            pending.add(v)
            d += 1
            for u in links[v]:
                if u in pending:
                    return False
                q.append((u, 0, d))
        else:
            pending.remove(node[0])
    return ans


n = int(input())
links = defaultdict(set)
may_root = set()
in_cnt = defaultdict(lambda: 0)
for i, line in enumerate(sys.stdin):
    aaa = list(map(int, line.split()))
    j = aaa[0] - 1
    a, b = (i, j) if i < j else (j, i)
    prev = a * 1000 + b
    may_root.add(prev)

    for j in aaa[1:]:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * 1000 + b
        links[prev].add(key)
        in_cnt[key] += 1
        prev = key
may_root = {r for r in may_root if in_cnt[r] == 0}

if not may_root:
    print(-1)
    exit()

ans = dfs(may_root, links)
if ans == False:
    print(-1)
    exit()

print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict


def dfs(root, links):
    status = {}
    topological = []
    q = [(r, 0, 1) for r in root]
    while q:
        node = q.pop()
        if node[1] == 0:
            v, _, d = node
            q.append((v, 1))
            status[v] = 1
            d += 1
            for u in links[v]:
                if u in status:
                    if status[u] == 1:
                        return False
                else:
                    q.append((u, 0, d))
        else:
            v = node[0]
            status[v] = 2
            topological.append(v)
    topological.reverse()
    return topological


n = int(input())
links = defaultdict(set)
may_root = set()
lines = sys.stdin.readlines()
matches = []
for i in range(n):
    line = lines[i]
    aaa = list(map(int, line.split()))
    match_order = []
    for j in aaa:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * n + b
        match_order.append(key)
    matches.append(match_order)
    may_root.add(match_order[0])

for i in range(n):
    kkk = matches[i]
    prev = kkk[0]

    for key in kkk[1:]:
        links[prev].add(key)
        may_root.discard(key)
        prev = key

if not may_root:
    print(-1)
    exit()

topological = dfs(may_root, links)
if topological == False:
    print(-1)
    exit()

ans = 0
depth = defaultdict(lambda: 1)
for v in topological:
    d = depth[v] + 1
    for u in links[v]:
        depth[u] = max(depth[u], d)

print(max(depth.values()))
### BUGGY CODE ###

a=input()
n=len(a)
dupli=0
from itertools import combinations
for i,j in combinations(range(n),2):
    if a[i:j+1]==a[i:j+1][::-1]:
        dupli+=1
    elif j-i>2 and a[i]==a[j]:
        dupli+=1
print(n*(n-1)//2-dupli+1)

### FIXED CODE ###

a=input()
n=len(a)
dupli=0
from collections import Counter
c=Counter(a)
for word,num in c.most_common():
    dupli+=num*(num-1)//2
print(n*(n-1)//2-dupli+1)
### BUGGY CODE ###

N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))

# set default color to -1

colors = {i:-1 for i in range(1,N+1)}
u,v,w = UVW[0]
colors[u] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    next_UVW = []
    for u, v, w in UVW:
        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])

        if colors[u] == -1 or colors[v] == -1:
            next_UVW.append((u,v,w))

    UVW = next_UVW



for i in range(1, N+1):
    print(colors[i])

### FIXED CODE ###

N = int(input())

u_list = []
v_list = []
w_list = []

for _ in range(N-1):
  u, v, w = map(int, input().split())
  u_list.append(u-1)
  v_list.append(v-1)
  w_list.append(w)
  
color_dict = dict()
uvw_list = list(zip(u_list, v_list, w_list))
color_dict[u_list[0]] = 1

def eval_single(u, v, w, color_dict):
  skip = True

  if u in color_dict:
    color_dict[v] = assign_color(color_dict[u], w)
    skip = False
    
  if v in color_dict:
    color_dict[u] = assign_color(color_dict[v], w)
    skip = False
    
  return skip, color_dict
  

def assign_color(color, w):
  if w%2==0:
    return color
  else:
    return color*(-1)+1
  
while True:
  ind_list = []
  for ind, (u, v, w) in enumerate(uvw_list):
    skip, color_dict = eval_single(u, v, w, color_dict)
    
    if skip:
      ind_list.append(ind)

  uvw_list = [uvw_list[ind] for ind in ind_list]
  
  if len(color_dict) == N:
    break

for i in range(N):
  print(color_dict[i])
### BUGGY CODE ###

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

count = 0
for i in range(K + 1):
  for j in range(K + 1):
    for k in range(K + 1):
      if i + j + k == S:
        count = count + 1

print(count)

### FIXED CODE ###

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

count = 0
for i in range(K + 1):
  for j in range(K + 1):
      if S - i - j <= K and 0 <= S - i -j:
        count = count + 1

print(count)
### BUGGY CODE ###

n = int(input())
s = int(input())
rtn = -1* int( -1 * (n**0.5))
def f(b,n):
    if n<b:
        return n
    return f(b,n//b) + n % b
if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
else:
    x = n // s
    if s - (n //(x+1))  <= x:
        x = x + 1
    if 5 < n/(x -1) - n/x :
        for b in range(n//x, n//(x-1)):
            if f(b,n) == s:
                print(b)
                exit()
        for i in range(x-1,2,-1):
            for b in range(n//i + (n//x)//(n//i), n//i + (n//x)//(n//i)  + (2*n//x - n//(x+1))//(x-i)):
                if f(b,n) == s:
                    print(b)
                    exit()
    else:
        for b in range(2,rtn+1):
            if f(b,n) == s:
                print(b)
                exit()
        for p in range(rtn,0,-1):
            if (n-s) % p == 0:
                b = (n-s)//p + 1
                if f(b,n) == s:
                    print(b)
                    exit()
    print(n-s+1)


### FIXED CODE ###

n = int(input())
s = int(input())
rtn = -1* int( -1 * (n**0.5))
def f(b,n):
    if n<b:
        return n
    return f(b,n//b) + n % b
if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
else:
    for b in range(2,rtn+1):
        if f(b,n) == s:
            print(b)
            exit()
    for p in range(rtn,0,-1):
        if (n-s) % p == 0:
            b = (n-s)//p + 1
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)
### BUGGY CODE ###

from operator import mul
from functools import reduce
def cmb(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=int(input())
a=sorted(list(map(int,input().split())))
l=a[-1]
ans=0
ans_r=0
for i in a:
  if i==l:
    continue
  b=cmb(l,i)
  if ans<b:
    ans=b
    ans_r=i
print(l,ans_r)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
l=a[-1]
b=[abs(i-l/2) for i in a]
c=float("inf")
for i in range(n-1):
  c=min(c,b[i])
print(l,a[b.index(c)])
### BUGGY CODE ###

n, a = int(input()), list(map(int, input().split()))
for i in range(int(input())):
    b, c = map(int, input().split())
    for j in range(n):
        if a[j] == b:
            a[j] = c
    print(sum(a))

### FIXED CODE ###

n, a = int(input()), list(map(int, input().split()))
s = sum(a)
d = [0] * (10 ** 5 + 1)
for i in a:
    d[i] += 1
for i in range(int(input())):
    b, c = map(int, input().split())
    d[c] += d[b]
    s += (c - b) * d[b]
    print(s)
    d[b] = 0
### BUGGY CODE ###

s = input()
k = int(input())
li = []
for i in range(1,len(s)+1):
    j = 0
    while i+j <= len(s):
        li.append(s[j:j+i])
        j += 1
ans = sorted(list(set(li)))
print(ans[k-1])


### FIXED CODE ###

s = input()
k = int(input())
li = []
for i in range(1,k+1):
    j = 0
    while i+j <= len(s):
        li.append(s[j:j+i])
        j += 1
ans = sorted(list(set(li)))
print(ans[k-1])
### BUGGY CODE ###

def create_z_array(s):
    n = len(s)
    z_array = [0] * n
    left = 0
    right = 0
    for i in range(1, n):
        if i > right:
            left, right = i, i
            while right < n and s[right - left] == s[right]:
                right += 1
            z_array[i] = right - left
            right -= 1
        else:
            k = i - left
            if z_array[k] < right - i + 1:
                z_array[i] = z_array[k]
            else:
                left = i
                while right < n and s[right - left] == s[right]:
                    right += 1
                z_array[i] = right - left
                right -= 1
    return z_array


n = int(input())
s = input().rstrip()
res = 0
for i in range(n):
    z_array = create_z_array(s[i:])
    for j in range(1, len(z_array)):
        res = max(res, min(j, z_array[j]))
print(res)

### FIXED CODE ###

def create_z_array(s):
    n = len(s)
    z_array = [0] * n
    left = 0
    right = 0
    for i in range(1, n):
        if i > right:
            left, right = i, i
            while right < n and s[right - left] == s[right]:
                right += 1
            z_array[i] = right - left
            right -= 1
        else:
            k = i - left
            if z_array[k] < right - i + 1:
                z_array[i] = z_array[k]
            else:
                left = i
                while right < n and s[right - left] == s[right]:
                    right += 1
                z_array[i] = right - left
                right -= 1
    return z_array


n = int(input())
s = input().rstrip()
res = 0
for i in range(n):
    z_array = create_z_array(s[i:])
    for j in range(1, len(z_array)):
        res = max(res, min(j, z_array[j]))
print(res)
### BUGGY CODE ###

import sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
chk = 0
for j in range(N*(N-1)//2):
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
print(ans)

### FIXED CODE ###

import sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
chk = 0
for j in range(N*(N-1)//2):
    if j >= 4000:
        chk = 1
        break
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
if chk == 0:
    print(ans)
else:
    print(N*(N-1)//2)
### BUGGY CODE ###

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

for i in range(n):
    y = x[:i] + x[i+1:]
    y.sort()
    print(y[n//2-1])


### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]
y = sorted(x)
a , b = y[n//2-1], y[n//2]
for i in x:
    if i > a:
        print(a)
    else:
        print(b)
### BUGGY CODE ###

import sys
from collections import deque

n = int(input())
a = [deque(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

day = 0
while True:
    popped = 0
    plist = set()
    zeros = 0
    for i in range(n):
        if len(a[i]) == 0:
            zeros += 1
            continue
        if i in plist:
            continue
        num = a[i][0] - 1
        if num < i:
            continue
        if num in plist:
            continue
        if a[num][0] - 1 == i:
            plist.add(num)
            a[i].popleft()
            a[num].popleft()
            popped += 1
    if popped == 0:
        if zeros == n:
            break
        else:
            day = -1
            break
    day += 1

print(day)


### FIXED CODE ###

import sys
from collections import deque

n = int(input())
a = [deque(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

current = []

for i in range(n):
    target = a[i][0] -1
    if a[target][0] -1 == i and i < target:
        current.append([i, target])

day = 0
zc = 0
while True:
    popped = 0
    plist = set()
    zeros = 0
    tc = []
    for i in current:
        a[i[0]].popleft()
        a[i[1]].popleft()
        if len(a[i[0]]) > 0:
            plist.add(i[0])
        else:
            zc += 1
        if len(a[i[1]]) > 0:
            plist.add(i[1])
        else:
            zc += 1
    for i in plist:
        target = a[i][0] -1
        if a[target][0] -1 == i:
            if not target in plist or i < target:
                tc.append([i, target])
    day += 1
    if len(tc) == 0:
        break
    current = tc

if zc != n:
    day = -1

print(day)
### BUGGY CODE ###

S = input()[::-1]
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
m = 0
x_10 = 1
for s in S:
    m = (m + int(s) * x_10) % 2019
    dp[m] += 1
    x_10 *= 10
for i in dp:
    ans += i * (i-1) // 2
print(ans)


### FIXED CODE ###

S = input()[::-1]
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
m = 0
x_10 = 1
for s in S:
    m = (m + int(s) * x_10) % 2019
    dp[m] += 1
    x_10 = (x_10 * 10) % 2019
for i in dp:
    ans += i * (i-1) // 2
print(ans)
### BUGGY CODE ###

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

All = 0
cnt = 0
for a in B:
    cnt = A.count(a)
    All +=  cnt*(cnt-1)//2

for k in range(N):
    ans_k = 0
    cnt = A.count(A[k])
    ans_k = cnt - 1
    Ans = All - ans_k
    print(Ans)
    










### FIXED CODE ###

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

from collections import Counter
cnt_A = Counter(A)

All = 0
cnt = 0
for a in B:
    cnt = cnt_A[a]
    All +=  cnt*(cnt-1)//2

for k in range(N):
    ans_k = 0
    cnt = cnt_A[A[k]]
    ans_k = cnt - 1
    Ans = All - ans_k
    print(Ans)
### BUGGY CODE ###

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


def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        half_p = p // 2
        half = mod_pow(a, half_p)
        return half * half % mod
    else:
        return a * mod_pow(a, p - 1) % mod


ans = 0
for i in range(60):
    cnt = 0
    for a in A:
        if a >> i & 1:
            cnt += 1
    ans += cnt * (N - cnt) * mod_pow(2, i)
    ans %= mod
print(ans)


### FIXED CODE ###

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


def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        half_p = p // 2
        half = mod_pow(a, half_p)
        return half * half % mod
    else:
        return a * mod_pow(a, p - 1) % mod


ans = 0
for i in range(60):
    cnt = 0
    for a in A:
        if a >> i & 1:
            cnt += 1
    now = cnt * (N - cnt) % mod
    ans += now * mod_pow(2, i) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
s = input()
t = input()

def LCS(S,T):
  #初期化
  dp = [["" for i in range(len(T)+1)] for j in range(len(S)+1)]

  #DP
  for i in range(len(S)):
    for j in range(len(T)):
      if S[i]==T[j]:
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],dp[i][j]+S[i], key=len)
      else:
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j], key=len)
  return dp[len(S)][len(T)]

print(LCS(s,t))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
S = input()
T = input()

#初期化
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]

#DP
for i in range(len(S)):
    for j in range(len(T)):
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + (S[i] == T[j]))

st = []

x = len(S)
y = len(T)
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]: x -= 1
    elif dp[x][y] == dp[x][y-1]: y -= 1
    else: 
        x -= 1
        y -= 1
        st += S[x]
print("".join(reversed(st)))
### BUGGY CODE ###

import itertools
n = int(input())
score = [ int(input()) for _ in range(n)]
for i in sorted(range(1, n+1),reverse=True):
  cnt = max([ sum(c) if sum(c) % 10 != 0 else 0 for c in itertools.combinations(score, i)])
  if(cnt != 0):
    print(cnt)
    exit()
print(0)

### FIXED CODE ###

import itertools
n = int(input())
score = [ int(input()) for _ in range(n)]
cnt = max([sum(c) if sum(c) % 10 != 0 else 0 for i in sorted(range(n-1, n+1)) for c in itertools.combinations(score, i)])
print(cnt)
### BUGGY CODE ###

K,S=map(int,input().split())
K+=1
ans=0
a=max(0,S-2*K)
for i in range(a,K):
  if i>S:
    break
  for j in range(a,K):
    if i+j>S :
      break
    for k in range (a,K):
      if i+j+k>S:
        break
      if i+j+k==S:
        ans+=1
print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans=0
#a=max(0,S-2*K)
for i in range(K+1):
  for j in range(K+1):
    if i+j+K>=S and i+j<=S :
      ans+=1

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

N=[int(e) for e in input().split()]
p=[(int(e)+1)/2 for e in input().split()]
p2=[0.]*(N[0]-N[1]+1)
for i in range(N[0]-N[1]+1):
    for j in range(N[1]):
        p2[i]=p2[i]+p[i+j]
print(max(p2))

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
for i in range(N-1):
    p[i+1]=p[i+1]+p[i]
max=p[K-1]
if N>K:
    for i in range(1,N-K+1):
        tmp=p[i+K-1]-p[i-1]
        if max < tmp:
            max=tmp
print((max+K)/2.)