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

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,MOD = [int(i) for i in input().split()]

to = [[] for _ in [0]*n]
for _ in range(n-1):
    x,y = [int(i)-1 for i in input().split()]
    to[x].append(y)
    to[y].append(x)


dp = [[0]*len(to_i) for to_i in to]
parent_index = [-9999]*n 
ans = [0]*n

def dfs(v, p):
    res = 1
    for i, vc in enumerate(to[v]):
        if vc == p:
            parent_index[v] = i
            continue
        """子供から情報をもらって処理する"""
        dp[v][i] = dfs(vc, v)
        res *= dp[v][i]+1
        res %= MOD
        """処理ここまで"""
    return res

def dfs2(v, res_p, p):
    deg = len(to[v])
    if p >= 0:
        dp[v][parent_index[v]] = res_p

    accl = [1]*(deg+1)
    for i, dpvi in enumerate(dp[v]):
        accl[i+1] = accl[i]*(dpvi+1)%MOD

    accr = [1]*(deg+1)
    for i, dpvir in enumerate(reversed(dp[v])):
        accr[-i-2] = accr[-i-1]*(dpvir+1)%MOD

    ans[v] = accr[0]
    for i,vc in enumerate(to[v]):
        if vc == p: continue
        dfs2(vc, accl[i]*accr[i+1]%MOD, v)

dfs(0,-1)
#print(dp)
dfs2(0,0,-1)
#print(dp)
for i in ans:
    print(i)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n,MOD = [int(i) for i in input().split()]

to = [[] for _ in [0]*n]
for _ in range(n-1):
    x,y = [int(i)-1 for i in input().split()]
    to[x].append(y)
    to[y].append(x)


dp = [[0]*len(to_i) for to_i in to]
parent_index = [-9999]*n 
ans = [0]*n

def dfs(v, p):
    res = 1
    for i, vc in enumerate(to[v]):
        if vc == p:
            parent_index[v] = i
            continue
        dp[v][i] = dfs(vc, v)
        res *= dp[v][i]+1
        res %= MOD
    return res

def dfs2(v, res_p, p):
    deg = len(to[v])
    if p >= 0:
        dp[v][parent_index[v]] = res_p

    accl = [1]*(deg+1)
    accr = [1]*(deg+1)

    for i in range(1, deg+1):
        accl[i] = accl[i-1] * (dp[v][i-1] + 1) % MOD
        accr[-i-1] = accr[-i] * (dp[v][-i] + 1) % MOD

    ans[v] = accr[0]
    for i,vc in enumerate(to[v]):
        if vc == p: continue
        dfs2(vc, accl[i]*accr[i+1]%MOD, v)

dfs(0,-1)
#print(dp)
dfs2(0,0,-1)
#print(dp)
for i in ans:
    print(i)
### BUGGY CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                s=0
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        if z[i]==0:
                            z[i]=1
                            s+=1
                if s>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

from operator import itemgetter

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

abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0),abli[:n]))

alist = []
blist = []
for x, i, aorb in abli[:n]:
    if not aorb:
        alist.append(i)
    else:
        blist.append(i)
 
flag = False
for i in range(n):
    if i in alist and i in blist:
        flag = True
        break
