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

h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=defaultdict(list)
wd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1
    wd2[w0].append(h0)

max_h_list = [kv[0] for kv in hd.items() if kv[1] == max(hd.values())]
max_w_list = [kv[0] for kv in wd.items() if kv[1] == max(wd.values())]

ans=float('inf')
for x in max_h_list:
    hlist=hd2[x]
    for y in max_w_list:
        if y in hlist:
            ans=min(ans,1)
        else:
            ans=min(ans,0)

print(hd[max_h_list[0]]+wd[max_w_list[0]]-ans)

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
h,w,m=map(int, input().split())
hd=[0 for i in range(h+1)]
wd=[0 for i in range(w+1)]
hw=defaultdict(int)
hmax=0
wmax=0
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hmax=max(hmax,hd[h0])
    wd[w0]+=1
    wmax=max(wmax,wd[w0])
    hw[(h0,w0)]+=1

max_h_list=[]
max_w_list=[]
for k in range(h+1):
    if hd[k]==hmax:
        max_h_list.append(k)

for k in range(w+1):
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break
print(hmax+wmax-ans)
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

current_max = len(n_dm_set)**2+d_dm

bucket = [0]*(N+1)
for t in n_dm_set:
    bucket[t] = -1

d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    t = t_arr[i]
    if bucket[t] != 0:
        continue
    d = d_arr[i]
    bucket[t] = d
    if len(small_arr) == 0:
        break
    d_x += d
    d_x -= small_arr[-1]
    small_arr = small_arr[:-1]
    nt_x += 1
    current_max = max(current_max, nt_x**2+d_x)

print(current_max)


### FIXED CODE ###

N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

current_max = len(n_dm_set)**2+d_dm

n_x_set = set(n_dm_set)
d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    if not small_arr:
        break
    t = t_arr[i]
    d = d_arr[i]
    if t in n_x_set:
        continue
    n_x_set.add(t)
    d_x += d
    d_x -= small_arr.pop()
    nt_x += 1
    current_max = max(current_max, nt_x**2+d_x)

print(current_max)
### BUGGY CODE ###

s=input()[::-1]

count=[0]*2019
count[0]+=1
gh=0
for i in range(0,len(s)):
    gh+=int(s[i])*(10**i)
    count[gh%2019]+=1

ans=0

for cnt in count:
    ans+=cnt*(cnt-1)//2

print(ans)



### FIXED CODE ###

s=input()[::-1]

count=[0]*2019
count[0]+=1
sd=0
d=1
for c in s:
   sd+=int(c)*d
   sd%=2019
   d*=10
   d%=2019
   count[sd]+=1

ans=0
for cnt in count:
    ans+=cnt*(cnt-1)//2

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

def solve():
    alpha = "abcdefghijklmnopqrstuvwxyz"
    inp1, inp2 = input(), input()
    sz = dict(zip(list(alpha), [0] * 26))
    tz = dict(zip(list(alpha), [0] * 26))
    siz = dict(zip(list(alpha), [[] for _ in range(26)]))
    tiz = dict(zip(list(alpha), [[] for _ in range(26)]))
    for i in range(len(inp1)):
        sz[inp1[i]] += 1
        tz[inp2[i]] += 1
        siz[inp1[i]].append(i)
        tiz[inp2[i]].append(i)
        if (sz[inp1[i]] != tz[inp2[i]]
                or siz[inp1[i]] != tiz[inp2[i]]):
            print("No")
            return
    print("Yes")


solve()


### FIXED CODE ###

def solve():
  from collections import Counter
  s = [i for i in sorted(Counter(input()).values())]
  t = [i for i in sorted(Counter(input()).values())]
  print(["No","Yes"][s==t])

solve()
### BUGGY CODE ###

def main():

    N, K, Q = map(int, input().split())
    player = [K] * N
    A = []
    for _ in range(Q):
        a = int(input())
        A.append(a)
    for i in range(Q):
        player[A[i] - 1] += 1
        player = [j - 1 for j in player]
    for k in range(N):
        if player[k] <= 0:
            print("No")
        else:
            print("Yes")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

