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

import sys
sys.setrecursionlimit(10**7)
MOD = 10**9+7

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

lim = 10**6
fact = [1, 1] + [0] * (lim-1)
fact_inv = [1, 1] + [0] * (lim-1)
inv = [0, 1] + [0] * (lim-1)
for i in range(2, lim+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
def comb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact[n] * (fact_inv[m] * fact_inv[n-m] % MOD) % MOD
def icomb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact_inv[n] * (fact[m] * fact[n-m] % MOD) % MOD

dp = [1] * n
size = [0] * n

def dfs(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        dfs(nv, v)
        ns = size[nv]+1
        size[v] += ns
        dp[v] *= dp[nv] * comb(size[v], ns) % MOD
        dp[v] %= MOD

def dfs2(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        d, sz = dp[v], size[v]
        d *= pow(dp[nv], MOD-2, MOD) * icomb(sz, size[nv]+1) % MOD
        d %= MOD
        sz -= size[nv]+1

        size[nv] += sz+1
        dp[nv] *= d * comb(size[nv], sz+1) % MOD
        dp[nv] %= MOD
        dfs2(nv, v)

dfs(0, -1)
dfs2(0, -1)
print(*dp, sep="\n")


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7

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

lim = 10**5*2
fact = [1, 1] + [0] * (lim-1)
fact_inv = [1, 1] + [0] * (lim-1)
inv = [0, 1] + [0] * (lim-1)
for i in range(2, lim+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
def comb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact[n] * (fact_inv[m] * fact_inv[n-m] % MOD) % MOD
def icomb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact_inv[n] * (fact[m] * fact[n-m] % MOD) % MOD

dp = [1] * n
size = [0] * n

def dfs(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        dfs(nv, v)
        ns = size[nv]+1
        size[v] += ns
        dp[v] *= dp[nv] * comb(size[v], ns) % MOD
        dp[v] %= MOD

def dfs2(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        d, sz = dp[v], size[v]
        d *= pow(dp[nv], MOD-2, MOD) * icomb(sz, size[nv]+1) % MOD
        d %= MOD
        sz -= size[nv]+1

        size[nv] += sz+1
        dp[nv] *= d * comb(size[nv], sz+1) % MOD
        dp[nv] %= MOD
        dfs2(nv, v)

dfs(0, -1)
dfs2(0, -1)
print(*dp, sep="\n")
### BUGGY CODE ###

#!/usr/bin/env python3
# TLE解

import numpy as np

n, k = map(int, input().split())
MOD = int(1e9+7)
rem = (10*100)%MOD 
ans = 0 

# i個取るとき
for i in range(k, n+2):
    #print('i =', i)
    minimum = np.arange(i).sum()
    maximum = np.arange(n, n-i, -1).sum()
    #print('minimum =', minimum)
    #print('maximum =', maximum)
    #print(maximum-minimum+1)
    ans += (maximum-minimum+1)%MOD

print(ans%MOD)


### FIXED CODE ###

#!/usr/bin/env python3
import numpy as np

n, k = map(int, input().split())
MOD = int(1e9+7)
rem = (10*100)%MOD 
ans = 0 

for i in range(k, n+2):
    if i == k:
        minimum = np.arange(i).sum()
        maximum = np.arange(n, n-i, -1).sum()
    else:
        minimum += i-1 
        maximum += n-i+1
    ans += (maximum-minimum+1)%MOD

print(ans%MOD)
### BUGGY CODE ###

import sys
import functools
import itertools
import math
from collections import deque

def bfs(H, W, S):
    cost = [[0]*(W+2) for _ in range(H+2)]
    visited = deque([])
    unvisited = deque([(1,1)])
    cost[1][1] = 1
    while unvisited:
        now = unvisited.popleft()
        visited.append(now)
        if S[now[1]-1][now[0]] != '#' and (now[0], now[1]-1) not in visited:
            cost[now[1]-1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]-1))
        if S[now[1]+1][now[0]] != '#' and (now[0], now[1]+1) not in visited:
            if now[1]+1 == H and now[0] == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]+1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]+1))
        if S[now[1]][now[0]-1] != '#' and (now[0]-1, now[1]) not in visited:
            cost[now[1]][now[0]-1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]-1, now[1]))
        if S[now[1]][now[0]+1] != '#' and (now[0]+1, now[1]) not in visited:
            if now[1] == H and now[0]+1 == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]][now[0]+1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]+1, now[1]))
    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def bfs(H, W, S):
    visited = [[False]*(W+2) for _ in range(H+2)]
    visited[1][1] = True
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            for t1, t2 in zip([-1,+1,0,0],[0,0,-1,1]):
                dx = x + t1
                dy = y + t2
                if S[dy][dx] != '#' and not visited[dy][dx]:
                    if dy == H and dx == W:
                        return dist
                    un.append((dx,dy))
                    visited[dy][dx] = True
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.append('#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

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

def main():
  N, Q = [int(x) for x in input().split()]
  S = input()
  counts = []
  for i in range(1, len(S) + 1):
    counts.append(S[:i].count('AC'))
  for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(counts[r - 1] - counts[l - 1])


if __name__ == "__main__":
  main()


### FIXED CODE ###

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


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

#!/usr/bin/env python
import numpy as np

def main():
    N = int(input().strip())
    arr = np.zeros(N, np.int32)
    for i in range(N):
        arr[i] = int(input().strip())
    for i in range(N):
        arr2 = np.copy(arr)
        arr2[i] = 0
        print(arr2.max())

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
import numpy as np

def main():
    N = int(input().strip())
    arr = np.zeros(N, np.int32)
    for i in range(N):
        arr[i] = int(input().strip())
    arr2 = np.sort(arr)[::-1]
    max1, max2 = arr2[0], arr2[1]

    for i in range(N):
        print(max1) if arr[i] != max1 else print(max2)

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

n = int(input())

def factorization(n):
    arr = []
    ret = 1
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
            ret = ret * (cnt+1)

    if temp!=1:
        arr.append([temp, 1])
        ret = ret*2

    if arr==[]:
        arr.append([n, 1])
        ret = ret *2

    return ret


ans = 1
if n != 1:
    for i in range(2,n+1):
        ans += i * factorization(i)

print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1): #各iについて、i*(1～n//iまでの総和)を足し合わせればよい
 k=n//i
 ans+=i*(k*(k+1)//2)
print(ans)
### BUGGY CODE ###

n = int(input())
a = []

for _ in range(n):
	a.append(int(input()))
b = [0]*n

index = 0
color = 0
for _ in range(n):
	color += 1
	minimum = a[index]
	b[index] = 1
	for i in range(index+1,n):
		if b[i] == 0 and minimum < a[i]:
			b[i] = 1
			minimum = a[i]
	if 0 not in b:
		break
	index = b.index(0)

print(color)


### FIXED CODE ###

import bisect
from collections import deque

N = int(input())
a = []
for _ in range(N):
  a.append(int(input()))

LIS = deque([a[0]])
for i in range(1,N):
    if a[i] > LIS[-1]:
    	LIS[-1] = a[i]
    elif LIS[0] >= a[i]:
    	LIS.appendleft(a[i])
    else:
    	LIS[bisect.bisect_left(LIS, a[i])-1] = a[i]

print(len(LIS))
### BUGGY CODE ###

import math

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

a=max(A)
def era(n):
  prime=[]
  furui=list(range(2,n+1))
  while furui[0]<math.sqrt(n):
    prime.append(furui[0])
    furui=[i for i in furui if i%furui[0]!=0]
  return prime+furui

b=A[0]
for i in range(1,N):
  b=math.gcd(b,A[i])

if b!=1:
  print("not coprime")
  exit()

furui=era(10**6+7)
dummy=[False]*(10**6+7)
for i in range(N):
  k=A[i]
  while k!=1:
    for j in furui:
      if k%j==0 and dummy[j-1]==True:
        print("setwise coprime")
        exit()
      elif k%j==0 and dummy[j-1]==False:
        dummy[j-1]=True
      while k%j==0:
        k//=j
print("pairwise coprime")

### FIXED CODE ###

import math

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

a=max(A)
def era(n):
  prime=[]
  furui=list(range(2,n+1))
  while furui[0]<math.sqrt(n):
    prime.append(furui[0])
    furui=[i for i in furui if i%furui[0]!=0]
  return prime+furui

b=A[0]
for i in range(1,N):
  b=math.gcd(b,A[i])

if b!=1:
  print("not coprime")
  exit()

furui=era(10**6+7)
minfac=list(range(10**6+7))
for i in furui:
  for j in range(i,(10**6+7)//i):
    if minfac[i*j]==i*j:
      minfac[i*j]=i
      
dummy=[False]*(10**6+7)
for i in range(N):
  k=A[i]
  while k!=1:
    if dummy[minfac[k]]==True:
      print("setwise coprime")
      exit()
    else:
      dummy[minfac[k]]=True
      f=minfac[k]
      while k%f==0:
        k//=f
print("pairwise coprime")
### BUGGY CODE ###

import sys
import itertools
from collections import deque
from operator import itemgetter

input = sys.stdin.readline
S = input()
counter = 0

for i in range(len(S)):
    null = 0
    if '01' in S:
        S = S.replace('01', '', 1)
        counter += 1
    else:
        null +=1
    if '10' in S:
        S = S.replace('10','', 1)
        counter += 1
    else:
        null += 1
    if null == 2:
        break
print(2*counter)

### FIXED CODE ###

import sys
import itertools
from collections import deque
from operator import itemgetter

input = sys.stdin.readline
S = input()
counter = 0

A = S.count('1')
B = S.count('0')
print(2*min(A,B))
### BUGGY CODE ###

a,b=map(int,input().split())
for i in range(10000000):
  if(i//12.5==a and i//10==b):
    print(i)
  else:
    print("-1")

### FIXED CODE ###

a,b=map(int,input().split())
for i in  range(1,1200):
  if int(i*0.08)==a and int(i*0.1)==b:
    print(i)
    exit()
print(-1)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    L = int(input())
    ln = int(math.log(N, 2))
    dpl = [[0] * N for _ in range(ln+1)]
    dpr = [[0] * N for _ in range(ln+1)]
    l = 0
    r = 0
    for i in range(N):
        x = X[i]
        while X[l] + L < x:
            l += 1
        while r < N-1 and x + L >= X[r+1]:
            r += 1
        dpl[0][i] = l
        dpr[0][i] = r
    for k in range(1, ln+1):
        for i in range(N):
            dpl[k][i] = dpl[k-1][dpl[k-1][i]]
            dpr[k][i] = dpr[k-1][dpr[k-1][i]]
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ans = 0
        if a < b:
            for k in range(ln+1)[::-1]:
                while dpr[k][a] <= b:
                    a = dpr[k][a]
                    ans += 2**k
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                while dpl[k][a] >= b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    L = int(input())
    ln = int(math.log(N, 2))
    dpl = [[0] * N for _ in range(ln+1)]
    dpr = [[0] * N for _ in range(ln+1)]
    l = 0
    r = 0
    for i in range(N):
        x = X[i]
        while X[l] + L < x:
            l += 1
        while r < N-1 and x + L >= X[r+1]:
            r += 1
        dpl[0][i] = l
        dpr[0][i] = r
    for k in range(1, ln+1):
        for i in range(N):
            dpl[k][i] = dpl[k-1][dpl[k-1][i]]
            dpr[k][i] = dpr[k-1][dpr[k-1][i]]
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ans = 0
        if a < b:
            for k in range(ln+1)[::-1]:
                if dpr[k][a] < b:
                    a = dpr[k][a]
                    ans += 2**k
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                if dpl[k][a] > b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


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

from heapq import heappush, heappop
from copy import deepcopy

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

left = []
for e in s:
    heappush(left, -e)
mx = heappop(left)

made = []
heappush(made, mx)

for _ in range(n):
    made_nxt = deepcopy(made)
    tmp = []

    while made:
        made_val = heappop(made)
        while left and left[0] <= made_val:
            pp = heappop(left)
            tmp.append(pp)

        if not left:
            print("No")
            exit()

        left_val = heappop(left)
        heappush(made_nxt, left_val)

    made = made_nxt

    for e in tmp:
        heappush(left, e)

print("Yes")


### FIXED CODE ###

from heapq import heappush, heappop
from copy import deepcopy

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

left = []
for e in s:
    heappush(left, -e)
mx = heappop(left)

made = []
heappush(made, mx)

for _ in range(n):
    made_nxt = deepcopy(made)
    tmp = []

    while made:
        made_val = heappop(made)
        while left and left[0] <= made_val:
            pp = heappop(left)
            tmp.append(pp)

        if not left:
            print("No")
            exit()

        left_val = heappop(left)
        heappush(made_nxt, left_val)

    made = made_nxt

    for e in tmp:
        heappush(left, e)

print("Yes")
### BUGGY CODE ###

h, w, d = map(int, input().split())
xy = {}
for i in range(h):
    a = list(map(int, input().split()))
    for j in range(w):
        xy[a[j]] = (i + 1, j + 1)

q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())

    m = list(range(l, r + 1, d))
    for i in range(len(m) - 1):
        x1, y1 = xy[m[i]]
        x2, y2 = xy[m[i + 1]]
        ans += abs(x1 - x2) + abs(y1 - y2)
    print(ans)

### FIXED CODE ###

H, W, D = map(int, input().split())
xy = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        xy[A[j]] = (i + 1, j + 1)

d = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
    x1, y1 = xy[i]
    x2, y2 = xy[i - D]
    d[i] = d[i - D] + abs(x1 - x2) + abs(y1 - y2)

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = d[R] - d[L]
    print(ans)
### BUGGY CODE ###

N, K = map(int,input().split())
A = sorted(map(int,input().split()))
F = sorted(map(int,input().split()),reverse=True)
low,high = -1, max([a*f for a,f in zip(A,F)])
while high-low>1:
  mid = (high+low)//2
  k = sum([max(0, a-mid//f) for a,f in zip(A,F)])
  if k>K: low = mid
  else: high = mid
print(high)

### FIXED CODE ###

import numpy as np
N, K = map(int,input().split())
A = np.array(sorted(map(int,input().split())))
F = np.array(sorted(map(int,input().split()) ,reverse=True))
low,high = -1, int(1e12)
while high-low>1:
  mid = (high+low)//2
  k = (A-np.minimum(A,mid//F)).sum()
  if k>K: low = mid
  else: high = mid
print(high)
### BUGGY CODE ###

import collections
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(M)]
        S, T = map(int, input().split())

        edge_map = collections.defaultdict(list)
        for u, v in edges:
            edge_map[u].append(v)

        q = queue.Queue()
        q.put((S, 0, 1))

        dp = collections.defaultdict(lambda: 10 ** 5)
        ans = 10 ** 5
        while not q.empty():
            node, kkp, cnt = q.get()

            kkp += 1

            if kkp < 3:
                for next_node in edge_map[node]:
                    q.put((next_node, kkp, cnt))
            else:
                for next_node in edge_map[node]:
                    if next_node == T:
                        ans = min(ans, cnt)
                        q = queue.Queue()
                        break
                    elif dp[next_node] > cnt + 1:
                        dp[next_node] = cnt + 1
                        q.put((next_node, 0, cnt + 1))

        if ans == 10 ** 5:
            print(-1)
        else:
            print(ans)

# Run main
if __name__ == '__main__':
    AtCoder().main()

### FIXED CODE ###

import collections
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(M)]
        S, T = map(int, input().split())

        edge_map = collections.defaultdict(list)
        for u, v in edges:
            edge_map[u - 1].append(v - 1)

        q = queue.Queue()
        q.put((S - 1, 0))

        INF = 10 ** 5
        dist = [[INF] * 3 for _ in range(N)]
        dist[S - 1][0] = 0
        while not q.empty():
            node, kkp = q.get()

            for next_node in edge_map[node]:
                next_kkp = (kkp + 1) % 3
                if dist[next_node][next_kkp] == INF:
                    dist[next_node][next_kkp] = dist[node][kkp] + 1
                    q.put((next_node, next_kkp))

        if dist[T - 1][0] == INF:
            print(-1)
        else:
            print(dist[T - 1][0] // 3)


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

S = input()[::-1]
MOD = 10**9+7
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]
p = 1
for i, s in enumerate(S):
    nx = [0,]*13
    if s == '?':
        for k in range(10):
            q = (k*p)%13
            for j, d in enumerate(dp):
                nx[(j+q)%13] += d
    else:
        q = (int(s)*p)%13
        for j, d in enumerate(dp):
            nx[(j+q)%13] += d
    dp = [n % MOD for n in nx]
    p = (10*p)%13
print(dp[5])

### FIXED CODE ###

S = input()[::-1]
MOD = 10**9+7
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]
p = 1
for i, s in enumerate(S):
    nx = [0,]*13
    if s == '?':
        for k in range(10):
            q = (k*p)%13
            for j, d in enumerate(dp):
                nx[(j+q)%13] += d
    else:
        q = (int(s)*p)%13
        for j, d in enumerate(dp):
            nx[(j+q)%13] += d
    dp = [n % MOD for n in nx]
    p = (10*p)%13
print(dp[5])
### BUGGY CODE ###

N, K = map(int, input().split())
# K > 1 かつ　N > Kの場合は、N - N // K * K をスタートにできる
if K > 1:
  N = N - N // K * K
else:
  N = 0
minimum = N
count = 0
#print(N)
while count < N:
  N = abs(N - K)
  minimum = min(N, minimum)
  count += 1
print(minimum)

### FIXED CODE ###

N, K = map(int, input().split())
# K > 1 かつ　N > Kの場合は、N - N // K * K をスタートにできる
if K > 1:
  N = N - N // K * K
else:
  N = 0
minimum = N
count = 0
#print(N)
while count <= N / K:
  N = abs(N - K)
  minimum = min(N, minimum)
  count += 1
print(minimum)
### BUGGY CODE ###

N = int(input())
power = 1
for i in range(N):
    power = power * (i + 1)
print(power % ((10**9) + 7))

### FIXED CODE ###

from math import factorial
N = int(input())
power = factorial(N)
print(power % ((10**9) + 7))
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod_v = 10**9 + 7
    ans = 0
    for i in range(0, N):
        for j in range(i + 1, N):
            if i != j:
                ai = A[i]
                aj = A[j]
                ans += ai * aj
                if ans > mod_v:
                    ans = ans % mod_v
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def calc(A, N, i):
    ans = 0
    ai = A[i]
    for i in range(i, N - 1):
        aj = A[i + 1]
        ans += ai * aj
    return (ans)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod_v = 10**9 + 7
    ans = [0] * (N + 1)
    for i in range(0, N - 1):
        if A[i] != 0:
            ans[i] = calc(A, N, i)
            break
    for j in range(i + 1, N - 1):
        if A[j] != 0:
            ans[j] = (ans[j - 1] - A[j - 1] * A[j]) // A[j - 1] * A[j]
        else:
            ans[j] = 0
    ret = 0
    for k in range(0, N):
        ret += ans[k]
    ret = ret % mod_v
    print(ret)


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

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
counter = Counter(a)
key = list(counter.keys())
value = list(counter.values())

s = sum(a)
q = int(input())

for i in range(q):
  b, c = map(int, input().split())
  if b in key:
    x = key.index(b)
    if c in key:
      y = key.index(c)
      s += (c - b) * value[x]
      value[y] += value[x]
      del key[x]
      del value[x]
    else:
      key[x] = c
      s += (c - b) * value[x]
  else:
    pass
  print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [i for i in range(10 ** 5 + 2)]
m = [0] * (10 ** 5 + 2)
for i in a:
  m[i] += 1
s = sum(a)
q = int(input())
for i in range(q):
  b, c = map(int, input().split())
  if m[b] != 0:
    s += (c - b) * m[b]
    m[c] += m[b]
    m[b] = 0
  print(s)
### BUGGY CODE ###

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

lx, lv = [], []

for _ in range(n):
    tmpx, tmpv = map(int, input().split())
    lx.append(tmpx)
    lv.append(tmpv)

lux = [c-x for x in reversed(lx)]

#両方向の累積和
tmpv1, tmpv2 = 0,0
vc, vuc = [],[]
for i in range(n):
    tmpv1 += lv[i]
    tmpv2 += lv[n-1-i]
    _ = [x.append(y) for x,y in zip([vc,vuc],[tmpv1,tmpv2])]

sc, suc = [],[]
tmp1,tmp2 = 0,0
for i in range(n):
    sc.append(vc[i] - lx[i])
    suc.append(vuc[i] - (c - lx[n-1-i]))

ans = 0

for i in range(n):
    s1 = sc[i]
    s2 = suc[i]
    tmpv,tmpx,s3,s4 = 0,0,0,0
    for j in range(n-1-i):
        s3 = max(s1 + suc[j] - min(lx[i],lux[j]),s3)
        s4 = max(s2 + sc[j] - min(lx[j],lux[i]),s4)
    ans = max(ans,s1,s2,s3,s4)

print(ans)

### FIXED CODE ###

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

lx, lv = [], []

for _ in range(n):
    tmpx, tmpv = map(int, input().split())
    lx.append(tmpx)
    lv.append(tmpv)

lux = [c-x for x in reversed(lx)]

#両方向の累積和
tmpv1, tmpv2 = 0,0
vc, vuc = [],[]
for i in range(n):
    tmpv1 += lv[i]
    tmpv2 += lv[n-1-i]
    _ = [x.append(y) for x,y in zip([vc,vuc],[tmpv1,tmpv2])]

sc, suc = [],[]
tmp1,tmp2 = 0,0
for i in range(n):
    sc.append(vc[i] - lx[i])
    suc.append(vuc[i] - (c - lx[n-1-i]))

ssc,ssuc = [],[]
tmp,tmpu = -c, -c
for i in range(n):
    tmp = max(tmp, sc[i])
    tmpu = max(tmpu, suc[i])
    ssc.append(tmp)
    ssuc.append(tmpu)
ans = 0

for i in range(n):
    s1 = sc[i]
    s2 = suc[i]
    if i == n-1:
        s3,s4 = 0,0
    else:
        s3 = s1 - lx[i] + ssuc[max(0,n-i-2)]
        s4 = s2 - lux[i] + ssc[max(0,n-i-2)]

    ans = max(ans,s1,s2,s3,s4)

print(ans)