Harryxun/stf_run huggingface dataset:
#ABC042.B
N,L = map(int,input().split())
s = [input() for_in range(n)]
s.sort()
ans=''
for i in range(N):
    ans =ans+ s[i]
print(ans)

### FIXED CODE ###

#ABC042.B
N,L = map(int,input().split())
s = [input()for _ in range(N)]
s.sort()
ans=''
for i in range(N):
    ans =ans +s[i]
print(ans)
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]

# バイナリインデックス木(BIT)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while 0 < i:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# エントリーポイント
def main():
    N, K = input(int, int)
    A = input([int, N])

    ppp = A * K
    bit = Bit(2010)
    ans = 0
    
    for i, p in enumerate(ppp):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

# バイナリインデックス木
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while 0 < i:
            s += self.tree[i]
            s %= MOD
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# エントリーポイント
def main():
    N, K = input(int, int)
    A = input([int, N])

    MAX = 2010
    bit = BIT(MAX)
    # 最終周をカウントする
    sum1 = []
    for i, a in enumerate(A, start=1):
        bit.add(a, 1)
        sum1.append(i - bit.sum(a))
    # 繰り返し周をカウントする
    sum2 = []
    for a in A:
        sum2.append(N - bit.sum(a))
    # (1 + (K - 1))回分を集計する
    ans = 0
    for v1, v2 in zip(sum1, sum2):
        ans += K * v1 + ((K * (K - 1)) // 2) * v2
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()
N = int(input())
L = [[map(int,input().split())] for i in range(N)]

dp = [[0,0,0] for i in range(N+1)]
for i in range(N) :
    for j in range(3) :
        for k in range(3) :
            if j == k :
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + L[i][k])
print(ax(dp[-1]))



### FIXED CODE ###

N = int(input())
L = [list(map(int,input().split())) for i in range(N)]

dp = [[0,0,0] for i in range(N+1)]
for i in range(N) :
    for j in range(3) :
        for k in range(3) :
            if j == k :
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + L[i][k])
print(max(dp[-1]))
S = input()
N = int(input())
count = 0
a = S.split('ABC')
for i in a:
    if i == '':
        count += 1
    else: continue
print (count)

### FIXED CODE ###

N = int(input())
S = input()
print(S.count("ABC"))
n,m,x = map(int,input().split())
c_ = [list(map(int,input().split())) for i in range(n)]

cc_ = []
for i in range(n):
    cc_.append(c_[i][0])
# print(cc_)

import numpy as np
import itertools
l_ = np.arange(n).tolist()

res_ = []
resList = []
flag = False
for i in range(2,n+1):
    c = list(itertools.combinations(l_, i))
    for j in c:
        # print(j)
        res_ = []
        flag2 = True
        for l in range(3):
            res = 0
            sum_money = 0
            for k in range(len(j)):
                res += c_[j[k]][l+1]
                sum_money += c_[j[k]][0]
            # print(res,sum_money)
            if res < x:
                flag2 = False
        if flag2:
            resList.append(sum_money)
            flag = True
# print(resList)
print(min(resList) if flag else -1)


### FIXED CODE ###

n,m,x = map(int,input().split())
c_ = [list(map(int,input().split())) for i in range(n)]

# print(c_)
cc_ = []
for i in range(n):
    cc_.append(c_[i][0])
# print(cc_)

import numpy as np
import itertools
l_ = np.arange(n).tolist()

res_ = []
resList = []
flag = False
flag3 = True
if n == 1:
    for i in range(m):
        if c_[0][i+1] < x:
            # print(c_[0][i+1])
            flag3 = False
    print(cc_[0] if flag3 else -1)
else:
    for i in range(1,n+1):
        c = list(itertools.combinations(l_, i))
        for j in c:
            res_ = []
            flag2 = True
            for l in range(m):
                res = 0
                sum_money = 0
                for k in range(len(j)):
                    res += c_[j[k]][l+1]
                    sum_money += c_[j[k]][0]
                # print(res,sum_money)
                if res < x:
                    flag2 = False
            if flag2:
                resList.append(sum_money)
                flag = True
    # print(resList)
    print(min(resList) if flag else -1)
