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

N = int(input())
data = [i for i in input().split()]

number_count = {}
for cmp in data:
    if cmp in number_count:
        number_count[cmp] += 1
        continue
    number_count[cmp] = 1

answer = {}
for i in range(N):
    if data[i] in answer:
        print(answer[data[i]])
        continue
    C = 0
    number_count_temp = number_count.copy()
    number_count_temp[str(data[i])] -= 1
    for cmp in number_count_temp:
        C += int(number_count_temp[cmp] * (number_count_temp[cmp] - 1) / 2)

    print(str(C))
    answer[data[i]] = str(C)


### FIXED CODE ###

N = int(input())
data = [i for i in input().split()]

number_count = {}
for cmp in data:
    if cmp in number_count:
        number_count[cmp] += 1
        continue
    number_count[cmp] = 1

C_tot = 0
for cmp in number_count:
    C_tot += int(number_count[cmp] * (number_count[cmp] - 1) / 2)

for k in range(N):
    C = C_tot - int(number_count[data[k]] * (number_count[data[k]] - 1) / 2) + int((number_count[data[k]] - 1) * (number_count[data[k]] - 2) / 2)
    print(str(C))
### BUGGY CODE ###

from math import log2,floor
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(61):
    bits = 0
    for x in A:
        if (x>>i)&1:
            bits += 1
    s = (bits*(N-bits))%mod
    t = (2**i)%mod
    ans = (ans+s*t)%mod
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
listA=[]
listIndexStock=[0]
index=0
while index < n:
    a = int(input())
    listA.append(a)
    index+=1

buttonLighted=0
pushCounter=0
index=0
while 1:
    pushCounter+=1
    if listA[buttonLighted] == 2:
        print(pushCounter)
        break
    elif listA[buttonLighted]-1 in listIndexStock:
        print(-1)
        break
    else:
        buttonLighted = listA[buttonLighted]-1
        listIndexStock.append(buttonLighted)


### FIXED CODE ###

import time

n = int(input())
listA=[]
index=0
while index < n:
    a = int(input())
    listA.append(a)
    index+=1

startT = time.time()
buttonLighted=0
pushCounter=0
index=0
while 1:
    pushCounter+=1
    if listA[buttonLighted] == 2:
        print(pushCounter)
        break
    else:
        buttonLighted = listA[buttonLighted]-1
    if time.time()-startT > 0.9:
        print(-1)
        break
### BUGGY CODE ###

n, m = map(int, input().split())
if m%2:
    if m//n % 2:
        for i in range(m//n, 0, -2):
            if not m%i:
                print(i)
                break
    else:
        for i in range(m//n+1, 0, -2):
            if not m%i:
                print(i)
                break
else:
    for i in range(m//n, 0, -1):
        if not m%i:
            print(i)
            break

### FIXED CODE ###

n, m = map(int, input().split())
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1
if is_prime(m):
    print(1)
else:
    for i in range(m//n, 0, -1):
        if not m%i:
            print(i)
            break
### BUGGY CODE ###

N,Q=map(int,input().split())
s=list(input())
l=[]
def times(l,s):
    first=l[0]-1
    last=l[1]
    ss=[]
    count=0
    #5,4
    for i in range(first,last):
        ss.append(s[i])
    #print(ss)
    for i in range(len(ss)-1):
        if ss[i]=='A' and ss[i+1]=='C':
            count+=1
    return count

for i in range(Q):
    a=list(map(int,input().split()))
    l.append(a)
#print(l)

    
for c in l:
    ans=times(c,s)
    print(ans)






### FIXED CODE ###

N,Q=map(int,input().split())
s=input()
#a=[]

l=[0]*(N)
for i in range(N-1):
    if s[i:i+2]=='AC':
        l[i+1]=l[i]+1
    else:
        l[i+1]=l[i]
#print(l)
ans=[]
for i in range(Q):
    first,last=map(int,input().split())
    ans.append(l[last-1]-l[first-1])

for i in ans:
    print(i)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = list(map(int, readline().split()))
ans = 1
for aa in a:
    ans *= aa
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = list(map(int, readline().split()))
a.sort()
ans = 1
for aa in a:
    ans *= aa
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))
dp = [10**10 for i in range(N+1)]
dp[0] = dp[1] = 0
for i in range(1, N+1):
    for k in range(1, K+1):
        if i + k <= N:
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))
dp = [10**10] * (N+1)
dp[0] = dp[1] = 0
for i in range(1, N+1):
    for k in range(1, K+1):
        if i + k <= N:
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
print(dp[N])
### BUGGY CODE ###

