Harryxun/stf_run huggingface dataset:
sys.setrecursionlimit(2000)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5+10)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)
a,b=input().split()
if (a=="1" and b=="2")or(a=="2" and b=="1"):
	print("3")
if (a=="1" and b=="3")or(a=="3" and b=="1"):
	print("2")
if (a=="3" and b=="2")or(a=="2" and b=="3"):
	print("1")

### FIXED CODE ###

a=input()
b=input()
if (a=="1" and b=="2")or(a=="2" and b=="1"):
	print("3")
if (a=="1" and b=="3")or(a=="3" and b=="1"):
	print("2")
if (a=="3" and b=="2")or(a=="2" and b=="3"):
	print("1")
L,A,B,M=map(int,input().split())
gap=[-1 for k in range(37)]
for k in range(37):
    tmp=10**k-A
    if tmp%B==0:
        gap[k]=-1+tmp//B
    else:
        gap[k]=tmp//B
    gap[k]=min(L-1,gap[k])
    gap[k]=max(-1,gap[k])
num=[0 for k in range(37)]
for k in range(1,37):
    #k-1,k
    num[k]=-gap[k-1]+gap[k]

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,M)[0]
ans=0
geta=0
for k in range(36,-1,-1):
    n=num[k]
    P=A+B*gap[k-1]
    Q=B
    R=pow(10,num[k],M)
    tmp=R*(P*(R-1)*(pow(R,n,M)-1)+n*Q*pow(R,n+1,M)-(n+1)*Q*pow(R,n,M)+Q)
    tmp%=M
    tmp*=pow(10,geta,M)
    tmp*=inv((R-1)**2)
    tmp%=M
    ans+=tmp
    ans%=M
    geta+=k*gap[k]
print(ans)

### FIXED CODE ###

L,A,B,M=map(int,input().split())
K=19
gap=[-1 for k in range(K)]
for k in range(K):
    tmp=10**k-A
    if tmp%B==0:
        gap[k]=-1+tmp//B
    else:
        gap[k]=tmp//B
    gap[k]=min(L-1,gap[k])
    gap[k]=max(-1,gap[k])
num=[0 for k in range(K)]
for k in range(1,K):
    #k-1,k
    num[k]=-gap[k-1]+gap[k]
def matrix(d):
    return [[pow(10,d,M),1,0],[0,1,B],[0,0,1]]