def main():

    N, K, Q = map(int, input().split())
    player = np.array([K - Q] * N)
    sub = np.array([-1] * N)
    A = [int(input()) for i in range(Q)]
    for i in range(Q):
        player[A[i] - 1] += 1
    for k in range(N):
        if player[k] <= 0:
            print("No")
        else:
            print("Yes")

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

import sys, math, copy
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial

sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
maze = [[c for c in input()] for _ in range(H)]

moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def chkcell(maze_copy, h, w):
    if 0<=h and h<H and 0<=w and w<W and maze_copy[h][w]=='.':
        return True

def count_steps(q, maze_copy):
    steps = -1
    while len(q):
#        print('q:', q)
#        print('maze:')
#        for row in maze_copy:
#            print(row)
        steps += 1
        next_cells = []
        cells = q.pop()
        for cell in cells:
            maze_copy[cell[0]][cell[1]] = '#'
            for move in moves:
                newcell = tuple(i+j for i, j in zip(cell, move))
                if chkcell(maze_copy=maze_copy, h=newcell[0], w=newcell[1]):
                    next_cells.append(newcell)
        if next_cells:
            q.append(next_cells)

#    print('max_step:', steps)
    return steps

res = 0
for i in range(H):
    for j in range(W):
#        print('i, j', i, j)
        if maze[i][j] == '#':
            continue
        q = deque()
        q.append([[i, j]])
#        maze_copy = copy.deepcopy(maze)
        maze_copy = [[c for c in row] for row in maze]
        val = count_steps(q, maze_copy)
        if res < val: res = val

print(res)



### FIXED CODE ###

from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

def check(ny, nx, sS):
    if 0<=ny<H and 0<=nx<W:
        if sS[ny][nx]=='.':
            return True
    else:
        return False

def bfs(sy, sx, sS):
    deq = deque()
    deq.append([(sy-1, sx-1)]) # insert indices
    sS[sy-1][sx-1] = '#'
    ddy = [-1, 0, 1, 0]
    ddx = [0, -1, 0, 1]
    step = 0
    while deq[0]:
        #print('deq', deq)
        nqueue = []
        cqueue = deq.popleft()
        for val in cqueue:
            y, x = val
            for dy, dx in zip(ddy, ddx):
                ny, nx = y+dy, x+dx
                if check(ny, nx, sS):
                    sS[ny][nx] = '#'
                    nqueue.append((ny, nx))
        deq.append(nqueue)
        if not(deq[0]):
            break
        step += 1
    return step

res = 0
for i in range(H):
    for j in range(W):
        #print('i, j:', i, j)
        if S[i][j] == '.':
            sS = deepcopy(S)
            val = bfs(i+1, j+1, sS)
            res = max(res, val)

print(res)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
midlen = sum(A)/2
B = [sum(A[:i]) for i in range(N+1)]
ans = 2*min(abs(B[i]-midlen) for i in range(N+1))
print(int(ans))

### FIXED CODE ###

N = int(input())
A = [0]
Sum = 0
for s in input().split():
    s = int(s)
    Sum += s
    A.append(Sum)
mid = A[-1]/2
ans = 2*min(abs(A[i]-mid) for i in range(N+1))
print(int(ans))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0

for i in range(len(P)):
  if P[i] == min(P[:i+1]):
    cnt += 1

print(cnt)


### FIXED CODE ###

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

'''
参考
https://cocoinit23.com/abc152/
すべての(i, j)を調べていると制限時間を超過してしまう。
listの2つ目の要素(index=1)から順に見ていって、最小値が更新されたら解をカウントアップする。
ただし、解の最小値は常に1となるので、解の初期値は1にしておくこと。
'''
ans = 1
min_p = P[0]

for i in range(1, N):
    if P[i] <= min_p:
        min_p = P[i]
        ans += 1

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

