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

H, W, A, B = list(map(int, input().split(' ')))
def move(i, j, H, W, A, B):
    grid = [[0 for i in range(W)] for j in range(H)]
    
    for i in range(H-A):
        grid[i][0] = 1
    for i in range(W):
        grid[0][i] = 1
    # print(grid)
    for i in range(1, H):
        for j in range(1, W):
            # print(grid)
            upper = 0
            try:
                upper = grid[i-1][j]
            except:
                pass
            left = 0
            try:
                left = grid[i][j-1]
            except:
                pass
            if (i >= (H-A) and j < B):
                continue
            else:
                grid[i][j] = upper + left
    return grid[H-1][W-1]
    

ways = move(1, 1, H, W, A, B)
print(ways % (10**9 + 7))

### FIXED CODE ###


# Function to find modulo inverse of b. It returns  
# -1 when inverse doesn't  
# modInverse works for prime m 
def gcd(b, m):
  if b == 0:
    return m
  return gcd(m%b, b)

def modInverse(b,m): 
    g = gcd(b, m) 
    if (g != 1): 
        # print("Inverse doesn't exist")  
        return -1
    else:  
        # If b and m are relatively prime,  
        # then modulo inverse is b^(m-2) mode m  
        return pow(b, m - 2, m) 
  
  
# Function to compute a/b under modulo m  
def modDivide(a,b,m): 
    a = a % m 
    inv = modInverse(b,m) 
    if(inv == -1): 
        print("Division not defined") 
    else: 
        return (inv*a) % m

MOD = (10 ** 9) + 7
H, W, A, B = list(map(int, input().split(' ')))

DP = []
j = 1
for i in range(1,200002):
    j *= i
    j %= MOD
    DP.append(j)

# print(DP)
def factorial(i):
    if (i == 0):
        return 1
    global DP
    # print(i)
    # print(i, DP[i-1])
    # print(DP[i-1])
    return DP[i-1]

def move2(H, W, A, B):
    numPaths = 0
    h = H-A
    w = W-(W-B)+1
    a = A+1
    pttp = 0
    for b in range(w, W+1):
        # print(h, b, a, W-b+1)
        ttp = (factorial(h+b-2)*modInverse((factorial(h-1)*factorial(b-1))% MOD, MOD)) % MOD
        tpttp = ttp
        ttp -= pttp
        pttp = tpttp
        btp = (factorial(a+(W-b+1)-2)*modInverse((factorial(a-1)*factorial(W-b))% MOD, MOD)) % MOD
        # btp = factorial(a+(W-b+1)-2)//(factorial(a-1)*factorial(W-b))
        numPaths += ttp*btp
    return numPaths

ways = move2(H, W, A, B)
print(ways % (10**9 + 7))
### BUGGY CODE ###

import math

A, B = map(int, input().split())

ans = -1

for i in range(1, 100000000):
    if math.floor(i * 0.08) == A and math.floor(i * 0.1) == B:
        ans = i
        break
print(ans)

### FIXED CODE ###

import math

A, B = map(int, input().split())

ans = -1

for i in range(1, 1000000):
    if math.floor(i * 0.08) == A and math.floor(i * 0.1) == B:
        ans = i
        break
print(ans)
### BUGGY CODE ###

from functools import reduce
from math import gcd

N=int(input())
A=list(map(int, input().split()))
c=max(A)+1
C=[0]*c
f=1
for i in A:
    C[i]+=1

for i in range(2,c):
    cnt=0
    for j in range(i,c,i):
        cnt+=C[j]
    if cnt>1:
        f=0


if f==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

### FIXED CODE ###

from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j
f=0
for i in A:
    if i==1:
        continue
    temp=i
    while temp!=1:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 and temp>=temp2:
            temp=temp//temp2
    if f==1:
        break
        


if max(div)<=1 and f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')
### BUGGY CODE ###

n,m = map(int,input().split())
iki = []
iki2 = []
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        iki.append(b)
    if b == n:
        iki2.append(a)
        

flag = False
for i in iki:
    if i in iki2:
        flag = True
        break
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")



### FIXED CODE ###

