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

#!/usr/bin/env python3
import sys

def solve(N: int):
    n = list(map(int,list(str(N))))
    pay = []
    kuriage = 0
    LEN = len(n)
    pay_count = 0
    oturi_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    oturi_count += 10-(n[i]+kuriage)
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    oturi_count += 10-(n[i]+kuriage)
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                oturi_count += 10-(n[i]+kuriage)
                kuriage = 1

    if kuriage == 1:
        pay_count += 1
    
    print(pay_count+oturi_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: str):
    n = list(map(int,list(N)))
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay_count += 10-(n[i]+kuriage)
                kuriage = 1

    if kuriage == 1:
        pay_count += 1
    print(pay_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)
    solve(N)

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

A,B,K=map(int,input().split())
for i in range(K):
  if A>=1:
    A-=1
  elif B>=1:
    B-=1
print(A,B)
    

### FIXED CODE ###

A,B,K=map(int,input().split())
a=max(A-K,0)
K-=A-a
b=max(B-K,0)
print(a,b)
### BUGGY CODE ###

data = input()
score = 0
size = len(data)

def get_score(data):
    global score
    for i in range(0, size-1):
        ab = data[i:i+2]

        if ab == '10' or ab =='01':
            score += 2
            data = data[:i] + data[i+2:]
            break

    if data == '' or set(data) == {'1'} or set(data) == {'0'}:
        return
    get_score(data)

get_score(data)
print(score)

### FIXED CODE ###

data=input()
n1 = data.count('1')
n0 = data.count('0')
print(min(n1, n0) * 2)
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def factorize(n):
    """
    nの値を素因数分解し、素因数とその指数をtupleにまとめたリストを返す
    e.g.
    [(2, 2), (5, 1)]
    """
    b = 2
    fct = []
    while b * b <= n:
        cnt = 0
        while n % b == 0:
            cnt += 1
            n //= b
        if cnt > 0:
            fct.append((b, cnt))
        b += 1
    if n > 1:
        fct.append((n, 1))
    return fct