while True:
    H,W=map(int,raw_input().split())
    if H==W==0:break
    L=[["*"]+list(raw_input())+["*"] for i in range(H)]
    L.append(["*"]*(W+2))
    L.insert(0,["*"]*(W+2))
    dp=[[set() for i in range(W+2)] for i in range(H+2)]
    T=[[[0,0] for i in range(W+2)] for i in range(H+2)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            if L[i][j]==".":
                T[i][j][0]+=T[i][j-1][0]+1
                T[i][j][1]+=T[i-1][j][1]+1
    maxInt=0
    for i in range(1,H+2):
        for j in range(1,W+2):
            if L[i][j]==".":
                if L[i-1][j]==L[i][j-1]=="*":
                    dp[i][j].add((1,1))
                    maxInt=max(maxInt,1)
                elif L[i-1][j]=="*":
                    for k in dp[i][j-1]:
                        dp[i][j].add((k[0]+1,1))
                        maxInt=max(maxInt,k[0]+1)
                elif L[i][j-1]=="*":
                    for k in dp[i-1][j]:
                        dp[i][j].add((1,k[1]+1))
                        maxInt=max(maxInt,k[1]+1)
                else:
                    h=T[i][j][1]
                    l=T[i][j][0]
                    for k in dp[i][j-1]:
                        m=min(k[1],h)
                        dp[i][j].add((k[0]+1,m))
                        maxInt=max(maxInt,(k[0]+1)*m)
                    for k in dp[i-1][j]:
                        m=min(k[0],l)
                        dp[i][j].add((m,k[1]+1))
                        maxInt=max(maxInt,m*(k[1]+1))
        dp[i-1]=[]
    print maxInt

### FIXED CODE ###

def histogram(mass, h, w):
    table = [[0]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if mass[i][j] == '*':
                table[i][j] = 0
            else:
                table[i][j] = table[i-1][j] + 1
    return table


def get_rectangle_area(table, w):
    maxv = 0
    stack = []
    table.append(0)
    for i, rect in enumerate(table):
        if stack == []:
            stack.append((rect, i))
        elif stack[-1][0] < rect:
            stack.append((rect, i))
        elif stack[-1][0] == rect:
            pass
        elif stack[-1][0] > rect:
            while stack != [] and stack[-1][0] >= rect:
                high, pos = stack.pop()
                maxv = max(maxv, high*(i-pos))
            stack.append((rect, pos))
    return maxv

while True:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break
    mass = [raw_input() for i in range(h)]
    table = histogram(mass, h, w)
    ans = 0
    for tab in table:
        ans = max(ans, get_rectangle_area(tab, w))
    print ans
### BUGGY CODE ###

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys
from functools import reduce
N,K = map(int,sys.stdin.readline().split())

A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
pre = reduce((lambda x, y: x * y), [A[i] for i in range(K)])

for i in range(K,N):
    #print(i)
    cur = (pre//A[i-K])*A[i]
    if pre < cur:
        print("Yes")
    else:
        print("No")
    pre = cur


### FIXED CODE ###

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys
from functools import reduce
N,K = map(int,sys.stdin.readline().split())

A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

#pre = reduce((lambda x, y: x * y), [A[i] for i in range(K)])
for i in range(K,N):
    #print(i)
    # cur = (pre//A[i-K])*A[i]
    if A[i-K] < A[i]:
        print("Yes")
    else:
        print("No")
    # if pre < cur:
    #
    # else:
    #     print("No")
    # pre = cur
### BUGGY CODE ###

from collections import defaultdict

class Unionfind:

    __slots__ = ['parents','sizes']

    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1]*n

    def root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root_x = self.root(self.parents[x])
            self.parents[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x

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

    # 集合自体の数 ({1,2}, {3}, {4} : kind -> 3)
    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.parents)))

    # xが属する集合の要素の数　({1,2,3} : size(2) -> 3)
    def size(self, x):
        self.sizes[x] = self.sizes[self.root(x)]
        return self.sizes[x]

N, K, L = map(int,input().split())
road = Unionfind(N)
train = Unionfind(N)