import math
from itertools import accumulate
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))

    for _ in range(K):
        data = [0] * len(A)
        for i in range(N):
            range_mai = math.ceil(i - A[i] - 0.5)
            range_pura = math.floor(i + A[i] + 0.5)
            if range_mai < 0:
                range_mai = 0
            if range_pura > N - 1:
                range_pura = N - 1
            data[range_mai] += 1
            if range_pura + 1 != N:
                data[range_pura + 1] -= 1
            
        ruiseki = list(accumulate(data))
        A = ruiseki
        if min(A) == N:
            break
    print(*A)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from itertools import accumulate
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))

    for _ in range(K):
        data = [0] * len(A)
        for i in range(N):
            range_mai = i - A[i]
            range_pura = i + A[i]
            if range_mai < 0:
                range_mai = 0
            if range_pura > N - 1:
                range_pura = N - 1
            data[range_mai] += 1
            if range_pura + 1 != N:
                data[range_pura + 1] -= 1

        A = list(accumulate(data))
        if min(A) == N:
            break
    print(*A)

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

def main():
    N, M = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0])
    ans = 0
    choice = []
    pointer = 0
    for m in range(1, M+1):
        for a, b in AB[pointer:]:
            if a > m:
                break
            choice.append([a, b])
            pointer += 1
        if len(choice) > 0:
            a, b = sorted(choice, key=lambda x: x[1], reverse=True)[0]
            ans += b
            choice.remove([a, b])
    print(ans)
main()

### FIXED CODE ###

from heapq import heappush as hpush
from heapq import heappop as hpop

class Descending_HeapQueue:
    def __init__(self, hq=[]):
        self.hq = []
        for i in hq:
            self.push(i)
    def push(self, n):
        hpush(self.hq, -n)
    def pop(self):
        return -hpop(self.hq)
    def __len__(self):
        return len(self.hq)

def main():
    N, M = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    ans = 0
    dhq = Descending_HeapQueue()
    pointer = 0
    for m in range(1, M+1):
        while (pointer < N) and (AB[pointer][0] <= m):
            dhq.push(AB[pointer][1])
            pointer += 1
        if len(dhq) > 0:
            ans += dhq.pop()
    print(ans)
main()
### BUGGY CODE ###

N, M = map(int,input().split())
A = []
B = []
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        if b in A:
            print('POSSIBLE')
            exit()
        else:
            B.append(b)
    if b == N:
        if a in B:
            print('POSSIBLE')
            exit()
        else:
            A.append(a)
print('IMPOSSIBLE')


### FIXED CODE ###

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if A & B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###



def diff_colors(x, m, modp):
    """
    長さxの列をm色で塗る
    このとき、連続して同じ色を使わないパターン数を数える
    """
    ans = m
    x -= 1
    while x:
        ans *= (m - 1)
        ans %= modp
        x -= 1
    return ans

def factorial(x, modp):
    fact = dict()
    fact[0] = 1
    curr = 1
    while curr <= 2 * x:
        fact[curr] = fact[curr - 1] * curr
        fact[curr] %= modp
        curr += 1
    return fact


def pow(x, k, modp):
    ans = 1
    while k:
        if k % 2:
            ans *= x
            ans %= modp
        x *= x
        x %= modp
        k //= 2
    return ans


def combi(fact, n, k, modp):
    ans = fact[n + k - 1]
    ans *= pow(fact[k], modp - 2, modp)
    ans %= modp
    ans *= pow(fact[n - 1], modp - 2, modp)
    ans %= modp
    return ans


