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

#!/usr/bin/python

# AtCoder Beginner Contest 077
# C - Snuke Festival

from sys import stdin

def solve(As, Bs, Cs):
    # Bs :: [(b, # of bottom parts > b)]
    Bs = [(b, sum([1 for c in Cs if c > b])) for b in Bs]
    # As :: [# of mid & bottom parts > a]
    As = [sum([b[1] for b in Bs if b[0] > a]) for a in As]
    return sum(As)

N = int(stdin.readline())
As = [int(w) for w in stdin.readline().split()]
Bs = [int(w) for w in stdin.readline().split()]
Cs = [int(w) for w in stdin.readline().split()]
if len(As) != N or len(Bs) != N or len(Cs) != N: raise
print(solve(As, Bs, Cs))

### FIXED CODE ###

#!/usr/bin/python

# AtCoder Beginner Contest 077
# C - Snuke Festival

from sys import stdin

def solve(As, Bs, Cs):
    As.sort()
    Bs.sort()
    Cs.sort()
    # Bs :: [(b, # of bottom parts > b)]
    # Bs = [(b, sum([1 for c in Cs if c > b])) for b in Bs]
    j = 0
    for i in range(len(Bs)):
        while j < len(Cs) and Bs[i] >= Cs[j]: j += 1
        Bs[i] = (Bs[i], len(Cs) - j)
    # Accumulate Bs[][1]
    for i in range(len(Bs) - 1, 0, -1):
        Bs[i-1] = (Bs[i-1][0], Bs[i-1][1] + Bs[i][1])
    # As :: [# of mid & bottom parts > a]
    # As = [sum([b[1] for b in Bs if b[0] > a]) for a in As]
    j = 0
    for i in range(len(As)):
        while j < len(Bs) and As[i] >= Bs[j][0]: j += 1
        As[i] = Bs[j][1] if j < len(Bs) else 0
    return sum(As)

N = int(stdin.readline())  # <= 1e+5
As = [int(w) for w in stdin.readline().split()]
Bs = [int(w) for w in stdin.readline().split()]
Cs = [int(w) for w in stdin.readline().split()]
if len(As) != N or len(Bs) != N or len(Cs) != N: raise
print(solve(As, Bs, Cs))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append((i, j, 0))

    ret = 0
    visited = [False] * (W * H)
    while queue:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k]:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if 0 < j and not visited[k - 1] and A[i][j-1] == '.':
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1] and A[i][j+1] == '.':
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W] and A[i-1][j] == '.':
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W] and A[i+1][j] == '.':
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False

    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))
                k = i * (W + 2) + j
                visited[k] = False

    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k] and 0 < n:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        if visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if visited[k + 1]:
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)]:
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

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

def main():
    n, q = map(int, input().split())
    s = input()
    # l = list()
    # r = list()
    s_list = list()
    # s_tuple = tuple()
    for _ in range(q):
        l_i, r_i = map(int, input().split())
        # l.append(l_i)
        # r.append(r_i)
        s_list.append(s[l_i - 1:r_i])
        # s_tuple = s_tuple + tuple(s[l_i - 1:r_i])
    
    s_tuple = tuple(s_list)

    for i in s_tuple:
        print(i.count('AC'))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    # n, q = map(int, input().split())
    # s = input()
    # # l = list()
    # # r = list()
    # s_list = list()
    # # s_tuple = tuple()
    # for _ in range(q):
    #     l_i, r_i = map(int, input().split())
    #     # l.append(l_i)
    #     # r.append(r_i)
    #     s_list.append(s[l_i - 1:r_i])
    #     # s_tuple = s_tuple + tuple(s[l_i - 1:r_i])
    # 
    # s_tuple = tuple(s_list)
    # 
    # for i in s_tuple:
    #     print(i.count('AC'))
    N, Q = map(int, input().split())
    S = input()
    cnt = [0] * (N + 1)
    for i in range(N):
        cnt[i + 1] = cnt[i] + (1 if S[i:i+2] == 'AC' else 0)
    for i in range(Q):
        l, r = map(int, input().split())
        print(cnt[r - 1] - cnt[l - 1])


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

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

