Harryxun/stf_run huggingface dataset:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

n = raw_input()
n = int(n)

tree = np.zeros([n,n],dtype=np.int64)
for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1,abc[1]-1] = abc[2]
    tree[abc[1]-1,abc[0]-1] = abc[2]

qk = raw_input()
qk = qk.split()
q,k = map(int,qk)


distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

while 1:
    for i in range(len(distance)):
        if distance[i] == -1:
            pass
        else:
            status = 0
            for j in range(n):
                if tree[i][j] == 0:
                    pass
                elif distance[j] == -1:
                    distance[j] = distance[i] + tree[i][j]
                if distance[j] == -1:
                    status = 1
    if status == 0:
        break

answers = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    ans = distance[xy[0]-1] + distance[xy[1]-1]
    answers.append(ans)

for ans in answers:
    print ans


### FIXED CODE ###

#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

n = raw_input()
n = int(n)

tree = []
for i in range(n):
    tree.append([])

for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1].append([abc[1]-1,abc[2]])
    tree[abc[1]-1].append([abc[0]-1,abc[2]])


qk = raw_input()
qk = qk.split()
q,k = map(int,qk)

question = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    question.append(xy)

distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

next_point = [k-1]

while 1:
    search_point = next_point
    next_point = []
    if len(search_point) == 0:
        break
    else:
        for i in search_point:
            for j in tree[i]:
                if distance[j[0]] == -1:
                    distance[j[0]] = distance[i] + j[1]
                    next_point.append(j[0])

for line in question:
    print distance[line[0]-1] + distance[line[1]-1]
import sys

args = sys.argv

a = "abcdefghijklmnopqrstuvwxyz"

c = args[1]
idx = a.index(c)
print(a[idx + 1])


### FIXED CODE ###

import sys

args = sys.argv

a = "abcdefghijklmnopqrstuvwxyz"

c = input()
idx = a.index(c)
print(a[idx + 1])
A = input()
B = input()        
print(6 - A - B)


### FIXED CODE ###

A = int(input())
B = int(input())
print(6 - A - B)
H,W = map(int,input().split())
h,w = map(int,input().split())

 print(max(H*W-h*W-(H-h)*w,0))

### FIXED CODE ###

H,W = map(int,input().split())
h,w = map(int,input().split())

print(max(H*W-h*W-(H-h)*w,0))
s = str(input())
a = ""
for i in range(len(s)//2+1):
    a += s[2*i]
print(a)


### FIXED CODE ###

s = str(input())
a = ""
if len(s) % 2 == 0:
    for i in range(len(s)//2):
        a += s[2*i]
    print(a)
else:
    for i in range(len(s)//2+1):
        a += s[2*i]
    print(a)
S = input()
mod = 10 ** 9 + 7
def DP(i, j, S):
    if i == len(S) and j == 3:
        return 1
    elif i == len(S) and j < 3:
        return 0
    elif i < len(S) and j == 3:
        if S[i] == "?":
            return 3 * DP(i+1, 3, S) 
        else:
            return DP(i+1, 3, S)
    elif i < len(S) and j < 3:
        ABC = "ABC"
        if S[i] == "?":
            return 3 * DP(i+1, j, S) + DP(i+1, j+1, S)
        elif S[i] == ABC[j]:
            return DP(i+1, j, S) + DP(i+1, j+1, S)
        else:
            return DP(i+1, j, S)

print(DP(0, 0, S)%mod)

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1, mod))

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        count += mult(leftA, leftQ, mod) * mult(rightC, rightQ, mod)
        count %= mod
        leftQ += (1 if S[i] == "?" else 0)
    elif S[i] == "A":
        leftA += 1 
    else:
        rightC -= 1
print(count)
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
l=[i for i in range(n)]
xy=[list(map(int,input().split()))  for _ in range(n)]
comb=itertools.permutations(l,2)
dic={}
for c in comb:
    i,j=c
    xi,yi=xy[i]
    xj,yj=xy[j]
    p=xi-xj
    q=yi-yj
    if (p,q) not in dic:
        dic[(p,q)]=1
    else:
        dic[(p,q)]+=1
res=-1
ai=-1
for i in dic.keys():
    if res<dic[i]:
        ai=i
        res=dic[i]
print(n-dic[i])

### FIXED CODE ###

import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
l=[i for i in range(n)]
xy=[list(map(int,input().split()))  for _ in range(n)]
if n==1:
  print(1)
  exit()
comb=itertools.permutations(l,2)
dic={}
for c in comb:
    i,j=c
    xi,yi=xy[i]
    xj,yj=xy[j]
    p=xi-xj
    q=yi-yj
    if (p,q) not in dic:
        dic[(p,q)]=1
    else:
        dic[(p,q)]+=1
res=-1
ai=-1
for i in dic.keys():
    if res<dic[i]:
        ai=i
        res=dic[i]
print(n-dic[ai])
a,b=input().split()
print(b,a sep='')


### FIXED CODE ###

a,b=input().split()
print(b,a, sep='')
import math

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

def factorization(n):
  factor=[]
  tmp=int(math.sqrt(n))+1
  for num in range(2,tmp):
    while n%num==0:
      n//=num
      factor.append(num)
      break
    if not factor:
      return 'prime number'
    else:
      factor.append(n)
      return factor

a_list=factorization(a)
b_list=factorization(b)

a_b_and=set(a_list)&set(b_list)
print(len(a_b_and)+1)


### FIXED CODE ###

from fractions import gcd

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

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)

    if temp!=1:
        arr.append(temp)

    return arr
  