"""
abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
alist = [i for x, i, aorb in abli[:n] if not aorb]
blist = [i for x, i, aorb in abli[:n] if aorb]
flag = bool([i for i in range(n) if i in alist and i in blist])
"""

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 10**16
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum([a for a,i,aorb in abli if not aorb])
rightsum = sum([b for b,i,aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

from operator import itemgetter

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

abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
aiset = set([i for x, i, aorb in abli[:n] if not aorb])
biset = set([i for x, i, aorb in abli[:n] if aorb])
flag = bool(set.intersection(aiset, biset))


y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]

if flag:
    tmpans = tmpans0
else:
    min1 = y-max([x for x, i, aorb in abli[:n] if j != i])
    min2 = z-max([x for x, i, aorb in abli[:n] if j == i])
    tmpans = tmpans0 + min(min1, min2)

leftsum = sum([aa for aa, i, aorb in abli if not aorb])
rightsum = sum([bb for bb, i, aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))
### BUGGY CODE ###

n = int(input())
sl = []
for i in range(n):
    s = list(input())
    s.sort()
    sl.append(s)

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if sl[i] == sl[j]:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
sl = []
for i in range(n):
    s = list(input())
    s.sort()
    sl.append("".join(s))
d = Counter(sl)

def cul(n):
    return n*(n - 1)//2

ans = 0
val = d.values()
for i in val:
    if i > 1:
        ans += cul(i)
print(ans)
### BUGGY CODE ###

N,C=map(int,input().split())
x=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    x[i],v[i]=map(int,input().split())
a=[0 for i in range(N)]
b=[0 for i in range(N)]
a[0]=v[0]
b[N-1]=v[N-1]
for i in range(1,N):
    a[i]=v[i]+a[i-1]
for i in range(N-1)[::-1]:
    b[i]=b[i+1]+v[i]
ans=0
for i in range(N+1):
    for j in range(N-i+1):
        if i==0:
            OA=0
            EA=0
        else:
            OA=x[i-1]
            EA=a[i-1]
        if j==0:
            OB=0
            EB=0
        else:
            OB=C-x[N-j]
            EB=b[N-j]
        tmpA=EA+EB-OA-OA-OB
        tmpB=EA+EB-OA-OB-OB
        if ans<tmpA:
            ans=tmpA
        if ans<tmpB:
            ans=tmpB
print(ans)


### FIXED CODE ###

N,C=map(int,input().split())
x=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    x[i],v[i]=map(int,input().split())
a=[0 for i in range(N)]
b=[0 for i in range(N)]
a[0]=v[0]
b[N-1]=v[N-1]
for i in range(1,N):
    a[i]=v[i]+a[i-1]
for i in range(N-1)[::-1]:
    b[i]=b[i+1]+v[i]
ans=0
f1=[0 for i in range(N+1)]
f1[0]=0
f1[1]=v[0]-x[0]
for i in range(1,N):
    f1[i+1]=f1[i]+v[i]+x[i-1]-x[i]
g1=[0 for i in range(N+1)]
g1[0]=f1[0]
for i in range(1,N+1):
    g1[i]=max([f1[i],g1[i-1]])
f2=[0 for i in range(N+1)]
f2[0]=0
f2[1]=v[0]-2*x[0]
for i in range(1,N):
    f2[i+1]=f2[i]+v[i]+2*x[i-1]-2*x[i]
g2=[0 for i in range(N+1)]
g2[0]=f2[0]
for i in range(1,N+1):
    g2[i]=max([f2[i],g2[i-1]])
for i in range(N+1):
    if i==0:
        OB=0
        EB=0
    else:
        OB=C-x[N-i]
        EB=b[N-i]
    tmpA=EB-2*OB+g1[N-i]
    tmpB=EB-OB+g2[N-i]
    if ans<tmpA:
        ans=tmpA
    if ans<tmpB:
        ans=tmpB
print(ans)
### BUGGY CODE ###

q=int(input())
a=[list(map(int,input().split())) for i in range(q)]

import math
def erato(n):
    prime=[]
    limit=math.sqrt(n)
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

tmp=max([a[i][1] for i in range(q)])+1
primes=erato(tmp)
#print(primes)
imos=[0]*(tmp)
for i in range(3,tmp):
    if i%2==1:
      if i in primes and (i+1)//2 in primes:
          imos[i]=imos[i-2]+1
      else:
          imos[i]=imos[i-2]
    if i%2==0:
      imos[i]=imos[i-1]
#print(imos)
for i in range(q):
    print(imos[a[i][1]]-imos[a[i][0]-1])


### FIXED CODE ###

q=int(input())
M=100000

import math
def erato(n):
    prime=[]
    cnt=[0]*n
    limit=math.sqrt(n)
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

prime=erato(M)
cnt=[0]*M
for i in range(len(prime)):
  cnt[prime[i]]+=0.6
  if 2*prime[i]-1<M:
    cnt[2*prime[i]-1]+=0.6
 
for i in range(1,M):
  if cnt[i]>1:
    cnt[i]=cnt[i-1]//1+1
  else:
    cnt[i]=cnt[i-1]//1
    
#print(cnt)
for i in range(q):
  l,r=map(int,input().split())
  print(cnt[r]-cnt[l-1])
### BUGGY CODE ###

q = int(input())
ans = []
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    ans+=[dp1[-1]]
print(*ans, sep="\n")


### FIXED CODE ###

def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))
### BUGGY CODE ###

import bisect
n, m = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
len_aaa = len(aaa)
aaa = sorted([-a for a in aaa])

for i in range(m):
    b, c = list(map(int, input().split(' ')))
    index = bisect.bisect_left(aaa, -c)
    for j in range(b):
        aaa.insert(index, -c)
    aaa = aaa[:len_aaa]
print(abs(sum(aaa)))

### FIXED CODE ###

import bisect
n, m = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
aaa = sorted([-a for a in aaa])[::-1]
len_aaa = len(aaa)