from collections import defaultdict

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

    d = defaultdict(int)
    for a in A:
        for num, f in factorize(a):
            d[num] = max(d[num], f)

    l = 1
    for num, f in d.items():
        l *= num ** f

    ans = 0
    for a in A:
        ans += l // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


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

    l = A[0]
    for i in range(1, N):
        l = l * A[i] // gcd(l, A[i])

    print(sum([l // a for a in A]) % MOD)


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

N = int(input())
# とりあえず先頭の性別を取得する
print(0)
begin = input()

l, r = 0, N
while r - l > 1:
    mid = (l+r)//2
    print(mid)
    sex = input()
    if sex != begin:
        r = mid
    else:
        l = mid

print(l)


### FIXED CODE ###

N = int(input())
# とりあえず先頭の性別を取得する
print(0)
begin = input()

l, r = 0, N
while r - l > 1:
    mid = (l+r)//2
    print(mid)
    sex = input()
    if sex == "Vacant":
        l = mid
        break
    elif mid % 2 == 0:
        if sex != begin:
            r = mid
        else:
            l = mid
    else:
        if sex != begin:
            l = mid
        else:
            r = mid

print(l)
### BUGGY CODE ###

import math as np
K=int(input())
sum_gcd=[]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum_gcd.append(np.gcd(np.gcd(i,j),k))
print(sum(sum_gcd))

### FIXED CODE ###

import math as np
K=int(input())
P=0
for i in range(1,K+1):
    for j in range(1,K+1):
        l=np.gcd(i,j)

        for k in range(1,K+1):
            m=np.gcd(l,k)
            P=m+P
print(P)
### BUGGY CODE ###

from collections import deque
import bisect

n=int(input())

graph = [[] for _ in range(n+1)]

A=[0]+list(map(int, input().split()))

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

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 1

d = deque()
d.append((1,[0,A[1]]))

def update(dp,AA):
    ndp=dp.copy()
    if ndp[-1]<AA:
        ndp.append(AA)
    else:
        bis=bisect.bisect_left(ndp, AA)
        ndp[bis]=AA
    return ndp

while d:
    v,dp = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        newdp=update(dp,A[i])
        dist[i] = len(newdp)-1
        d.append((i,newdp))

ans = dist[1:]
print(*ans, sep="\n")

### FIXED CODE ###

from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

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

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")
### BUGGY CODE ###

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

R = [v for v,i in enumerate(S) if i == 'R']
G = [v for v,i in enumerate(S) if i == 'G']
B = [v for v,i in enumerate(S) if i == 'B']

c = 0
for i in R:
    for j in G:
        for k in B:
            t = [i,j,k]
            t.sort()
            if not t[0] + t[2] == 2 * t[1]:
                c += 1

print(c)

### FIXED CODE ###

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

R = set([v for v,i in enumerate(S) if i == 'R'])
G = set([v for v,i in enumerate(S) if i == 'G'])
B = set([v for v,i in enumerate(S) if i == 'B'])
t = len(B)
c = 0
for i in R:
    for j in G:
        d = [2* i -j,2 * j - i,(i+j)/2]
        for a,s in enumerate(d):
            if s in B:
                c -= 1
        c += t

print(c)
### BUGGY CODE ###

import sys

def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = 0
    for b in xy[a]:
      num = cal(b)
      dp[b] = num
      if num+1 > ans:
        ans = num+1
    return ans
  return 0

if __name__ == "__main__":
  sys.setrecursionlimit(100000)
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()



### FIXED CODE ###

import sys

def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = 0
    for b in xy[a]:
      if dp[b]:
        num = dp[b]
      else:
        num = cal(b)
        dp[b] = num
      if num+1 > ans:
        ans = num+1
    return ans
  return 0

if __name__ == "__main__":
  sys.setrecursionlimit(100000)
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()
### BUGGY CODE ###

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

dp = [0] * n

for i in range(1, n):
    min_cost = 1e19
    for j in range(1, k + 1):
        if i - j >= 0:
            cost = dp[i - j] + abs(hs[i] - hs[i - j])
            min_cost = min(cost, min_cost)
    dp[i] = min_cost

print(dp[n - 1])


### FIXED CODE ###

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

dp = [0] * n

for i in range(1, n):
    costs = []
    for j in range(1, k + 1):
        if i - j >= 0:
            cost = dp[i - j] + abs(hs[i] - hs[i - j])
            costs.append(cost)
    dp[i] = min(costs)

print(dp[n - 1])
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
BC=n3(m)

A.sort()

for b,c in BC:
    i = bisect_left(A,c)
    if i<=b:
        A=[c]*i+A[i:]
    else:
        A=[c]*b+A[b:]
    A.sort()
print(sum(A))

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
BC=t3(m)

heapify(A)
BC.sort(key=lambda x:-x[1])

D=[]
for b,c in BC:
    D.extend([c]*b)
    if len(D)>=n:
        break
D=D[:n]


for d in D:
    a=heappop(A)
    if a>=d:
        heappush(A,a)
        break;
    else:
        heappush(A,d)

print(sum(A))
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))

    seen = [False] * (N+1)
    arr = [1]
    seen[1] = True
    while True:
        next = A[arr[-1]]
        if seen[next]:
            arr.append(next)
            break
        arr.append(next)
        seen[next] = True

    x = int(math.log2(K)) + 1
    dub = [[0] * (N+1) for _ in range(x)]
    for idx, a in enumerate(arr[:-1]):
        dub[0][a] = arr[idx+1]
    for d in range(1,x):
        for k in range(1, N+1):
            tmp = dub[d - 1][k]
            #if tmp == 0:continue
            dub[d][k] = dub[d-1][tmp]

    ret = 1
    while K:
        d = int(math.log2(K))
        K -= 1 << d
        ret = dub[d][ret]
    print(ret)

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))
    perm = [1]
    seen = [[-1, False] for _ in range(N+1)]
    seen[1] = [1,True]
    l = 1
    while True:
        v = perm[-1]
        idx, boo = seen[A[v]]
        if boo: break
        l += 1
        perm.append(A[v])
        seen[A[v]] = [l,True]

    if K <= idx -1:
        print(perm[K])
        return None
    K -= idx - 1
    perm = perm[idx-1:]
    print(perm[K % len(perm)])

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