n,m = map(int,input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        c[b] = True 
    if b == n:
        d[a] = True
        
flag = False
for i in range(200000):
    if c[i] and d[i]:
        flag = True
        break
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

for i in range(m):
    bc[i] = list(map(int, input().split()))

new = a

for i in range(m):
    new.extend([bc[i][1]] * bc[i][0])

new.sort()
ans = 0
n_len = len(new)

for i in range(n_len - 1, n_len - n - 1, -1):
    ans += new[i]

print(ans)


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

for i in range(m):
    bc[i] = list(map(int, input().split()))

a.sort()
bc = sorted(bc, key=lambda x: -x[1])
new = []

cnt = 0

for e in bc:
    new += [e[1]] * e[0]
    cnt += e[0]

    if (n <= cnt):
        break

for i in range(min(n, cnt)):
    a[i] = max(a[i], new[i])

print(sum(a))
### BUGGY CODE ###

import itertools


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))


x_dir = [[INF] * n for i in range(1 << n)]
y_dir = [[INF] * n for i in range(1 << n)]

for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state][i] = min(costs[i], x_dir[bit_state][i])
        y_dir[bit_state][i] = min(costs[i], y_dir[bit_state][i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state][j] = min(x_dir[bit_state][j], c * abs(yi - yj))
            y_dir[bit_state][j] = min(y_dir[bit_state][j], c * abs(xi - xj))


ans = [INF] * (n + 1)

for bit_state in range(1 << n):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit][i], y_dir[y_bit][i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

for res in ans:
    print(res)

### FIXED CODE ###

#import random


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13

#n = 15
#info = []
#for i in range(n):
#    info.append([random.randint(-10000, 10000), random.randint(-10000, 10000), random.randint(1, 1000000)])


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))

OFFSET = n
x_dir = [INF] * ((1 << n) * OFFSET)
y_dir = [INF] * ((1 << n) * OFFSET)