def mattime(P,Q):
    R=[[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                R[i][j]+=P[i][k]*Q[k][j]
                R[i][j]%=M
    return R
def matexp(P,n):
    if n==0:
        return [[1,0,0],[0,1,0],[0,0,1]]
    elif n%2==0:
        return matexp(mattime(P,P),n//2)
    else:
        return mattime(P,matexp(mattime(P,P),n//2))
Mat=[[1,0,0],[0,1,0],[0,0,1]]
for d in range(1,K):
    Mat=mattime(matexp(matrix(d),num[d]),Mat)
print((A*Mat[0][1]+Mat[0][2])%M)
n=int(input())
p=map(int,input().split())
ans=0
for i in range(1,n-1):
  if p[i-1]<p[i] and p[i]<p[i+1]:
    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(1,n-1):
  if max(p[i-1],p[i],p[i+1])!=p[i] and min(p[i-1],p[i],p[i+1])!=p[i]:
    ans+=1
print(ans)
x,y = map(int, input().split())
temp = x
if x == y:
    print(-1)
    sys.exit()
while True:
    temp **= 2
    if temp % y != 0:
        print(temp)
        sys.exit()
    elif temp > 100000000000000000:
        print(-1)
        sys.exit()

### FIXED CODE ###

import sys
def gcd(a, b):
        while b:
                a, b = b, a % b
        return a
def lcm(a, b):
    return a * b // gcd (a, b)

x,y = map(int, input().split())
temp = x
if x == y:
    print(-1)
    sys.exit()
while True:
    temp += x
    if temp % y != 0:
        print(temp)
        sys.exit()
    elif temp > lcm(x, y):
        print(-1)
        sys.exit()
while True:
  H,W=map(int,input().split())
  for i in range(H):
      print("#"*W)


### FIXED CODE ###

while True:
  H,W=map(int,input().split())
  if H==0 and W==0:
      break
  for i in range(H):
      print("#"*W)
  print()
from collections import defaultdict

n,m=map(int,input().split())
visited=[0]*n
d=defaultdict(list)
def dfs(n):
    visited[n]=1
    #print(visited)
    for i in d[n]:
        if visited[i]==0:
            dfs(i)

for i in range (m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    d[a].append(b)
    d[b].append(a)

r=-1
for i in range (n):
    if visited[i]==0:
        dfs(i)
        r+=1
print(r)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

from collections import defaultdict

n,m=map(int,input().split())
visited=[0]*n
d=defaultdict(list)
def dfs(n):
    visited[n]=1
    #print(visited)
    for i in d[n]:
        if visited[i]==0:
            dfs(i)

for i in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    d[a].append(b)
    d[b].append(a)

r=-1
for i in range (n):
    if visited[i]==0:
        dfs(i)
        r+=1
print(r)
a5=[]
while True:
    x=int(input())
    if x==0:
        break
    a5.append(x)
j = 0
for i in a5:
    print("Case " + j+1+": "+ i)
    j=j+1


### FIXED CODE ###

a5=[]
while True:
    x=int(input())
    if x==0:
        break
    a5.append(x)
j = 0
for i in a5:
    print("Case " + str(j+1)+": "+ str(i))
    j=j+1
a, b = [int(x) for i in input().split()]
m = a * b
n = a * 2 + b * 2
print(m, n)

### FIXED CODE ###

a, b = [int(x) for x in input().split()]
m = a * b
n = a * 2 + b * 2
print(m, n)
x,y,a,b,c = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort()
q.sort()
r.sort()

ans = 0

cnt = 0

while x+y-cnt > 0:
    if x > 0:
        p1 = p[-1]
    else:
        p1 = 0
    if y > 0:
        p2 = q[-1]
    else:
        p2 = 0
    p3 = r[-1]
    eat = max(p1,p2,p3)
    ans += eat
    if x > 0 and p[-1] == eat:
        x -= 1
        p.pop()
    elif y > 0 and q[-1] == eat:
        y -= 1
        q.pop()
    else:
        cnt += 1
        r.pop()
print(ans)


### FIXED CODE ###

x,y,a,b,c = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort()
q.sort()
r.sort()

ans = 0

cnt = 0

while x+y-cnt > 0:
    if x > 0:
        p1 = p[-1]
    else:
        p1 = 0
    if y > 0:
        p2 = q[-1]
    else:
        p2 = 0
    if cnt < c:
        p3 = r[-1]
    else:
        p3 = 0
    eat = max(p1,p2,p3)
    ans += eat
    if x > 0 and p[-1] == eat:
        x -= 1
        p.pop()
    elif y > 0 and q[-1] == eat:
        y -= 1
        q.pop()
    else:
        cnt += 1
        r.pop()
print(ans)
n = int(input())
a = list(map(int,input().split()))
l =[0]
k = 0
for i in range(n):
  if a[i]>=a[i+1]:
    l[k] += 1   
  else:
    k += 1
    l.append(0)
print(max(l))
    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l = [0]
k = 0
for i in range(n-1):
  if a[i]>=a[i+1]:
    l[k] += 1   
  else:
    k += 1
    l.append(0)
print(max(l))
s,t=input().split(" ")
a,b.=map(int,input().split(" "))
u=input()
 
if s==u:
  print(a-1,b.split(" "))
else:
  print(a,b-1.split(" "))

### FIXED CODE ###

s,t=input().split(" ")
a,b=map(int,input().split(" "))
u=input()
 
if s==u:
  print(a-1, b)
else:
  print(a, b-1)
from operator import itemgetter

def calc(n, A, B):
    count = 0
    for i in range(n):#scanB
        print('i=',i)#Debug
        if A[i] <= B[i]:
            continue
        elif i < n-1:
            for j in range(i+1,n):#scanA
                if A[j] <= B[i] and A[i] <= B[j]:
                    A[j],A[i] = A[i],A[j]
                    count += 1
                    if count > n-2:
                        return 'No'
                    print(f'swap:{count}')
                    print(f'A:{A}')
                    print(f'B:{B}')
                    break
                elif j == n-1:
                    return 'No'
        else:
            return 'No'
    
    return 'Yes'

                
#main

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

#print(A)
#print(B)

pair = list(zip(A,B))
pair.sort(key=itemgetter(1))#sortB

A, B = zip(*pair)

ltA = list(A)
ltB = list(B)

#print(f'A:{ltA}')
#print(f'B:{ltB}')

#print(f'pair:{pair}')

print(calc(n,ltA,ltB))#for stdout

### FIXED CODE ###

n = int(input())
print((n-1)//2)
import math

n,x=map(int,input().split())
z=[]
y=[]
z=list(map(int, input().split()))

for i in range(n):
  y.append(abs(x-z[i]))

if n==1:
  print(y[0])
else:
  for i in range(n):
    if i<2:
      gcm=math.gcd(y[0],y[1])
    else:
      gcm=math.gcd(gcm,y[i])
  print(gcm)


### FIXED CODE ###

import fractions

n,x=map(int,input().split())
z=[]
y=[]
z=list(map(int, input().split()))

for i in range(n):
  y.append(abs(x-z[i]))

if n==1:
  print(y[0])
else:
  gcm=y[0]
  for i in range(n):
    gcm=fractions.gcd(gcm,y[i])
  print(gcm)
import string

S = input()
alphabetsStr = string.ascii_lowercase
alphabets = list(map(lambda x: x, string.ascii_lowercase))
lastWord = ''.join(alphabets[::-1])
cnt = [S.count(chr(ord('a')+i)) for i in range(26)]
if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        for i in S:
            if alphabets[i] != S[i]:
                print(S[:i] + alphabets[i])
                break
else:
    for j in range(26):
        if cnt[j] == 0:
            S += chr(ord('a')+j)
            print(S)
            break

### FIXED CODE ###

import string

S = input()
reversedS = ''.join(list(S)[::-1])
alphabets = list(string.ascii_lowercase)
lastWord = ''.join(alphabets[::-1])
cnt = [S.count(chr(ord('a')+i)) for i in range(26)]
if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        found = False
        for i in range(len(reversedS)):
            s = reversedS[i]
            largeS = alphabets[ord(s)-ord('a')+1:]
            tailS = list(S)[26-i-1:]
            for lS in largeS:
                if lS in tailS:
                    print(S[:26-i-1]+lS)
                    found = True
                    break
            if found: break
else:
    for j in range(26):
        if cnt[j] == 0:
            S += chr(ord('a')+j)
            print(S)
            break
Row = int(input())
List = []
for i in range (Row):
  List.append(list(map(int, input().split())))
s_l = set(List)
print(len(s_l))

### FIXED CODE ###

Row = int(input())
List = []
for i in range (Row):
  List.append(int(input()))
s_l = set(List)
print(len(s_l))
K, X = map(int(input().split())

if 500*K >= X:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

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

if 500*K >= X:
  print("Yes")
else:
  print("No")
n = int(input())
framelist = [int(i) for i in input().split()]

sum = 0


for i in range(n):
  sum += framelist[i]

avg = sum /n

min = avg

for i in range(n):
  difference = abs(framelist[i]-avg)
  if min>difference:
    min = difference
    
print(framelist.index(difference))

### FIXED CODE ###

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

sum = 0


for i in range(n):
  sum += framelist[i]

avg = sum /n

min = avg
value = 0

for i in range(n):
  difference = abs(framelist[i]-avg)
  if min>difference:
    min = difference
    value = framelist[i]
    
print(framelist.index(value))
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
m=0
for i in range(N):
    m +=B[a[i] -1]
for i in range(N-1):
    if a[i] + 1 == a[i + 1]:
        m + =C[a[i] - 1]
print(m)
         
    

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
m = 0
for i in range(N):
    m += B[A[i] - 1]
for t in range(N-1):
    if A[t] + 1 == A[t + 1]:
        m += C[A[t] - 1]
print(m)
N,M = map( int,input().split())
A = list(map(int,input().split())
print(N - sum(A))

### FIXED CODE ###

N,M = map( int, input().split() )
A = list( map(int, input().split() ))
print(max(-1, N - sum(A)))
sum([n for n in range(1, int(inpt())) if (n%3!=0) and (n%5!=0)])

### FIXED CODE ###

n = int(input())

ans = 0
for i in range(n+1):
    if i % 3 != 0 and i % 5 != 0:
        ans += i
print(ans)
n, m = map(int, input().split())
a = sorted([int(x) for x in input().split()])

if n == 1:
    print(sum(a) % m)
    exit()


def chk(x):
    for i in range(2*x, 2*n):
        if i != 2*n - 1 - (i - 2*x) and a[i] + a[2*n-1-(i-2*x)] < m:
            return False
    for i in range(2*x):
        if i != 2*x-1-i and a[i] + a[2*x-1-i] >= m:
            return False
    return True


bottom = -1
top = n+1

while top - bottom > 1:
    mid = (top + bottom)//2
    if chk(mid):
        top = mid
    else:
        bottom = mid
    if top == 0:
        break

ans = -1

for i in range(2*top, 2*n):
    ans = max(ans, (a[i]+a[2*n-1-(i-2*top)]) % m)
for i in range(2*top):
    ans = max(ans, (a[i] + a[2*top-1-i]) % m)

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
a = sorted([int(x) for x in input().split()])


def chk(x):
    for i in range(2*x, 2*n):
        if i != 2*n - 1 - (i - 2*x) and a[i] + a[2*n-1-(i-2*x)] < m:
            return False
    return True


bottom = -1
top = n

while top - bottom > 1:
    mid = (top + bottom)//2
    if chk(mid):
        top = mid
    else:
        bottom = mid

ans = -1

for i in range(2*top, 2*n):
    ans = max(ans, (a[i]+a[2*n-1-(i-2*top)]) % m)
for i in range(2*top):
    ans = max(ans, (a[i] + a[2*top-1-i]) % m)

print(ans)
n = int(input())
sum_a = 0
for i in range(n):
  a = n[i]
  sum_a += a
if n % sum_a == 0:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

N = input()
ans = 0
for i in N:
    ans += int(i)
if int(N)%ans == 0:
    print('Yes')
else:
    print('No')
import sys

n = int(sys.stdin.readline())

dp = [0 for i in range(n+1)]
cost = list(map(int, sys.stdin.readline()))

dp[1] = cost[0]
dp[2] = abs(dp[1] - cost[2])


for i in range(3, n+1):
  dp[i] = min(dp[i-1] + abs(cost[i+1] - cost[i]), dp[i-2] + abs(cost[i-1] - cost[i+1])

### FIXED CODE ###

import sys

n = int(sys.stdin.readline())

dp = [0 for i in range(n+1)]
cost = list(map(int, sys.stdin.readline().split())) # 0~3
cost.insert(0, 0)

dp[2] = abs(cost[1] - cost[2])


for i in range(3, n+1):
  dp[i] = min(dp[i-1] + abs(cost[i-1] - cost[i]), dp[i-2] + abs(cost[i-2] - cost[i]))
  
print(dp[n])
N=int(input())
P=[(0,0,0)]*(N+1)

D=[0]*(N+1)

P[0]=(0,0,0)
D[0]=1
for i in range(1,N+1):
    t,x,y=map(int,input().split())
    dt=t-P[i-1][0]
    dx=abs(x-P[i-1][1])
    dy=abs(y-P[i-1][2])
    if dt < (dx+dy): 時間<移動距離
        print('No')
        break
    if ((dx+dy)==0 and dt%2!=0):移動しない場合には時間はmod2==0
        print('No')
        break
    #if (dt-(dx+dy))%2==0 or dt%(dx+dy)==0:
    if (dt-(dx+dy))%2!=0:
        print('No')
        break
    
    P[i]=(t,x,y)
else:
    print('Yes')    

### FIXED CODE ###

N=int(input())
P=[(0,0,0)]*(N+1)

D=[0]*(N+1)

P[0]=(0,0,0)
D[0]=1
for i in range(1,N+1):
    t,x,y=map(int,input().split())
    dt=t-P[i-1][0]
    dx=abs(x-P[i-1][1])
    dy=abs(y-P[i-1][2])
    if dt < (dx+dy): #時間<移動距離
        print('No')
        break
    if ((dx+dy)==0 and dt%2!=0): #移動しない場合には時間はmod2==0
        print('No')
        break
    #if (dt-(dx+dy))%2==0 or dt%(dx+dy)==0:
    if (dt-(dx+dy))%2!=0:
        print('No')
        break
    
    P[i]=(t,x,y)
else:
    print('Yes')
#include <complex>
#include <iostream>
using namespace std;
complex<double> A[100],j=sqrt(-1),p;
double a,b,d;
int n;
int f(int m,int i1,int i2){
	int i,s1=2,s2=2;
	complex<double> p1=polar(1.0,b+d)+p,p2=polar(1.0,b-d)+p;
	for(i=0;i<n;i++){
		if(i==i1||i==i2)continue;
		if(abs(A[i]-p1)-1<1e-6)s1++;
		if(abs(A[i]-p2)-1<1e-6)s2++;
	}
	if(m<s1)m=s1;
	if(m<s2)m=s2;
	return m;
}
int main(){
	int m,i,i1;
	char c;
	while(cin>>n,n!=0){
		for(i=0;i<n;i++){
			cin>>a>>c>>b;
			A[i]=complex<double>(a,b);
		}
		m=1;
		for(i=0;i<n;i++){
			p=A[i];
			for(i1=i+1;i1<n;i1++){
				a=abs(A[i1]-p);
				b=arg(A[i1]-p);
				d=acos(a/2);
				if(a<=2)m=f(m,i,i1);
			}
		}
		cout<<m<<endl;
	}
}

### FIXED CODE ###

import math,cmath
def f(m):
  c=1j*math.acos(a/2)
  r=cmath.exp(b+c)+p
  s=cmath.exp(b-c)+p
  u,v=2,2
  for t in A:
    if t in[p,q]:continue
    if abs(t-r)-1<1e-6:u+=1
    if abs(t-s)-1<1e-6:v+=1
  return max(m,u,v)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  A=[]
  for i in N:
    x,y=map(float,input())
    A+=[x+1j*y]
  m=1
  for i in N:
    p=A[i]
    for q in A[i+1:]:
      a,b=cmath.polar(q-p)
      b*=1j
      if a<=2:m=f(m)
  print m
import heapq
def main():
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
#    v_cum = [x for x in v]
#    for i in range(1, n):
#        v_cum[i] += v_cum[i-1]
    ans = 0
    for L_i in range(min(k+1, n)):#左から取る回数
        R_i_max = k - L_i+1
        if n < L_i + R_i_max:
            R_i_max = n - L_i + 1
        for R_i in range(R_i_max):#右から取る回数
            pop_i = k - L_i - R_i
            q = []
            heapq.heapify(q)
            tmp = 0
            for L_j in range(L_i):
                tmp += v[L_j]
                heapq.heappush(q, v[L_j])
            for R_j in range(n-R_i, n):
                tmp += v[R_j]
                heapq.heappush(q, v[R_j])
            for _ in range(pop_i):
                if len(q) == 0:
                    break
                x = heapq.heappop(q)
                if 0 < x:
                    break
                tmp -= x
#            print(L_i, R_i, tmp)
            if ans < tmp:
                ans = tmp
    print(ans)

if __name__ == "__main__":
    main()import heapq
def main():
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
#    v_cum = [x for x in v]
#    for i in range(1, n):
#        v_cum[i] += v_cum[i-1]
    ans = 0
    for L_i in range(min(k+1, n)):#左から取る回数
        R_i_max = k - L_i+1
        if n < L_i + R_i_max:
            R_i_max = n - L_i + 1
        for R_i in range(R_i_max):#右から取る回数
            pop_i = k - L_i - R_i
            q = []
            heapq.heapify(q)
            tmp = 0
            for L_j in range(L_i):
                tmp += v[L_j]
                heapq.heappush(q, v[L_j])
            for R_j in range(n-R_i, n):
                tmp += v[R_j]
                heapq.heappush(q, v[R_j])
            for _ in range(pop_i):
                if len(q) == 0:
                    break
                x = heapq.heappop(q)
                if 0 < x:
                    break
                tmp -= x
#            print(L_i, R_i, tmp)
            if ans < tmp:
                ans = tmp
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
def main():
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
    ans = 0
    for L_i in range(min(k+1, n)):#左から取る回数
        R_i_max = k - L_i+1
        if n < L_i + R_i_max:
            R_i_max = n - L_i + 1
        for R_i in range(R_i_max):#右から取る回数
            pop_i = k - L_i - R_i
            q = []
            heapq.heapify(q)
            tmp = 0
            for L_j in range(L_i):
                tmp += v[L_j]
                heapq.heappush(q, v[L_j])
            for R_j in range(n-R_i, n):
                tmp += v[R_j]
                heapq.heappush(q, v[R_j])
            for _ in range(pop_i):
                if len(q) == 0:
                    break
                x = heapq.heappop(q)
                if 0 < x:
                    break
                tmp -= x
            if ans < tmp:
                ans = tmp
    print(ans)

if __name__ == "__main__":
    main()
n,m=map(int,input().split())
ans =[-1] * (n+1)
for _ in range(m):
    s,c = map(int,input().split())
    if ans[s] == -1 or ans[s] == c:
        ans[s] = c
    else:
        print(-1)
        exit()

for i in range(1,n+1):
    if ans[i] == -1:
        ans[i] = 0
if ans[1] == 0:
    print(-1)
else:
    print(ans[1]*100 + ans[2]*10+ans[3])

### FIXED CODE ###

n,m=map(int,input().split())
ans = [-1] * 4

for _ in range(m):
    s,c=map(int,input().split())
    if ans[s] == -1 or ans[s] == c:
        ans[s] = c
    else:
        print(-1)
        exit()
    
if n == 1:
    print(ans[1] if ans[1]!=-1 else 0)
else:
    if ans[1] == 0:
        print(-1)
        exit()
    if ans[1] == -1:
        ans[1] = 1
    for i in range(2,n+1):
        if ans[i] == -1:
            ans[i] = 0
    res = 0
    for i in range(1,n+1):
        res*=10
        res += ans[i]
    print(res)
N=int(input())

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

ans=[0]*max(a)

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

ll = [ans[0], ans[0]+ans[1], ans[N-2]+ans[N-1], ans[N-1]]

ans_a=max(ll)

for i in range(N-2):
    aa = ans[i]+ans[i+1]+ans[i+2]
    if aa>ans_a:
        ans_a=aa
    
print(ans_a)

### FIXED CODE ###

N=int(input())

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

a_max=100001
ans=[0]*(a_max)

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

ll = [ans[0], ans[0]+ans[1], ans[a_max-2]+ans[a_max-1], ans[a_max-1]]

ans_a=max(ll)

for i in range(a_max-2):
    aa = ans[i]+ans[i+1]+ans[i+2]
    if aa>ans_a:
        ans_a=aa
    
print(ans_a)
import math
N,K = [int(x) for x in input().split()]
inf = 10**9+7
for i in range(1,K+1):
  k = i-1
  kumi = math.factorial(K-i+k)//(math.factorial(K-i)*math.factorial(k))%inf
  ans = kumi*math.factorial(N-K+1)//(math.factorial(i)*math.factorial(N-K+1-i))
  print(int(ans%inf))
  
  

### FIXED CODE ###

import math
N,K = [int(x) for x in input().split()]
inf = 10**9+7
for i in range(1,K+1):
  k = i-1
  kumi = math.factorial(K-i+k)//(math.factorial(K-i)*math.factorial(k))%inf
  a = math.factorial(N-K+1)
  b = math.factorial(i)
  if (N-K+1-i)<0:
    print(0)
    continue
  c = math.factorial(N-K+1-i)
  a = a//b
  a = a//c%inf
  ans = kumi*a
  print(int(ans%inf))
c1=input()
c2=input()
c3=input()
print(c1[0]+c2[1]+c3[2

### FIXED CODE ###

c1=input()
c2=input()
c3=input()
print(c1[0]+c2[1]+c3[2])
N=input()

a = None

if(len(N) == 1):
    a = int(N)
elif(len(N) == 2):
    a = int(N[1])
else:
    a = int(N[3])

s = ""

if(a == 3):
    s = "bon"
elif(a == 0 or a ==1 or a==6 or a==8):
    s = "pon"
else:
    s="hon"

print(s)


### FIXED CODE ###

N=input()

a = None

if(len(N) == 1):
    a = int(N)
elif(len(N) == 2):
    a = int(N[1])
else:
    a = int(N[2])

s = ""

if(a == 3):
    s = "bon"
elif(a == 0 or a ==1 or a==6 or a==8):
    s = "pon"
else:
    s="hon"

print(s)