d = gcd(a,b)
print(len(factorization(d)) + 1)
n,m,l = map(int,input().split(" "))
Ns = input().split(" ")
N = [int (n) for n in Ns]
Ms = input().split(" ")
M = [int(n) for n in Ms]
#print(n,m,l)
#print(N,M)
i = 0
j = 0
total = 0
cnt = 0
while total < l:
  #print(i,j,total,cnt)
  if  i == n and j == m:
    break
  elif i < n and j == m:
    if total + N[i] <= l:
      total = total + N[i]
      i = i+1
      cnt = cnt + 1
    else:
      break
  elif i == n and j < m:
    if total + M[i] <= l:
      total = total + M[j]
      j = j+1
      cnt = cnt +1
    else:
      break
  elif i < n and j < m and (total+N[i] <= l or total+M[j] <= l):
    if N[i] <= M[j]:
      total = total + N[i]
      i = i+1
      cnt = cnt +1
    elif N[i] > M[j]:
      total = total + M[j]
      j = j+1
      cnt = cnt +1
  else:
    break
print(cnt)#,i,j,total,n,m,l)

### FIXED CODE ###

N,M,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a,b = [0],[0]
for i in range(N):
  a.append(a[i]+A[i])
for j in range(M):
  b.append(b[j]+B[j])
ans = 0
#print(a,b,N+1)
j = M
for i in range(N+1):
  if a[i] > K:
    break

  while K - a[i] < b[j]:
    j = j-1
  ans = max(ans,i+j)

print(ans)
n,k=map(int,input().split())
p=10**9+7
def fact(n,p):
    a=[[] for _ in range(n+1)]
    a[0]=1
    for i in range(n):
        a[i+1]=(a[i]*(i+1))%p
    return a
f=fact(n-k+1,p)
invf=[]
for i in f:
    invf.append(pow(i,-1,p))
ans=[]
for i in range(1,k+1):
    ans.append(f[n-k+1]*invf[n-k+1-i]*invf[i]*i**(k-i))
for i in ans:
    print(i%p)

### FIXED CODE ###

n,k=map(int,input().split())
p=10**9+7
def fact(n,p):
    a=[[] for _ in range(n+1)]
    a[0]=1
    for i in range(n):
        a[i+1]=(a[i]*(i+1))%p
    return a
f=fact(n,p)
invf=[]
for i in f:
    invf.append(pow(i,-1,p))
ans=[]
for i in range(1,k+1):
    if i>n-k+1:
        ans.append(0)
        continue
    ans.append(((f[n-k+1]*invf[n-k+1-i])%p)*((invf[i]*f[k-1])%p)*((invf[i-1]*invf[k-i]))%p)
for i in ans:
    print(i%p)
(defun calc (x a b n)
  (- (floor (/ (* a x) b))
     (* a (floor (/ x b)))))

(let ((a (read))
      (b (read))
      (n (read)))
     (format t "~A" (if (<= b n)
                        (calc (1- b) a b n)
                        (calc n a b n))))


### FIXED CODE ###

a, b, n = map(int, input().split())

if b < n:
  x = b-1
elif b == n:
  x = b-1
else:
  x = n

print(int(a*x/b) - a*int(x/b))
i = 0
while True:
    x = int(raw_input())
    if x == 0:
        break
    i += 1
    i=str(i)
    x=str(x)
    print "Case %d: %d" % (i, x)

