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

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.7:
        return # gori~~~
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')

### FIXED CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        # gori~~~
        print('No')
        exit()
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')
### BUGGY CODE ###

import collections

n = int(input())
s = [str(input()) for _ in range(n)]
ans = []

c = collections.Counter(s)
for i in c:
    if c[i] == max(c.values()):
        ans.append(i)
ans.sort()

for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())

d = {}
for i in range(n):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

m = max(d.values())
for i in sorted(k for k in d if d[k] == m):
    print(i)
### BUGGY CODE ###

s=input()
t=input()

dp=[[0]*(len(t)+1) for x in range(len(s)+1)]
arr = ""

for i in range(len(s)-1,-1,-1):
    for j in range(len(t)-1,-1,-1):
        if s[i] == t[j]:
            dp[i][j] = dp[i+1][j+1] + 1
        else:
            dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
# print(dp)
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)


### FIXED CODE ###

s=input()
t=input()

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            if s[i] == t[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)
### BUGGY CODE ###

import itertools

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
              #if (d[i][k] != float("INF")) and (d[k][j] != float("INF")):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        #print(d)
    return d

N, M ,R = map(int, input().split())
r = list(map(int, input().split()))
rr = list(itertools.permutations(r, R))
ab = [[10 ** 10] * N for i in range(N)]
for i in range(N):
  ab[i][i] = 0
  
for i in range(M):
  a, b, c = list(map(int, input().split()))
  ab[a - 1][b - 1] = c
  ab[b - 1][a - 1] = c
  
ans = warshall_floyd(ab)  
#print(rr)
#print(ans)
#2 ** 8
answer = 10 ** 12
for i in rr:
  now = 0
  #print(i)
  for j in range(R - 1):
    now += ans[i[j] - 1][i[j + 1] - 1]
    
  answer = min(answer, now)  
  
print(answer)



    
    
    



### FIXED CODE ###

import itertools

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
              #if (d[i][k] != float("INF")) and (d[k][j] != float("INF")):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        #print(d)
    return d

N, M ,R = map(int, input().split())
r = list(map(int, input().split()))
rr = list(itertools.permutations(r, R))
ab = [[10 ** 10] * N for i in range(N)]
for i in range(N):
  ab[i][i] = 0
  
for i in range(M):
  a, b, c = list(map(int, input().split()))
  ab[a - 1][b - 1] = c
  ab[b - 1][a - 1] = c
  
ans = warshall_floyd(ab)  
#print(rr)
#print(ans)
#2 ** 8
answer = 10 ** 12
for i in rr:
  now = 0
  #print(i)
  for j in range(R - 1):
    now += ans[i[j] - 1][i[j + 1] - 1]
    
  answer = min(answer, now)  
  
print(answer)
### BUGGY CODE ###

import numpy as np
MOD = 10 ** 9 + 7

n=int(input()) #3
alst=np.array(list(map(int,input().split()))) #[1,2,3]

total=np.sum(alst) #6
sum=0

for i in range(n-1):
  for j in range(i+1,n):
    sum=sum+alst[i]*alst[j]
    sum%=MOD

print(sum)

### FIXED CODE ###

MOD = 10 ** 9 + 7

n=int(input())
alst=list(map(int,input().split()))

total=sum(alst)
sum=0

# for i in range(n-1):
#   for j in range(i+1,n):
#     sum=pow(sum+alst[i]*alst[j],1,MOD)

# print(sum)

for a in alst:
  sum = sum+a * (total - a)
  sum %= MOD

sum *= pow(2, MOD - 2, MOD)
sum %= MOD
print(sum)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b0 = [n]*41
b1 = [0]*41
ans = 0
temp = 0
for i in a:
    bit = bin(i)
    for j in range(len(bit)-2):
        t = (int(bit[-j-1]) == 1)
        b0[-j-1] -= t
        b1[-j-1] += t
# print(b1)
# print(b0)
for i in range(41):
    if temp + 2**(40-i) <= k and b0[i] > b1[i]:
        temp += 2**(40-i)
        ans += 2**(40-i) * b0[i]
    else:
        ans += 2**(40-i) * b1[i]

print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b0 = [n]*41
b1 = [0]*41
ans = 0
temp = 0
for i in a:
    bit = bin(i)
    for j in range(len(bit)-2):
        t = (int(bit[-j-1]) == 1)
        b0[-j-1] -= t
        b1[-j-1] += t
