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

def main():
    """
    """
    N, M, Q = map(int, input().split())
    L, R = zip(*(
        map(int, input().split())
        for _ in range(M)
    ))
    p, q = zip(*(
        map(int, input().split())
        for _ in range(Q)
    ))

    # answers = f(N, M, Q, L, R, p, q)
    # experiment(N, M, Q, L, R, p, q)
    # answers = TLE(N, M, Q, L, R, p, q)
    answers = editorial(N, M, Q, L, R, p, q)
    for ans in answers:
        print(ans)


def editorial(N, M, Q, L, R, p, q):
    """
    ２次元累積和のライブラリを持っておくとよいらしい
        確かに実装ミスりそう

    """
    # LRの組合せ, N<=500より間に合う
    t1 = [[0] * (N+1) for _ in range(N+1)]
    t2 = [[0] * (N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        t1[l][r] += 1

    # Lごとの累積和
    for l in range(1, N+1):
        for r in range(1, N+1):
            t2[l][r] = t2[l][r-1] + t1[l][r]

    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for l in range(_p, _q+1):
            ans += t2[l][_q] - t2[l][_p-1]

        answers.append(ans)

    return answers


def TLE(N, M, Q, L, R, p, q):
    """
    10^5 * 10^5
    """
    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for left, right in zip(L, R):
            if _p <= left and right <= _q:
                ans += 1

        answers.append(ans)

    return answers


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    """
    """
    N, M, Q = map(int, input().split())
    L, R = zip(*(
        map(int, input().split())
        for _ in range(M)
    ))
    p, q = zip(*(
        map(int, input().split())
        for _ in range(Q)
    ))

    # answers = f(N, M, Q, L, R, p, q)
    # experiment(N, M, Q, L, R, p, q)
    # answers = TLE(N, M, Q, L, R, p, q)
    answers = editorial(N, M, Q, L, R, p, q)
    for ans in answers:
        print(ans)


def editorial(N, M, Q, L, R, p, q):
    """
    ２次元累積和のライブラリを持っておくとよいらしい
        確かに実装ミスりそう

    """
    # LRの組合せ, N<=500より間に合う
    t1 = [[0] * (N+1) for _ in range(N+1)]
    t2 = [[0] * (N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        t1[l][r] += 1

    # Lごとの累積和
    for l in range(1, N+1):
        for r in range(1, N+1):
            t2[l][r] = t2[l][r-1] + t1[l][r]

    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for l in range(_p, _q+1):
            ans += t2[l][_q] - t2[l][_p-1]

        answers.append(ans)

    return answers


def TLE(N, M, Q, L, R, p, q):
    """
    10^5 * 10^5
    """
    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for left, right in zip(L, R):
            if _p <= left and right <= _q:
                ans += 1

        answers.append(ans)

    return answers


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

import collections

N = int(input())
texts = []
for i in range(N):
    texts.append((input()))
    

counters = []
count = 0
for text in texts:
    c = collections.Counter(text)
    for t in counters:
        if t == c:
            count += 1
    counters.append(c)
print(count)

### FIXED CODE ###

N = int(input())
texts = []
for i in range(N):
    texts.append((input()))

import collections
counters = []
count = 0
for text in texts:
    text_list = list(text)
    text_list.sort()
    text = "".join(text_list) 
    c = collections.Counter(text)
    counters.append(c)



ccccc = []
anss = []
for ccc in counters:
    ccc = str(ccc)
    ccccc.append(ccc)
    

dd = collections.Counter(ccccc)
for v in dd.values():
    ans = v * (v-1) / 2
    anss.append(ans)
    
print(int(sum(anss)))
### BUGGY CODE ###

A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]

T = [int(input()) for _ in range(B)]

from bisect import bisect_left

for _ in range(Q):
    ans = 10**12
    x = int(input())
    idxs = bisect_left(S,x)
    idxt = bisect_left(T,x)

    if idxs < A and idxt < B:
        ans = min(ans, max(S[idxs],T[idxt])-x)
    if 0 <= idxs-1 and 0 <= idxt-1:
        ans = min(ans, x-min(S[idxs-1],T[idxt-1]))
    if idxs < A and 0 <= idxt-1:
        ans = min(ans, S[idxs]-T[idxt-1] + min(S[idxs]-x, x-T[idxt-1]))
    if idxt < B and 0 <= idxs-1:
        ans = min(ans, T[idxt]-S[idxs-1] + min(T[idxt]-x, x-S[idxs-1]))
    print(ans)


### FIXED CODE ###

A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]

T = [int(input()) for _ in range(B)]

from bisect import bisect_left

for _ in range(Q):
    ans = 10**12
    x = int(input())
    idxs = bisect_left(S,x)
    idxt = bisect_left(T,x)

    if idxs < A and idxt < B:
        ans = min(ans, max(S[idxs],T[idxt])-x)
    if 0 <= idxs-1 and 0 <= idxt-1:
        ans = min(ans, x-min(S[idxs-1],T[idxt-1]))
    if idxs < A and 0 <= idxt-1:
        ans = min(ans, S[idxs]-T[idxt-1] + min(S[idxs]-x, x-T[idxt-1]))
    if idxt < B and 0 <= idxs-1:
        ans = min(ans, T[idxt]-S[idxs-1] + min(T[idxt]-x, x-S[idxs-1]))
    print(ans)
### BUGGY CODE ###

a, b, k = map(int, input().split(' '))
ab = [i for i in range(a, b+1)]
del ab[k:-k]
abp = [print(i) for i in ab]


### FIXED CODE ###

a, b, k = map(int, input().split(' '))
if b - a + 1 < 2 * k:
  for i in range(a, b + 1):
    print(i) 
else:
  for i in range(a, a + k):
    print(i)
  for i in range(b - k + 1, b + 1):
    print(i)
### BUGGY CODE ###

H,W,D=map(int,input().split())

A=list()
for h in range(H):
  for w,a in enumerate(map(int,input().split())):
    A.append([a,h,w])

A=sorted(A, key=lambda x:x[0])

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  t,i=0,~-l  
  for j in range((r-l)//D):
    t+=abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
    i+=D
  print(t)


### FIXED CODE ###

H,W,D=map(int,input().split())

def main():
  A=list()
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A.append([a,h,w])

  A=sorted(A, key=lambda x:x[0])

  B=[0]*(H*W)
  for i in range(D):
    while i+D<W*H:
      B[i+D]=B[i]+abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
      i+=D

  for q in range(int(input())):
    l,r=map(int,input().split())
    print(B[~-r]-B[~-l])

main()
### BUGGY CODE ###

n = int(input())
al = list(map(int,input().split()))
al_p = 1

for i in range(n):
    al_p *= al[i]
print(['-1',al_p][al_p <= 10**18])
    

### FIXED CODE ###


def main():
    n = int(input())
    al = list(map(int,input().split()))
    al_p = 1

    if 0 in al:
        print(0)
        return

    for i in range(n):
        al_p *= al[i]
        if al_p > 10**18:
            print(-1)
            return
        
    print(al_p)

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
else:
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = -1
    print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
else:
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
A = deque([int(x) for x in input().split()])

while M > 0:
    a = max(A)
    A.remove(a)
    A.append(a//2)
    M -= 1

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)

for _ in range(M):
    tmin = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmin//2))

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

def q3():
    N = int(input())
    A = []
    for n in range(N):
        A.append(int(input()))

    for n in range(N):
        tmp = A.copy()
        tmp.pop(n)
        print(max(tmp))

        
if __name__ == '__main__':
    q3()

### FIXED CODE ###

def q3():
    """ C - Exception Handling """
    N = int(input())
    A = []
    for n in range(N):
        A.append(int(input()))

    max_A = max(A)
    second_A = sorted(A, reverse=True)[1]
    for n in range(N):
        if A[n] == max_A:
            print(second_A)
        else:
            print(max_A)

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

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

a = [i%100 if i >100 else i for i in a]
pair = n*(n - 1)/2
not_4 = 0
ans = 'Yes'
num = len(a)
for i in range(num):
  for j in range(num):
    
    if i != j and a[i]*a[j]%4 != 0:
      not_4 += 1
      
      
    if not_4 >= pair:
      ans = 'No'
      break
    
print(ans)

### FIXED CODE ###

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

four = 0
two = 0
one = 0
for i in a:
  if i%4 == 0:
    four += 1
  elif i%2 == 0 and i%4 != 0:
    two += 1
  elif i%2 != 0:
    one += 1

if four >= one or four + 1 >= two//2 + two%2 + one or n == two:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[False for i in range(k+1)]
for i in range(k+1):
    for j in range(n):
        if i-a[j]>=0:
            dp[i]|=(dp[i-a[j]]^(True))
if dp[k]:
    print("First")
else:
    print("Second")

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[False for i in range(k+1)]
for i in range(k+1):
    for j in range(n):
        if i-a[j]>=0:
            dp[i]|=(dp[i-a[j]]^(True))
if dp[k]:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

n = int(input())
s = []
ans = 0
for _ in range(n):
    tmp = sorted(input())
    ans += s.count(tmp)
    s.append(tmp)
print(ans)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0
for i in range(n):
    s = str(sorted(input()))
    if s in d:
        ans+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(ans)
### BUGGY CODE ###

# coding:utf-8


INF = float('inf')


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


N, X = inpl()
A = inpl()
B = [0]
for a in A:
    B.append(B[-1] + a)

ans = INF
for k in range(1, N + 1):
    tmp = 0
    i = 0
    cur = N
    while True:
        e = 5 if i == 0 else 2 * i + 3
        tmp += e * (B[cur] - B[max(cur - k, 0)])
        if cur - k <= 0:
            break
        i += 1
        cur -= k

    ans = min(ans, tmp + (N + k) * X)

print(ans)

### FIXED CODE ###

# coding:utf-8


INF = float('inf')


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


N, X = inpl()
A = inpl()
B = [0]
for a in A:
    B.append(B[-1] + a)

ans = INF
for k in range(1, N + 1):
    e = 5
    cur = N - k
    tmp = e * (B[N] - B[cur]) + (N + k) * X
    cur -= k
    while True:
        tmp += e * (B[cur + k] - B[max(cur, 0)])
        if cur <= 0:
            break
        e += 2
        cur -= k

    ans = min(ans, tmp)

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

def main():
    MOD = 10 ** 9 + 7
    N, M = list(map(int, input().split(' ')))
    S = list(map(int, input().split(' ')))
    T = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    sdp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    for n, s in enumerate(S):
        for m, t in enumerate(T):
            sdp_val = sdp[n][m]
            new_dp_val = (sdp_val + 1) if s == t else 0
            dp[n + 1][m + 1] = new_dp_val % MOD
            sdp[n + 1][m + 1] = (sdp[n][m + 1] + sdp[n + 1][m] - sdp_val + new_dp_val) % MOD
    print((sdp[N][M] + 1) % MOD)  # 1: an empty sequence


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 10 ** 9 + 7
    N, M = list(map(int, input().split(' ')))
    S = list(map(int, input().split(' ')))
    T = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    sdp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    for n, s in enumerate(S):
        for m, t in enumerate(T):
            sdp_val = sdp[n][m]
            new_dp_val = (sdp_val + 1) if s == t else 0
            dp[n + 1][m + 1] = new_dp_val % MOD
            sdp[n + 1][m + 1] = (sdp[n][m + 1] + sdp[n + 1][m] - sdp_val + new_dp_val) % MOD
    print((sdp[N][M] + 1) % MOD)  # 1: an empty sequence


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

from math import factorial
S=list(map(int,input()))
S.reverse()
# print(S)
count2019 = [0]*2019
count2019[0]=1
mod2019 = 0
for i in range(len(S)):
    mod2019 =(mod2019+S[i]*10**i)%2019
    count2019[mod2019] +=1

ans =0
for i in count2019:
    if(i>=2):
        ans += factorial(i) // factorial(i) // factorial(i - 2)
print(ans)
# print(count2019)

### FIXED CODE ###

s = list(input())
# s = list(str(10**200000))
n = len(s)
ans = 0
s.reverse()
# print(s)
x = 1
tot = 0
count = [0]*2019
for i in range(n):
    count[tot]+=1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    ans += count[tot]
    x = x*10%2019
print(ans)
### BUGGY CODE ###


x = input().split()
n = int(x[0]) # n == 比較文字列の長さ
q = int(x[1]) # q == 検討する回数
s = input()
def sc():
    global s
    global n
    global q
    maxx = 0
    count = 0
    com = [int(s)-1 for s in input().split()]
    if "A" not in  s[com[0]:com[1]]:
        print(0)
        return None
    if "C" not in s[com[0] +1:com[1] + 1]:
        print(0)
        return None
    for i in range(com[0],com[1]): # i == 先頭の文字
        if (s[i] == "A") and(s[i+1] == "C"):
            count += 1      
    print(count)

for i in range(q):
    sc()


### FIXED CODE ###


x = input().split()
n = int(x[0]) # n == 比較文字列の長さ
q = int(x[1]) # q == 検討する回数
s = input()

        
t = [0] * n
if s[0] == "A":
    t[0] = 1
    
for i in range(0,n-1):
    if s[i:i+2] == "AC":
        
        if (i == 0) :
            t[i] =  + 1
        else:
            t[i] = t[i-1] + 1
    else :
        if i == 0:
            t[i] = 0
        else:
            t[i] = t[i-1]



def sc():
    global t
    global s
    global n
    global q
    global idbox
    maxx = 0
    count = 0
    com = [int(s)-1 for s in input().split()]
    
    
    print(t[com[1]-1] - t[com[0]-1])
        
    

    

for i in range(q):
    
    sc()
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
  que=input().split()
  if que[0]==str(1):
    s=s[::-1]
  else:
    if que[1]==str(1):
      s=que[2]+s
    else:
      s=s+que[2]
print(s)




### FIXED CODE ###

from collections import deque
s=deque(input())
q=int(input())
cnt=0
for i in range(q):
  t=input().split()
  if t[0]=="1":
    cnt+=1
  else:
    if (int(t[1])+cnt)%2==1:
      s.appendleft(t[2])
    else:
      s.append(t[2])
      
if cnt%2==1:
  s.reverse()
print("".join(s))
### BUGGY CODE ###

def main():
    N, Q = map(int, input().split())
    S = input().rstrip()
    ac_flag = []
    for i in range(N-1):
        if S[i:i+2] == 'AC':
            ac_flag.append(1)
        else:
            ac_flag.append(0)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(sum(ac_flag[l-1:r-1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = input().rstrip()
    ac_freq = [0]
    for i in range(0, N-1):
        if S[i:i+2] == 'AC':
            ac_freq.append(ac_freq[-1] + 1)
        else:
            ac_freq.append(ac_freq[-1])
    ac_freq.append(ac_freq[-1])
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ac_freq[r-1] - ac_freq[l-1])


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

from collections import deque

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

s = [list(input()) for _ in range(h)]

yoko = [[0] * w for _ in range(h)]
#tate = [[0] * w for _ in range(h)]

q = deque([])
c = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            q.append((i, j))
            c += 1
        
        if s[i][j] == "#" or j == w-1:
            while len(q) > 0:
                x, y = q.pop()
                yoko[x][y] = c
            c = 0



m = 0

#print(yoko)

c = 0
for j in range(w):
    for i in range(h):
        if s[i][j] == ".":
            q.append((i, j))
            c += 1

        if s[i][j] == "#" or i == h-1:
            while len(q) > 0:
                x, y = q.pop()
                m = max(m, yoko[x][y] + c - 1)
            c = 0


print(m)


### FIXED CODE ###

from collections import deque

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

s = [list(input()) for _ in range(h)]

yoko = [[0] * w for _ in range(h)]
#tate = [[0] * w for _ in range(h)]

q = deque([])
c = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            q.append((i, j))
            c += 1
        
        if s[i][j] == "#" or j == w-1:
            while len(q) > 0:
                x, y = q.pop()
                yoko[x][y] = c
            c = 0



m = 0

#print(yoko)

c = 0
for j in range(w):
    for i in range(h):
        if s[i][j] == ".":
            q.append((i, j))
            c += 1

        if s[i][j] == "#" or i == h-1:
            while len(q) > 0:
                x, y = q.pop()
                m = max(m, yoko[x][y] + c - 1)
            c = 0


print(m)
### BUGGY CODE ###

import sys
n = int(input())

a = (list(map(int, input().split())))
dx = 10 ** 9 + 7

a = [i % dx for i in a if i != 0]

ans = 0
alist = []
for i in range(len(a)):
    for j in range(i+1, len(a)):
        alist.append((a[i] * a[j]) % dx)

for i in range(len(alist)):
    ans += alist[i]
    ans %= dx

ans %= dx
print(ans)


### FIXED CODE ###

n = int(input())

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

S = sum(a)

S2 = sum(map(lambda x: x * x, a ))

ans = (S * S - S2) // 2 % 1000000007
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
data = []

for i in range(N):
  tmp_a, tmp_b = map(int, input().split())
  data.append((tmp_a, tmp_b))

sorted_data = sorted(data, key=lambda x: x[0])
  
buy_count = 0
money_count = 0

while buy_count < M:
  tmp_a = sorted_data[0][0]
  tmp_b = sorted_data[0][1]

  if buy_count + tmp_b < M:
    buy_count += tmp_b
    money_count += tmp_b * tmp_a
    sorted_data.pop(0)
  else:
    while buy_count < M:
      buy_count += 1
      money_count += tmp_a
      
print(money_count)

### FIXED CODE ###

N, M = map(int, input().split())
data = []

for i in range(N):
  tmp_a, tmp_b = map(int, input().split())
  data.append((tmp_a, tmp_b))

sorted_data = sorted(data, key=lambda x: x[0])
  
buy_count = 0
money_count = 0

while buy_count < M:
  tmp_a = sorted_data[0][0]
  tmp_b = sorted_data[0][1]

  if buy_count + tmp_b < M:
    buy_count += tmp_b
    money_count += tmp_b * tmp_a
    sorted_data.pop(0)
  else:
    while buy_count < M:
      buy_count += 1
      money_count += tmp_a
      
print(money_count)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
B = []
for i in range(n):
    B.append(A[i])
    B.reverse()

text = ""
for b in B:
    text += str(b) + " "
text = text[:-1]
print(text)

### FIXED CODE ###

from collections import deque

n = int(input())
A = list(map(int, input().split()))
B = deque()
for i in range(n):
    if(i%2 == 0):
        B.append(A[i])
    if(i%2 == 1):
        B.appendleft(A[i])

if(n%2 == 1):
    B.reverse()
text = ""
for b in B:
    text += str(b) + " "
text = text[:-1]
print(text)
### BUGGY CODE ###

"""
int(input())
map(int,input().split())
list(map(int,input().split()))

"""

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append((a[i]+1)/2)
mx=0
for i in range(n-k+1):
    y=sum(b[i:i+k])
    if(y>mx):
        mx=y
print(mx)    

### FIXED CODE ###

"""
int(input())
map(int,input().split())
list(map(int,input().split()))

"""

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append((a[i]+1)/2)
c=[]
s=sum(b[0:k])
for i in range(k-1,n):
    c.append(s)
    if(i==n-1):
        break
    s=s+b[i+1]-b[i-k+1]

print(max(c))
### BUGGY CODE ###

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

if A < B:
    pass
else:
    C = A
    A = B
    B = C
for k in range(A, B):
    if abs(A-k) ==abs(B-k):
        ans = k
        break
    else:
        ans = "IMPOSSIBLE"

print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
 
if (A+B)%2==0:
  print((A+B)//2)
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self//value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

from sys import setrecursionlimit
setrecursionlimit(200200)
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N-1)]
G = [[] for _ in range(N)]
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    G[a].append((b, i))
    G[b].append((a, i))

P = [0] * N
visited = [False] * N
visited[0] = True
def dfs(x, i):
    e = 1
    for v, c in G[x]:
        if not visited[v]:
            visited[v] = True
            e += dfs(v, c)
    P[i] = e
    return e

dfs(0, -1)
ans = Fp(0)
one = Fp(1)
two = Fp(2)
for i in range(N-1):
    ans += (one-one//two**P[i])*(one-one//two**(N-P[i]))
print(ans-Fp(N)//2-two**-N+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200200)
input = sys.stdin.readline
MOD=10**9+7
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N-1)]
G = [[] for _ in range(N)]
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    G[a].append((b, i))
    G[b].append((a, i))

P = [0] * N
visited = [False] * N
visited[0] = True
def dfs(x, i):
    e = 1
    for v, c in G[x]:
        if not visited[v]:
            visited[v] = True
            e += dfs(v, c)
    P[i] = e
    return e

dfs(0, -1)
W = [1] * (N + 1)
inv_2 = pow(2, MOD-2, MOD)
for i in range(N):
    W[i+1] = W[i]*inv_2%MOD
ans = (W[N] + 1) * (N - 1) % MOD
for i in range(N-1):
    ans -= W[P[i]] + W[N-P[i]]
    ans %= MOD
print((ans - inv_2*N - W[N] + 1) % MOD)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
a = list(map(int, input().split()))
dp = []


def mincos(dp, a, i, k):
    if i == 0:
        return 0
    elif i < k:
        mincos = 10000000000
        for j in range(1, i + 1):
            b = dp[i - j] + abs(a[i] - a[i - j])
            if mincos > b:
                mincos = b
        return mincos
    else:
        mincos = 10000000000
        for j in range(1, k + 1):
            b = dp[i - j] + abs(a[i] - a[i - j])
            if mincos > b:
                mincos = b
        return mincos


for i in range(N):
    dp.append(mincos(dp, a, i, K))

print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)

for i in range(1, N):
    j = max(0, i-K)
    dp[i] = (dp[j:i] + np.abs(h[i] - h[j:i])).min()


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

n = input().split()
N = int(n[0])
Q = int(n[1])
S = input()

#import numpy as np
#tmp_list = np.zeros(N)

#for i in range(N-1):
#    if S[i] == 'A' and S[i+1] == 'C':
#        tmp_list[i] = 1

for i in range(Q):
    lr = input().split()
    l = int(lr[0])
    r = int(lr[1])
    tmp = S[l-1:r]
    tmp_num = 0
    for j in range(len(tmp)-1):
        if tmp[j] == 'A' and tmp[j+1] == 'C':
            tmp_num += 1
    print(str(tmp_num))


### FIXED CODE ###

from itertools import accumulate

N, Q = list(map(int, input().split()))
S = input()
A = [list(map(int, input().split())) for i in range(Q)]

tmp = []
for i in range(N-1):
    tmp_S  = S[i:i+2]
    if tmp_S == 'AC':
        tmp.append(1)
    else:
        tmp.append(0)

tmp2 = [0] + tmp
tmp2 = list(accumulate(tmp2))
#print(tmp2)

for j in A:
    print(tmp2[j[1]-1] - tmp2[j[0]-1])