### FIXED CODE ###

i = 0
while True:
    x = int(raw_input())
    if x == 0:
        break
    i += 1
    print "Case %d: %d" % (i, x)
a, b, c = list(map(int, input().split()))

if a + b + c == 17 && a * b * c == 5 * 5 * 7:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

if (a + b + c == 17) and (a * b * c == 5 * 5 * 7):
    print("YES")
else:
    print("NO")
n=str(input())
a=set(n)
p=0
if len(a)==1:
  p=1
elif len(a)==2:
  b=n[0]
  if b==n[1]:
    if b==n[2] or b==n[3]:
        p=1
  elif b==n[2] and b==n[3]:
      p=1
if p=1:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

n=str(input())
a=set(n)
p=0
if len(a)==1:
  p=1
elif len(a)==2:
  b=n[0]
  if b==n[1] and b==n[2]:
      p=1
  b=n[1]
  if b==n[2] and b==n[3]:
      p=1
if p==1:
    print('Yes')
else:
    print('No')
A,B,N=map(int,iput(),split())
if A*N<B :
  print(A*N)
else:
    print(B)

### FIXED CODE ###

N,A,B=map(int,input().split())
if A*N<B :
  print(A*N)
else:
  print(B)
#!/usr/bin/python3

def set_color(i, ci, e, color):
    color[i] = ci
    for next_i in e[i]:
        if color[next_i] != ci:
            set_color(next_i, ci, e, color)

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

e = [set() for i in range(n)]
color = [None] * n

for i in range(m):
    s, t = map(int, input().split())
    e[s].add(t)
    e[t].add(s)

ci = 0
for i in range(n):
    if color[i] == None:
        set_color(i, ci, e, color)
        ci += 1

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if color[s] == color[t]:
        print('yes')
    else:
        print('no')

### FIXED CODE ###

#!/usr/bin/python3

def set_color(i, ci, e, color):
    color[i] = ci
    next_i = set(e[i])
    while len(next_i):
        s = next_i.pop()
        if color[s] != ci:
            color[s] = ci
            next_i.update(e[s])


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

e = [set() for i in range(n)]
color = [None] * n

for i in range(m):
    s, t = map(int, input().split())
    e[s].add(t)
    e[t].add(s)

ci = 0
for i in range(n):
    if color[i] == None:
        set_color(i, ci, e, color)
        ci += 1

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if color[s] == color[t]:
        print('yes')
    else:
        print('no')
import itertools
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

#必要ないならTrueを返す
def test(i):
    b=itertools.chain(a[:i],a[i+1:])
    dp=[False]*k
    dp[0]=True
    for u in b:
        dp[u:]=np.logical_or(dp[u:],dp[:-u])
    return not any(dp[-a[i]:])
    

low=0
high=n-1
while high-low>1:
    mid=(high+low)//2
    if test(mid):
        low=mid
    else:
        high=mid
    
if test(high):
    print(high+1)
else:
    print(high)

### FIXED CODE ###

import itertools

def fff(x):
    dp=[0]*k
    dp[0]=1
    for u in itertools.chain(a[:x],a[x+1:]):
        h=dp[:]
        for i in range(u,k):
            h[i]=h[i]|dp[i-u]
        dp=h
    cnt=0
    for i in range(max(0,k-a[x]),k):
        cnt+=dp[i]
    if cnt==0:
        return True
    else:
        return False

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
low=0
high=n-1
while high-low>1:
    mid=(high+low)//2
    if fff(mid):    #不必要
        low=mid
    else:
        high=mid

if fff(high):
    print(high+1)
elif fff(low):
    print(low+1)
else:
    print(0)
# -*- coding: utf-8 -*-
import math
a,b,c,d = list(map(int,input().split()))

lcm_cd = c*d//math.gcd(c,d)

a_div_c = a//c
ac_mod = a%c
bc = b//c

a_div_d = a//d
ad_mod = a%d
bd = b//d

a_div_lcm_cd = a//lcm_cd
alcm_cd_mod = a%lcm_cd
blcm_cd = b//lcm_cd

cnt_c = 0
cnt_d = 0
cnt_lcmcd = 0

cnt_c = (bc-a_div_c)
if not ac_mod:
    cnt_c+=1

cnt_d = (bd-a_div_d)
if not ad_mod:
    cnt_d+=1

cnt_lcmcd = (blcm_cd-a_div_lcm_cd)
if not alcm_cd_mod:
    cnt_lcmcd+=1
