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

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

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

pow2 = [0 for _ in range(n+1)]
pow2[0] = 1
for i in range(n):
    pow2[i+1] = pow2[i]*2 %mod

for _ in range(n-1):
    a,b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

depth = [-1]*n
ko_all = [0 for _ in range(n)]
ko_only =[0 for _ in range(n)]

def dfs(v,d):
    depth[v] = d
    for w in g[v]:
        if depth[w] == -1:
            dfs(w,d+1)
            ko_all[v] += ko_all[w]+1
            ko_only[v] += pow2[ko_all[w]+1]-1

dfs(0,0)

cnt = 0

for i in range(n):
    tmp = pow2[n-1]-1-(pow2[n-1-ko_all[i]]-1) - ko_only[i]
    tmp %=mod
    cnt += tmp
    cnt %= mod

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

print(inv(pow2[n],mod)*cnt %mod)


### FIXED CODE ###

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

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

pow2 = [0 for _ in range(n+1)]
pow2[0] = 1
for i in range(n):
    pow2[i+1] = pow2[i]*2 %mod

for _ in range(n-1):
    a,b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

depth = [-1]*n
ko_all = [0 for _ in range(n)]
ko_only =[0 for _ in range(n)]

def dfs(v,d):
    depth[v] = d
    for w in g[v]:
        if depth[w] == -1:
            dfs(w,d+1)
            ko_all[v] += ko_all[w]+1
            ko_only[v] += pow2[ko_all[w]+1]-1

dfs(0,0)

cnt = 0

for i in range(n):
    tmp = pow2[n-1]-1-(pow2[n-1-ko_all[i]]-1) - ko_only[i]
    tmp %=mod
    cnt += tmp
    cnt %= mod

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

print(inv(pow2[n],mod)*cnt %mod)
### BUGGY CODE ###

import math
n = int(input())
count = [0]*n
for i in range(1,n+1):
    for x in range(1,int(n**0.5)+1):
        for y in range(1,int(n**0.5)+1):
            b = x + y
            c = x*x + y*y + x*y - i
            if b**2 >= 4*c:
                d = (-b + math.sqrt(b**2-4*c))/2 #zの解
                if d.is_integer() == True and d >= 1:
                    count[i-1] += 1
    print(count[i-1])

### FIXED CODE ###

import math
n = int(input())
count = [0]*(10**7)
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            count[i*i + j*j + k*k + i*j + j*k + k*i -1] += 1
for i in range(n):
    print(count[i])
### BUGGY CODE ###


def main():
    
    N, K = map(int,input().split())
    moves = []

    mod = 998244353

    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        moves.append((L, R))
    moves.sort()

    dp = [0] * (N + 1)
    dp[1] = 1
    # for dis in moves:
    #     dp[dis] = 1
    # print(moves)

    for n in range(1, N+1):
        for L, R in moves:
            if n - L <= 0 :
                break
            for dis in range(L, R+1):
                if n - dis >= 1:
                    dp[n] += dp[n - dis]
                else:
                    break

    # print(dp)
    print(dp[N] % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = [int(x) for x in input().split()]
mgcd = 0
for ind,i in enumerate(A):
    mgcd = max(mgcd,gcd_list(A[:ind]+A[ind+1:]))
print(mgcd)


### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = [int(x) for x in input().split()]
L = [0]*N
R = [0]*N
ans = 0
for i in range(N):
    if(i==0):
        L[i] = A[0]
        R[i] = A[-1]
    else:
        L[i] = gcd(A[i],L[i-1])
        R[i] = gcd(A[-i-1],R[i-1])

for i in range(N):
    if(i==0):
        ans = R[-2]
    elif(i==N-1):
        ans = max(ans,L[-2])
    else:    
        ans = max(ans,gcd(L[i-1],R[-i-2]))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


r,c,k = readints()
a = [[0]*(c+1) for i in range(r+1)]

for i in range(k):
    R,C,V = readints()
    a[R][C] = V

dp = [[[0]*4 for j in range(c+1)] for i in range(r+1)]

for i in range(1,r+1):
    for j in range(1,c+1):
        for l in range(4):
            if l == 0:
                dp[i][j][l] = max(dp[i][j-1][l], dp[i-1][j][3])
            else:
                dp[i][j][l] = max(dp[i][j-1][l], dp[i-1][j][3]+a[i][j], dp[i][j-1][l-1]+a[i][j])


print(dp[r][c][3])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


r,c,k = readints()
a = [[0]*(c+1) for i in range(r+1)]

for i in range(k):
    R,C,V = readints()
    a[R][C] = V

dp = [0]*(r+1)*(c+1)*4

for x in range((r+1)*(c+1)*4):
    i = x//((c+1)*4)
    l = x%((c+1)*4)
    j = l//4
    l %= 4
    if i==0 or j==0:
        continue
    if l==0:
        dp[x] = max(dp[i*(c+1)*4 + (j-1)*4], dp[(i-1)*(c+1)*4 + j*4 + 3])
    else:
        dp[x] = max(dp[i*(c+1)*4 + (j-1)*4 + l], dp[(i-1)*(c+1)*4 + j*4 + 3]+a[i][j], dp[i*(c+1)*4 + (j-1)*4 + l-1]+a[i][j])

print(dp[-1])
### BUGGY CODE ###

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()))

