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

import sys
sys.setrecursionlimit(10**6)
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

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

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res

    return 

dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[x] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
    return
dfs2(0,-1)
for i in ans:
    print(i)

### FIXED CODE ###


import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return (fact[n]*finv[r])%mod*finv[n-r]%mod

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

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res

    return 

dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[x] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
    return
dfs2(0,-1)
for i in ans:
    print(i)
### BUGGY CODE ###

n = int(input())
mod = 10**9+7
num = [ int(v) for v in input().split() ]
bits = [ 0 for i in range(100) ]
num_bin_len = []

for i in num:
    t = bin(i)[2:][::-1]
    num_bin_len.append(len(t))
    for j, v in enumerate(t):
        bits[j] += int(v)

binmax = max(num_bin_len)+1

pow_2_list = []
q = 1
for i in range(100):
    pow_2_list.append(q)
    q *= 2
    q %= mod


ans = 0
for i, v in enumerate(bits[:binmax]):
    ans += v * (n-v)  * pow_2_list[i] 
print(ans % mod)

### FIXED CODE ###

n = int(input())
mod = 10**9+7
num = [ int(v) for v in input().split() ]
bits = [ 0 for i in range(100) ]

for i in num:
    j = 0
    while i > 0:
        if i % 2 == 1:
            bits[j] += 1
        i //= 2
        j += 1


binmax = 0
for i in range(100):
    if bits[i] > 0:
        binmax = i
binmax += 2


pow_2_list = []
q = 1
for i in range(100):
    pow_2_list.append(q)
    q *= 2
    q %= mod


ans = 0
for i, v in enumerate(bits[:binmax]):
    ans += v * (n-v)  * pow_2_list[i] 
print(ans % mod)
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
cmb = [0]*N
cmb[K-1] = 1
for i in range(K, N):
    cmb[i] = cmb[i-1]*i//(i - K + 1)

for i in range(N):
    fac = (cmb[i] - cmb[N-i-1])%(10**9+7)
    num = (fac*a[i])%(10**9+7)
    ans += num
    ans = ans%(10**9+7)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7
ans = 0
cmb = [0]*N
x = [0]*N
cmb[K-1] = 1
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
for i in range(1,N-K+1):
    x[i] = Pow(i, mod-2)
    
for i in range(K, N):
    cmb[i] = cmb[i-1]*i%mod*x[i-K+1]%mod
for i in range(N):
    fac = cmb[i] - cmb[N-i-1]
    num = fac*a[i]%mod
    ans += num
    ans = ans%(10**9+7)
print(ans)
### BUGGY CODE ###

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

total=0
for i in range(N-1):
    for j in range(i+1,N):
        total+=A[i]*A[j]
        total%=(1000000007)
print(total)


### FIXED CODE ###

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

mod = 10 ** 9 + 7

sum_a=0
for i in A:
    sum_a+=i
    sum_a%=mod

total=0
for i in range(N - 1):
    sum_a -= A[i]
    total+=A[i]*(sum_a)
    total%=mod
print(total)
### BUGGY CODE ###

MOD = 10**9 + 7
n, m = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
t = [int(item) for item in input().split()]

dp = [[0] * (n+1) for _ in range(m+1)]
for i, tt in enumerate(t):
    val = 0 
    for j, ss in enumerate(s):
        # Update Partial
        if ss == tt:
            val += dp[i][j] + 1
        # Keep prev
        dp[i+1][j+1] += dp[i][j+1] + val
        dp[i+1][j+1] %= MOD 
print((dp[m][n]+1) % MOD)


### FIXED CODE ###

MOD = 10**9 + 7
n, m = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
t = [int(item) for item in input().split()]

dp = [[0] * (n+1) for _ in range(m+1)]
for i, tt in enumerate(t):
    val = 0 
    for j, ss in enumerate(s):
        # Update Partial
        if ss == tt:
            val += dp[i][j] + 1
            val %= MOD
        # Keep prev
        dp[i+1][j+1] += dp[i][j+1] + val
        dp[i+1][j+1] %= MOD 