C = collections.Counter(A)
#print(C)
calc = {}
for i,cnt in C.items():
    calc[i] = cnt*(cnt-1)//2
#print("calc:",calc)
for i in range(N):
    ans = 0
    for j,k in calc.items():
#        print(j,k,A[i])
        if j != A[i]:
            ans += k
#    print("ans",ans)
#    print("A[i]",A[i],"calc[A[i]]",calc[A[i]])
    if calc[A[i]] != 0:
        ans += (C[A[i]]-1)*(C[A[i]]-2)//2
#        print((calc[A[i]]-2)*(calc[A[i]]-1)//2)
#        ans += (calc[A[i]]-2)*(calc[A[i]]-1)//2
    print(ans)


### FIXED CODE ###

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

C = collections.Counter(A)
#print(C)
calc = {}
for i,cnt in C.items():
    calc[i] = cnt*(cnt-1)//2
#print("calc:",calc)
calc_sum = sum(calc.values())
for i in range(N):
    ans = calc_sum - calc[A[i]]
#    print("ans",ans)
#    print("A[i]",A[i],"calc[A[i]]",calc[A[i]])
    if calc[A[i]] != 0:
        ans += (C[A[i]]-1)*(C[A[i]]-2)//2
#        print((calc[A[i]]-2)*(calc[A[i]]-1)//2)
#        ans += (calc[A[i]]-2)*(calc[A[i]]-1)//2
    print(ans)
### BUGGY CODE ###

N,W  = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    weight = wv[i][0]
    for j in range(W+1):
        dp[i+1][j] = dp[i][j]
        if j >= weight:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight]+wv[i][1])
print(dp[N][W])



### FIXED CODE ###

N,W  = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
MAX_VAL = 100100
MAX_WEIGHT = 10**10

dp = [[MAX_WEIGHT for _ in range(MAX_VAL+1)] for _ in range(N+1)]

dp[0][0] = 0
for i in range(N):
    value = wv[i][1]
    for v in range(MAX_VAL+1):
        dp[i+1][v] = dp[i][v]
        if v >= value:
            dp[i+1][v] = min(dp[i+1][v], dp[i][v-value]+wv[i][0])
max_v = 0
for i in range(MAX_VAL+1):
    if dp[N][i] <= W:
        max_v = i
print(max_v)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    S = [input() for _ in range(N)]

    T = list(set(sorted(S)))
    C = []
    for i in T:
        C.append(S.count(i) * -1)

    Z = zip(C, T)
    Z = sorted(Z)
    C, T = zip(*Z)

    for i in range(len(C)):
        if C[i] == min(C):
            print(T[i])

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    S = [input() for _ in range(N)]

    T = sorted((set(S)))
    l = len(T)

    D = {}
    for i in range(l):
        D[T[i]] = 0
    for i in range(N):
        D[S[i]] += 1

    m = max(D.values())
    for i in range(l):
        if D[T[i]] == m:
            print(T[i])


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

# 高速版input
import sys
input = sys.stdin.readline

n, q = (int(i) for i in input().split())
s = input()
e = [[int(i)-1 for i in input().split()] for i in range(q)]

mem = []
for i in range(len(s)-1):
    if s[i]+s[i+1] == "AC":
        mem.append(1)
    else:
        mem.append(0)

for x in e:
    res = sum(mem[x[0]:x[1]]) 
    print(max(0,res))


### FIXED CODE ###

# 高速版input
import sys
input = sys.stdin.readline

n, q = (int(i) for i in input().split())
s = input()

mem = [0]
count = 0
for i in range(1, len(s)):
    if s[i-1]+s[i] == "AC":
        count +=1
    mem.append(count)
    
for x in [[int(i)-1 for i in input().split()] for i in range(q)]:
    res = mem[x[1]] - mem[x[0]]
    print(res)
### BUGGY CODE ###

h,w,m = map(int,input().split())