for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state * OFFSET + i] = min(costs[i], x_dir[bit_state * OFFSET + i])
        y_dir[bit_state * OFFSET + i] = min(costs[i], y_dir[bit_state * OFFSET + i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state * OFFSET + j] = min(x_dir[bit_state * OFFSET + j], c * abs(yi - yj))
            y_dir[bit_state * OFFSET + j] = min(y_dir[bit_state * OFFSET + j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit * OFFSET + i], y_dir[y_bit * OFFSET + i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)
### BUGGY CODE ###

a, b, k = map(int,input().split())
xs = [x for x in range(a,b+1) if x < a+k or x > b-k]
for x in range(len(xs)):
    print(xs[x])

### FIXED CODE ###

a, b, k = map(int, input().split())
if b-a+1 < 2*k:
    for i in range(a,b+1):
        print(i)
    exit(0)
for i in range(a,a+k):
    print(i)
for i in range(b-k+1,b+1):
    print(i)
### BUGGY CODE ###

N = input()
AN = list(map(int, input().split()))
X = 1
T = len(AN)
for i in range(T):
    X = X*AN[i]
    
if X <= 10**18:
    print(X)
else:
    print(-1)

### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
    exit()
    
for i in range(N):
    ans *= A[i]
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
m = 2*k
G = [[0]*m for _ in range(m)]
for _ in range(n):
  x, y, c = input().split()
  x = int(x)%m
  y = int(y)%m
  if c == "W":
    for i in range(x+k, x+m):
      for j in range(y, y+k):
        G[i%m][j%m] += 1
    for i in range(x, x+k):
      for j in range(y+k, y+m):
        G[i%m][j%m] += 1
  else:
    for i in range(x, x+k):
      for j in range(y, y+k):
        G[i%m][j%m] += 1
    for i in range(x+k, x+m):
      for j in range(y+k, y+m):
        G[i%m][j%m] += 1
ans = max(max(g) for g in G)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
X, Y, C = [], [], []
for _ in range(n):
  x, y, c = input().split()
  X.append(int(x)%(2*k))
  Y.append(int(y)%(2*k))
  C.append(c=="B")
G = [[0]*k for _ in range(k)]
cnt = 0
for x, y, c in zip(X, Y, C):
  if (x >= k and y < k) or (x < k and y >= k):
    x += k
    c ^= 1
  x %= k
  y %= k
  G[x][y] += (-1)**c
  cnt += c
for i in range(k):
  for j in range(k-1):
    G[i][j+1] += G[i][j]
for j in range(k):
  for i in range(k-1):
    G[i+1][j] += G[i][j]
ans = 0
for i in range(k):
  for j in range(k):
    temp = G[k-1][k-1] - G[i][k-1] - G[k-1][j] + G[i][j]*2 + cnt
    ans = max(ans, temp, n-temp)
print(ans)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(int(i) for i in input().split())
b = list(int(i) for i in input().split())
c = list(int(i) for i in input().split())

sums = []

for i in range(x):
    for j in range(y):
        for l in range(z):
            sums.append(a[i] + b[j] + c[l])
sums.sort()
ans = sums[::-1]

for i in range(k):
    print(ans[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(int(i) for i in input().split())
B = list(int(i) for i in input().split())
C = list(int(i) for i in input().split())

A.sort()
A = A[::-1]
B.sort()
B = B[::-1]
C.sort()
C = C[::-1]

ABC = []

for a in range(len(A)):
    for b in range(len(B)):
        if (a+1)*(b+1) > k:
            break
        for c in range(len(C)):
            if (a+1)*(b+1)*(c+1) > k:
                break
            #print(A[a], B[b], C[c])
            ABC.append(A[a]+B[b]+C[c])

ABC.sort()
ABC = ABC[::-1]

for i in range(k):
    print(ABC[i])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
m = max(A)
for i in range(N):
  if A.count(m) >= 2:
    print(m)
  elif m == A[i]:
    B = A.pop(i)
    print(max(A))
    A.insert(i,B)
  else:
    print(m)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
B = list(A)
B.sort()
m1 = B[N-1]
m2 = B[N-2]
#a = A.count(m1)
for i in range(N):
  if A[i] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

def main():
  t = input().split(" ")
  N, M = int(t[0]), int(t[1])
  x = [0]
  n = [1]*N
  for i in range(M):
    t = input().split(" ")
    fr, to = int(t[0])-1, int(t[1])-1
    if (fr in x) and (to not in x):
      x.append(to)
    n[fr] -= 1
    n[to] += 1
    if (fr in x) and n[fr] == 0:
        x.remove(fr)
  print(len(x))

main()


### FIXED CODE ###

def main():
  t = input().split(" ")
  N, M = int(t[0]), int(t[1])
  x = set([0])
  n = [1]*N
  for i in range(M):
    t = input().split(" ")
    fr, to = int(t[0])-1, int(t[1])-1
    if fr in x:
      x.add(to)
    n[fr] -= 1
    n[to] += 1
    if (fr in x) and n[fr] == 0:
        x.remove(fr)
  print(len(x))

main()
### BUGGY CODE ###

from sys import stdin
readline = stdin.readline


from itertools import combinations
def brute_force(p):
    return min(abs(p[i] - p[j]) for i, j in combinations(range(len(p)), 2))

def main():
    n = int(readline())
    p = [map(float, readline().split()) for _ in range(n)]
    p = [x + y * 1j for x, y in p]

    print('{:.6f}'.format(brute_force(p)))
main()

### FIXED CODE ###

from sys import stdin
from operator import attrgetter
readline = stdin.readline


def norm(a):
    return a.real * a.real + a.imag * a.imag


def closest_pair(p):
    if len(p) <= 1:
        return float('inf')
    m = len(p) // 2
    d = min(closest_pair(p[:m]), closest_pair(p[m:]))
    p = [pi for pi in p if p[m].imag - d < pi.imag < p[m].imag + d]
    return brute_force(p, d)

def brute_force(p, d=float('inf')):
    p.sort(key=attrgetter('real'))
    for i in range(1, len(p)):
        for j in reversed(range(i)):
            tmp = p[i] - p[j]
            if d < tmp.real:
                break
            tmp = abs(tmp)
            if d > tmp:
                d = tmp
    return d


def main():
    n = int(readline())
    p = [map(float, readline().split()) for _ in range(n)]
    p = [x + y * 1j for x, y in p]

    p.sort(key=attrgetter('imag'))
    print('{:.6f}'.format(closest_pair(p)))
main()
### BUGGY CODE ###

inf = 0x10101010
def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if cost[i] < min:
				min = cost[i]
				next = i
		strt = next 
		if next == -1: break
	return cost
						
while 1:
	n,m = map(int, raw_input().split())


	if n == 0:
		break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]

	for i in range(n):
		a, b, c, t = map(int, raw_input().split()) 
		T[a-1][b-1] = T[b-1][a-1] = t 
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T, i) for i in range(m)]
	CS = [solve(C, i) for i in range(m)]
	for i in range(input()):
		a, b, q = map(int, raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]

### FIXED CODE ###

inf = 0x10101010
def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:	
				min = cost[i]
				next = i
		strt = next 
		if next == -1: break
	return cost
						
while 1:
	n,m = map(int, raw_input().split())
	if n == 0:break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]
	for i in range(n):
		a,b,c,t = map(int, raw_input().split()) 
		T[a-1][b-1] = T[b-1][a-1] = t 
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T,i) for i in range(m)]
	CS = [solve(C,i) for i in range(m)]
	for i in range(input()):
		a, b, q = map(int,raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]