print(b-a+1-(cnt_c+cnt_d-cnt_lcmcd))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
a,b,c,d = list(map(int,input().split()))

lcm_cd = c*d//fractions.gcd(c,d)

a_div_c = a//c
ac_mod = a%c
bc = b//c

a_div_d = a//d
ad_mod = a%d
bd = b//d

a_div_lcm_cd = a//lcm_cd
alcm_cd_mod = a%lcm_cd
blcm_cd = b//lcm_cd

cnt_c = 0
cnt_d = 0
cnt_lcmcd = 0

cnt_c = (bc-a_div_c)
if not ac_mod:
    cnt_c+=1

cnt_d = (bd-a_div_d)
if not ad_mod:
    cnt_d+=1

cnt_lcmcd = (blcm_cd-a_div_lcm_cd)
if not alcm_cd_mod:
    cnt_lcmcd+=1
print(b-a+1-(cnt_c+cnt_d-cnt_lcmcd))
def ip():
  	return list(map(int, input().split()))
[n,k]=ip()
arr=ip()
s=0
e=k
u=k-1
while u:
  if arr[s]<arr[e]:
      print("Yes")
  else:
      print("No")
  s+=1
  u-=1
  e+=1

### FIXED CODE ###

def ip():
  	return list(map(int, input().split()))
[n,k]=ip()
arr=ip()
s=0
e=k
u=n-k
while u:
  if arr[s]<arr[e]:
      print("Yes")
  else:
      print("No")
  s+=1
  u-=1
  e+=1
#!/usr/bin/env python3
import math

A, B, X = [int(s) for s in input().split()]
right = 10 ** 9
left = 1

if A + B > X:
    print(0)
    exit()

if A * right + B * 10 <= X:
    print(right)
    exit()

while (left < right):
    middle = (left + right) // 2 + 1
    if A * middle + B * int((math.log(middle * 10, 10))) < X:
        left = middle 
    else:
        right = middle - 1

print(right)

### FIXED CODE ###

week = ['MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT', 'SUN']
S = input()

print(6 - week.index(S)) if week.index(S) != 6 else print(7)
n,m=map(int,input().split())
p=10**9+7
a=[int(input()) for i in range(m)]
b=[a[0]-1]
for i in range(m):
  b.append(a[i+1]-a[i]-2)
x=[1]*(max(b)+1)
for i in range(2,max(b)+1):
  x[i]=(x[i-1]+x[i-2])%p

ans=1
if min(b)==-1:
  ans=0
else:
  for i in range(m):
    ans=(ans*x[b[i]])%p
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
p=10**9+7
a=[int(input()) for i in range(m)]
a.append(n+1)
b=[a[0]-1]
for i in range(m):
  b.append(a[i+1]-a[i]-2)
x=[1]*(max(b)+1)
for i in range(2,max(b)+1):
  x[i]=(x[i-1]+x[i-2])%p

ans=1
if min(b)==-1:
  ans=0
else:
  for i in range(m+1):
    ans=(ans*x[b[i]])%p
print(ans)
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
d=defaultdict(int)
for i in range(n):
    d[a[i]]+=1

for i,j in d.items():
    if j>=2:
        b.append(i)
    if j>=4:
        c.append(i)
if len(b)<2:
    print(0)
else:
    b.sort(reverse=True)
    rec=b[0]*b[1]
    if len(c)>=1:
        c.sort(reverse=True)
        cube=c[0]**2
    print(max(rec,cube))

### FIXED CODE ###

from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
d=defaultdict(int)
for i in range(n):
    d[a[i]]+=1

for i,j in d.items():
    if j>=2:
        b.append(i)
    if j>=4:
        c.append(i)

if len(b)<2 and len(c)<1:
    print(0)
elif len(c)==1 and len(b)<2:
    print(c[0]**2)
else:
    b.sort(reverse=True)
    rec=b[0]*b[1]
    if len(c)>=1:
        c.sort(reverse=True)
        cube=c[0]**2
    else:
        cube=0
    print(max(rec,cube))
N = int(input())
B = list(map(int,input().split()))
 
ans = []
while B:
    for i in range(len(B)-1, -1, -1):
        b = B[i]
        if i+1 == b:
            ans.append(i+1)
            break
    else:
        print(-1)
        exit()
    del B[i]

ans.reverse()
for an in range(0, N+1):
	tmp = ans.pop(0)
	print(tmp)

### FIXED CODE ###

N = int(input())
B = list(map(int,input().split()))
 
