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

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

n,k = [int(x) for x in stdin.readline().rstrip().split()]
p = [(int(x)+1)/2 for x in stdin.readline().rstrip().split()]

m = 0
for i in range(n-k+1):
    m = max([sum(p[i:i+k]), m])

print(m)




### FIXED CODE ###

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

n,k = [int(x) for x in stdin.readline().rstrip().split()]
p = [(int(x)+1)/2 for x in stdin.readline().rstrip().split()]

m = sum(p[0:k])
maxm = m

for i in range(1,n-k+1):
    m = m - p[i-1] + p[i+k-1]
    maxm = max([maxm,m])

print(maxm)
### BUGGY CODE ###

n = int(input())
ar = list(map(int,input().split(" ")))
count = 0
for i in range(n-1):
    br = ar[i+1:n]
    count += ar[i] * sum(br)
print(count % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
ar = list(map(int,input().split(" ")))
sm = sum(ar)
count = 0
for i in range(n-1):
    sm -= ar[i]
    count += ar[i] * sm
print(count % (10 ** 9 + 7))
### BUGGY CODE ###

def main():
  a = list(input())
  b = list(input())
  c = list(input())
  ab = [False]*20000
  ac = [False]*20000
  bc = [False]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  for i in range(-4000,4001,1):
    for j in range(-4000,4001,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()

### FIXED CODE ###

def main():
  a = input()
  b = input()
  c = input()
  ab = [None]*20000
  ac = [None]*20000
  bc = [None]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  AB = A+B
  AC = A+C
  for i in range(-AC,AC,1):
    for j in range(-AB,AB,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
cnt=0
while True:
  cnt+=1
  if cnt%2==0:
    s=a-(cnt/2)*d
    if s<=0:
      print('No')
      
  else:
    s=c-(cnt+1)/2*b
    if s<=0:
      print('Yes')

### FIXED CODE ###

a,b,c,d=map(int,input().split())
cnt=0
while True:
  cnt+=1
  if cnt%2==0:
    s=a-(cnt/2)*d
    if s<=0:
      print('No')
      break
      
  else:
    s=c-(cnt+1)/2*b
    if s<=0:
      print('Yes')
      break
### BUGGY CODE ###

#n₌品物の数
#m=割引券の数
#ans =合計金額

n,m = map(int, input().split())
ans =0
#割引券をY枚使うと、品物をX/2**Y円で変える()小数点はむし
ma =0
#各品物の値段を保管しておくための配列
a = list(map(int, input().split()))

#品物を高いもの順に並び替える
a.sort(reverse=True)

#割引をｍ回繰り返す
for i in range(m):
    ma =a[0]
    ma = int(ma/2)
    a[0] = ma
    a.sort(reverse =True)
ans = int(sum(a))
print(ans)
        




### FIXED CODE ###

import heapq

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

#heappopは最小の値（一番上のノードの値を返す)
for _ in range(m):
    tmp = int(heapq.heappop(a)/2)
    #新しい値(2で割った値)を挿入してヒープを保つ)
    heapq.heappush(a,tmp)

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

import sys
read = lambda : sys.stdin.readline().rstrip('\n')
tint = lambda x: [int(x) for x in x.split()]
inf = float('inf')

def main():
    n, k = tint(read())
    stones = tint(read())
    dp = [inf]*n
    dp[0] = 0
    for i in range(n):
        for t in range(1, k+1):
            if i+t < n:
                v = dp[i]+abs(stones[i]-stones[i+t])
                if dp[i+t] > v:
                    dp[i+t] = v
    print(dp[-1])


if __name__ == '__main__':    
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

import sys


def input():
    return sys.stdin.readline().strip()


n, k = map(int, input().split())
H = list(map(int, input().split()))

INF = 10 ** 9
dp = [INF] * n
dp[0] = 0
for i in range(n - 1):
    for j in range(1, k + 1):
        if j >= n - i:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[-1])


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


n, k = map(int, input().split())
H = list(map(int, input().split()))

INF = 10 ** 9
dp = [INF] * n
dp[0] = 0
for i in range(n - 1):
    for j in range(1, k + 1):
        if j >= n - i:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[-1])
### BUGGY CODE ###


def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    a=[]
    for i in range(m):
        a.append(int(input()) )
    mod=10**9 + 7
    
    def cmb(n, r, m,g1,g2):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % m
    
    def nCrMOD(n,r,m):
        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range( 2, n + 1 ):
            g1.append( ( g1[-1] * i ) % m )
            inverse.append( ( -inverse[m % i] * (m//i) ) % m )
            g2.append( (g2[-1] * inverse[-1]) % m )
        return cmb(n,r,m,g1,g2)
    
    
    c=0
    for i in range(m-1):
        if a[i]==a[i+1]-1: c+=1
    if c!=0:
        print(0)
    elif m==0:
         print( sum( nCrMOD(n-i,i,mod) for i in range(n//2+1) )%mod )
        
        
    else:
        b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
        cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]
    
        ans=1
        for ccc in cc:
            ans = ans*ccc%mod
        print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

#c dp version
n,m = map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()) )
from collections import deque
a=deque(a)
mod=10**9 + 7

dp=[0]*(n+2)
dp[0]=0
dp[1]=1
aa=0
if len(a)>0:
    aa=a.popleft()
for i in range(2,n+2):
    if i-1 == aa:
        dp[i]=0
        if len(a)>0:
            aa=a.popleft()
    else:
        dp[i]=( dp[i-1]+dp[i-2] )%mod
print(dp[-1])
### BUGGY CODE ###

import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
def f(x):
    L=[set() for i in range(N+1)]
    L[0].add(0)
    for i in range(N):
        s=A[i]
        if i==x:
            s=0
        for k in L[i]:
            L[i+1].add(k)
            if k+s<K:
                L[i+1].add(k+s)
    for k in L[N]:
        if k+A[x]>=K:
            return True
    return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

### FIXED CODE ###

import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
sa=sum(A)
def f(x):
    y=A[x]
    if y>=K:
        return True
    L=set()
    L.add(0)
    dp=[False]*(K-y)
    dp[0]=True
    t=0
    for i in range(N):
        if i==x:
            continue
        s=A[i]
        for k in range(t,-1,-1):
            if not dp[k]:
                continue
            if k+s>=K:
                continue
            if k+s+y>=K:
                return True
            dp[k+s]=True
        t=min(t+s,K-y-1)
    return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)
### BUGGY CODE ###

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

for i in range(n):
    print(str(a.index(i+1) + 1), end=" ")

### FIXED CODE ###

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

ans = [0]*n

for i in range(n):
    ans[a[i]-1] = i + 1
print(" ".join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
wordlist = [input() for i in range(n)]
wordtuple = tuple(set(wordlist))
ans = []
maxnum = 0
a = len(wordtuple)
for j in range(a) :
    countnum = wordlist.count(wordtuple[j])
    if countnum == maxnum :
        ans.append(wordtuple[j])
    if countnum > maxnum :
        maxnum = countnum
        ans = []
        ans.append(wordtuple[j])
ans.sort()
for l in range(len(ans)) :
    print(ans[l])

### FIXED CODE ###

n = int(input())
d = {}
for i in range(n) :
    s = input()
    if s not in d :
        d[s] = 1
    else :
        d[s] += 1
m = max(d.values())
ans = []
for i in d :
    if d[i] == m :
        ans.append(i)
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

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

acc = 1
for i in range(n):
    acc *= a[i]

if acc > 10 ** 18:
    print(-1)
else:
    print(acc)

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit(0)

acc = 1
for i in range(n):
    acc *= a[i]
    if acc > 10 ** 18:
        print(-1)
        exit(0)

print(acc)
### BUGGY CODE ###

from itertools import product
n = int(input())

nums = [0]*(n+1)
for i in product(range(1, n//6+1),repeat=3):
  t = i[0]**2 + i[1]**2 + i[2]**2 + i[0]*i[1] + i[1]*i[2] + i[0]*i[2]
  if t <= n: nums[t] += 1

for i in range(1,n+1): print(nums[i])

### FIXED CODE ###

from itertools import product
n = int(input())

nums = [0]*(n+1)
for i in product(range(1, int(n**0.5)+1),repeat=3):
  t = i[0]**2 + i[1]**2 + i[2]**2 + i[0]*i[1] + i[1]*i[2] + i[0]*i[2]
  if t <= n: nums[t] += 1

for i in range(1,n+1): print(nums[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
mod = 10 ** 9 + 7
ans = 1
for _ in range(n):
  ans *= 2
cef = [ans//2]
for i in range(n-1):
  tmp = cef[-1] + ans // 4
  tmp %= mod
  cef.append(tmp)
son = 0
for i in range(n):
  son += cef[i] * a[i]
  son %= mod
ans *= son
ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
mod = 10 ** 9 + 7
ans = 1
for _ in range(2*n-2):
  ans *= 2
  ans %= mod
cef = [i+2 for i in range(n)]
for i in range(n):
  a[i] *= cef[i]
ans *= sum(a)
ans %= mod
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for a in range(k+1):
  for b in range(k+1):
    for c in range(k+1):
      if a+b+c==s:
        ans += 1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
upper  = min(k,s)+1
lower = max(0,s-2*k)
ans = 0
for i in range(lower,upper):
  for j in range(lower,upper):
    if 0 <= s-(i+j) <= k:
      ans += 1
print(ans)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

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

for i in range(m):
  a = aaa.pop() // 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))
### BUGGY CODE ###

n, k = [int(_) for _ in input().split()]
s = []
for i in range(k):
    l, r = [int(_) for _ in input().split()]
    for j in range(l, r+1):
        s.append(j)
# print(s)
dp = [0 for i in range(n)]
dp[0] = 1
# print(dp)
for i in range(n):
    for j in s:
        if i-j >= 0:
            dp[i] += dp[i-j]
    dp[i] = dp[i] % 998244353
    # print(dp)
print(dp[-1])

### FIXED CODE ###

n, k = [int(_) for _ in input().split()]
s = []
for i in range(k):
    s.append([int(_) for _ in input().split()])
# print(s)
dp = [0 for i in range(n)]
dp[0] = 1
dp_s = [0 for i in range(n+1)]
dp_s[1] = 1
# print(dp)
# print(dp_s)
# print('*****************')
for i in range(1, n):
    for j in range(len(s)):
        r, l = s[j]
        if i-r >= 0:
            if i-l >= 0:
                dp[i] += dp_s[i-r+1] - dp_s[i-l]
            else:
                dp[i] += dp_s[i-r+1] - dp_s[0]
    dp[i] = dp[i] % 998244353
    # print(dp)
    dp_s[i+1] += dp_s[i] + dp[i]
    dp_s[i+1] = dp_s[i+1] % 998244353
    # print(dp_s)
    # print('*****************')
print(dp[-1])
### BUGGY CODE ###

N, A = map(int, input().split())
X = list(map(int, input().split()))
n = N * 50
dp = [[[0]*(n+1) for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1

for i, a in enumerate(X, 1):
  for j in range(N+1):
    for s in range(n+1):
      dp[i][j][s] = dp[i-1][j][s]
      if a <= s:
        dp[i][j][s] += dp[i-1][j-1][s-a]

ans = 0
for m in range(1, N+1):
  ans += dp[-1][m][A*m]

print(ans)

### FIXED CODE ###

N, A = map(int, input().split())
X = list(map(int, input().split()))
n = N * 50
dp = [[[0]*(n+1) for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1

for i, a in enumerate(X, 1):
  for j in range(N+1):
    for s in range(n+1):
      dp[i][j][s] = dp[i-1][j][s]
      if a <= s:
        dp[i][j][s] += dp[i-1][j-1][s-a]

ans = 0
for m in range(1, N+1):
  ans += dp[-1][m][A*m]

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

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

count = 0
for i in range(N):
    if min(P[0:i+1]) >= P[i]:
        count += 1
print(count)


### FIXED CODE ###

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

count,min = 0,P[0]
for i in range(N):
    if min >= P[i]:
        count += 1
        min = P[i]
print(count)
### BUGGY CODE ###

N = int(input())
A = [0]*N

for i in range(N):
  A[i] = int(input())

for i in range(N):
  Atmp = A[0:i]
  Atmp.extend(A[i+1:N])
  ans = max(Atmp)
  print(ans)


### FIXED CODE ###

N = int(input())
A = [0]*N

for i in range(N):
  A[i] = int(input())

As = sorted(A, reverse=True)
M = As[0]
Ms = As[1]

for i in range(N):
  if M == A[i]:
    print(Ms)
  else:
    print(M)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0

for i in range(0, N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      
      if j-i == k-j:
        pass
      else:
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
          ans += 1
          
          
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

## 組み合わせの総数
ans = S.count('R') * S.count('B') * S.count('G')

## 除外
## j - i = k - j 
## k = 2*j -i

for i in range(0, N-2):
  for j in range(i+1, N-1):
    
    if 2*j-i >= N:
      break
    elif S[i] != S[j] and S[j] != S[2*j-i] and S[2*j-i] != S[i]:
      ans -= 1
  
print(ans)
### BUGGY CODE ###

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

def check(K):
    X = []; Y = []
    for i, a in enumerate(A):
        while X and a < X[-1]:
            X.pop(); Y.pop()
        u = (i > 0 and A[i-1] >= a)
        if not X:
            X.append(a); Y.append(u)
            continue
        v = X[-1]
        if v != a:
            X.append(a); Y.append(u)
            continue
        Y[-1] += 1
        while X and Y[-1] == K:
            X.pop(); Y.pop(); a -= 1
            if a == 0:
                return 0
            if not X:
                X.append(a); Y.append(1)
                break
            if X[-1] != a:
                X.append(a); Y.append(1)
                break
            Y[-1] += 1
    return 1

ok = 1
for i in range(N-1):
    if not A[i] < A[i+1]:
        ok = 0
if ok:
    print(1)
    exit(0)

left = 1; right = N+1
while left+1 < right:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

### FIXED CODE ###

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

def check(K):
    st = []
    for i, a in enumerate(A):
        #print(K, i, st, a)
        while st and a < st[-1][0]:
            st.pop()
        u = i > 0 and A[i-1] >= A[i]
        if not st:
            st.append([a, u])
            continue
        l = st[-1]
        if l[0] == a:
            l[1] += 1
            while st and l[1] == K:
                st.pop(); a -= 1
                if a == 0:
                    return 0
                if not st:
                    st.append([a, 1])
                    break
                l = st[-1]
                if l[0] == a:
                    l[1] += 1
                else:
                    st.append([a, 1])
                    break
            #print(l, st)
        else:
            st.append([a, u])
    #print(st)
    return 1

ok = 1
for i in range(N-1):
    if not A[i] < A[i+1]:
        ok = 0
if ok:
    print(1)
    exit(0)

left = 1; right = N+1
while left+1 < right:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

from operator import itemgetter
n,m=map(int,input().split())
wa=0
ac=0
ig=0
l=[(input().split()) for _ in range(m)]
l=sorted(l, key=itemgetter(0))
ll=sorted(l, key=itemgetter(0))

for t in l:
  c,r=t[0],t[1]
  if c == ig:
    continue
  
  if [c,'AC'] not in ll:
    continue
  
  if r == 'WA':
    wa+=1
  elif r == 'AC':
    ac+=1
    ig=c
  del ll[0]
print(ac,wa)

### FIXED CODE ###

n,m=map(int,input().split())
l=[[] for _ in range(n)]
for _ in range(m):
  a,b=input().split()
  l[int(a)-1].append(b)
  
wacnt=0
accnt=0

for rl in l:
  cnt = 0
  for r in rl:
    if r == 'WA':
      cnt+=1
    elif r == 'AC':
      wacnt+=cnt
      accnt+=1
      break
      
print(accnt, wacnt)
### BUGGY CODE ###

import random
A, B = map(int, input().split())
X = [[0] * (10**4) for _ in range(10**5)]
print(A)


### FIXED CODE ###

A, B = map(int, input().split())
print(max(A*2-1,A+B,B*2-1))
### BUGGY CODE ###

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

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

### FIXED CODE ###

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

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[-1]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])
### BUGGY CODE ###

H = int(input())
cnt=1
x=1
while True:
    H=H//2
    if H==1:
        cnt*=2
        x+=cnt
        print(x)
        exit()
    cnt*=2
    x+=cnt

### FIXED CODE ###

import math
H = int(input())
a = math.log2(H)
a = math.floor(a)
print(int((1-2**(a+1))/(1-2)))
### BUGGY CODE ###

# D - Ki

import queue

class Node:
    def __init__(self, children, point):
        self.children = children
        self.point = 0

N, Q = map(int, input().split())
nodes = [Node([], 0) for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].children.append(b - 1)
    nodes[b - 1].children.append(a - 1)

for _ in range(Q):
    p, x = map(int, input().split())
    nodes[p - 1].point += x

q = queue.Queue()
q.put(0)
visited = [False] * N
while not q.empty():
    key = q.get()
    visited[key] = True
    for child in nodes[key].children:
        if visited[child] == False:
            nodes[child].point += nodes[key].point
            q.put(child)

print(*[node.point for node in nodes])


### FIXED CODE ###

# D - Ki

N, Q = map(int, input().split())

children = [[] for _ in range(N)]
points = [0] * N

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

for _ in range(Q):
    p, x = map(int, input().split())
    points[p - 1] += x

stack = []
stack.append(0)
visited = [False] * N
while stack:
    key = stack.pop()
    for child in children[key]:
        if visited[child] == True:
            continue
        points[child] += points[key]
        visited[key] = True
        stack.append(child)

print(*points)
### BUGGY CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q = int(input())
rl = [map(int, input().split()) for _ in range(q)]

li = set(get_sieve_of_eratosthenes(10**5))
# print(li)
for l, r in rl:
  cnt = 0
  for j in range(l, r + 1):
    if j % 2 == 1 and j in li and (j + 1) // 2 in li:
      cnt += 1
  print(cnt)


### FIXED CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q = int(input())
rl = [map(int, input().split()) for _ in range(q)]

li = get_sieve_of_eratosthenes(10**5+1)
pli = [False] * (10**5+1)

for i in li:
  pli[i] = True

# print(pli)
  
# print(li)
cpli = [0] * (10**5+1)

cnt = 0
for i in range(10**5+1):
  if i % 2 == 1 and pli[i] and pli[(i + 1) // 2]:
    cnt += 1
  cpli[i] = cnt

# print(cpli)
  
for l, r in rl:
  print(cpli[r] - cpli[l-1])
### BUGGY CODE ###

A,B,C,D = list(map(int, input().split()))

n_list=[i for i in range(A,B+1) if  i%C!=0 and i%D!=0]
print(len(n_list))

### FIXED CODE ###

from fractions import gcd
A,B,C,D = map(int, input().split())

c_div=B//C
d_div=B//D
dc_div=B//((C*D)//gcd(C,D))

not_div1 = B-(d_div+c_div-dc_div)

A =A-1
c_div=A//C
d_div=A//D
dc_div=A//((C*D)//gcd(C,D))

not_div2 = A-(d_div+c_div-dc_div)

print(not_div1-not_div2)