cccbbb = []
for i in range(m):
    b, c = list(map(int, input().split(' ')))
    cccbbb.append((-c, b))
cccbbb = sorted(cccbbb)
ccc = []
for c, b in cccbbb:
    ccc += [c] * b
    if len(ccc) > len_aaa:
        break
ans = 0
for i in range(len_aaa):
    c = ccc[i] if i < len(ccc) else 0
    ans += min(aaa[i], c)
print(abs(ans))
### BUGGY CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
cost_list = [0, abs(h_list[0] - h_list[1])]
for i in range(2, n):
    cost = 10**9
    h = h_list[i]
    for j in range(max(i-k, 0), i):
        cost = min(cost, abs(h_list[j] - h) + cost_list[j])
    cost_list.append(cost)
print(cost_list[-1])


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h_arr = np.array(list(map(int, input().split())))
cost_arr = np.zeros(n, dtype=int)
for i in range(1, n):
    start = max(i-k, 0)
    cost_arr[i] = (abs(h_arr[start:i] - h_arr[i]) + cost_arr[start:i]).min()
print(int(cost_arr[-1]))
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = Counter((list(map(int, input().split(' ')))))
ans = 0
pre= 10**6+1
for i in sorted(A.keys(),reverse=True):
    flg = True
    if A[i] > 1:
        continue
    for j in range(1,min(int(pow(i,0.5))+2,pre)):
        if not i%j:
            if A[j] and i != j:
                flg = False
                break
            if j != i//j and A[i//j] and i//j != i:
                    flg = False
                    break
    if flg:
        ans += 1
    pre = i
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = Counter(list(map(int,input().split(' '))))
ans = 0
m = max(A.keys())
L = [1]*(10**6+1)
for i in sorted(A.keys()):
    if not L[i]:
        continue
    if A[i] == 1:
        ans += 1
    for j in range(i,m+1,i):
        L[j] = 0
print(ans)
### BUGGY CODE ###

N, M = map(int,input().split())
An = sorted(list(map(int,input().split())), reverse=True)

for _ in range(M):
  B, C = map(int,input().split())
  for b in range(N-1,N-1-B,-1):
    if An[b] < C:
      An[b] = C
    else:
      break
  else:
    An.sort(reverse=True)
print(sum(An))

### FIXED CODE ###

N, M = map(int,input().split())
An = list(map(lambda x:[int(x),1],input().split()))
D = [[0]*2 for _ in range(M)]
for i in range(M):
  B, C = map(int,input().split())
  D[i] = [C,B]
An.extend(D)
An.sort(reverse=True)
num = 0
cnt = 0
for i in range(len(An)):
  if cnt+An[i][1] >= N:
    num += An[i][0]*(N-cnt)
    print(num)
    break
  else:
    cnt += An[i][1]
    num += An[i][0]*An[i][1]
### BUGGY CODE ###

N = int(input())
print(sum(i for i in range(N)))


### FIXED CODE ###

N = int(input())
print((N-1)*N//2)
### BUGGY CODE ###

N = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

a_list.sort()
c_list.sort()
result = 0
for b in b_list:
    a_count = list(filter(lambda x: x < b, a_list))
    c_count = list(filter(lambda x: x >b, c_list))
    result += len(a_count)*len(c_count)

print(result)

### FIXED CODE ###

import bisect
N = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

a_list.sort()
c_list.sort()
result = 0

for b in b_list:
    a_count = bisect.bisect_left(a_list, b)
    c_count = bisect.bisect_right(c_list, b)
    result += a_count*(len(c_list)-c_count)

print(result)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
import math
#import collections
#from collections import deque
#from bisect import bisect_left
K = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
s = 0
d = 0
e = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            d = math.gcd(c,b)
            e = math.gcd(a,d)
            s += e
print(s)

### FIXED CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
import math
#import collections
#from collections import deque
#from bisect import bisect_left
K = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
s = 0
d = 0
e = 0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            d = math.gcd(c,b)
            e = math.gcd(a,d)
            if a == b and b == c:
                s += e
            elif a != b and b != c :
                s += 6 * e
            else:
                s += 3 * e
print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N,K=map(int,input().split())
    ans=0
    
    A=list(map(int,input().split()))
    A=[A[j]%K for j in range(N)]
    ans += A.count(1)
    
    B=[(A[j]+A[j+1])%K for j in range(N-1)]
    ans += B.count(2)
    
    for i in range(2,min(K+1,N)):
        C = [(B[j]+B[j+1]-A[j+1])%K for j in range(N-i)]
        ans += C.count(i+1)
        A = B
        B = C
        
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy
N,K=map(int,input().split())

if K==1:
    print(0)
    exit(0)

A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        if S2[j-K] in d:
            d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)