bombw = [0]*w
bombh = [0]*h
bomb = [[0 for j in range(w)] for i in range(h)]
# print(bomb)
for i in range(m):
    hi,wi = map(int,input().split())
    bombw[wi-1] += 1
    bombh[hi-1] += 1
    bomb[hi-1][wi-1] = 1
    # print(bomb)
maw = max(bombw)
mah = max(bombh)
# print(maw,mah)
inmaw = [i for i, x in enumerate(bombw) if x == maw]
inmah = [i for i, x in enumerate(bombh) if x == mah]
# print(inmaw,inmah)

ans = maw + mah
# print(bomb)
# print(ans)
for i in inmah:
    for j in inmaw:
        if bomb[i][j] == 0:
            print(ans)
            exit()
print(ans-1)

### FIXED CODE ###

from collections import defaultdict

h,w,m = map(int,input().split())

bombw = [0]*w
bombh = [0]*h
dd = defaultdict(bool)
# print(bomb)
for i in range(m):
    hi,wi = map(int,input().split())
    bombw[wi-1] += 1
    bombh[hi-1] += 1
    dd[str(hi-1)+"-"+str(wi-1)] = True
    # print(bomb)
maw = max(bombw)
mah = max(bombh)
# print(maw,mah)
inmaw = [i for i, x in enumerate(bombw) if x == maw]
inmah = [i for i, x in enumerate(bombh) if x == mah]
# print(inmaw,inmah)

ans = maw + mah
# print(bomb)
# print(ans)
for i in inmah:
    for j in inmaw:
        if not dd[str(i)+"-"+str(j)]:
            print(ans)
            exit()
print(ans-1)
### BUGGY CODE ###

S = input()
T = input()
lenS = len(S)
lenT = len(T)

dp=[[0]*(lenT+1) for _ in range(lenS+1)]

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

"""
復元
"""
ans = []
j = lenT
for i in range(lenS,0,-1):
    if dp[i][j] == dp[i-1][j-1]+1:
        ans.append(S[i-1])
    j -= 1
ans = ans[::-1]
print("".join(ans))

### FIXED CODE ###

# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

#ABC154C

n, k = list(map(int,input().split()))
p = list(int(x) for x in input().split())

ave = 0
j = 0
for i in range(n-2):
    temp = p[i:i+k]
    _ave = (sum(temp))/k
    if _ave>=ave:
        ave = _ave
        j = i

kitai = 0
for x in p[j:j+k]:
    kitai += sum(range(1,x+1))/x

print(kitai)
  

### FIXED CODE ###

#ABC154C

n, k = list(map(int,input().split()))
p = [((int(x)+1)/2) for x in input().split()]

ave = sum(p[0:k])
max = ave
for i in range(n-k):
    ave = ave-p[i]+p[k+i]
    if ave > max:
        max = ave
print(max)
### BUGGY CODE ###

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

def stair(n):
    m=1
    for i in range (2,n+1):
        m=m*i
    return m

def comb(n,r):
    return stair(n)//(stair(r)*stair(n-r))

if (X+Y)%3==0 and (X+Y)//3>=abs(X-Y):
    ans=comb((X+Y)//3,( (X+Y)//3 - abs(X-Y) )//2)
    print(ans%1000000009)
else:
    print(0)

### FIXED CODE ###

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

if (X+Y)%3==0 and (X+Y)//3>=abs(X-Y):
    ans=combination((X+Y)//3,( (X+Y)//3 - abs(X-Y) )//2)
    print(ans%1000000007)
else:
    print(0)
### BUGGY CODE ###

i = int(input())

while True:
    if set(str(i)) == 1:
        print(i)
        break
    i += 1

### FIXED CODE ###

i = int(input())

while True:
    if len(set(str(i))) == 1:
        print(i)
        break
    i += 1
### BUGGY CODE ###

n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)
	i=i+1

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

### FIXED CODE ###

n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)
	i=i+1

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))
### BUGGY CODE ###

# solution 1
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)
AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])
AB.sort(reverse=True)
ABC = []
for k in range(Z):
    for ij in range(min(K, len(AB))):
        ABC.append(AB[ij]+C[k])
ABC.sort(reverse=True)
for l in range(K):
    print(ABC[l])