ab = []
for a in A:
	for b in B:
		ab += [a + b]

ab3000 = sorted(ab)[::-1][:3000]

abc = []
for ab in ab3000:
	for c in C:
		abc += [ab + c]

abc.sort(reverse=True)

for k in range(K):
	print(abc[k])


### FIXED CODE ###

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()))

ab = []
for a in A:
	for b in B:
		ab += [a + b]

ab3000 = sorted(ab)[::-1][:3000]

abc = []
for ab in ab3000:
	for c in C:
		abc += [ab + c]

abc.sort(reverse=True)

for k in range(K):
	print(abc[k])
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
l=[]
for j in range(n):
  if a[j] not in l:l.append(a[j])
  else:l.remove(a[j])
print(len(l))

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
a=sorted(a)
x=a[0]
c=1
ct=0
for i in range(1,n):
  if a[i]==x:
    c+=1
    if i==n-1:
      if c%2==1:
        ct+=1
  else:
    if c%2==1:
      ct+=1
    x=a[i]
    c=1
    if i==n-1:
      ct+=1
print(ct)
### BUGGY CODE ###

A,B,C,K = list(map(int, input().split()))
count = 0

if A + B + C == K:
    print(A - C)

elif A > K:
    print(K)
elif A+B > K:
    print(A)
else:
    for i in reversed(range(0, K)):
        if A > 0:
            count += 1
            A = A - 1
        elif B > 0:
            B = B - 1
        else: 
            count -= 1

    print(count)

### FIXED CODE ###

A,B,C,K = list(map(int, input().split()))
count = 0

if A + B + C == K:
    print(A - C)

elif A >= K:
    print(K)
elif A+B >= K:
    print(A)
else:
    t = K - A - B

    print(A - t)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from itertools import permutations

def main():
    n,m,r = map(int,input().split())
    dest = [int(i) - 1 for i in input().split()]
    dist = [[INF] * n for _ in range(n)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j])
    
    ans = INF
    for ptr in permutations(range(r)):
        tmp = 0
        for i in range(r - 1):
            tmp += dist[dest[ptr[i]]][dest[ptr[i + 1]]]
        ans = min (ans, tmp)
    
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from itertools import permutations

def main():
    n,m,r = map(int,input().split())
    dest = [int(i) - 1 for i in input().split()]
    dist = [[INF] * n for _ in range(n)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j])
    
    ans = INF
    for ptr in permutations(range(r)):
        tmp = 0
        for i in range(r - 1):
            tmp += dist[dest[ptr[i]]][dest[ptr[i + 1]]]
        ans = min (ans, tmp)
    
    print(ans)

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

n,q = map(int, input().split())
s = input()
t = [0]*n
for i in range(n):
    t[i] = len([0 for j in range(i) if s[j:j+2] == "AC"])
for i in range(q):
    r,l = map(int, input().split())
    print(t[l-1]-t[r-1])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

import itertools
n = int(input())
l = list(map(int, input().split()))
p = list(itertools.combinations(l,3))
def triangle(a, b, c):
    if a < b + c and b < c + a and c < a + b:
        return True
    else:
        return False