for _ in range(K):
    p, q = map(int,input().split())
    p -= 1; q -= 1
    road.unite(p, q)

for _ in range(L):
    r, s = map(int,input().split())
    r -= 1; s -= 1
    train.unite(r, s)

ans_list = []

r = defaultdict(set)
for i in range(N):
    r[road.root(i)].add(i)

t = defaultdict(set)
for i in range(N):
    t[train.root(i)].add(i)

ans_list = []

for i in range(N):
    ans = len(r[road.root(i)] & t[train.root(i)])
    ans_list.append(ans)

print(*ans_list)

### FIXED CODE ###

from collections import defaultdict

class Unionfind:

    __slots__ = ['parents','sizes']

    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1]*n

    def root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root_x = self.root(self.parents[x])
            self.parents[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x

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

    # 集合自体の数 ({1,2}, {3}, {4} : kind -> 3)
    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.parents)))

    # xが属する集合の要素の数　({1,2,3} : size(2) -> 3)
    def size(self, x):
        self.sizes[x] = self.sizes[self.root(x)]
        return self.sizes[x]

N, K, L = map(int,input().split())
road = Unionfind(N)
train = Unionfind(N)

for _ in range(K):
    p, q = map(int,input().split())
    p -= 1; q -= 1
    road.unite(p, q)

for _ in range(L):
    r, s = map(int,input().split())
    r -= 1; s -= 1
    train.unite(r, s)

cnt = defaultdict(int)

for i in range(N):
    key = (road.root(i), train.root(i))
    cnt[key] += 1

ans_list = []
for i in range(N):
    key = (road.root(i), train.root(i))
    ans = cnt[key]
    ans_list.append(ans)

print(*ans_list)
### BUGGY CODE ###

s=input()
x,y=map(int,input().split())
t=s.split("T")
x-=len(t[0])
dx,dy=[],[]

for i,tt in enumerate(t[1:]):
  if i%2==1:
    dx.append(len(tt))
  else:
    dy.append(len(tt))
x=abs(x)
y=abs(y)
if max(x,y)>8000:
  print("No")
  exit(0)
def is_ok(n,l):
  dp=[[0]*16001 for _ in range(len(l)+1)]
  n+=8000
  dp[0][8000]=1
  for i in range(1,len(l)+1):
    for j in range(16001):
      if j+l[i-1]<=16000:
        dp[i][j+l[i-1]]|=dp[i-1][j]
      if j-l[i-1]>=0:
        dp[i][j-l[i-1]]|=dp[i-1][j]
  if dp[len(l)][n]==1:
    return True
  else:
    return False

if is_ok(abs(x),dx) and is_ok(abs(y),dy):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s=input()
x,y=map(int,input().split())
t=s.split("T")
x-=len(t[0])
dx,dy=[],[]

for i,tt in enumerate(t[1:]):
  if i%2==1:
    dx.append(len(tt))
  else:
    dy.append(len(tt))

def is_ok(n,l):
  dp=set([0])
  for d in l:
    t=[]
    for v in dp:
      t.append(v+d)
      t.append(v-d)
    dp=set(t)
  return True if n in dp else False

if is_ok(x,dx) and is_ok(y,dy):
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

X,Y,Z,K = (int(i) for i in input().split())
ax = [int(i) for i in input().split()]
by = [int(i) for i in input().split()]
cz = [int(i) for i in input().split()]
ab = [0] * (X*Y)
cnt = 0
for i in ax:
  for j in by:
    ab[cnt] = i + j
    cnt += 1
ab.sort(reverse=True)
kab = ab[:K]
ans = [0] * (len(kab)*Z)
cnt = 0
for i in kab:
  for j in cz:
    ans[cnt] = i + j
    cnt += 1
ans.sort(reverse=True)   
for i in range(K):
  print(ans[i])

### FIXED CODE ###

import heapq

X,Y,Z,K = (int(i) for i in input().split())
a = [-int(i) for i in input().split()]
b = [-int(i) for i in input().split()]
c = [-int(i) for i in input().split()]
q = []
S = set()
a.sort()
b.sort()
c.sort()