### BUGGY CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    # j桁目のビットが1であるものの数を記憶
    count_zeros = [0 for j in range(L+1)]
    count_ones = [0 for j in range(L+1)]
    for i in range(N):
        for j in range(L):
            count_ones[j] = count_ones[j] + ((A[i] >> j) & 1)
            count_zeros[j] = N - count_ones[j]
    # A[i] と A[j] (i<j) のxorをとる
    modsum = 0
    for j in range(L):
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros[j] * count_ones[j]
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


### FIXED CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = sum([1 for a in A if (a >> j) & 1])
        # count_ones = sum([(A[i] >> j) & 1 for i in range(N)])
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
### BUGGY CODE ###

import bisect
import math
import sys
imput = sys.stdin

N, M = [int(item) for item in input().rstrip().split()]
As = sorted([float(item) for item in input().rstrip().split()])
for i in range(M):
    _t = As.pop()
    bisect.insort_right(As, _t/2)
    
_sum = sum([math.floor(item) for item in As])
print(_sum)


### FIXED CODE ###

import heapq
 
N, M = [int(item) for item in input().rstrip().split()]
hp = [-1 * int(item) for item in input().rstrip().split()]
heapq.heapify(hp)

for i in range(M):
    _t = heapq.heappop(hp)
    heapq.heappush(hp, -1 * (-1 * _t // 2))
    
_sum = sum([-1 * int(item) for item in hp])
print(_sum)
### BUGGY CODE ###

from itertools import groupby

[H, W] = map(int, input().split())
Ss = [list(map( lambda x: int(x == "."), list(input()) )) for _ in range(H)]

res = 0
count = [[-Ss[i][j] for j in range(W)] for i in range(H)]
for i in range(H):
    j = 0
    for x in groupby(Ss[i]):
        k = len(list(x[1]))
        for _ in range(k):
            count[i][j] += k * x[0]
            j += 1

for j in range(W):
    i = 0
    for x in groupby([Ss[i][j] for i in range(H)]):
        k = len(list(x[1]))
        for _ in range(k):
            new_res = count[i][j] + k * x[0]
            if res < new_res:
                res = new_res
            i += 1

print(res)


### FIXED CODE ###

from itertools import groupby
 
[H, W] = map(int, input().split())
Ss = [list(map( lambda x: int(x == "."), list(input()) )) for _ in range(H)]
 
res = 0
count = [[-Ss[i][j] for j in range(W)] for i in range(H)]
for i in range(H):
    j = 0
    for x in groupby(Ss[i]):
        k = len(list(x[1]))
        for _ in range(k):
            count[i][j] += k * x[0]
            j += 1

for j in range(W):
    i = 0
    for x in groupby([Ss[i][j] for i in range(H)]):
        k = len(list(x[1]))
        for _ in range(k):
            new_res = count[i][j] + k * x[0]
            if res < new_res:
                res = new_res
            i += 1

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

N = int(input())

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

import sys

if 0 in A:
    print(0)
    sys.exit(0)

ans = 1
for i in range(len(A)):
    ans *= A[i]
if ans > int(1e18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())

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

import sys

if 0 in A:
    print(0)
    sys.exit(0)

ans = 1
for i in range(len(A)):
    ans *= A[i]
    if (ans > int(1e18)):
        print(-1)
        sys.exit(0)
if ans > int(1e18):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
count=0
for i in range(n):
    flag=True
    for j in range(n):
        if i!=j and l[i]%l[j]==0:
            flag=False
            break
    if flag==True:
        count+=1
print(count)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
counter=[0]*(10**6+1)
l=sorted(l)
for i in l:
    counter[i]+=1
    if counter[i]<2:
        for j in range(2*i,10**6+1,i):
            counter[j]+=2
print(counter.count(1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#print(a)

bc=[]
for i in range(m):
    B = list(map(int, input().split()))
    bc.append(B)
bc.sort(key=lambda x: x[1])
#print(bc)

clis=[]
for i in range(m)[::-1]:
    clis+=[bc[i][1]]*bc[i][0]
#print(clis)

ans=0
for i in range(n):
    #print(clis[i],a[i])
    if i<len(clis) and clis[i]>a[i]:
        ans+=clis[i]
    else:
        ans+=a[i]
    #print(ans)
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1],reverse=True)
#print(bc)
cnt=0
for i in range(n):
    if bc[cnt][0]>0:
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    else:
        cnt+=1
        if cnt==len(bc):
            break
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    #print(cnt,bc,a)
print(sum(a))
### BUGGY CODE ###

from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

DIV = 10**9+7

def mod_inv(a,mod = DIV):
    return pow(a,mod-2,mod)

def ncr(n,r, mod =DIV):
	r = min(r,n-r)
	ret = 1
	for i in range(1,r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * pow(i, mod-2, mod) % mod
	return ret

class MedianHeap:
    def __init__(self):
        self.lupper = []
        self.rlower =[]
        self.s=0
    def push(self,a):
        L = self.lupper
        R = self.rlower
        if len(L)== 0 or a<=-L[0]:
            heappush(L,-a)
            self.s+=-L[0]-a
        else:
            heappush(R,a)
            self.s+=a+L[0]
        if len(R)>len(L):
            self.s+=-L[0]-R[0]
            heappush(L,-heappop(R))
        if len(L)-len(R)>=2:
            heappush(R,-heappop(L))

        
def main():
    Q = int_raw()
    sb = 0
    mh = MedianHeap()
    for _ in range(Q):
        cmds = ints_raw()
        if cmds[0]==1:
            a,b = cmds[1:]
            sb+= b
            mh.push(a)
        else:
            print (-mh.lupper[0], mh.s+sb)
    
main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from heapq import heappush,heappop

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))

def main():
    Q = int(input())
    sb = 0
    lupper = []
    rlower = []
    s = 0
    for _ in range(Q):
        cmds = tuple(map(int,input().split()))
        if cmds[0]==1:
            _,a,b = cmds
            sb+= b
            if len(lupper)== 0 or a<=-lupper[0]:
                heappush(lupper,-a)
                s+=-lupper[0]-a
                if len(lupper)-len(rlower)>=2:
                    heappush(rlower,-heappop(lupper))
            else:
                heappush(rlower,a)
                s+=a+lupper[0]
                if len(rlower)>len(lupper):
                    s+=-lupper[0]-rlower[0]
                    heappush(lupper,-heappop(rlower))  
        else:
            print (-lupper[0], s+sb)
    
main()
### BUGGY CODE ###

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

for i in range(n-k+1):
    a=max(a,sum(p[i:i+k]))

print((k+a)/2)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=0
for i in range(n-k+1):
    if i==0:
        xe=sum(p[0:k])
    else:
        xe=xe-p[i-1]+p[i+k-1]
    a=max(a,xe)
print((k+a)/2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = []
h = 0
for i in range(a - b + 1):
	h = sum(c[i:b + i])
	d.append(h)
e = 0
f = 0
g = d.index(max(d))
for i in range(b):
	f = sum(range(1, c[g + i] + 1))
	e += f / c[g + i]
print(e)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
f = e
for i in range(a - b):
	f -= d[i]
	f += d[i + b]
	if f > e:
		e = f
print(e)