ans = 0
for i in p:
    if triangle(i[0], i[1], i[2]):
        ans += 1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
lis = sorted(list(map(int, input().split())))
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += max(bisect.bisect_left(lis, lis[j]+lis[i]) - j - 1, 0)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_4
# CreatedDate:  2020-07-20 00:18:24 +0900
# LastModified: 2020-07-20 00:49:48 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    A = sorted(map(int, input().split()))
    ans = [1 if i in A else 0 for i in range(A[-1]+1)]
    for i, a in enumerate(A):
        if ans[a] == 0:
            continue
        for s in range(a+a, A[-1]+1, a):
            ans[s] = 0
        if i < n-1 and A[i] == A[i+1]:
            ans[A[i]] = 0

    print(sum(ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_3
# CreatedDate:  2020-06-19 15:09:52 +0900
# LastModified: 2020-06-19 15:27:30 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    _ = int(input())
    a_s = list(map(int, input().split()))
    m = max(a_s)+1
    cnt = [0 for _ in range(m)]

    for a in a_s:
        if cnt[a] != 0:
            cnt[a] = 2
            continue
        for n in range(a, m, a):
            cnt[n] += 1

    print(sum(cnt[a] for a in a_s if cnt[a]==1))


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

from collections import Counter as cnt
import copy
n = int(input())
s = input()

count = cnt(s)
num_rest = []
for i in range(n):
  dic = copy.copy(count)
  dic[s[i]] -= 1
  num_rest.append(len([i for i in dic.values() if i != 0]))
  count = dic
#print(num_rest)

checked = set()
total = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    if s[i] + s[j] not in checked:
      checked.add(s[i] + s[j])
      total += num_rest[j]
print(total)

### FIXED CODE ###

n = int(input())
s = list(input())

def search(s, c, left):
  for idx in range(left, len(s)):
    if s[idx] == c:
      return idx
  return -1

total = 0
for keta1 in range(10):
  first_keta1 = search(s, str(keta1), 0)
  if first_keta1 == -1 or first_keta1 >= n-2:
    continue
  for keta2 in range(10):
    first_keta2 = search(s, str(keta2), first_keta1 + 1)
    if first_keta2 == -1 or first_keta2 >= n-1:
      continue
    for keta3 in range(10):
      first_keta3 = search(s, str(keta3), first_keta2 + 1)
      if first_keta3 != -1:
        total += 1
print(total)
### BUGGY CODE ###

def main():
    N = int(input())
    A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
    d = 0
    p = [0] * N
    r = N
    cur = list(range(N))
    while r:
        matched = False
        d += 1
        m = [False] * N
        nxt = []
        for i in cur:
            if m[i]:
                continue
            if p[i] == N - 1:
                continue
            o = A[i][p[i]]
            if (not m[o]) and A[o][p[o]] == i:
                matched = True
                p[i] += 1
                p[o] += 1
                m[i] = True
                m[o] = True
                if p[i] == N - 1:
                    r -= 1
                else:
                    nxt.append(i)
                if p[o] == N - 1:
                    r -= 1
                else:
                    nxt.append(o)
        cur = nxt
        if not matched:
            return -1
    return d


print(main())


### FIXED CODE ###

def main():
    N = int(input())
    A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if o == -1:
                continue
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
                w[i] = -1
                w[o] = -1
        if not nxt:
            return -1
        cur = []
        for i in nxt:
            if A[i]:
                w[i] = A[i].pop()
                cur.append(i)
            else:
                r -= 1
    return d


print(main())
### BUGGY CODE ###

n=int(input())
a=list(map(lambda x:('0'*62+bin(int(x))[2:])[-62:],input().split()))
mod=pow(10,9)+7
ans=0
for i in range(61):# 2^iの位
  bit1=0
  for ai in a:
    bit1+=int(ai[-i-1])
  ans+=pow(2,i)*bit1*(n-bit1)
  ans%=mod
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  ans=0
  bit=[0]*61 #bit[i]:2^iの位が1である物の個数
  for ai in a:
    for j in range(61):
      if ((ai>>j) & 1):
        bit[j]+=1
  for i in range(61):
    ans+=(pow(2,i)%mod)*bit[i]*(n-bit[i])
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

from collections import defaultdict

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

count_dict = defaultdict(int)
for cal in A:
  count_dict[cal] += 1
    
    
"""
それぞれの要素について、1個減った時とそのままの場合での組み合わせ数を事前に計算しておく
"""
from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
  
# list[0]=そのまま、list[1]=1個減った場合
count_result = defaultdict(list)
for k,v in count_dict.items():
  if v > 2:
    count_result[k] = [combinations_count(v,2), combinations_count(v-1,2)]
  elif v == 2:
    count_result[k] = [1,0]    
  else:
    count_result[k] = [0,0]


"""
対象の数字を指定した場合の答え、を事前に計算しておく
"""
ans_dict = defaultdict(int)
for k,v in count_dict.items():
  ans_dict[k] = count_result[k][1]
  for _k,_v in count_result.items():
    if _k != k:
      ans_dict[k] += _v[0]

    
"""
前から順に表示していく
"""
for _ in A:
  # 対象の数字
  ans = ans_dict[_]
  print(ans)



### FIXED CODE ###

from collections import defaultdict

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

count_dict = defaultdict(int)
for cal in A:
  count_dict[cal] += 1
    
from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

count_result = defaultdict(list)
for k,v in count_dict.items():
  if v > 2:
    count_result[k] = [combinations_count(v,2), combinations_count(v-1,2)]
  elif v == 2:
    count_result[k] = [1,0]    
  else:
    count_result[k] = [0,0]

all_ans = 0
for v in count_result.values():
  all_ans += v[0]


for _ in A:
  ans = all_ans - count_result[_][0] + count_result[_][1]
  print(ans)
### BUGGY CODE ###

def f(i):
    a[i]=(a[i]+1)%10
    if a[i]==0: f(i+1)

n=int(input())
a=[]
tmp=10
while n!=0:
    a.append(n%tmp)
    n=n//tmp
a.append(0)

ans=0
for i in range(len(a)-1):
    if a[i]<5: ans+=a[i]
    elif a[i]==5:
        if a[i+1]<5: ans+=5
        else:
            ans+=5
            f(i+1)

    else:
        ans+=10-a[i]
        f(i+1)

if a[-1]!=0: ans+=1

print(ans)

### FIXED CODE ###

def f(i):
    while True:
        a[i]=(a[i]+1)%10
        if a[i]==0: i+=1
        else: break

s=input()
a=[]
for i in range(len(s)-1,-1,-1):
    a.append(int(s[i]))
a.append(0)

ans=0
for i in range(len(a)-1):
    if a[i]<5: ans+=a[i]
    elif a[i]==5:
        if a[i+1]<5: ans+=5
        else:
            ans+=5
            f(i+1)

    else:
        ans+=10-a[i]
        f(i+1)

if a[-1]!=0: ans+=1

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

def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k:return 0
  if n==0 and k==0:return 1
  a=factorial(n)%p
  b=factorial(k)%p
  c=factorial(n-k)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0:
    return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d*d)%p
  else:
    return (a*power_func(a,b-1,p))%p
n,k=map(int,input().split())
mod=10**9+7
ans=0
r=min(k,n)
for i in range(r+1):
  ans=(ans+comb(n,i,mod)*comb(n-1,i,mod))%mod
print(ans)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def power_func(a,b,p):
  if b==0:
    return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d*d)%p
  else:
    return (a*power_func(a,b-1,p))%p