def submit():
    n, m, k = map(int, input().split())
    modp = 998244353
    fact = factorial(n, modp)

    ans = 0
    base_pattern = diff_colors(n - k, m, modp)
    for i in range(k + 1):
        ans += base_pattern * combi(fact, n - (k - i), k - i, modp)
        ans %= modp
        base_pattern *= (m - 1)
        base_pattern %= modp

    print(ans)
    

if __name__ == "__main__":
    submit()    

### FIXED CODE ###



def diff_colors(x, m, modp):
    """
    長さxの列をm色で塗る
    このとき、連続して同じ色を使わないパターン数を数える
    """
    ans = m
    x -= 1
    while x:
        ans *= (m - 1)
        ans %= modp
        x -= 1
    return ans

def factorial(x, modp):
    fact = dict()
    fact[0] = 1
    curr = 1
    while curr <= 2 * x:
        fact[curr] = fact[curr - 1] * curr
        fact[curr] %= modp
        curr += 1
    return fact


def pow(x, k, modp):
    ans = 1
    while k:
        if k % 2:
            ans *= x
            ans %= modp
        x *= x
        x %= modp
        k //= 2
    return ans


def combi(fact, n, k, modp):
    ans = fact[n + k - 1]
    ans *= pow(fact[k], modp - 2, modp)
    ans %= modp
    ans *= pow(fact[n - 1], modp - 2, modp)
    ans %= modp
    return ans


def submit():
    n, m, k = map(int, input().split())
    modp = 998244353
    fact = factorial(n, modp)

    ans = 0
    base_pattern = diff_colors(n - k, m, modp)
    for i in range(k + 1):
        ans += base_pattern * combi(fact, n - (k - i), k - i, modp)
        ans %= modp
        base_pattern *= (m - 1)
        base_pattern %= modp

    print(ans)
    

if __name__ == "__main__":
    submit()
### BUGGY CODE ###

import math
N = int(input())
x = [list(map(int, input().split())) for _ in range(N)]
nlst = '01234567'
xlst = []
a = [-1] * N
def dfs(cnt):
    if cnt == N:
        tmpF = True
        for i in range(N):
            if a.count(int(nlst[i])) != 1:
                tmpF = False
                break
        if tmpF:
            tmp = 0
            for i in range(1, N):
                tmp += math.sqrt(((x[a[i - 1]][0] - x[a[i]][0]) ** 2) + (x[a[i - 1]][1] - x[a[i]][1]) ** 2)
            xlst.append(tmp)
        return

    for i in range(N):
        a[cnt] = i
        dfs(cnt + 1)

dfs(0)

kain = 1
for i in range(1, N + 1):
    kain *= i

print(sum(xlst) / kain)

### FIXED CODE ###

import itertools
import math
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
p = []
cnt = 0

for v in itertools.permutations(xy, N):
    p.append(v)

ans = 0
for i in range(len(p)):
    for j in range(N - 1):
        ans += math.sqrt((p[i][j][0] - p[i][j + 1][0]) ** 2 + (p[i][j][1] - p[i][j + 1][1]) ** 2)

print(ans / len(p))
### BUGGY CODE ###

import numpy as np
import math

_, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

logk = 50
half = len(a) / 2

base = np.array([2**i for i in range(logk + 1)])

a = np.array(a)

ones = a[:,None] & base > 0
zeros = (ones != True)

# print(base[:5])
# print(ones)
# print(zeros)

no = np.sum(ones, axis=0)
nz = np.sum(zeros, axis=0)

ov = no * base
zv = nz * base

# print(no)
# print(nz)

inc = no < half
# vi = np.sum(v * base)


def largest(fx, kk, i):
    if i == len(base):
        return fx

    kone = kk + base[i]
    kzero = kk
    fzero = fx + ov[i]
    if kone <= k:
        fone = fx + zv[i]
        return max(largest(fzero, kzero, i + 1), largest(fone, kone, i + 1))
    return largest(fzero, kzero, i+1)

print(largest(0, 0, 0))


# print(np.sum(a ^ vi))


### FIXED CODE ###

import numpy as np
import math

_, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

logk = 50
half = len(a) / 2

base = np.array([2**i for i in range(logk + 1)])

a = np.array(a)