n, m = map(int, input().spllit())
tmp = abs(n)-abs(m)
print(tmp if (n <= 0 and m <= 0) or  (n >= 0 and m >= 0) else tmp+1

### FIXED CODE ###

x, y = map(int, input().split())
tmp = abs(abs(x) - abs(y))
if (y == 0 and 0 < x) or (x == 0 and y < 0):
    print(tmp + 1)
elif 0 <= x * y and x <= y:
    print(tmp)
elif 0 <= x * y and y < x:
    print(tmp + 2)
else:
    print(tmp + 1)
r = map(int,input())
s = 3 * r * r
print("s")

### FIXED CODE ###

r = int(input())
s = 3 * r * r
print(s)
def t118C():
    N = int(input())
    A = [int(input()) for i in range(N)]
    A.sort()
    anslist = []
    ans = 0
    tmplist = []
    tmplist2 = []

    up = 0
    down = N - 1
    checklist = [0 for i in range(N)]
    while True:
        if checklist[up] == 1:
            break
        tmplist.append(up)
        checklist[up] = 1
        up += 1

        if checklist[down] == 1:
            break
        tmplist2.append(down)
        checklist[down] = 1
        down -= 1

        if checklist[down] == 1:
            break
        tmplist.append(down)
        checklist[down] = 1
        down -= 1

        if checklist[up] == 1:
            break
        tmplist2.append(up)
        checklist[up] = 1
        up += 1

    for i in range(len(tmplist)):
        tmplist[i] = A[tmplist[i]]

    for i in range(len(tmplist2)):
        tmplist2[i] = A[tmplist2[i]]

    #print(tmplist, tmplist2)
    for i in range(1, len(tmplist)):
        ans += abs(tmplist[i] - tmplist[i - 1])
    for i in range(1, len(tmplist2)):
        ans += abs(tmplist2[i] - tmplist2[i - 1])
    ans += abs(tmplist[0] - tmplist2[0])
    ans2 = ans
    ans2 -= abs(tmplist[-1] - tmplist[-2])
    ans2 -= abs(tmplist2[-1] - tmplist2[-2])
    ans2 += abs(tmplist[-1] - tmplist2[-2])
    ans2 += abs(tmplist[-2] - tmplist2[-1])
    #print(ans2)
    print(max(ans, ans2))
t118C()

### FIXED CODE ###

def t118C():
    N = int(input())
    A = [int(input()) for i in range(N)]
    A.sort()
    AFromMinimum = A
    AFromMaxim = A[::-1]
    ans = 0
    if N % 2 == 0:
        ans = -2 * sum(AFromMinimum[:N // 2]) + 2 * sum(AFromMaxim[:N // 2]) + AFromMinimum[N // 2 - 1] - AFromMaxim[N // 2 - 1]
    else:
        c = (N - 1) // 2
        tmp1 = -2 * sum(A[:c]) + 2 * sum(A[c + 2:]) + A[c] + A[c + 1]
        tmp2 = -2 * sum(A[:c - 1]) + 2 * sum(A[c + 1:]) - A[c - 1] - A[c]
        ans = max(tmp1, tmp2)
    print(ans)
t118C()
def common():
??????X = raw_input()
??????Y = raw_input()
????????????????????????????
??????for i in range(0, len(Y)+1):
????????????s[i] = 0
????????????????????????????
??????for j in range(0, len(X)):
????????????t = s + []
????????????for k in range(0, len(Y)):
??????????????????if X[j] == Y[k]:
????????????????????????s[k+1] = t[k] + 1
??????????????????elif s[k+1] < s[k]:
????????????????????????s[k+1] = s[k]
??????????????????????
??????return s[-1]
??????????
q = input()???????? 
for l in range(0, q):
??????common()

### FIXED CODE ###

def common():
   X = raw_input()
   Y = raw_input()
  
   s = [0 for i in range(len(Y)+1)]
 
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if X[j] == Y[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
  
   print s[-1]
 
q = input()
for l in range(0, q):
   common()
N = int(input())
S = input().strip()

def tree(N,s,index):
  if N <= index:
      if len(s) > 0:
          return 1
      else:
          return 0

  if S[index] in s:
      return tree(N,s, index + 1)
  else:
      return tree(N,s, index + 1) + tree(N,s + S[index], index + 1)


print(tree(N,"",0) % 1000_000_007)




### FIXED CODE ###

N = int(input())
S = input()

words = {}

for s in S:
    if s in words.keys():
        words[s] += 1
    else:
        words[s] = 2

res = 1
for k in words.keys():
    res *= words[k]

print((res - 1) % 1000000007)
import sys
sys.setrecursionlimit(10 ** 5 + 10)
from numba import jit
def input(): return sys.stdin.readline().strip()

@jit
def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    m=n
    log = 0
    while m >= 2:
        m = m // 2
        log += 1
    from itertools import accumulate

    for i in range(min(k,n*2*log+1)):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]
    
    

    print(*A[:-1])    
    
    
resolve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()
a=input()
b=input()
c=input()
d=input()
e=input()
k=input()
f=[b-a,c-b,d-c,e-d]

if((f[0]>k) or (f[1]>k) or (f[2]>k)or (f[3]>k)):
  print(':(')
else if(((f[0]+f[1])>k)or ((f[1]+f[2])>k)or ((f[2]+f[3])>k)):
  print(':(')
else if(((f[0]+f[1]+f[2])>k) or((f[1]+f[2]+f[3])>k)):
  print(':(')
else if((e-a)>k):
  print(':(')
else:
  print('Yay!')

### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
f=[b-a,c-b,d-c,e-d]
 
if((f[0]>k) or (f[1]>k) or (f[2]>k)or (f[3]>k)):
  print(':(')
elif(((f[0]+f[1])>k)or ((f[1]+f[2])>k)or ((f[2]+f[3])>k)):
  print(':(')
elif(((f[0]+f[1]+f[2])>k) or((f[1]+f[2]+f[3])>k)):
  print(':(')
elif((e-a)>k):
  print(':(')
else:
  print('Yay!')
A,B=map(int,input().split())
Aset=set([int(i) for i in range(1,1010) if int(i*0.08)==A])
Bset=set([int(i) for i in range(1,1010) if int(i*0.1)==B])
if Aset&Bset!={}:
    print(min(Aset&Bset))
else:
    print(-1)

### FIXED CODE ###

A,B=map(int,input().split())
Aset=set([int(i) for i in range(1,1010) if int(i*0.08)==A])
Bset=set([int(i) for i in range(1,1010) if int(i*0.1)==B])
if Aset&Bset :
    print(min(Aset&Bset))
else:
    print(-1)
def solve():
    maxCards, gates = map(int, input().split())
    gateRanges = [tuple(map(int, input().split())) for i in range(gates)]

    for i, permitRange in enumerate(gateRanges):
        if i == 0:
            activeBegin, activeEnd = permitRange
            continue
        begin, end = permitRange
        if not (begin <= activeEnd and end >= activeBegin):
            print(0)
            break
        else:
            activeBegin, activeEnd = max(activeBegin, begin), min(activeEnd, end)
    else:
        if (maxCards < activeBegin):
            return print(0)
        print(activeBegin, activeEnd)
        ans = min(activeEnd, maxCards) - activeBegin + 1
    print(ans)
solve()

### FIXED CODE ###

def solve():
    maxCards, gates = map(int, input().split())
    gateRanges = [tuple(map(int, input().split())) for i in range(gates)]

    for i, permitRange in enumerate(gateRanges):
        if i == 0:
            activeBegin, activeEnd = permitRange
            continue
        begin, end = permitRange
        if not (begin <= activeEnd and end >= activeBegin):
            return print(0)
        else:
            activeBegin, activeEnd = max(activeBegin, begin), min(activeEnd, end)
    else:
        if (maxCards < activeBegin):
            return print(0)
        ans = min(activeEnd, maxCards) - activeBegin + 1
    print(ans)
solve()
a,b,k = map(int ,input().split())
c=b-k
l=list(range(a,b+1))

for i in l[:k]:
    print(i)

if len(l)<=k:
    exit()

if (b-a+1)/2<=k:
    for i in l[k:]:
        print(i)
else:    
    for i in l[c:]:
        print(i)

### FIXED CODE ###

a,b,k = map(int, input().split())
for i in range(a,min(b+1,a+k)):
    print(i)
for i in range(max(b-k+1,(a+k)),b+1):
    print(i)
a = [int(input()) for i in range(5)]
b = int(input())
c = sorted(a)

if c[5]-c[0]<=b:
  print("Yay!")
else:
  print(":(")

### FIXED CODE ###

a = [int(input()) for i in range(5)]
b = int(input())
c = sorted(a)

if c[4]-c[0]<=b:
  print("Yay!")
else:
  print(":(")
import numpy as np
import itertools
n,m,d = map(int, input().split())

n = np.arange(1, n+1)
x = np.array(list(itertools.product(n, repeat=m)))
print(np.sum((x[:,1:] - x[:,:-1]) == d) / x.shape[0])


### FIXED CODE ###

a, b = map(int, input().split())
print('+' if a + b ==15 else '*' if a * b == 15 else 'x')
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import bisect

n,q = na()
s = ns()
x = []

for r in range(len(s)):
  if s[r] == 'A':
    if s[r+1] == 'C':
      x.append(r)

for i in range(q):
  l,r = na()
  b = bisect.bisect_left(x,l-1)
  a = bisect.bisect_right(x,r-2)
  c = a-b if a-b>0 else 0
  print(c)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
import bisect
 
n,q = na()
s = ns()
x = []
 
for r in range(len(s)-1):
  if s[r] == 'A':
    if s[r+1] == 'C':
      x.append(r)
 
for i in range(q):
  l,r = na()
  b = bisect.bisect_left(x,l-1)
  a = bisect.bisect_right(x,r-2)
  c = a-b if a-b>0 else 0
  print(c)
k,s=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        if 0<=(s-i-j)<=K:
            ans+=1
print(ans)


### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    for j in range(k+1):
        if 0<=(s-i-j)<=k:
            ans+=1
print(ans)
n = int(input())
A = list(map(int, input().split()))
cnt = 0
w = A[0]
for i in range(n - 1):
    nw = w + A[i + 1]
    if w > 0:
        if nw >= 0:
            cnt += nw + 1
            chg = -(nw  + 1)
    else:
        if nw <= 0:
            cnt += 1 - nw
            chg = 1 - nw
    w = nw + chg
    chg = 0
    
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [a_ for a_ in a]
 
ans = 10**14
for a0 in [-1,a[0],1]:
    if a0 == 0:
        continue
    ans_ = abs(a[0]-a0)
    b[0] = a0
    sign = b[0] > 0
    for i in range(1,n):
        b[i] = a[i]+b[i-1]
        if sign:
            if b[i] >= 0:
                ans_ += b[i]+1
                b[i] = -1
        else:
            if b[i] <= 0:
                ans_ += 1-b[i]
                b[i] = 1
        sign = not sign
    ans = min(ans, ans_)
print(ans)
import numpy as np
n = input()
A = input()
a = list(map(int,A.split(" ")))
a = np.array(a)
odd = a[1::2]
even = a[0::2]
if n//2 == 0:
    b = np.append(even[::-1],odd)
else:
    b = np.append(odd[::-1],even)
import sys
for d in b[:-1]:
    sys.stdout.write(str(d)+ " ")
sys.stdout.write(str(b[-1])+"\n")

### FIXED CODE ###

import numpy as np
n = int(input())
A = input()
a = list(map(int,A.split(" ")))
a = np.array(a)
even= a[1::2]
odd= a[0::2]
if n%2 == 0:
    b = np.append(even[::-1],odd)
else:
    b = np.append(odd[::-1],even)
 
import sys
for d in b[:-1]:
    sys.stdout.write(str(d)+ " ")
sys.stdout.write(str(b[-1])+"\n")
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

n = ri()
ans = 0
d = 2
for d in range(2, int(n**0.5) + 1):
    e = d
    while n%d == 0:
        n //= d
        d *= d
        ans += 1
    while n%e == 0:
        n = n//e

if n >= d:
    ans += 1
print(ans)




### FIXED CODE ###

a, b = input().split()
b = b.replace('.', '')
a = int(a)
b = int(b)
print((a*b)//100)
a,b=map(int,input().split())
if b==2:
    a=format(a,'b')
elif b==8:
    a=format(a,'o')
elif b==10:
    a=int(a)
print(len(a))

### FIXED CODE ###

a,b=map(int,input().split())
count=1
while a>=b:
    a=a/b
    count+=1
print(count)
n=list(input())
ans=0
for i in range(0,10):
  for x in range(len(n)):
    if s[x]==str(i):
      for j in range(0,10):
        for y in range(len(n)):
          if s[y]==str(j):
            for k in range(0,10):
              for z in range(len(n)):
                if s[z]==str(k):
                  ans+=1
                  
print(ans)

### FIXED CODE ###

n=int(input())
s=list(input())
d={}
ans=0
for x in range(n-2):
  if s[x] not in d:
    d[s[x]]=0
    for y in range(x+1,n-1):
      if (s[x]+s[y]) not in d:
        d[(s[x]+s[y])]=0
        for z in range(y+1,n):
          if (s[x]+s[y]+s[z]) not in d:
            d[(s[x]+s[y]+s[z])]=0
            ans+=1
    
print(ans)
stack = []
store_num = []
store_result = []

for i,c in enumerate(input().split()): 
        
        def pop_and_stack(list_,num):
                     
            list_.pop()
            list_.pop()
            list_.append(num)
            
            return list_
            
    
        if c == '+' :
            a = stack[-2]
            b = stack[-1]
            num = a+b
            pop_and_stack(stack,num)

        elif c== "-":
            a = stack[-2]
            b = stack[-1]
            num = a-b
            pop_and_stack(stack,num)
        elif c =='*':
            a = stack[-2]
            b = stack[-1]
            num = a*b
            pop_and_stack(stack,num)  
        elif c == '/':
            a = stack[-2]
            b = stack[-1]
            num = a/b
            pop_and_stack(stack,num)
        else:
            stack.append(int(c))
 
print(input())         
#print(stack[-1]) 


### FIXED CODE ###

stack = []
store_num = []
store_result = []

for i,c in enumerate(input().split()): 
        
        def pop_and_stack(list_,num):
                     
            list_.pop()
            list_.pop()
            list_.append(num)
            
            return list_
            
    
        if c == '+' :
            a = stack[-2]
            b = stack[-1]
            num = a+b
            pop_and_stack(stack,num)

        elif c== "-":
            a = stack[-2]
            b = stack[-1]
            num = a-b
            pop_and_stack(stack,num)
        elif c =='*':
            a = stack[-2]
            b = stack[-1]
            num = a*b
            pop_and_stack(stack,num)  
        elif c == '/':
            a = stack[-2]
            b = stack[-1]
            num = a/b
            pop_and_stack(stack,num)
        else:
            stack.append(int(c))
            
print(stack[-1])
R , C , K = map(int,input().split())
masu = [[0 for i in range(C)] for j in range(R)]
for i in range(K):
    r , c , v = map(int,input().split())
    masu[r-1][c-1] = v

dp0 = [[0 for i in range(C)] for j in range(R)]
dp1 = [[0 for i in range(C)] for j in range(R)]
dp2 = [[0 for i in range(C)] for j in range(R)] 
dp3 = [[0 for i in range(C)] for j in range(R)]

if masu[0][0] != 0:
    dp1[0][0] = masu[0][0]
for i in range(1,C):
    dp0[0][i] = max(dp0[0][i],dp0[0][i-1])
    dp1[0][i] = max(dp1[0][i],dp1[0][i-1])
    dp2[0][i] = max(dp2[0][i],dp2[0][i-1])
    dp3[0][i] = max(dp3[0][i],dp3[0][i-1])
    if masu[0][i] != 0:
        dp3[0][i] = max(dp3[0][i],dp2[0][i]+masu[0][i])
        dp2[0][i] = max(dp2[0][i],dp1[0][i]+masu[0][i])
        dp1[0][i] = max(dp1[0][i],dp0[0][i]+masu[0][i])


if R == 1:
    print(dp[-1][-1])
    exit()

for i in range(1,R):
    for j in range(C):
        dp0[i][j] = max(dp0[i][j],dp0[i-1][j],dp1[i-1][j],dp2[i-1][j],dp3[i-1][j])
        if j != 0:
            dp0[i][j] = max(dp0[i][j],dp0[i][j-1])
            dp1[i][j] = max(dp1[i][j],dp1[i][j-1])
            dp2[i][j] = max(dp2[i][j],dp2[i][j-1])
            dp3[i][j] = max(dp3[i][j],dp3[i][j-1])
        if masu[i][j] != 0:
            dp3[i][j] = max(dp3[i][j],dp2[i][j]+masu[i][j])
            dp2[i][j] = max(dp2[i][j],dp1[i][j]+masu[i][j])
            dp1[i][j] = max(dp1[i][j],dp0[i][j]+masu[i][j])
print(max(dp0[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1]))

### FIXED CODE ###

R , C , K = map(int,input().split())
masu = [[0 for i in range(C)] for j in range(R)]
for i in range(K):
    r , c , v = map(int,input().split())
    masu[r-1][c-1] = v

dp0 = [[0 for i in range(C)] for j in range(R)]
dp1 = [[0 for i in range(C)] for j in range(R)]
dp2 = [[0 for i in range(C)] for j in range(R)] 
dp3 = [[0 for i in range(C)] for j in range(R)]

if masu[0][0] != 0:
    dp1[0][0] = masu[0][0]
for i in range(1,C):
    dp0[0][i] = max(dp0[0][i],dp0[0][i-1])
    dp1[0][i] = max(dp1[0][i],dp1[0][i-1])
    dp2[0][i] = max(dp2[0][i],dp2[0][i-1])
    dp3[0][i] = max(dp3[0][i],dp3[0][i-1])
    if masu[0][i] != 0:
        dp3[0][i] = max(dp3[0][i],dp2[0][i]+masu[0][i])
        dp2[0][i] = max(dp2[0][i],dp1[0][i]+masu[0][i])
        dp1[0][i] = max(dp1[0][i],dp0[0][i]+masu[0][i])




for i in range(1,R):
    for j in range(C):
        dp0[i][j] = max(dp0[i][j],dp0[i-1][j],dp1[i-1][j],dp2[i-1][j],dp3[i-1][j])
        if j != 0:
            dp0[i][j] = max(dp0[i][j],dp0[i][j-1])
            dp1[i][j] = max(dp1[i][j],dp1[i][j-1])
            dp2[i][j] = max(dp2[i][j],dp2[i][j-1])
            dp3[i][j] = max(dp3[i][j],dp3[i][j-1])
        if masu[i][j] != 0:
            dp3[i][j] = max(dp3[i][j],dp2[i][j]+masu[i][j])
            dp2[i][j] = max(dp2[i][j],dp1[i][j]+masu[i][j])
            dp1[i][j] = max(dp1[i][j],dp0[i][j]+masu[i][j])
print(max(dp0[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1]))
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
C = []
for i in range(H):
    C.append([input().replace(".","0").replace("#","1")])

C_arr = np.array(C)

In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)

### FIXED CODE ###

H, W, K = list(map(int, input().split()))
 
c = [list(input()) for i in range(H)]
 
cnt = 0
for i in range(2**H):
    for j in range(2**W):
        cnt_black = 0
        for k in range(H):
            if (i >> k) & 1:
                continue
            for l in range(W):
                if (j >> l) & 1:
                    continue
                if c[k][l] == '#':
                    cnt_black += 1
        if cnt_black == K:
            cnt += 1
 
print(cnt)