n,k=map(int,input().split())
mod=10**9+7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
ans=0
r=min(k,n)
for i in range(r+1):
  ans=(ans+cmb(n,i,mod)*cmb(n-1,i,mod))%mod
print(ans)
### BUGGY CODE ###

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

if N == 1:
    print(P)
    exit()

primelist=[]
powerlist=[]

p=2
while P >= p**N:        
    f = 0
    for q in primelist:
        if p % q == 0:
            f = 1
            break
    if f == 1:
        p += 1
        continue
    else:
        k = 0
        while P % p == 0:
            P // p
            k += 1
        primelist.append(p)
        powerlist.append(k//N)
        p += 1

ans = 1
for i in range(len(primelist)):
    ans *= (primelist[i]**powerlist[i])

print(ans)

### FIXED CODE ###

import math

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

if N == 1:
    print(P)
    exit()

ans = 1
p = 2
logP = math.log(P)
while N * math.log(p) <= logP:
    k = 0
    while P % p == 0:
        P //= p
        k += 1
    ans *= p**(k//N)
    if k > 0:
        logP = math.log(P)

    r = p % 6
    if r == 1:
        p += 4
    elif r == 5:
        p += 2
    else:
        p += 1

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

N = int(input())
A = [int(a) for a in input().split(" ")]
B = [int(b) for b in input().split(" ")]
C = [int(c) for c in input().split(" ")]

A.sort()
B.sort()
C.sort()

combiBC = [0] * len(B)
# combiBC[i] : number of combination of B, C when B[i] is selected

ic = 0
lc = len(C)
for ib in range(len(B)):
	b = B[ib]
	while ic < lc:
		c = C[ic]
		if b >= c:
			ic += 1
		else:
			combiBC[ib] = lc - ic
			break

cnt = 0
ib = 0
for ia in range(len(A)):
	a = A[ia]
	while ib < len(B):
		b = B[ib]
		if a >= b:
			ib += 1
		else:
			cnt += sum(combiBC[ib:])
			break

print(cnt)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split(" ")]
B = [int(b) for b in input().split(" ")]
C = [int(c) for c in input().split(" ")]

A.sort()
B.sort()
C.sort()

combiBC = [0] * len(B)
# combiBC[i] : number of combination of B, C when B[i] is selected

ic = 0
lc = len(C)
for ib in range(len(B)):
	b = B[ib]
	while ic < lc:
		c = C[ic]
		if b >= c:
			ic += 1
		else:
			combiBC[ib] = lc - ic
			break

sumCombiBC = []
for i in range(len(combiBC)):
	if i == 0:
		sumCombiBC.append(combiBC[-1])
	else:
		sumCombiBC.insert(0, combiBC[-i-1] + sumCombiBC[0])

cnt = 0
ib = 0
for ia in range(len(A)):
	a = A[ia]
	while ib < len(B):
		b = B[ib]
		if a >= b:
			ib += 1
		else:
			cnt += sumCombiBC[ib]
			break

print(cnt)
### BUGGY CODE ###

def gcd(x, y):
    if x > y:
        tmp = x
        x = y
        y = tmp
    if x == 0:
        return y
    elif y%x == 0:
        return x
    else:
        return gcd(y%x, x)

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

# if N == 2:
#     print(max(A[0], A[1]))
#     return 0

Llist = [0]
Rlist = [0]

for i in range(N):
    Llist.append(gcd(Llist[i], A[i])) 
    Rlist.insert(0, gcd(Rlist[0], A[N-1-i]))

ans = []
for i in range(N):
    ans.append(gcd(Llist[i], Rlist[i+1]))

print(max(ans))


### FIXED CODE ###

def gcd(x, y):
    if x > y:
        tmp = x
        x = y
        y = tmp
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

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

Llist = [0]
Rlist = [0]

for i in range(N):
    Llist.append(gcd(Llist[i], A[i])) 
    # Rlist.insert(0, gcd(Rlist[0], A[N-1-i]))
    Rlist.append(gcd(Rlist[i], A[N-1-i]))
Rlist = Rlist[::-1]
ans = 0
for i in range(N):
    t = gcd(Llist[i], Rlist[i+1])
    if ans < t:
        ans = t

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

#13:12
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  event.append([s-x,1,x])
  event.append([t-x,0,x])
event.sort()
t = 0
now = set()
for _ in range(q):
  d = int(input())
  if t == 2*n:
    print(-1)
    continue
  while event[t][0] <= d:
    if event[t][1] == 1:
      now.add(event[t][2])
    else:
      now.remove(event[t][2])
    t += 1
    if t == 2*n:
      break
  try:
    print(min(now))
  except:
    print(-1)

### FIXED CODE ###

#13:12
n,q = map(int,input().split())
import heapq
import sys
input = sys.stdin.readline
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,(s-x,t-x,x))
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,(tmp[2],tmp[1]))
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)