ones = a[:,None] & base > 0
zeros = (ones != True)

# print(base[:5])
# print(ones)
# print(zeros)

no = np.sum(ones, axis=0)
nz = np.sum(zeros, axis=0)

ov = no * base
zv = nz * base

# print(no)
# print(nz)

inc = ov < zv

inceq = ov == zv
# vi = np.sum(v * base)


# def largest(fx, kk, i):
#     if i == len(base):
#         return fx

#     kone = kk + base[i]
#     if kone > k:
#         return fx

#     kzero = kk
#     fzero = fx + ov[i]
#     fone = fx + zv[i]
#     return max(largest(fzero, kzero, i + 1), largest(fone, kone, i + 1))

# print(largest(0, 0, 0))

kk = [0]
fx = [0]
for i, b in reversed(list(enumerate(base))):
    for j in range(len(fx)):
        added = kk[j] + b
        if (inc[i] or inceq[i]) and added <= k:
            if inceq[i]:
                fx.append(fx[j] + ov[i])
                kk.append(kk[j])
            fx[j] += zv[i]
            kk[j] += b

        else:
            fx[j] += ov[i]

print(max(fx))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
a_set = set(a)
a_dict = dict([(i, a.count(i))for i in a_set])
a_sum = sum(a)

for i in range(q):
    b,c = map(int,input().split())
    if not b in a_dict:
        print(a_sum)
        continue
    a_sum = a_sum - a_dict[b]*b + a_dict[b]*c
    if c in a_dict:
        a_dict[c] = a_dict[c] + a_dict[b]
    else:
        a_dict[c] = a_dict[b]
    a_dict[b] = 0
    print(a_sum)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
a_dict = dict()
for i in a:
    if i in a_dict:
        a_dict[i] = a_dict[i] + 1
    else:
        a_dict[i] = 1
a_sum = sum(a)

for i in range(q):
    b,c = map(int,input().split())
    if not b in a_dict:
        print(a_sum)
        continue
    a_sum = a_sum - a_dict[b]*b + a_dict[b]*c
    if c in a_dict:
        a_dict[c] = a_dict[c] + a_dict[b]
    else:
        a_dict[c] = a_dict[b]
    a_dict[b] = 0
    print(a_sum)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    a = [[0]*(N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        a[l][r] += 1

    for i in range(1, N+1):
        for j in range(1, N+1):
            a[i][j] = a[i][j]+a[i][j-1]

    for pp, qq in zip(p, q):
        print(int(sum([a[i][qq]-a[i][pp-1] for i in range(pp, qq+1)])))
    # print(a)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


class Bit:
    def __init__(self, n, m):
        self.size = [n, m]
        self.tree = [[0] * (n + 1) for _ in range(m+1)]

    def sum(self, i, j):
        s = 0
        while i > 0:
            jj = j
            while jj > 0:
                s += self.tree[i][jj]
                jj -= jj & -jj
            i -= i & -i
        return s

    def add(self, i, j, x):
        while i <= self.size[0]:
            jj = j
            while jj <= self.size[1]:
                self.tree[i][jj] += x
                jj += jj & -jj
            i += i & -i


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    b = Bit(N, N)

    for l, r in zip(L, R):
        b.add(N-l+1, r, 1)

    for pp, qq in zip(p, q):
        print(b.sum(N-pp+1, qq))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


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

n,k = map(int,input().split())
h = list(map(int, input().split()))
v = [0 for _ in range(n)]
for i in range(1,n):
	v[i] = min([v[j] + abs(h[j]-h[i]) for j in range(max(0, i-k), i)])
print(v[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

black_idx = set()
white_idx = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == ".":
            white_idx.add((h,w))
        else:
            black_idx.add((h,w))

ans = 0
for white in white_idx:
    tmp = float("inf")
    for black in black_idx:
        tmp = min(tmp, abs(white[0] - black[0]) + abs(white[1] - black[1]))
    ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1], [int(y)-1, int(x)], [int(y), int(x)-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

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

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

n = 1000000000000000001

for i in range(n):
    if i % x == 0 and i % y != 0:
        print(i)
        exit()
print(-1)

### FIXED CODE ###

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

if x % y == 0:
    print(-1)
else:
    print(x)
### BUGGY CODE ###

import sys

def Not_Divisible(n,p):
    k=0
    for i,a in enumerate(p):
        for j,b in enumerate(p):
            if b == 1:
                return 0 if p.count(1) > 1 else 1
            if  i != j and a % b == 0:
                k-=1
                break
        k+=1
    return k

if __name__ == '__main__':
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = list(map(int,inp2))
    print(Not_Divisible(n,p))

### FIXED CODE ###

import sys

def Not_Divisible(n,p):
    maxp = max(p)
    dp = [[True,0] for _ in range(maxp+1)]
    for a in p:
        dp[a][1]+=1
        t =2
        while a*t <= maxp:
            if dp[a*t][0] == True :
                dp[a*t][0] = False
            t+=1
    k=0
    for d in p:
        if dp[d][1] == 1 and dp[d][0] == True:
            k+=1
    return k


def main():
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = tuple(map(int,inp2))
    print(Not_Divisible(n,p))


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

R,C,K = map(int,input().split())
dp = [[[0 for l in range(4)] for _ in range(C+1)] for f in range(R+1)]
vl = [[0 for _ in range(C+1)] for f in range(R+1)]

for i in range(K):
	r,c,v = map(int,input().split())
	vl[r][c] = v

for i in range(1, R+1):
	for j in range(1, C+1):
		dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3])
		for k in range(3, 0, -1):
			dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k], dp[i][j][k-1]+vl[i][j], dp[i][j-1][k-1]+vl[i][j])
		