# print(b1)
# print(b0)
for i in range(41):
    if temp + 2**(40-i) <= k and b0[i] > b1[i]:
        temp += 2**(40-i)
        ans += 2**(40-i) * b0[i]
    else:
        ans += 2**(40-i) * b1[i]

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

n = int(input())
a_inputs = list(map(int,input().split()))
len_bar = sum(a_inputs)

gap = float('inf')
for i in range(n-1):
    g = abs(len_bar-2*sum(a_inputs[:i+1]))
    if g<gap:
        gap=g
print(gap)


### FIXED CODE ###

n = int(input())
a_inputs = list(map(int,input().split()))
len_bar = sum(a_inputs)

cum_bar = [0]*n
cum_bar[0]=a_inputs[0]
for i in range(1,n):
    cum_bar[i]=cum_bar[i-1]+a_inputs[i]

gap = float('inf')
for i in range(n-1):
    g = abs(len_bar-2*cum_bar[i])
    if g<gap:
        gap=g
print(gap)
### BUGGY CODE ###

import sys 
N,K = map(int,input().split())
l = list(map(int,input().split()))
m = [0 for i in range(N)]
location = 0
count = 0
for i in range(K):
    location = l[location] -1
    m[location] += 1
    if m[location] == 2:
        start = location
        for j in range(K-i-1):
            location = l[location] -1
            count += 1
            if location == start:
                print(count)
                for k in range((K-i-j-2)//count):
                    location = l[location] -1
                print(location + 1)
                sys.exit()
        print(location + 1)
        sys.exit()
print(location + 1)


### FIXED CODE ###

import sys 
N,K = map(int,input().split())
l = list(map(int,input().split()))
m = [0 for i in range(N)]
location = 0
count = 0
for i in range(K):
    location = l[location] -1
    m[location] += 1
    if m[location] == 2:
        start = location
        for j in range(K-i-1):
            location = l[location] -1
            count += 1
            if location == start:
                for k in range((K-i-j-2)%count):
                    location = l[location] -1
                print(location + 1)
                sys.exit()
        print(location + 1)
        sys.exit()
print(location + 1)
### BUGGY CODE ###

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

a.insert(0,0)
a.append(0)

for i in range(1,n+1):
    ans=0
    tmp=a.copy()
    tmp.pop(i)
    for j in range(1,n+1):
        ans+=abs(tmp[j]-tmp[j-1])
    print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))+[0]
A.insert(0,0)
cost=0
for i in range(N+1):
    cost+=abs(A[i+1]-A[i])
