Harryxun/stf_run huggingface dataset:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a=sorted(a,reverse=True)
b=sorted(b)

def ok(N):
    sums=0
    for i in range(n):
        sums+=max(0,a[i]-N//b[i])
    if sums<=k:
        return True
    else:
        return False
    
import math

left=0
right=a[0]*b[-1]
for _ in range(math.ceil(math.log2(right))):
    if ok(math.floor((left+right)/2)):
      left=left
      right=(left+right)/2
    elif not ok(math.floor((left+right)/2)):
      left=(left+right)/2
      right=right
print(math.floor(right))
   


### FIXED CODE ###

# いきぬきreview　忘れた問題
# gluttony
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
F.sort()
A.sort(reverse=True)


def func(X):
    s = 0
    for i in range(N):
        a, f = A[i], F[i]
        s += max(0, a-X//f)
    return s <= K


R = 10**12
L = -1
while R-L > 1:
    m = (R+L)//2
    if func(m):
        R = m
    else:
        L = m
print(R)
import math

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

c = int(B/C) - int((A-1)/C)
d = int(B/D) - int((A-1)/D)

CD = int(C * D / math.gcd(C, D))
cd = int(B/CD) - int((A-1)/CD)

ans = B - (A-1) - (c + d - cd)
print(ans)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

c = B//C - (A-1)//C
d = B//D - (A-1)//D

CD = C * D // gcd(C, D)
cd = B//CD - (A-1)//CD

ans = B - (A-1) - (c + d - cd)
print(ans)
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math

a,b,k = map(int,input().split())
num = [i for i in range(a,b+1)]
ans = []
if len(num)<=k:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(k):
        ans.append(num[i])
    for i in range(k):
        ans.append(num[len(num)-i-1])
    ans = set(ans)
    ans = list(ans)
    ans.sort()
    for i in range(len(ans)):
        print(ans[i])


### FIXED CODE ###

import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math

a,b,k = map(int,input().split())
ans = []
if b-a<=k:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(a,a+k):
        ans.append(i)
    for i in range(b-k+1,b+1):
        ans.append(i)
    ans = set(ans)
    ans = list(ans)
    ans.sort()
    for i in range(len(ans)):
        print(ans[i])
a=[[0]*3 for i in range(3)]
b=[]
for i in range(3):
  x=input().split()
  a[i][0]=x[0]
  a[i][1]=x[1]
  a[i][2]=x[2]
n=int(input())
for i in range(n):
  b.append(input())
for i in range(n):
  for j in range(9):
    if b[i]==a[j//3][j%3]:
      a[j//3][j%3]='X'
jud=[0,0,0,0]
z=0
res=0
for i in range(3):
  for j in range(2):
    if a[i][j]==a[i][j+1]:
      jud[0]+=1
    if a[j][i]==a[j+1][i]:
      jud[1]+=1
  if max(jud)>1:
    res-=1
for j in range(2):
  if a[j][j]==a[j+1][j+1]:
    jud[2]+=1
  if a[j][2-j]==a[j+1][2-j-1]:
    jud[3]+=1
  if max(jud)>1:
    res-=1
if res<0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n=int(input())
if n%2==0:
  print(n//2)
else:
  print((n+1)//2)
n,k =(int(x) for x in input().split())
list = (int(x) for x in input().split())
p = 0

for i in range(0, n)
	if list[i] >= k:
    	p = p + 1

print(p)

### FIXED CODE ###

n,k =(int(x) for x in input().split())
list = input().split()
p = 0
list = [int(s) for s in list]
     
for i in range(0, n):
    if list[i] >= k:
        p = p + 1

print(p)
[W,H,x,y,r]=[int(x) for x in input().split()]
if (0=<x=<W) and (0=<y=<H):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

W,H,x,y,r=[int(x) for x in input().split()]
print("No" if x < r or y < r or (x+r) > W or (y+r) > H else "Yes")
# 5
# 3 5 2 1 4
def cum(i):
    res = 0
    while i>0:
        res += bit[i]
        i -= i&-i
    return res

def add(i, x):
    while i<=N:
        bit[i] += x
        i += i&-i

def solve():
    global N,A,bit
    N = int(input())
    A = list(map(int, input().split()))
    bit = [0]*(N+1)

    res = 0
    for i in range(N):
        res += cum(A[i])
        add(A[i], 1)

    print(N*(N-1)//2-res)

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
    except:
        pass
    solve()
# vim: set foldmethod=marker:}}}



### FIXED CODE ###

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
def dump(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

# 5
# 3 5 2 1 4
def cum(i):
    res = 0
    while i>0:
        res += bit[i]
        i -= i&-i
    return res

def add(i, x):
    while i<=N:
        bit[i] += x
        i += i&-i

def pos(a):
    return i

def solve():
    global N,A,bit
    N = int(input())
    A = list(map(int, input().split()))
    bit = [0]*(N+1)

    B = list(set(A))
    B.sort()
    B = [-1] + B

    res = 0
    for i in range(N):
        j = bisect_left(B, A[i])
        res += cum(j)
        add(j, 1)

    print(N*(N-1)//2-res)

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
    except:
        pass
    solve()
# vim: set foldmethod=marker:}}}
ab=[]
n,m = map(int,input().split())

for i in range(m):
    ab=(map(int,input().split()))

abr=[]
enabled=[]
removed=[]
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    enabled.append(False)
    removed.append(False)

res=0
for i in range(n):
    for j in range(len(abr)):
        if i == abr[j][0] and not removed[j]:
            enabled[j]=True
    for j in range(len(abr)):
        if i == abr[j][-1]:
            res+=1
            for k in range(len(abr)):
                if enabled[j]:
                    enabled[j]=False
                    removed[j]=True
print(res)

### FIXED CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)
A =int(input())
B=input()
c=int(input())
d=B[c]
E=""
for i in range(A):
    if B[i]==d:
        E=E+d
    else:
        E=E+"*"
print(E)

### FIXED CODE ###

A =int(input())
B=input()
c=int(input())
d=B[c-1]
E=""
for i in range(A):
    if B[i]==d:
        E=E+d
    else:
        E=E+"*"
print(E)
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = list(set(a))
N = len(a)
for k in range(N):
  a[k] //= 2


count = 0
foo = 1

while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

baisu = []

a.sort()



import math
lcm = a[0]
for k in range(1, N):
  lcm = lcm * a[k] // math.gcd(lcm, a[k])
lcm = np.lcm(a)
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)



### FIXED CODE ###

N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] //= 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

import math
lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // math.gcd(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)
N=int(input())
for i in range(1,10):
  if N/i==N//i and N/i<10:
    print("Yes")
    sys.exit()
  else:
    print("No")

### FIXED CODE ###

import sys
 
N=int(input())
for i in range(1,10):
  if N/i==N//i  and N/i<10:
    print("Yes")
    sys.exit()
print("No")
N = int(input())
liss = {}
for i in range(N):
  s = input()
  a = sorted(s)
  if a in liss:
    liss[a] += 1
  else:
    liss[a] = 1

ans = 0
for cc in liss:
  ans = ans + (liss[cc] * (liss[cc] - 1) / 2)
print(int(ans))


### FIXED CODE ###

N = int(input())
liss = {}
for i in range(N):
  s = input()
  a = "".join(sorted(s))
  if a in liss:
    liss[a] += 1
  else:
    liss[a] = 1

ans = 0
for cc in liss:
  ans = ans + (liss[cc] * (liss[cc] - 1) / 2)
print(int(ans))
from collections import deque

h, w = map(int, input().split())
inf = 10 ** 6
a = [[0] * (w + 2), *[[0] + [inf] * w + [0] for _ in range(h)], [0] * (w + 2)]
d = deque()

for i in range(h):
    for j, k in enumerate(input()):
        if k == "#":
            a[i + 1][j + 1] = 0
            d.append((i + 1, j + 1))

stp = ((0, 1), (0, -1), (1, 0), (-1, 0))
res = 0

while d:
    x, y = d.popleft()
    for k, l in stp:
        nx, ny = x + k, y + l
        if a[x][y] + 1 < a[nx][ny]:
            a[nx][ny] = a[x][y] + 1
            res = max(res, a[nx][ny])
            d.append((nx, ny))
print(res)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
inf = 10 ** 6
a = [[0] * (w + 2)] + [[0] + [inf] * w + [0] for _ in range(h)] + [[0] * (w + 2)]
d = deque()

for i in range(h):
    for j, k in enumerate(input()):
        if k == "#":
            a[i + 1][j + 1] = 0
            d.append((i + 1, j + 1))

stp = ((0, 1), (0, -1), (1, 0), (-1, 0))
res = 0

while d:
    x, y = d.popleft()
    for k, l in stp:
        nx, ny = x + k, y + l
        if a[x][y] + 1 < a[nx][ny]:
            a[nx][ny] = a[x][y] + 1
            res = max(res, a[nx][ny])
            d.append((nx, ny))
print(res)
import math
n = int(input())
f = [0] * n
sqrt_n = int(math.sqrt(n)) +1
for i in range(n) :
    for x in range(1,sqrt_n) :
        for y in range(1,sqrt_n) :
            for z in range(1,sqrt_n) :
                if x*x+y*y+z*z+x*y+y*z+z*x == i+1 :
                    f[i] += 1
for _ in range(n) :
    print(f[_])


### FIXED CODE ###

l, r, d = map(int, input().split())
count = 0
for i in range(l,r+1) :
    if i%d == 0 :
        count += 1
print(count)
import math

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

print((a*b)//math.gcd(a, b))


### FIXED CODE ###

def yu(x, y):
    min_v = min(x, y)
    max_v = max(x, y)

    mod = max_v % min_v
    if mod != 0:
        min_v = yu(min_v, mod)
    return min_v


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

print(a*b//yu(a, b))
input_=Input.split('\n')
A,B=input_[0].split()
A=int(A)
B=int(B.replace('.', ''))
print(A,B)
print(int(A*B//100))

### FIXED CODE ###

A,B=input().split()
A=int(A)
B=int(B.replace('.', ''))
print(int(A*B//100))
S = input()


l = 0
r = len(S)-1
cnt = 0
while l != r:
    if S[l] == S[r]:
        l += 1
        r -= 1
    else:
        if S[l] == "x":
            #末尾にxを追加し削除
            l += 1
            cnt += 1
        elif S[r] == "x":
            r -= 1
            cnt += 1
        else:
            print(-1)
            exit()


print(cnt)

### FIXED CODE ###

S = input()


l = 0
r = len(S)-1
cnt = 0
while l < r:
    #print(l,r)
    if S[l] == S[r]:
        l += 1
        r -= 1
    else:
        if S[l] == "x":
            #末尾にxを追加し削除
            l += 1
            cnt += 1
        elif S[r] == "x":
            r -= 1
            cnt += 1
        else:
            print(-1)
            exit()


print(cnt)
n = input()
l = list(map,input().split())
print(sum(l)-n)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
print(sum(l)-n)
a,b = int(input())
ans = 0
for i in range(2):
  if a > b:
    ans = a+ans
    a = a-1
  else:
    ans = b+ans
    b = b-1
    
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())
s = 0
for i in range(2):
    if a >= b:
        s += a
        a -= 1
    else:
        s += b
        b -= 1

print(s)
s = list(input())
if s[2] = s[3] and s[4] = s[5]:
  print("Yes")
  
else:
  print"No")

### FIXED CODE ###

s =list(input())
if s[2] == s[3] and s[4] == s[5]:
  print("Yes")
  
else:
  print("No")
h, w = map(int,input().split())
grid = []
grid.append('#' * (w+2))
for _ in range(h):
    grid.append('#' + input().rstrip() + '#')
grid.append('#' * (w+2))
            
from collections import deque
import sys
sys.setrecursionlimit(1000000)


def flatten_2dim(array):
    return [item for sublist in array for item in sublist]
def all_argmax_2dim(array):
    flat_array = flatten_2dim(array)

    row_num = len(array)
    max_value = max(flat_array)

    for i, elem in enumerate(flat_array):
        if elem == max_value:
            yield i // row_num, i % row_num

maxstep = 0
flag = 0
step = [[-1] * (w+2) for _ in range(h+2)]
def bfs():
    global maxstep

    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    
    que = deque([])
    que.append((s_y, s_x))
    step[s_y][s_x] = 0
    
    while que:
        y, x = que.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if step[ny][nx] == -1 and grid[ny][nx] != "#":
                que.append((ny, nx))
                step[ny][nx] = step[y][x] + 1
    if flag == 0:
        maxstep = max(flatten_2dim(step))
    else:
        maxstep = max(max(flatten_2dim(step)), maxstep)
    
for i in range(h+2):
    for j in range(w+2):
        if grid[i][j] == ".":
            s_y, s_x = i, j
            break
bfs()
flag = 1
li = []
for argmax in all_argmax_2dim(step):
    li.append(argmax)

for s_y, s_x in li:
    bfs()
for argmax in all_argmax_2dim(step):
    li.append(argmax)
for s_y, s_x in li:
    bfs()   
print(maxstep)

### FIXED CODE ###

h, w = map(int,input().split())
grid = []
grid.append('#' * (w+2))
for _ in range(h):
    grid.append('#' + input().rstrip() + '#')
grid.append('#' * (w+2))
            
from collections import deque
import sys
sys.setrecursionlimit(1000000)


def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

maxstep = 0
step = [[-1] * (w+2) for _ in range(h+2)]
def bfs():
    global maxstep
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    
    que = deque([])
    que.append((s_y, s_x))
    step[s_y][s_x] = 0
    
    while que:
        y, x = que.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if step[ny][nx] == -1 and grid[ny][nx] != "#":
                que.append((ny, nx))
                step[ny][nx] = step[y][x] + 1

    maxstep = max(max(flatten_2dim(step)), maxstep)
    
for i in range(h+2):
    for j in range(w+2):
        if grid[i][j] == ".":
            s_y, s_x = i, j
            bfs()
            step = [[-1] * (w+2) for _ in range(h+2)]
print(maxstep)
N = int(input())
if N == 1:
    print(0)
else:
    result = 0
    for i in range(len(factorization(N))):
        tempnumber = factorization(N)[i][1]
        plusnumber = 1
        while tempnumber > 0:
            tempnumber -= plusnumber
            result += 1
            plusnumber += 1
    print(result)

### FIXED CODE ###

def factorization(n):
    arr = []
    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])

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

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

    return arr
N = int(input())
if N == 1:
    print(0)
else:
    result = 0
    for i in range(len(factorization(N))):
        tempnumber = factorization(N)[i][1]
        plusnumber = 1
        while tempnumber > 0:
            result += 1
            plusnumber += 1
            tempnumber -= plusnumber
    print(result)
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
cnt = 0
check = 0
ans = 1

a.sort(reverse=True)
for i in range(n - 1):
    if a[cnt] == a[cnt + 1]:
        cnt += 2
        check += 1
        ans *= a[cnt]
        if check == 2:
            print(ans)
            exit()
    else:
        cnt += 1

    if cnt == n - 1:
        break
print(0)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
cnt = 0
check = 0
ans = 1

a.sort(reverse=True)
for i in range(n - 1):
    if a[cnt] == a[cnt + 1]:
        check += 1
        ans *= a[cnt]
        cnt += 2
        if check == 2:
            print(ans)
            exit()
    else:
        cnt += 1

    if cnt == n - 1:
        break
print(0)
while True:
  must1 = 1
  for mi in range(m):
    onoff = 0
    for ni in range(n):
      onoff += li[mi][ni]*yyy[ni]
    should1 = bool(onoff%2 == p[mi])
    must1 *= should1
  if must1 == 1:
    score += 1
  yyy[0] += 1
  for ni in range(n-1):
    if yyy[ni] == 2:
      yyy[ni] = 0
      yyy[ni+1] += 1
  if yyy[n-1] == 2:
    break
print(score)

### FIXED CODE ###

n,m = map(int,input().split())
ls = []
for _ in range(m):
  tmp = list(map(int,input().split()))[1:]
  lls = []
  for i in range(1,n+1):
    lls += [int(i in tmp)]
  ls += [lls]
p = list(map(int,input().split()))
count = 0
yyy = [0]*n
while True:
  if yyy[-1] == 2:
    break
  dd = 0
  for mi in range(m):
    c = 0
    for ni in range(n):
      c += ls[mi][ni] * yyy[ni]
    d = c%2
    dd += 1-int(d==p[mi])
  if dd == 0:
    count += 1
  yyy[0] += 1
  for j in range(0,n-1):
    if yyy[j] == 2:
      yyy[j] = 0
      yyy[j+1] += 1
print(count)
import re
ans = max(map(len, re.findall("[ACGT]+", input())))
print(ans)

### FIXED CODE ###

S = str(input())
m=0
point=0
for i in S:
    if i == "A" or i == "G" or i == "C" or i == "T":
        point+=1
    else:
        point*=0
    m = max(m, point)
print(m)
print(sum(range(1, N)))

### FIXED CODE ###

N = int(input())
print(N * (N - 1) // 2)
# -*- coding: utf-8 -*-

r, c = list(map(int, input().split()))
a = []
line_sum = 0

for i in range(r):
    a.append(list(map(int, input().split())))

for i in range(r):
    for j in range(c + 1):
        if j == c:
            print('{0}'.format(sum(a[i])))
            line_sum += sum(a[i])
        else:
            print('{0} '.format(a[i][j]), end='')

for i in range(c + 1):
    column_sum = 0
    for j in range(r):
        column_sum += a[j][i]

    print('{0} '.format(column_sum), end='')

print(line_sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-

r, c = list(map(int, input().split()))
a = []
line_sum = 0

for i in range(r):
    a.append(list(map(int, input().split())))

for i in range(r):
    for j in range(c + 1):
        if j == c:
            print('{0}'.format(sum(a[i])))
            line_sum += sum(a[i])
        else:
            print('{0} '.format(a[i][j]), end='')

for i in range(c):
    column_sum = 0
    for j in range(r):
        column_sum += a[j][i]

    print('{0} '.format(column_sum), end='')

print(line_sum)
import sys
n,y = map(int, input().split())

for a in range(n+1):
  for b in range(n+1-a):
    if a * 10000 + b * 5000 + (n-a-b) * 1000 == y:
		print(str(a) + ' ' + str(b) + ' ' + str(c))
		sys.exit()

print('-1 -1 -1')
sys.exit()

### FIXED CODE ###

import sys

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

for a in range(n+1):
	for b in range(n+1-a):
		c = n - a - b
		if (a * 10000 + b * 5000 + c * 1000 == y):
				print(str(a) + ' ' + str(b) + ' ' + str(c))
				sys.exit()
	
print('-1 -1 -1')
sys.exit()
import math
def lcm(a,b):
    return int(a*b/math.gcd(a,b))


def div(n,divn):
    #1からnまでの中で、divnで割り切れる数の数を示す
    return n//divn

def divor(n,div1,div2):
    #1からnまでの中で、div1,div2のどちらかで割り切れる数の数を示す
    return div(n,div1)+div(n,div2)-div(n,lcm(div1,div2))
def nondivor(n,div1,div2):
    #１からnまでの中で、div1,div2のどちらでも割り切れない数の数を示す
    return n-divor(n,div1,div2)


a,b,c,d=[int(i) for i in input().split()]


print(nondivor(b,c,d)-nondivor(a-1,c,d))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

from fractions import gcd
def lcm(a,b):
    return int(a*b/gcd(a,b))


def div(n,divn):
    #1からnまでの中で、divnで割り切れる数の数を示す
    return n//divn

def divor(n,div1,div2):
    #1からnまでの中で、div1,div2のどちらかで割り切れる数の数を示す
    return div(n,div1)+div(n,div2)-div(n,lcm(div1,div2))
def nondivor(n,div1,div2):
    #１からnまでの中で、div1,div2のどちらでも割り切れない数の数を示す
    return n-divor(n,div1,div2)


a,b,c,d=[int(i) for i in input().split()]


print(nondivor(b,c,d)-nondivor(a-1,c,d))
N, K = map(int, input().split())
sunukes = [0 for k in range(N)]
for k in range(K):
  d = int(input())
  A = list(map(int, input().split()))
  for a in A:
    sunukes[a] += 1
  assert len(A) == d
print(len([k for k in sunukes if k == 0]))

### FIXED CODE ###

N, K = map(int, input().split())
sunukes = [0 for k in range(N)]
for k in range(K):
  d = int(input())
  A = list(map(int, input().split()))
  for a in A:
    sunukes[a-1] += 1
  assert len(A) == d
print(len([k for k in sunukes if k == 0]))
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    sa = sum(a)
    for i in range(k):
        mov = [0]*n
        for i,ai in enumerate(a):
            if i-ai >= 0:
                mov[i-ai] += 1
            else:
                mov[0] += 1
            if i+ai+1 < n:
                mov[i+ai+1] -= 1
        na = a*1
        sna = sa
        a[0] = mov[0]
        sa = mov[0]
        for i in range(1,n):
            a[i] = a[i-1]+mov[i]
            sa += a[i]
        if sna == sa:
            break
    print(" ".join(map(str,a)))

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    sa = sum(a)
    for i in range(k):
        mov = [0]*n
        for i,ai in enumerate(a):
            if i-ai >= 0:
                mov[i-ai] += 1
            else:
                mov[0] += 1
            if i+ai+1 < n:
                mov[i+ai+1] -= 1
        na = a*1
        sna = sa
        a[0] = mov[0]
        sa = mov[0]
        for i in range(1,n):
            a[i] = a[i-1]+mov[i]
            sa += a[i]
        if sna == sa:
            break
    print(" ".join(map(str,a)))

    return

if __name__ == '__main__':
    main()