### BUGGY CODE ###

import sys
import collections
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K,Q=nm()
Al=[0]*Q
for i in range(Q):
    Al[i]=ni()



for i in range(N):
    print('No' if (K-Q+Al.count(i+1)<1) else 'Yes')

### FIXED CODE ###

import sys
import collections
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K,Q=nm()
Al=[0]*Q
ans_l=[K-Q]*N
for i in range(Q):
    #Al[i]=int(input())
    ans_l[int(input())-1]+=1
    


for i in range(N):
    #print(Al.count(i+1))
    #print('No' if (K-Q+Al.count(i+1)<1) else 'Yes')
    print('No' if (ans_l[i]<1) else 'Yes')
### BUGGY CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
#while(True):  
for answer in range(1,N**3): 
  #answer+=1
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if len(amat[i]) == 0 or matched_flag[i]:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      amat[i].pop()
      amat[ai_next].pop()
      matched_flag[i]=True
      matched_flag[ai_next]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    maxlist=-1
    for i in range(1,N+1):
      maxlist=max(maxlist,len(amat[i]))
    if maxlist==0:
      print(answer)
      sys.exit()


### FIXED CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>3000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().split()))
ans = 0
next = 1
a = True
while (a):
    a = False
    b = False
    for i in range(next,len(array)):
        if array[i] < array[i-1]:
            array[i] = array[i] + 1
            ans += 1
            a = True
            if b == False:
                b= True
                next = i

print(ans)


### FIXED CODE ###

N = int(input())
array = list(map(int, input().split()))
ans = 0
next = 1
a = True
while (a):
    a = False
    b = False
    for i in range(next,len(array)):
        if array[i] < array[i-1]:
            ans += array[i-1] - array[i]
            array[i] = array[i - 1]
            a = True
            if b == False:
                b= True
                next = i

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

def resolve():


    import sys
    input = sys.stdin.readline
    n, m = map(int, input().split())
    dp = [0] * (n + 2)

    li_broken = [0] * m
    for i in range(m):
        li_broken[i] = int(input())

    dp[n] = 1
    li_i = list(reversed(range(n)))

    for i in li_i:

        if i in li_broken:
            dp[i] = 0

        else:
            dp[i] = (dp[i+1] + dp[i+2]) % 1000000007

    print(dp[0])
    
resolve()

### FIXED CODE ###

def step(n):
  if n == 0:
      return 1
  steps = [0 for i in range(n + 2)]
  steps[1] = 1
  steps[2] = 2
  for i in range(3, n + 1):
    steps[i] = steps[i - 1] + steps[i - 2]
  return steps[n]

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

a.append(n)

sum = 1

for i in range(m + 1):

  if i == 0:
    sum *= step(a[i] - 1)
    continue
  
  elif i == m:
    sum *= step(a[m] - a[m-1] -1)
    
  elif a[i] - a[i-1] == 1:
    sum = 0
    break

  else:
    sum *= step(a[i] - a[i-1] -2)
    
if m == 0:
  sum = step(n)

print(sum % 1000000007)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
m = [0] * n
m[0] = 0
for i in range(1, n):
    m[i] = float('inf')
    t = k if i >= k else i
    for j in range(t):
        m[i] = min(m[i], m[i - j - 1] + abs(h[i - j - 1] - h[i]))
print(m[n-1])


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    m = [0] * n
    m[0] = 0
    for i in range(1, n):
        m[i] = min(m[j] + abs(h[j] - h[i]) for j in range(max(0, i-k),i))
    print(m[-1])

main()
### BUGGY CODE ###

from bisect import bisect_left
 
N = int(input())
L = list(map(int, input().split()))
L.sort()
 
cnt = 0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    t = L[i]+L[j]
    idx = bisect_left(L,t,lo=j+1)
    cnt += max(0,idx-j-1)
print(cnt)

### FIXED CODE ###

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

from bisect import bisect_left 
cnt = 0
for i in range(0,N):
  for j in range(i+1,N):
    t = L[i]+L[j]
    idx = bisect_left(L,t)
    cnt += max(0,idx-j-1)
print(cnt)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()

for i in range(m):
  a = aaa.pop(-1) // 2
  insert_index = bisect.bisect_right(aaa, a)
  aaa.insert(insert_index, a)
  
print(sum(aaa))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
aaa = [-1 * int(a) for a in input().split()]
heapq.heapify(aaa)

for i in range(m):
  a = -heapq.heappop(aaa) // 2
  heapq.heappush(aaa, -a)
  
print(-sum(aaa))