print((dp[m][n]+1) % MOD)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
H,N = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
mem = [0] * H
def dp(rem):
    global mem
    if rem <= 0:
        return 0
    elif mem[rem-1]:
        return mem[rem-1]
    else:
        a = min([dp(rem-AB[i][0]) + AB[i][1] for i in range(N)])
        mem[rem-1] = a
        return a
print(dp(H))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
H,N = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
mem = [0] * H
def dp(rem):
    global mem
    if rem <= 0:
        return 0
    elif mem[rem-1]:
        return mem[rem-1]
    else:
        a = min([dp(rem-AB[i][0]) + AB[i][1] for i in range(N)])
        mem[rem-1] = a
        return a
print(dp(H))
### BUGGY CODE ###

S = input()
T = input()
for i in range(0, len(S)-1):
  for j in range(i+1, len(S)):
    if (S[i]==S[j]) and (T[i]!=T[j]):
      print("No")
      break
    elif (S[i]!=S[j]) and (T[i]==T[j]):
      print("No")
      break
  else:
    continue
  break
else:
  print("Yes")

### FIXED CODE ###

S = input()
T = input()

SS = [s for s in S]
SS_set = list(set(SS))
CS = []
for c in SS_set:
  C_idx_in_S = [i for i, x in enumerate(SS) if x==c]
  if len(C_idx_in_S) > 1:
    CS.append(C_idx_in_S)

TT = [t for t in T]
TT_set = list(set(TT))
CT = []
for c in TT_set:
  C_idx_in_T = [i for i, x in enumerate(TT) if x==c]
  if len(C_idx_in_T) > 1:
    CT.append(C_idx_in_T)

if len(CS) == len(CT):
  for i in CS:
    if i in CT:
      continue
    else:
      print("No")
      break
  else:
    print("Yes")
else:
  print("No")
### BUGGY CODE ###

from time import sleep

x = int(input())
a = int(input())
b = int(input())

ans = (x - a) % b

sleep(x * 0.001)

print(ans)

### FIXED CODE ###

from time import sleep

x = int(input())
a = int(input())
b = int(input())

ans = (x - a) % b

sleep(0)

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

from collections import Counter

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

count_a = Counter(A)

for i in range(N):
    ans = 0
    count_a[A[i]] -= 1
    for a in count_a.values():
        if a > 1:
            ans += int(a * (a-1) / 2)
    print(ans)
    count_a[A[i]] += 1

### FIXED CODE ###

from collections import Counter

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

count_a = Counter(A)
ans_list = [0] * (N+1)
for k, v in count_a.items():
    ans_list[k] = int(v * (v-1) / 2)

all_sum = sum(ans_list)
for i in range(N):
    print(all_sum - count_a[A[i]] + 1)
### BUGGY CODE ###

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

b = sorted(a,reverse=True)

def binary_search(x):
    l,r = 0,n-1
    while l+1<r:
        i = (l+r)//2
        if b[i] > x:
            l = i
        else:
            r = i
    if abs(b[l]-x)>=abs(b[l+1]-x):
        l += 1
    return b[l]

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(1,r+1):
        ret *= (n+1-i)
        ret /= i
    return int(ret)