heapq.heappush(q,(a[0]+b[0]+c[0],0,0,0))

for i in range(K):
  p,i,j,k=heapq.heappop(q)
  print(-p)
  if i+1 < X and not((i+1,j,k) in S):
    S.add((i+1,j,k))
    heapq.heappush(q,(a[i+1]+b[j]+c[k],i+1,j,k))
  if j+1 < Y and not((i,j+1,k) in S):
    S.add((i,j+1,k))
    heapq.heappush(q,(a[i]+b[j+1]+c[k],i,j+1,k))
  if k+1 < Z and not((i,j,k+1) in S):
    S.add((i,j,k+1))
    heapq.heappush(q,(a[i]+b[j]+c[k+1],i,j,k+1))
### BUGGY CODE ###

def kouyakusuuset(x,y):
    lst=set()
    for i in range(1,x+1):
     if x%i==0 and y%i==0:
         lst.add(i)
    return(lst)
def sosuu(x):
    lst=set()
    for i in range(2,x+1):
        flag=0
        for s in lst:
            if i%s==0:
                flag=1
        if not flag:
            lst.add(i)
    return(lst)

A,B=map(int,input().split())
if A>B:A,B=B,A
lst=kouyakusuuset(A,B)
lst=list(lst)
sosuulst=sosuu(max(lst))
print(len([1 for i in lst if i in sosuulst])+1)


### FIXED CODE ###

A,B=map(int,input().split())
lst=set()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

if A==B==1:
    print(1)
else:
    print(len(set([i[0] for i in factorization(A)])&set([i[0] for i in factorization(B)]))+1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
total = sum(a)
for i in range(n):
    other = 0
    for j in range(n // 2):
        other += a[(i + 1 + 2 * j) % n]
    print(total - 2 * other, end = " ")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
total = sum(a)
other = 0
for i in range(n // 2):
    other += a[(1 + 2 * i) % n]
ans = [total - 2 * other]
for i in range(n - 1):
    ans.append(a[i] * 2 - ans[-1])
for i in range(n):
    print(ans[i], end = " ")
### BUGGY CODE ###

while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[] for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n].append(e)
        event[n].append(a)
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    for i in xrange(y):
        for k in xrange(maxm+1):
            for j in xrange(int(x)):
                if i+v[j]>=y:
                    dp[y][k]+=dp[i][k]/x
                    continue

                if event[i+v[j]]==[]:
                    dp[i+v[j]][k]+=dp[i][k]/x

                elif event[i+v[j]][0]==1:
                    skip=event[i+v[j]][1]
                    dp[min(y,i+skip)][k]+=dp[i][k]/x

                elif event[i+v[j]][0]==2:
                    m=event[i+v[j]][1]
                    dp[i+v[j]][k+m]+=dp[i][k]/x

                else:
                    m=event[i+v[j]][1]
                    dp[i+v[j]][max(0,k-m)]+=dp[i][k]/x

    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))

### FIXED CODE ###

def solve(x,y,maxm):
    for i in xrange(y):
        for j in xrange(maxm+1):
            if dp[i][j]==0:continue
            for k in xrange(int(x)):

                if event[min(y,i+v[k])][0]==0:
                    dp[min(y,i+v[k])][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==1:
                    skip=event[i+v[k]][1]
                    dp[min(y,i+v[k]+skip)][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==2:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][j+m]+=dp[i][j]/x

                else:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][max(0,j-m)]+=dp[i][j]/x
    return dp

while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[0]*2 for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n][0]=e
        event[n][1]=a
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    dp=solve(x,y,maxm)
    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))
### BUGGY CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
for i in range(m):
    A[0] = A[0]//2
    A = sorted(A,reverse=True)
print(sum(A))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
A = list(map(int,input().split()))
A = [(-a,a) for a in A]
heapq.heapify(A)
for i in range(m):
    max = heapq.heappop(A)[1]
    max //= 2
    heapq.heappush(A,(-max,max))
print(sum([a[1] for a in A]))