### 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)
Q = []
heapq.heappush(Q, (-A[0]-B[0]-C[0], 0, 0, 0))
for n in range(K):
    ans = heapq.heappop(Q)
    print(-ans[0])
    i, j, k = ans[1], ans[2], ans[3]
    if i < X-1:
        if (- A[i+1] - B[j] - C[k], i+1, j, k) not in Q:
            heapq.heappush(Q, (- A[i+1] - B[j] - C[k], i+1, j, k))
    if j < Y-1:
        if (- A[i] - B[j+1] - C[k], i, j+1, k) not in Q:
            heapq.heappush(Q, (- A[i] - B[j+1] - C[k], i, j+1, k))
    if k < Z-1:
        if (- A[i] - B[j] - C[k+1], i, j, k+1) not in Q:
            heapq.heappush(Q, (- A[i] - B[j] - C[k+1], i, j, k+1))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

#############
# Main Code #
#############

k,q = map(int, input().split())
d = list(map(int, input().split()))

def query(n,x,m):
  x %= m
  ans = n-1
  n -= 1
  s1 = 0
  t1 = 0
  for i in range(k):
    s1 += d[i] % m
    if d[i] % m == 0:
      t1 += 1
  s2 = 0
  t2 = 0
  for i in range(n%k):
    s2 += d[i] % m
    if d[i] % m == 0:
      t2 += 1
  x += s1 * (n//k) + s2
  ans -= x//m
  ans -= t1 * (n//k) + t2
  
  print(ans)
  
    

for _ in range(q):
  n,x,m = map(int, input().split())
  query(n,x,m)


### FIXED CODE ###

# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

#############
# Main Code #
#############

k,q = map(int, input().split())
d = list(map(int, input().split()))

def query(n,x,m):
  x %= m
  ans = n-1
  n -= 1
  s1 = 0
  t1 = 0
  for i in range(k):
    s1 += d[i] % m
    if d[i] % m == 0:
      t1 += 1
  s2 = 0
  t2 = 0
  for i in range(n%k):
    s2 += d[i] % m
    if d[i] % m == 0:
      t2 += 1
  x += s1 * (n//k) + s2
  ans -= x//m
  ans -= t1 * (n//k) + t2
  
  print(ans)
  
    

for _ in range(q):
  n,x,m = map(int, input().split())
  query(n,x,m)
### BUGGY CODE ###

n, l = map(int, input().split())
ss = [input() for _ in range(n)]

ds = set()
bs = set()
for s in ss:
    i = int(s, 2) + (1 << len(s))
    while i >= 1:
        if i in ds:
            bs.add(i << 1)
            bs.add((i << 1) + 1)
            break
        ds.add(i)
        i >>= 1
# print(ds)
# print(bs)
ds.discard(1)
xor = 0
ofs = l + 2
for r in ds - bs:
    level = ofs - r.bit_length()
    xor ^= level & -level

print('Alice' if xor else 'Bob')


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)


def dfs(cur, dep=0):
    if cur == -1:
        x = l - dep
        return x & -x
    return dfs(trie[cur][0], dep + 1) ^ dfs(trie[cur][1], dep + 1)


n, l = map(int, input().split())
trie = [[-1, -1] for _ in range(100001)]
idx = 1
for s in (input() for _ in range(n)):
    cur = 0
    for c in map(int, s):
        if trie[cur][c] == -1:
            trie[cur][c] = idx
            idx += 1
        cur = trie[cur][c]

xor = dfs(trie[0][0]) ^ dfs(trie[0][1])
print('Alice' if xor else 'Bob')
### BUGGY CODE ###

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

def solve():
    N = int(input())
    AB = [tuple(map(int,input().split())) for i in range(N-1)]
    MOD = 10**9+7
    es = [[] for _ in range(N)]
    for a,b in AB:
        a,b = a-1,b-1
        es[a].append(b)
        es[b].append(a)

    cs = [1] * N
    def dfs(v,p=-1):
        ret = 1
        for to in es[v]:
            if to==p: continue
            ret += dfs(to,v)
        cs[v] = ret
        return ret
    dfs(0)
    ans = 0
    for i in range(N):
        if len(es[i]) == 1: continue
        ans += pow(2,N-1,MOD) - 1
        c = 0
        for to in es[i]:
            if cs[to] > cs[i]: continue
            c += cs[to]
            ans -= pow(2,cs[to],MOD) - 1
        ans -= pow(2,N-c-1,MOD) - 1

    ans *= pow(pow(2,N,MOD), MOD-2, MOD)
    print(ans%MOD)
solve()

### FIXED CODE ###

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

def solve():
    N = int(input())
    AB = [tuple(map(int,input().split())) for i in range(N-1)]
    MOD = 10**9+7
    es = [[] for _ in range(N)]
    for a,b in AB:
        a,b = a-1,b-1
        es[a].append(b)
        es[b].append(a)

    cs = [1] * N
    def dfs(v,p=-1):
        ret = 1
        for to in es[v]:
            if to==p: continue
            ret += dfs(to,v)
        cs[v] = ret
        return ret
    dfs(0)

    pow2 = [1]
    for i in range(N):
        pow2.append((pow2[-1]*2) % MOD)

    ans = 0
    for i in range(N):
        if len(es[i]) == 1: continue
        ans += pow2[N-1] - 1
        c = 0
        for to in es[i]:
            if cs[to] > cs[i]: continue
            c += cs[to]
            ans -= pow2[cs[to]] - 1
        ans -= pow2[N-c-1] - 1

    ans *= pow(pow2[N], MOD-2, MOD)
    print(ans%MOD)
solve()
### BUGGY CODE ###

import fractions
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
l = []
for i in range(N):
    B = A[:]
    B.pop(i)
    l.append(reduce(fractions.gcd, B))
    
print(max(l))

### FIXED CODE ###

from itertools import*
from fractions import*
n,*a=map(int,open(0).read().split())
b=list(accumulate([0]+a,gcd))
c=list(accumulate([0]+a[::-1],gcd))
print(max(gcd(s,t)for s,t in zip(b,c[::-1][1:])))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
  b.append(a[i])
  b = b[::-1]
print(*b)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
print(*A[::-2],end=" ")
print(*A[N%2::2])
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    INF = int(1e20)
    dp = np.array([[INF] * (1000 * N + 1) for i in range(N+1)])
    dp[0][0] = 0

    for i in range(N):
        w, v = wv[i]
        dp[i+1] = dp[i]
        dp[i+1, v:] = np.minimum(dp[i+1, v:], dp[i, :-v] + w)
    
    for i in range(1000, -1, -1):
        if dp[N][i] <= W:
            print(i)
            break

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    INF = int(1e18)
    dp = np.full(1000 * N + 1, INF, dtype=int)
    dp[0] = 0

    max_v = 0
    for i in range(N):
        w, v = wv[i]
        dp[v:max_v + v + 1] = np.minimum(dp[v:max_v + v + 1], dp[:max_v + 1] + w)
        max_v += v
    
    print(np.where(dp <= W)[0].max())

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

import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF=10 ** 10
N = int(input())
XL = sorted([list(map(int,input().split())) for _ in range(N)])
# print(N,XL)

DP = [ INF for _ in range(N+1)]
DP[0] = -INF
for i in range(N):
    #print(DP)
    (x,l) = XL[i]
    # print(x,l)
    for j in range(1,N+1):
        if DP[j-1] > x -l:
            continue
        if ( DP[j-1]<= x -l and x + l < DP[j]):
                DP[j] = x + l
#print(DP)
for i in range(2,N+1):
    if DP[i] == INF:
        print(i-1)
        exit(0)
print(N)



### FIXED CODE ###

import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF=10 ** 10
N = int(input())
XL = [list(map(int,input().split())) for _ in range(N)]
XLs =sorted([ [xl[0]+xl[1],xl[0]-xl[1]] for xl in XL ])
# print(N,XL,XLs)

t = -INF 
n = 0

for xl in XLs:
    if t <= xl[1]:
        t = xl[0]
        n = n + 1
print(n)