ans = ""
m = 0
for c in b[:-1]:
    if m > c**(c//2):
        break
    r = binary_search(c/2)
    comb_c_r = comb(c,r)
    if m < comb_c_r:
        m = comb_c_r
        ans = str(c)+" "+str(r)
print(ans)

### FIXED CODE ###

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

b = sorted(a,reverse=True)

def binary_search(x):
    l,r = 0,n-1
    while l+1<r:
        i = (l+r)//2
        if b[i] > x:
            l = i
        else:
            r = i
    if abs(b[l]-x)>=abs(b[l+1]-x):
        l += 1
    return b[l]

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(1,r+1):
        ret *= (n+1-i)
        ret /= i
    return int(ret)

ans = ""
m = 0
for c in b[:1]:
    r = binary_search(c/2)
    #comb_c_r = comb(c,r)
    #if m < comb_c_r:
        #m = comb_c_r
    ans = str(c)+" "+str(r)
print(ans)
### BUGGY CODE ###

N = int(input())
P = [0]
P.extend(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 1

for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = dp[i-1][j-1] * P[i] + dp[i-1][j] * (1-P[i])

print(dp[-1][N//2+1])


### FIXED CODE ###

N = int(input())
P = [0]
P.extend(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 1

for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = dp[i-1][j-1] * P[i] + dp[i-1][j] * (1-P[i])

print(dp[-1][N//2+1])
### BUGGY CODE ###

n,m,k = map(int,input().split())
A = [int(p) for p in input().split()]
B = [int(p) for p in input().split()]
a,b = [0],[0]

a_apnd = a.append
b_apnd = b.append
for i in range(n):
  a_apnd(a[i]+A[i])
for i in range(m):
  b_apnd(b[i]+B[i])

count = 0
for i in range(n+1):
  res = k-a[i]
  if res<0:
    break
  if res<b[1]:
    count = max(count,i)
    continue
  for t in range(m,-1,-1):
    if b[t] <= res:
      break
  count = max(count,i+t)

print(count)

### FIXED CODE ###

n,m,k = map(int,input().split())
A = [int(p) for p in input().split()]
B = [int(p) for p in input().split()]
a,b = [0],[0]

a_apnd = a.append
b_apnd = b.append
for i in range(n):
  a_apnd(a[i]+A[i])
for i in range(m):
  b_apnd(b[i]+B[i])

count = 0
t = m
for i in range(n+1):
  if k<a[i]:
    break
  while b[t] > k-a[i]:
    t -= 1
  count = max(count,i+t)

print(count)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

f = [1, 1]
for i in range(2, N+1):
    f.append(f[i-1] * i)

fk = pow(f[K-1], mod - 2, mod)

total = 0

for i in range(N - K + 1):
    p = N - i - 1
    q = K - 1

    c = (f[p] * fk * pow(f[p-q], mod-2, mod)) % mod
    total += c * (A[-1 - i] - A[i])
    total %= mod

print(total)


### FIXED CODE ###

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

mod = 10 ** 9 + 7

f = [i for i in range(N+1)]
for i in range(2, N+1):
    f[i] *= f[i-1]
    f[i] %= mod
f[0] = 1

q = K - 1
fk = pow(f[q], mod - 2, mod)

total = 0

for i in range(N - K + 1):
    p = N - i - 1

    c = (f[p] * fk * pow(f[p-q], mod-2, mod)) % mod
    total += c * (A[-1 - i] - A[i])
    total %= mod

print(total)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
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()))

l1=sorted([i+j for i in a for j in b],reverse=True)[:k]
l2=[i+j for i in l1 for j in c]
l2.sort(reverse=True)
for i in l2[:k]:
  print(i)


### FIXED CODE ###

import sys
input=sys.stdin.readline
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)
l1=sorted([i+j for i in a for j in b],reverse=True)[:k]
l2=sorted([i+j for i in l1 for j in c],reverse=True)[:k]
for i in l2:
  print(i)
### BUGGY CODE ###

s = input()
q = int(input())
flag = 0b0
for i in range(q) :
    t = input()
    if len(t) == 5 :
        if (int(t[2]) - flag) == 1 :
            s = t[4] + s
        else :
            s = s + t[4]
    else :
        flag ^= 1
if flag == 0 :
    print(s)
else :
    print(s[::-1])

### FIXED CODE ###

right = input()
Q = int(input())
flag = 0b1
left = ""
for i in range(Q):
    q = input()
    if q == "1":
        flag ^= 1
        continue
    m,f,c = q.split(" ")
    f = int(f)
    left += c*(1-flag)*(f-1)
    right += c*flag*(f-1)
    left += c*flag*(2-f)
    right += c*(1-flag)*(2-f)
if flag == 1:
    print(left[::-1]+right)
else:
    print(right[::-1]+left)
### BUGGY CODE ###

import math
k=int(input())
list=[]
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      list.append(math.gcd(math.gcd(a,b),c))
print(sum(list))

### FIXED CODE ###

import math
k=int(input())
list=[]
for a in range(1,k+1):
  for b in range(1,k+1):
    t=math.gcd(a,b)
    for c in range(1,k+1):
      list.append(math.gcd(t,c))
print(sum(list))
### BUGGY CODE ###

n,m=map(int,input().split())
r=[[] for i in range(n+1)]
#r=[]*(n+1)
for i in range(m):
    ai,bi=map(int,input().split())
    if not bi in r[ai]:
        r[ai].append(bi)
        r[bi].append(ai)
yn=""
for i in range(2,n):
    if (i in r[1]) and (i in r[n]):
        print("POSSIBLE")
        yn="POSSIBLE"
        break
if yn=="":
    print("IMPOSSIBLE")

### FIXED CODE ###


n,m=map(int,input().split())
a1=set()
an=set()
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        a1.add(bi)
    elif bi==n:
        an.add(ai)

if len(a1&an)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

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

ans = 10 ** 12
for i in range(N):
  d = 0
  for j in range(N):
    a = abs(A[i]-A[j])
    d += min(a, K-a)
  ans = min(ans, d)
print (ans)


### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
ans = min(A[-1]-A[0],K-(A[-1]-A[0]))
for i in range(N-1):
  ans = max(ans,A[i+1]-A[i])
print (K-ans)
### BUGGY CODE ###

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

count = 0
for i in range(a, b + 1):
  if i % x == 0:
    count += 1

print(count)


### FIXED CODE ###

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

count = b // x - (a - 1) // x
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*(m+1) for _ in range(n+1)]
sum=[[0]*(m+1) for _ in range(n+1)]
mod=10**9+7
ans=0
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=(sum[i][j]+1)%mod
    else:
      dp[i+1][j+1]=0
    sum[i+1][j+1]=(sum[i][j+1]+sum[i+1][j]-sum[i][j]+dp[i+1][j+1])%mod
    ans+=dp[i+1][j+1]
    ans%=mod
print((ans+1)%mod)

### FIXED CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*m for _ in range(n)]
sum=[[0]*m for _ in range(n)]
mod=10**9+7
for i in range(n):
  if s[i]==t[0]:
    dp[i][0]=1
  else:
    dp[i][0]=0
for i in range(m):
  if t[i]==s[0]:
    dp[0][i]=1
  else:
    dp[0][i]=0
sum[0][0]=dp[0][0]
for i in range(1,n):
  sum[i][0]=sum[i-1][0]+dp[i][0]
for i in range(1,m):
  sum[0][i]=sum[0][i-1]+dp[0][i]
for i in range(1,n):
  for j in range(1,m):
    if s[i]==t[j]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:
      dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
ans=0
for i in range(n):
  for j in range(m):
    ans+=dp[i][j]
    ans=ans%mod
print((ans+1)%mod)
### BUGGY CODE ###

N = int(input())
x = []
y = []
h = []
for i in range(N):
    x_i, y_i, h_i = map(int, input().split())
    x.append(x_i)
    y.append(y_i)
    h.append(h_i)

#i:情報番号 j:求めるx座標 k:求めるy座標 l:求める高さ
for j in range(101):
    for k in range(101):
        for l in range(h[0] - 200, h[0] + 200):
            flag = 1
            for i in range(N):
                h_i_test = max(l - abs(x[i] - j) - abs(y[i] - k), 0)
                if h_i_test != h[i]:
                    flag = 0
            if flag == 1:
                print(str(j)+ " " + str(k) + " " + str(l))


### FIXED CODE ###

N = int(input())
x = []
y = []
h = []
for i in range(N):
    x_i, y_i, h_i = map(int, input().split())
    x.append(x_i)
    y.append(y_i)
    h.append(h_i)

#i:情報番号 j:求めるx座標 k:求めるy座標 l:求める高さ
for j in range(101):
    for k in range(101):
        for l in range(h[0], h[0] + 200):
            flag = 1
            for i in range(N):
                h_i_test = max(l - abs(x[i] - j) - abs(y[i] - k), 0)
                if h_i_test != h[i]:
                    flag = 0
                    break
            if flag == 1:
                print(str(j)+ " " + str(k) + " " + str(l))
                break
        if flag == 1:
            break
    if flag == 1:
        break
### BUGGY CODE ###

S =list(input())
L =list(map(int,S))

n = 0
X = 0
while X<1:
	K = len(L)-1
	for i in range(K):
		if L[i]+L[i+1]==1:
			L.pop(i)
			L.pop(i)
			n=n+1
			break
		elif i == K-1:
			X=1

print(n*2)

### FIXED CODE ###

S =list(input())
L =list(map(int,S))

print(min(L.count(0),L.count(1))*2)
### BUGGY CODE ###

inputs=lambda:map(int,raw_input().split())
n, m = inputs()
es = [inputs() for i in xrange(m)]
es.sort(key=lambda x:x[-1])
parent = range(n+1)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
su = 0
g = [[] for i in xrange(n+1)]
for a, b, c in es:
    if root(a) != root(b):
        unite(a, b)
        su += c
        g[a].append((b, c))
        g[b].append((a, c))

import sys
sys.setrecursionlimit(100000)
dic = {}
def dfs(s, v, prev, cost):
    dic[s,v] = cost
    for e, c in g[v]:
        if prev != e:
            dfs(s, e, v, max(cost, c))
for i in xrange(n):
    dfs(i+1, i+1, -1, 0)
for i in xrange(input()):
    s, t = inputs()
    print su-dic[s,t]


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b, c = map(int, input().split())
    E.append((c, a-1, b-1))
E.sort()

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

L = 2*N-1
G = [[]] * L
C = [0]*L
*lb, = range(N)
cur = N

s = 0
for c, a, b in E:
    pa = root(a); pb = root(b)
    if pa == pb:
        continue
    s += c
    chds = [lb[pa], lb[pb]]
    if pa < pb:
        p[pb] = pa
        lb[pa] = cur
    else:
        p[pa] = pb
        lb[pb] = cur
    C[cur] = c
    G[cur] = chds
    cur += 1

H = [0]*L
prv = [-1]*L
def dfs(v):
    s = 1; heavy = -1; m = 0
    for w in G[v]:
        prv[w] = v
        c = dfs(w)
        if m < c:
            heavy = w
            m = c
        s += c
    H[v] = heavy
    return s
dfs(L-1)

SS = []
D = []
LB = [0]*L
I = [0]*L
que = deque([(L-1, 0)])
while que:
    v, d = que.popleft()
    S = []
    k = len(SS)
    while v != -1:
        I[v] = len(S)
        S.append(v)
        LB[v] = k
        h = H[v]
        for w in G[v]:
            if h == w:
                continue
            que.append((w, d+1))
        v = h
    SS.append(S)
    D.append(d)


def query(u, v):
    lu = LB[u]; lv = LB[v]
    dd = D[lv] - D[lu]
    if dd < 0:
        lu, lv = lv, lu
        v, u = u, v
        dd = -dd

    for _ in range(dd):
        v = prv[SS[lv][0]]
        lv = LB[v]

    while lu != lv:
        u = prv[SS[lu][0]]
        lu = LB[u]

        v = prv[SS[lv][0]]
        lv = LB[v]

    return u if I[u] < I[v] else v


def gen():
    Q = int(input())
    for i in range(Q):
        u, v = map(int, input().split())
        w = query(u-1, v-1)
        yield "%d\n" % (s - C[w])
ans = list(gen())
sys.stdout.writelines(ans)
### BUGGY CODE ###

#
import sys
import math
import numpy as np
import itertools
# いくつか入力
n,t = (int(i) for i in input().split())  

# n行の複数列ある数値を二次元配列へ。x[n][?]
ab = [[int(i) for i in input().split()] for i in range(n)]
# 0:weight 1:value

ab = sorted(ab,key=lambda x: x[1])

dp = [[0 for i in range(t)] for j in range(n+1)]
dp2 = [[0 for i in range(t)] for j in range(n+1)]


for i in range(n):
    for w in range(t):
        if w >= ab[i][0] :
            dp[i+1][w] = max(dp[i][w-ab[i][0]] + ab[i][1], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
        if w >= ab[i][0] :
            dp2[i+1][w] = max(dp2[i][w-ab[i][0]] + ab[i][1],dp[i][w] + ab[i][1], dp[i][w])
        else:
            dp2[i+1][w] = max(dp[i][w] + ab[i][1], dp[i][w])

answer =0
for i in range(n+1):
    for w in range(t):
        answer = max(answer, dp2[i][w])
print(answer)

#print(dp2)


### FIXED CODE ###

#
import sys
import math
import numpy as np
import itertools
# いくつか入力
n,t = (int(i) for i in input().split())

# n行の複数列ある数値を二次元配列へ。x[n][?]
ab = [[int(i) for i in input().split()] for i in range(n)]
# 0:weight 1:value

ab = sorted(ab,key=lambda x: x[1])

dp = np.zeros((n+1,t),int)
dp2 = np.zeros((n+1,t),int)

for i in range(n):
    w = ab[i][0]
    dp[i+1][w:] = np.fmax(dp[i][:-w] + ab[i][1], dp[i][w:])
    dp2[i+1][w:] = np.fmax(dp2[i][:-w] + ab[i][1],dp[i][w:] + ab[i][1], dp2[i][w:])
    dp[i+1][:w] = dp[i][:w]
    dp2[i+1][:w] = np.fmax(dp[i][:w] + ab[i][1], dp2[i][:w])

answer = np.amax(dp2)
print(answer)
### BUGGY CODE ###

n = input()
for i in range(n):
  x = i
  if x%3==0:
    print ' %d' % x
  while x<=n:
    if x%10==3:
      print ' %d' % x
    else:
      x /= 10

### FIXED CODE ###

import sys
n = input()
for i in range(1,n+1):
  x = i
  if x%3==0:
    sys.stdout.write(' %d' % i)
    continue
  while x<=n:
    if x%10==3:
      sys.stdout.write(' %d' % i)
      break
    else:
      x /= 10
      if x==0:
        break
sys.stdout.write('\n')
### BUGGY CODE ###

N = int(input())
ixy=[]
for i in range(N):
  x, y = map(int,input().split())
  ixy+=[[i,x,y]]
costs = [[] for i in range(N)]

ixy.sort(key=lambda x:x[1])
for j in range(N-1):
  costs[ixy[j][0]] += [[ixy[j+1][0],abs(ixy[j][1]-ixy[j+1][1])]]
  costs[ixy[j+1][0]] += [[ixy[j][0],abs(ixy[j][1]-ixy[j+1][1])]]
ixy.sort(key=lambda y:y[2])
for j in range(N-1):
  costs[ixy[j][0]] += [[ixy[j+1][0],abs(ixy[j][2]-ixy[j+1][2])]]
  costs[ixy[j+1][0]] += [[ixy[j][0],abs(ixy[j][2]-ixy[j+1][2])]]

import heapq
pq = []
heapq.heappush(pq,[0,0])

visited = [0]*N
ans = 0
while pq:
  cost, v = heapq.heappop(pq)

  if visited[v]: continue
  
  ans += cost
  visited[v]=1
  
  for u,c in costs[v]:
    if not visited[u]:
      heapq.heappush(pq, [c,u])

print(ans)

### FIXED CODE ###

N = int(input())
ixy=[]
for i in range(N):
  x, y = map(int,input().split())
  ixy+=[[i,x,y]]
costs = [[] for i in range(N)]

ixy.sort(key=lambda x:x[1])
for j in range(N-1):
  costs[ixy[j][0]] += [(ixy[j+1][0],abs(ixy[j][1]-ixy[j+1][1]))]
  costs[ixy[j+1][0]] += [(ixy[j][0],abs(ixy[j][1]-ixy[j+1][1]))]
ixy.sort(key=lambda y:y[2])
for j in range(N-1):
  costs[ixy[j][0]] += [(ixy[j+1][0],abs(ixy[j][2]-ixy[j+1][2]))]
  costs[ixy[j+1][0]] += [(ixy[j][0],abs(ixy[j][2]-ixy[j+1][2]))]

import heapq
pq = []
heapq.heappush(pq, (0,0))

visited = [0]*N
ans = 0
while pq:
  cost, v = heapq.heappop(pq)

  if visited[v]: continue
  
  ans += cost
  visited[v]=1
  
  for u,c in costs[v]:
    if not visited[u]:
      heapq.heappush(pq, (c,u))

print(ans)