print(max(dp[R][C][0], dp[R][C][1], dp[R][C][2], dp[R][C][3]))

### FIXED CODE ###

R,C,K = map(int,input().split())
dp0 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp1 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp2 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp3 = [[0 for _ in range(C+1)] for f in range(R+1)]
vl = [[0 for _ in range(C+1)] for f in range(R+1)]

for i in range(K):
	r,c,v = map(int,input().split())
	vl[r][c] = v

for i in range(1, R+1):
	for j in range(1, C+1):
		dp0[i][j] = max(dp0[i][j], dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
		dp3[i][j] = max(dp3[i][j], dp3[i][j-1], dp2[i][j-1]+vl[i][j], dp2[i][j]+vl[i][j])
		dp2[i][j] = max(dp2[i][j], dp2[i][j-1], dp1[i][j-1]+vl[i][j], dp1[i][j]+vl[i][j])
		dp1[i][j] = max(dp1[i][j], dp1[i][j-1], dp0[i][j-1]+vl[i][j], dp0[i][j]+vl[i][j])

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))
### BUGGY CODE ###


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

result=0
LR=[]
for i in range(M):
        LR.append(input().split())


for i in range(N+1):#0からNまで
    counter=0
    flag=False
    for j in LR:
        if flag:
            break
        L=int(j[0])
        R=int(j[1])
        if i<L or R<i:
            flag=True
            break
        if L<=i and i<=R:
            counter+=1

    if counter==M:
        result+=1
print(result)


### FIXED CODE ###


N,M=map(int,input().split())#ID,ゲート


LR=[]
for i in range(M):
        LR.append(input().split())


numbers=[]
for i in range(N+1):
    numbers.append(i)




Lmax=1
Rmax=100000
for j in LR:

    L=int(j[0])
    R=int(j[1])

    if Lmax<L:
        Lmax=L
    if Rmax>R:
        Rmax=R
result=0

for i in numbers:

    if i>=Lmax:

        if i<=Rmax:
            result+=1



print(result)
### BUGGY CODE ###

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

for i in range(m):
	c = a.index(max(a))
	a[c] = a[c]//2
	
print(sum(a))

### FIXED CODE ###

import heapq
import math

n,m=map(int,input().split())
a = map(int,input().split())
a = list(map(lambda x:x*-1,a))

heapq.heapify(a)

for _ in range(m):
	l = heapq.heappop(a)
	l = math.ceil(l/2)
	heapq.heappush(a,l)

print(abs(sum(list(a))))