n = int(input())
x = list(map(int, input().split()))
def median(list):
    L = sorted(list)
    n = len(L)
    m = int(n/2)
    if n % 2 == 0:
        return (L[m - 1] + L[m]) / 2
    else:
        return L[(n - 1) // 2]
for i in range(n):
    b = x[:i] + x[i+1:]
    print(median(b))

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
def median(L):
    L = sorted(L)
    n = len(L)
    m = int(n/2)
    if n % 2 == 0:
        return (L[m - 1] + L[m]) / 2
    else:
        return L[(n - 1) // 2]
x_median = median(x)
l = median(sorted(x)[:-1])
r = median(sorted(x)[1:])
for i in range(n):
    if x[i] > x_median:
        print(l)
    else:
        print(r)
### BUGGY CODE ###

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

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

if a<= 10**18:
  print(a)
else:
  print(-1)

### FIXED CODE ###

n = int(input())
values =list(map(int, input().split()))
a=1
t = 10**18
for i in range(n):
  if values[i] == 0:
    a = 0
    break
  if a > t:
    continue
  else:
    a=a*values[i]
 
if a <= t:
  print(a)
else:
  print(-1)
### BUGGY CODE ###

n=int(input())
a=input().split()
ans=1

for i in range(n):
  ans*=int(a[i])
  
if ans>10**18:
  print("-1")
else:
  print(str(ans))

### FIXED CODE ###

n=int(input())
a=input().split()
ans=1

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

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

def main():
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    def init(n_):
        #簡単にするために2のべき乗に揃える
        n = 1
        while n < n_:
            n *= 2
        return n

    #初期化
    N = int(input())
    n = init(N) + 1
    data = [0] * (2 * MAX_N - 1)

    def update(k, a):
        k += n - 1
        data[k] = a
        while k > 0:
            k = (k - 1) // 2
            data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k = 0, l = 0, r = n):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return data[k]
        else:
            v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
            v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
            return max(v1, v2)

    def initialize(A): #リストAを与えて初期化する
        for i, a in enumerate(A):
            data[i + n - 1] = a
        for i in range(N + n - 1, 0, -2):
            tmp = i
            tmp = (tmp - 1) //2
            data[tmp] = max(data[tmp * 2 + 1], data[tmp * 2 + 2])

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

    ans = 0
    for i in range(N):
        # h = int(input())
        # a = int(input())
        h = H[i]
        a = A[i]
        tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(h, tmp + a)
        ans = max(ans, tmp + a)
        # print (data)

    print (ans)

    # print (update(1, 1))
    # print (update(2, 5))
    # print (query(1, 2))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

n, x, m = map(int, input().split())
a = x
mod = [a]
loop = []
cnt = 0
while cnt < n:
    a = a**2 % m
    if a in mod:
        i = mod.index(a)
        before = mod[:i]
        loop = mod[i:]
        break
    mod.append(a)
    cnt += 1

length = len(loop)
if length == 0:
    print(sum(mod[:n]))
else:
    t = (n-i)//length
    amari = (n-i) % length
    ans = sum(before) + t * sum(loop) + sum(loop[:amari])
    print(ans)


### FIXED CODE ###

n, x, m = map(int, input().split())
a = x
dup = [0]*(10**5+10)
mod = [a]
loop = []
cnt = 0
while cnt < n:
    a = a**2 % m
    if dup[a]==1:
        i = mod.index(a)
        before = mod[:i]
        loop = mod[i:]
        break
    mod.append(a)
    dup[a] = 1
    cnt += 1

length = len(loop)
if length == 0:
    print(sum(mod[:n]))
else:
    t = (n-i)//length
    amari = (n-i) % length
    ans = sum(before) + t * sum(loop) + sum(loop[:amari])
    print(ans)
### BUGGY CODE ###

import heapq
n, q = map(int, input().split())
g = [[] for i in range(n+1)]
point = [0 for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    point[p] += x

q = [[1,0]]
heapq.heapify(q)
while len(q)!=0:
    now = heapq.heappop(q)
    point[now[0]] += point[now[1]]
    for i in range(len(g[now[0]])):
        if g[now[0]][i]==now[1]:
            continue
        heapq.heappush(q,[g[now[0]][i],now[0]])

for i in range(1, n+1):
    print(point[i], end='')
    if i!=n:
        print(' ', end='')
print('')


### FIXED CODE ###

def main():
    from collections import deque
    n, q = map(int, input().split())
    g = [[] for i in range(n+1)]
    point = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    for i in range(q):
        p, x = map(int, input().split())
        point[p] += x

    q = deque([[1,0]])
    for j in range(n):
        now = q.pop()
        point[now[0]] += point[now[1]]
        for i in g[now[0]]:
            if i==now[1]:
                continue
            q.append([i,now[0]])
    for i in range(1, n+1):
        print(point[i], end='')
        if i!=n:
            print(' ', end='')

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

M=10**9+7;B,W=map(int,input().split());F=[1];I=[1];p=q=0;C=lambda n,k:F[n]*pow(F[k]*F[n-k],M-2,M)if n>=k else 0
for i in range(1,B+W+1):F+=[F[-1]*i];I+=[I[-1]+I[-1]%2*M>>1];print((1-p+q)*I[1]%M);p+=C(i-1,B-1)*I[i];q+=C(i-1,W-1)*I[i]

### FIXED CODE ###

U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
B, W = map(int, input().split())
p = 0
q = 0
for i in range(1, B+W+1):
  ans = 1 - p + q
  ans %= MOD
  ans *= pow(2, MOD-2, MOD)
  ans %= MOD
  print(ans)
  p += comb(i-1, B-1) * pow(pow(2, i, MOD), MOD-2, MOD) % MOD
  p %= MOD
  q += comb(i-1, W-1) * pow(pow(2, i, MOD), MOD-2, MOD) % MOD
  q %= MOD
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
#print(A,B,C,D)
count = 0
for i in range(A,B+1):
    if i%C != 0 and i%D != 0:
        count+=1
print(count)

### FIXED CODE ###

from fractions import gcd

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

adivc = A//C
if A%C != 0:
    adivc = A//C + 1
bdivc = B//C
countC = bdivc - adivc + 1

adivd = A//D
if A%D != 0:
    adivd = A//D + 1
bdivd = B//D
countD = bdivd - adivd + 1

lcm = (int)(C * D / gcd(C, D))
adivlcm = A // lcm
if A%lcm != 0:
    adivlcm = A // lcm + 1
bdivlcm = B // lcm
countlcm = bdivlcm - adivlcm + 1

print(B-A+1-(countC+countD-countlcm))
### BUGGY CODE ###

h,w,m = map(int,input().split())
dich = {}
dicw = {}
 
havew = {}
for _ in range(m):
    h,w = map(int,input().split())
    if h in dich:
        dich[h] += 1
        havew[h].append(w)
    else:
        dich[h] = 1
        havew[h] = [w]
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1
 
dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])
 
# print(havew)
#
# print(dichi)
# print(dicwi)
 
hmax = dichi[0][1]
wmax = dicwi[0][1]
 
for hs in dichi:
    if hs[1] != hmax:
        break
    for ws in dicwi:
        if ws[1] != wmax:
            break
        if ws[0] not in havew[hs[0]]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)

### FIXED CODE ###

import bisect
horigin,worigin,m = map(int,input().split())
dich = {}
dicw = {}
 
havew = {}
for _ in range(m):
    h,w = map(int,input().split())
    if h in dich:
        dich[h] += 1
        havew[h].append(w)
    else:
        dich[h] = 1
        havew[h] = [w]
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1
 
dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])
 
# print(havew)
#
# print(dichi)
# print(dicwi)
 
hmax = dichi[0][1]
wmax = dicwi[0][1]
 
for hs in dichi:
    if hs[1] != hmax:
        break
    wlis = sorted(havew[hs[0]])
    for ws in dicwi:
        if ws[1] != wmax:
            break
        idx = bisect.bisect_left(wlis, ws[0])
        if idx >= len(wlis):
            print(hmax+wmax)
            exit()
        if ws[0] != wlis[idx]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)