for i in range(1,N+1):
    print(cost-abs(A[i+1]-A[i])-abs(A[i]-A[i-1])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

def acinput():
    return list(map(int, input().split(" ")))

import numpy as np


N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

#ab=sorted(ab,key=lambda x:x[1],reverse=True)
ab=sorted(ab,key=lambda x:x[0])


res=0
do=[0]*(M+1)
nowdate=M-1
koho=np.array([])
k=0
while True:
    #print(k)
    i=k
    while True:
        if i>=len(ab):
            k=10**8
            break
        if ab[i][0]+nowdate>M:
            k=i
            break
        koho=np.append(koho,ab[i][1])
        i+=1
    #print(koho)
    if len(koho)>0:
        maxi=np.argmax(koho)
        #print(koho)
        res+=koho[maxi]
        koho=np.delete(koho,maxi)
    nowdate-=1
    if nowdate<0:
        break
    

print(int(res))


### FIXED CODE ###

def acinput():
    return list(map(int, input().split(" ")))


import heapq

N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

#ab=sorted(ab,key=lambda x:x[1],reverse=True)
ab=sorted(ab,key=lambda x:x[0])
#print(ab)

res=0
do=[0]*(M+1)
nowdate=M-1

koho=[]
k=0
while True:
    #print(k)
    #print(nowdate)
    i=k
    while True:
        if i>=len(ab):
            k=10**10
            break
        if ab[i][0]+nowdate>M:
            k=i
            break
        #koho=np.append(koho,ab[i][1])
        heapq.heappush(koho,-ab[i][1])
        i+=1
    #print(koho)
    try:
        tmp=heapq.heappop(koho)
        res+=(-tmp)
    except:
        pass

    
    nowdate-=1
    if nowdate<0:
        break
    

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

def divisors(n):
    i = 1
    cnt = 0
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i * i != n:
                cnt += 1
        i += 1
    return cnt

n = int(input())
ans = 0
for i in range(1, n + 1):
    ans += i * divisors(i)

print(ans)

### FIXED CODE ###

def cal(b, e):
    return ((b + (e//b) * b) * (e//b))//2

n = int(input())
ans = 0

for i in range(1, n+1):
    ans += cal(i, n)

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

N = int(input())
S = input()
count = 0
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if S[i] != S[j]:
            for k in range(j+1,N):
                if j-i != k-j:
                    if S[j] != S[k] and S[k] != S[i]:
                        count += 1
print(count)


### FIXED CODE ###

N = int(input())
S = "A"
S += input()
r = 0
g = 0
b = 0
k = 0
for i in range(1, N+1):
    if S[i] == "R":
        r += 1
    elif S[i] == "G":
        g += 1
    else:
        b += 1

sum = r * g * b
for i in range(1, N-1):
    for j in range(i+1,N):
        k = 2*j - i
        if k <= N:
            if S[j] != S[i] and S[k] != S[j] and S[i] != S[k]:
                sum -= 1

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

import numpy as np 
n,k=map(int,input().split())
a=list(map(int,input().split()))
arr=np.array(a)

def imo(a):
    imos=np.zeros(n+1,dtype="int64")
#print(arr[0])
    for i in range(n):
        imos[max(0,i-arr[i])]+=1
        imos[min(n,i+arr[i]+1)]-=1
    
    immo=np.zeros(n+1)
    immo=np.cumsum(imos)
    return immo[:n]


for _ in range(min(k,41)):
    arr=imo(arr)
    
print(*arr)


### FIXED CODE ###

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

def imo(a):
    imos=[0]*(n+1)

    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=[0]*(n+1)
    immo[0]=imos[0]
    for i in range(n):
        immo[i+1]=immo[i]+imos[i+1]

    return immo[:n]

for i in range(min(k,41)):
    a=imo(a)
    
print(*a)
### BUGGY CODE ###

from heapq import heapify,heappop,heappush
N,M=map(int,input().split())
S,T=map(int,input().split())
Graph=[set() for i in range(N)]
Edge=[]
mod=10**9+7
inf=float("inf")
for i in range(N):
  Edge.append((i,i,0))
for i in range(M):
  a,b,c=map(int,input().split())
  Graph[a-1].add((c,b-1))
  Graph[b-1].add((c,a-1))
  Edge.append((a-1,b-1,c))
  Edge.append((b-1,a-1,c))
def dijkstra(s,n,links):
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    for c,p in links[hp]:
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]+=P[hp]
  return cost,P
  
cost_S,P_S=dijkstra(S-1,N,Graph)
cost_T,P_T=dijkstra(T-1,N,Graph)
D=cost_S[T-1]
List=[]
for a,b,c in Edge:
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]<D/2 and cost_T[b]<D/2 and c>0:
    List.append(P_S[a]*P_T[b]%mod)
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]==D/2 and cost_T[b]==D/2 and c==0:
    List.append(P_S[a]*P_T[b]%mod)
Sum=sum(List)%mod
ans=0
for i,c in enumerate(List):
  ans=(ans+(Sum-List[i])*List[i])%mod
print(ans)



      
  
  
  
  


### FIXED CODE ###

from heapq import heapify,heappop,heappush
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
S,T=map(int,input().split())
Graph=[set() for i in range(N)]
Edge=[]
mod=10**9+7
inf=float("inf")
for i in range(M):
  a,b,c=map(int,input().split())
  Graph[a-1].add((c,b-1))
  Graph[b-1].add((c,a-1))
  Edge.append((a-1,b-1,c))
  Edge.append((b-1,a-1,c))
def dijkstra(s,n,links):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

def dp(s,n,links,d):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if 2*hc>d:
      break
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

cost_S,P_S=dijkstra(S-1,N,Graph)
D=cost_S[T-1]
cost_T,P_T=dp(T-1,N,Graph,D)
Pat=P_S[T-1]
ans=(Pat**2)%mod
for a,b,c in Edge:
  if cost_S[a]+cost_T[b]+c==D:
    if 2*cost_S[a]<D and 2*cost_T[b]<D:
      ans-=((P_S[a]*P_T[b])**2)%mod
for i in range(N):
  if 2*cost_S[i]==2*cost_T[i]==D:
    ans-=((P_S[i]*P_T[i])**2)%mod
print(ans%mod)
### BUGGY CODE ###

def low_left(ls,key):
    left,right = -1,len(ls)
    while right - left > 1:
        mid = (right+left)//2
        if ls[mid] >= key:
            right = mid
        else:
            left = mid
    return len(ls[:(left+1)])


def high_right(ls,key):
    left,right = -1,len(ls)
    while right - left > 1:
        mid = (right+left)//2
        if ls[mid]<=key:
            left = mid
        else:
            right = mid
    return len(ls[right:])


def test():
    n = int(input())
    A,B,C = [list(sorted((map(int,input().split())))) for i in range(3)]
    ans = 0

    for b in B:
        ans += high_right(C,b)*low_left(A,b)
    print(ans)


if __name__ == "__main__":
    test()


### FIXED CODE ###

def test():
    n = int(input())
    A,B,C = [list(sorted(map(int,input().split()))) for i in range(3)]
    ans = 0

    for b in B:
        ans += low_left(A,b) * (n-high_right(C,b))
    print(ans) 


def low_left(ls,t):
    low,high = 0,len(ls)
    while low<high:
        mid = (low+high)//2
        if ls[mid] < t:
            low = mid + 1
        else:
            high = mid
    return low


def high_right(ls,t):
    low,high = 0,len(ls)
    while low<high:
        mid = (low+high)//2
        if ls[mid] > t:
            high = mid
        else:
            low = mid + 1
    return low


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

n=int(input())
s=[int(input()) for _ in [0]*n]

from itertools import chain,combinations
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

m=0
for i in powerset(s):
    v=sum(i)
    if m<v and v%10!=0:
        m=v
print(m)

### FIXED CODE ###

n=int(input())
s=sorted([int(input()) for _ in [0]*n])

if sum(s)%10==0:
    f=False
    for i in s:
        if i%10!=0:
            f=True
            break
    if f:
        s.remove(i)
        print(sum(s))
    else:
        print(0)
else:
    print(sum(s))
### BUGGY CODE ###

def main() :
  N, M = map(int, input().split())
  p = []
  S = []

  for i in range(M) :
    tmp = input().split()
    p.append(int(tmp[0]))
    S.append(tmp[1])

  s = set(p)
  dict = {}
  for i in s :
    dict[i] = 0
  # print(dict)
  w_cnt = 0
  a_cnt = 0
  skip = []
  for i in range(M) :
    if p[i] not in skip :
      if S[i] == 'WA' :
        dict[p[i]] += 1
        continue
      else :
        a_cnt += 1
        w_cnt += dict[p[i]]
        skip.append(p[i])
        continue

  print(a_cnt, w_cnt)

if __name__ == '__main__' :
  main()

### FIXED CODE ###

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

p = [0]*(n+1)
q = [False]*(n+1)

for _ in range(m) :
  v,s = input().split()
  v = int(v)
  if q[v] : continue
  if s[0] == 'A' : q[v] = True
  else : p[v] += 1

print(sum(q), sum(p[i] for i in range(n+1) if q[i]))
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-



import sys
############
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def main():
    X = int(input())
    divs = make_divisors(X)
    for d in divs:
        if (X-pow(d,5))%10!=0:
            continue
        for i in range(-d,X):
            Y=pow(i+d,5)-pow(i,5)
            if Y==X:
                print(i+d,i)
                sys.exit()
            elif Y>X and i>0:
                break

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys

def main():
    X = int(input())
    for a in range(-200, 200):
        a5 = pow(a,5)
        for b in range(-200, 200):
            b5 = pow(b,5)
            if a5-b5 == X:
                print(a,b)
                sys.exit()

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

import copy
a = int(input())
a_list = []
for i in range(a):
    a_list.append(int(input()))
b_list = copy.copy(a_list)
for i in range(len(a_list)):
    b_list.pop(i)
    print(max(b_list))
    b_list = copy.copy(a_list)

### FIXED CODE ###

import sys
a = int(input())
a_list = []
for i in range(a):
    a_list.append(int(input()))
max_num = max(a_list)
if a_list.count(max_num) != 1:
    for i in range(a):
        print(max_num)
else:
    sec_num = sorted(a_list)[-2]
    for i in a_list:
        if i == max_num:
            print(sec_num)
        else:
            print(max_num)
### BUGGY CODE ###

N, T = map(int, input().split())
A = [int(i) for i in input().split()]

c = 0
MAX = 0
for i in range(N-1):
    a1 = min(A[:i+1])
    a2 = A[i+1]
    if MAX == a2 - a1:
        c += 1
    elif MAX < a2 - a1:
        MAX = a2 - a1
        c = 1
print(c)


### FIXED CODE ###

N, T = map(int, input().split())
A = [int(i) for i in input().split()]

c = 0
MAX = 0
a1 = A[0]
for i in range(N-1):
    if A[i] <= a1:
        a1 = A[i]
    a2 = A[i+1]
    if MAX == a2 - a1:
        c += 1
    elif MAX < a2 - a1:
        MAX = a2 - a1
        c = 1
print(c)
### BUGGY CODE ###

import math

cand = list(set([2**x * 5**y for x in range(18)
                 for y in range(8) if 2**x * 5**y <= 200000]))
cand.sort()


def f(n):
    for i in cand:
        x = n * i
        if x.is_integer():
            return i
    else:
        return None


def div(n, bl=True):
    if n is None:
        return (-1, -1)
    if n == -1:
        return (-1, -1)
    if n == 10**9 + 1:
        return (False, False)
    elif bl and not n.is_integer():
        return (0, 0)
    else:
        n = int(n)
        two = format(n, 'b')[::-1].find('1')
        if two < 0:
            return(-1, -1)
        n = n >> two
        cnt = 0
        while n % 5 == 0:
            n //= 5
            cnt += 1
        return (two, cnt)


n = int(input())
arr = [float(input()) for _ in range(n)]
arr = [x for x in arr if min(
    x - int(x), math.ceil(x) - x) >= 0.000005 or x == int(x)]

x = [div(x) for x in arr]
y = [div(x, False) for x in [f(x) for x in arr]]
z = [div(x * 2**y1 * 5**z, False) for x, (y1, z) in zip(arr, y)]


ans = 0
for i in range(len(y)):
    for j in range(i + 1, len(y)):
        (a, b), (c, d) = y[i], y[j]
        if a == -1 or b == -1 or c == -1 or d == -1:
            continue
        elif a == 0 and b == 0 and c == 0 and d == 0:
            ans += 1
        elif a + c <= z[i][0] + z[j][0] and b + d <= z[i][1] + z[j][1]:
            ans += 1

print(ans)

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

import heapq

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

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

hq = [[-a[0]-b[0]-c[0], 0, 0, 0]]
heapq.heapify(hq)
visited = [[[0] * z for yy in range(y)] for xx in range(x)]
for i in range(k):
    ii, ia, ib, ic = heapq.heappop(hq)
    print(-ii)
    na = min(ia+1, x-1)
    nb = min(ib+1, y-1)
    nc = min(ic+1, z-1)
    if visited[na][ib][ic] == 0:
        heapq.heappush(hq, [-a[na] -b[ib] -c[ic], na, ib, ic])
        visited[na][ib][ic] = 1
    if visited[ia][nb][ic] == 0:
        heapq.heappush(hq, [-a[ia] -b[nb] -c[ic], ia, nb, ic])
        visited[ia][nb][ic] = 1
    if visited[ia][ib][nc] == 0:
        heapq.heappush(hq, [-a[ia] -b[ib] -c[nc], ia, ib, nc])
        visited[ia][ib][nc] = 1

### FIXED CODE ###

import heapq

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

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

hq = [[-a[0]-b[0]-c[0], 0, 0, 0]]
heapq.heapify(hq)
visited = {(0,0,0)}

for i in range(k):
    ii, ia, ib, ic = heapq.heappop(hq)
    print(-ii)
    na = min(ia+1, x-1)
    nb = min(ib+1, y-1)
    nc = min(ic+1, z-1)
    if not (na, ib, ic) in visited:
        heapq.heappush(hq, [-a[na] -b[ib] -c[ic], na, ib, ic])
        visited.add((na, ib, ic))
    if not (ia, nb, ic) in visited:
        heapq.heappush(hq, [-a[ia] -b[nb] -c[ic], ia, nb, ic])
        visited.add((ia, nb, ic))
    if not (ia, ib, nc) in visited:
        heapq.heappush(hq, [-a[ia] -b[ib] -c[nc], ia, ib, nc])
        visited.add((ia, ib, nc))