ans = []
while B:
    for i in range(len(B)-1, -1, -1):
        b = B[i]
        if i+1 == b:
            ans.append(i+1)
            break
    else:
        print(-1)
        exit()
    del B[i]
    
for idx in range(0, N):
	tmp = ans.pop(-1)
	print(tmp)
H, W = map(int, input().split())
for i in range(H):
  	s = input()
    print(s)
    print(s)


### FIXED CODE ###

H, W = map(int, input().split())
for _ in range(H):
    s = input()
    print(s)
    print(s)
a, b = map(int, input().split())
if a == 'H':
    print(b)
else:
    if b == 'H':
        print('D')
    else:
        print('H')

### FIXED CODE ###

a, b = input().split()
if a == 'H':
    print(b)
else:
    if b == 'H':
        print('D')
    else:
        print('H')
from fractions import gcd
def result(n):
    lists = list()
    num = n
    for i in range(2, int((n**0.5//1))+1):
        if num%i==0:
            time=0
            while num%i==0:
                num //= i
                time+=1
            if not i in lists:
                lists.append(i)
    if num!=1:
        if not num in arr:
                lists.append(num)
    return lists
A , B = list(map(int,input().split()))
print(len(result(gcd(A,B)))+1)

### FIXED CODE ###

from fractions import gcd
def result(n):
    lists = list()
    num = n
    for i in range(2, int((n**0.5//1))+1):
        if num%i==0:
            time=0
            while num%i==0:
                num //= i
                time+=1
            if not i in lists:
                lists.append(i)
    if num!=1:
        if not num in lists:
                lists.append(num)
    return lists
A , B = list(map(int,input().split()))
print(len(result(gcd(A,B)))+1)
from fractions import gcd
n,m = map(int,input().split())
s = input()
t = input()
x = gcd(n,m)
for i in range(x+1):
  if s[i*n//x]!=t[i*m//x]:
    print(-1)
    break
else:
  print(n*m//x)

### FIXED CODE ###

from fractions import gcd
n,m = map(int,input().split())
s = input()
t = input()
x = gcd(n,m)
for i in range(x):
  if s[i*n//x]!=t[i*m//x]:
    print(-1)
    break
else:
  print(n*m//x)
import math

a , b , h, m = map(int , input())

x = 360/12
y = (h/12)+(m/45)*x
z = math.radians(y)
ans = a**2+b**2-2*a*b*cos(z)

print(ans)

### FIXED CODE ###

import math
a, b, h, m = map(int, input().split())
     
mr = 6*m
hr = 360*(h/12+m/720)
r = math.radians(abs(mr-hr))
ans = math.sqrt((a**2)+(b**2)-2*a*b*math.cos(r))
print(ans)
n = int(input())
edge = [[[] for i in range(2)] for j in range(n)]
dp = [-1] * n
for i in range(n - 1):
    a, b, c = map(int, input().split())
    edge[a - 1][0].append(b - 1)
    edge[a - 1][1].append(c)
    edge[b - 1][0].append(a - 1)
    edge[b - 1][1].append(c)


def distance(x, prev, d):
    dp[x] = d
    for i, j in zip(edge[x][0], edge[x][1]):
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        distance(i, x, d + j)
    return

q, k = map(int, input().split())
k -= 1

ans = []
distance(k, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    ans.append(dp[x - 1] + dp[y - 1])

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

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n = int(input())
edge = [[[] for i in range(2)] for j in range(n)]
dp = [-1] * n
for i in range(n - 1):
    a, b, c = map(int, input().split())
    edge[a - 1][0].append(b - 1)
    edge[a - 1][1].append(c)
    edge[b - 1][0].append(a - 1)
    edge[b - 1][1].append(c)


def distance(x, prev, d):
    dp[x] = d
    for i, j in zip(edge[x][0], edge[x][1]):
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        distance(i, x, d + j)
    return

q, k = map(int, input().split())
k -= 1

ans = []
distance(k, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    ans.append(dp[x - 1] + dp[y - 1])

for i in range(q):
    print(ans[i])
n,m,v,p = map(int, input().split())
a = list( map(int, input().split()))

a.sort(reverse=True)
# a = np.array(a)

def isok(i):

    if i <= (p-1):
        return True

    points = a.copy()

    points[i] += m

    adding_point = m*v-m*p

    if points[i] < points[p-1]:
        return False

    j = n-1
    while adding_point > 0:

        if j <= p-2:
            return False

        if i == j:
            j -= 1
            continue
        adding_point -= min(m, points[i]- points[j])

        j -= 1

    return True

if isok(n-1):
    print(n)
    exit()

ok = p-1
ng = n-1

while ng - ok > 1:
    mid = (ok+ng)//2

    if isok(mid):
        ok = mid
    else:
        ng = mid
print(ok+1)



### FIXED CODE ###

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

a.sort(reverse=True)

def isok(i):

    if i <= (p-1):
        return True

    points = a.copy()

    points[i] += m

    adding_point = m*v-m*p

    if points[i] < points[p-1]:
        return False

    j = n-1
    while adding_point > 0:

        if j <= p-2:
            return False

        if i == j:
            j -= 1
            continue
        adding_point -= min(m, points[i]- points[j])

        j -= 1

    return True

if isok(n-1):
    print(n)
    exit()

ok = p-1
ng = n-1

while ng - ok > 1:
    mid = (ok+ng)//2

    if isok(mid):
        ok = mid
    else:
        ng = mid
print(ok+1)
import math

x = int(input())

def is_prime(n):
  for i in range(int(math.sqrt(n))):
    if(n%i==0):
      return False
  return True

for i in range(x, x+100):
  if is_prime(i):
    print(i)
    exit()

### FIXED CODE ###

import math

x = int(input())

def is_prime(n):
  for i in range(2, int(math.sqrt(n))):
    if(n%i==0):
      return False
  return True

for i in range(x, x+100):
  if is_prime(i):
    print(i)
    exit()
n,q=map(int,input().split())
s=input()
list_ac=[]
number=0
for i in range(0,n):
    if s[i]=='A':
        state=1
        list_ac.append(number)
    elif s[i]=='C':
        if state==1:
            number=number+1   
        list_ac.append(number)
        state=0
    else:
        state=0
        list_ac.append(number)
print(list_ac)
for i in range(0,q):
    l,r=map(int,input().split())
    print(list_ac[r-1]-list_ac[l-1])
        
    


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
list_ac=[0]
number=0
for i in range(0,n):
    if s[i:i+2]=='AC':
        number=number+1
        list_ac.append(number)
    else:
        list_ac.append(number)
for i in range(0,q):
    l,r=map(int,input().split())
    print(list_ac[r-1]-list_ac[l-1])
N = input()
if int(N[-1]) %2 == 0:
    ans = int(N[:-1])
    N = int(N[:-1])
    k = 1
    while k != 0:
        k = N // 5
        N = k
        ans += k
    print(ans)
else:
    print(0)
    

### FIXED CODE ###

N = input()
if len(N) <= 1:
  print(0)
  exit()
if int(N[-1]) %2 == 0:
    ans = int(N[:-1])
    N = int(N[:-1])
    k = 1
    while k != 0:
        k = N // 5
        N = k
        ans += k
    print(ans)
else:
    print(0)
for i in range(K-1):
  x = q.get()
  print(x)
  if x%10 != 0:
    q.put(10*x + (x%10 -1) )
  q.put(10*x+x%10)
  if x%10 != 9:
    q.put(10*x + (x %10 + 1) )
print(q.get())

### FIXED CODE ###

import queue
K = int(input())
q = queue.Queue()
for i in range(1,10):
  q.put(i)
    
    
for i in range(K-1):
  x = q.get()
  if x%10 != 0:
    q.put(10*x + (x%10 -1) )
  q.put(10*x+x%10)
  if x%10 != 9:
    q.put(10*x + (x %10 + 1) )
print(q.get())
K = input()
A, B = map(int, input().split())

result = False
for i in range(A, B + 1):
    if (i % K) == 0:
        result = True
print("OK" if result else "NG")

### FIXED CODE ###

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

result = False
for i in range(A, B + 1):
    if (i % K) == 0:
        result = True
print("OK" if result else "NG")
S=input()
if S=="ABC":
  print("ARC")
else:
  print("ABC)

### FIXED CODE ###

S=input()
if S=="ABC":
  print("ARC")
else:
  print("ABC")
a, b, c, d = map(int, input().split())

if a >= 0 and c >= 0:
    ans = b * d
elif  b <= 0 and d <= 0:
    ans = a * c
elif a >= 0 and d <= 0:
    ans = a * d
elif b <= 0 and c >= 0:
    ans = b * c

    
print(ans)


### FIXED CODE ###

a, b, c, d = map(int, input().split())

ans = []

ans.append(a * c)
ans.append(b * c)
ans.append(a * d)
ans.append(b * d)

print(max(ans))