Harryxun/stf_run huggingface dataset:
N,W=(int(x) for x in input().split())
t=0
weight=[0]*N
value=[0]*N
while t<N:
    v,w=(int(x) for x in input().split())
    value[t]=v
    weight[t]=w
    t=t+1
def kotae(N,W):
    dp=[[0 for i in range(110)] for j in range(110)]
    i=0
    while i<N:
        wei=0
        while wei<W+1:
            if wei>=weight[i]:
                dp[i+1][wei]=max(dp[i][wei],dp[i][wei-weight[i]]+value[i])
            else:
                dp[i+1][wei]=dp[i][wei]
            wei=wei+1
        i=i+1
    return dp[N][W]
print(kotae(N,W))


### FIXED CODE ###

N,W=(int(x) for x in input().split())
value=[]
weight=[]
for n in range(N):
    a,b=(int(x) for x in input().split())
    value.append(a)
    weight.append(b)
def knap(N,W,value,weight):
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N+1):
        for w in range(W+1):
            if i>0:
                if weight[i-1]<=w:
                    dp[i][w]=max(dp[i-1][w],dp[i-1][w-weight[i-1]]+value[i-1])
                else:
                    dp[i][w]=dp[i-1][w]
    return dp[N][W]
print(knap(N,W,value,weight))
H, W = map(int, input().split())
S = [list(map(int, input().split())) for i in range(H)]
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

for i in range(H):
  for j in range(W):
    if s[i][j] == '.':
      cnt = 0
      for n in range(8):
        ni = i + dx
        nj = j + dy
        if ni < 0 or ni >= H:
          continue
        if nj < 0 or nj >= W:
          continue
        if s[ni][nj] == '#':
          cnt += 1
      S[i][j] = cnt

print(S)
    


### FIXED CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(list(input()))
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    cnt = 0
    for n in range(8):
      ni = i + dx[n]
      nj = j + dy[n]
      if ni < 0 or H <= ni or nj < 0 or W <= nj:
        continue
      if S[ni][nj] == '#':
        cnt += 1
    S[i][j] = str(cnt)


    
for i in range(H):
    print("".join(S[i]))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import gcd, floor

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
cumsum = a[0]
for i in range(1, n):
    cumsum = gcd(cumsum, a[i])
for i in range(n):
    a[i] //= cumsum
lcm_memo = a[0]
for i in range(1, n):
    lcm_memo = lcm_memo * a[i] // gcd(lcm_memo, a[i])
print(floor(m / lcm_memo) - floor(m / (lcm_memo * 2)))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from fractions import gcd

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
for i in range(n):
    a[i] //= 2
lcm_memo = 1
for i in range(n):
    lcm_memo *= a[i] // gcd(lcm_memo, a[i])
    if lcm_memo > m:
        print(0)
        exit()
for i in range(n):
    if (lcm_memo // a[i]) % 2 == 0:
        print(0)
        exit()
print(1 + (m - lcm_memo) // (lcm_memo * 2))
N, A = map(int, input().split())
lst = [int(x) - A for x in input().split()]
dp = [[0] * (2 * N + 1) for _ in range(N + 1)]
dp[0][1 * N] = 1
for i in range(N):
    for j in range(1, 2 * N + 1 - 1):
        dp[i + 1][j] = dp[i][j] + dp[i][j - lst[i]]
print(dp[N][1 * N] - 1)

### FIXED CODE ###

N, A = map(int, input().split())
lst = [int(x) - A for x in input().split()]
dp = [[0] * (100 * N + 1) for _ in range(N + 1)]
dp[0][50 * N] = 1
for i in range(N):
    for j in range(50, 100 * N + 1 - 50):
        dp[i + 1][j] = dp[i][j] + dp[i][j - lst[i]]
print(dp[N][50 * N] - 1)
n = int(input())
h = list(map(int, input().split()))
max_count = 0
count = 0
for i in range(1, n):
    if h[i - 1] >= h[i]:
        count += 1
    else:
        if max_count < count:
            max_count = count
        count = 0
if max_count < count:
    max_count = count
print(max_count)

### FIXED CODE ###

s = input()
t = input()
count = 0
for i in range(len(s)):
    if s[i] == t[i]:
        count += 1
print(count)
#!/usr/bin/env python3
import sys
from collections import defaultdict
from collections import deque
INF = float("inf")

MOD = 1000000007  # type: int


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def solve(N: int, x: "List[int]", y: "List[int]"):

    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)

    white = [-1]*N
    black = [-1]*N

    def rec(node, pre):
        if white[node] > 0:
            return white[node], black[node]

        # nodeを黒と塗る場合
        bbb = 1
        www = 1
        for t, _ in g.E[node]:
            if t != pre:
                w, b = rec(t, node)
                bbb *= w
                www *= (w+b)
        black[node] = bbb % MOD
        white[node] = www % MOD
        return white[node], black[node]

    w, b = rec(0, -1)
    print((w+b) % MOD)
    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
    x = [int()] * (N - 1)  # type: "List[int]"
    y = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def solve(N: int, x: "List[int]", y: "List[int]"):

    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)

    white = [-1]*N
    black = [-1]*N

    def rec(node, pre):
        if white[node] > 0:
            return white[node], black[node]

        # nodeを黒と塗る場合
        bbb = 1
        www = 1
        for t, _ in g.E[node]:
            if t != pre:
                w, b = rec(t, node)
                bbb *= w
                bbb %= MOD
                www *= (w+b) % MOD
                www %= MOD
        black[node] = bbb % MOD
        white[node] = www % MOD
        return white[node], black[node]

    w, b = rec(0, -1)
    print((w+b) % MOD)
    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
    x = [int()] * (N - 1)  # type: "List[int]"
    y = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()
friends=input()
friends.split(' ')
friends_all=friends[0]
cakes=input()
cakes.split(' ')
cakes_amount(sum(cakes))
person=friends+1
one_person=cakes_amount//person
if cakes_amount%person==0:
        pass
else:
        one_person+=1
print(one_person)



### FIXED CODE ###

friends=input()
friends=friends.split()
friends_all=friends[0]
person=int(friends_all)+1
cakes=input()
cakes_amount=0
for a in cakes.split():
        cakes_amount+=int(a)
one_person=cakes_amount//person

if cakes_amount%person!=0:
        one_person+=1
else:
        pass
print(one_person)
n, m = map(int, input().split())
a = list(map(int, input().split()))

x = [-float('inf')] * (n + 1)
x[0] = 0
l = [0] * (n + 1)
_c = [2,5,5,4,5,6,3,7,6]
c = dict()
for i in range(m):
    c[a[i]] = _c[a[i] - 1]
# print(c)

for i in range(1, n + 1):
    tmp_xl = []
    for digit in c.keys():
        left = i - c[digit]
        if left >= 0:
            tmp_xl.append([digit * (10 ** l[left]) + x[left], l[left] + 1])

    if len(tmp_xl):
        tmp_xl = sorted(tmp_xl, key=lambda x:x[0])
        x[i] = tmp_xl[-1][0]
        l[i] = tmp_xl[-1][1]
print(x[-1])


### FIXED CODE ###

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

x = [-float('inf')] * (n + 1)
x[0] = 0
l = [0] * (n + 1)
_c = [2,5,5,4,5,6,3,7,6]
c = dict()
for i in range(m):
    c[a[i]] = _c[a[i] - 1]

for i in range(1, n + 1):
    x_max = -float('inf')
    l_max = 0
    for digit in c.keys():
        left = i - c[digit]
        if left >= 0:
            tmp_x = digit * (10 ** l[left]) + x[left]
            tmp_l = l[left] + 1
            if tmp_x > x_max:
                x_max = tmp_x
                l_max = tmp_l

    x[i] = x_max
    l[i] = l_max
print(x[-1])
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    vector<double> e(n);
    for (int i = 0; i < n; i++) {
        int s = 0;
        for (int j = 1; j <= p[i]; j++) s+=j;
        e[i] = (double) s / p[i];
    }

    double curr = 0;
    for (int i = 0; i < k-1; i++) curr += e[i];
    double best = curr;
    for (int i = k-1; i < n; i++) {
        curr += e[i];
        best = max(best, curr);
        curr -= e[i-k+1];
    }
    cout << best << endl;
    
    return 0;
}

### FIXED CODE ###

def main():
    N, K  = map(int, input().split())
    P = list(map(int, input().split()))
    best = sum(P[:K]) # sum of first K terms
    curr = best # tmp var for iteration
    for i in range(N - K):
        curr += P[i+K] - P[i] # slide window
        best = max(best, curr)
    print((best + K) / 2) # based on n(n+1)/2 == sum(range(1, n))

if __name__ == '__main__':
    main()
s=input(s)
S=list(s)
b = len(S)
a =len(set(S))
if a==b: print("yes")
else: print("no")

### FIXED CODE ###

s=input()
S=set(s)
if len(s)==len(S): 
    print("yes")
else: 
    print("no")
n, m = map(int, input().split())
prime_list = [2]
for i in range(3, int(m // 2) + 1, 2):
    calc = True
    if m % i == 0:
        for j in prime_list:
            if (i % j != 0):
                continue
            else:
                calc = False
                break
        if calc:
            prime_list.append(i)
a = []
for prime in prime_list:
    while m % prime == 0:
        a.append(prime)
        m = int(m // prime)
import collections
k = collections.Counter(a)
b = list(k.values())
import math
ans = 1
for bb in b:
    ans *= math.factorial(bb + n - 1) % inf
    ans *= pow(math.factorial(bb), inf - 2, inf)
    ans *= pow(math.factorial(n - 1), inf - 2, inf)
    ans = ans % inf
print(ans)

### FIXED CODE ###

import copy
import math
import collections

inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_dict = {}
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    if 2 not in prime_dict.keys():
        prime_dict[2] = 1
    else:
        prime_dict[2] += 1
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        if i not in prime_dict.keys():
            prime_dict[i] = 1
        else:
            prime_dict[i] += 1
if m_copy != 1:
    if m_copy not in prime_dict.keys():
        prime_dict[m_copy] = 1
    else:
        prime_dict[m_copy] += 1
b = list(prime_dict.values())
ans = 1

dp = [[1 for _ in range(30)] for _ in range(n)]
for i in range(1, 30):
    for j in range(1,n):
        dp[j][i] = (dp[j - 1][i] + dp[j][i - 1]) % inf

for bb in b:
    ans *= dp[n - 1][bb]
    ans = ans % inf
print(ans)
import math

dp = [-1]*(100*1000+1)
tab = [[] for x in range(100*1000+1)]

def get_max(root):
    if(dp[root] > -1): return dp[root]
    
    mi = 0
    for nei in tab[root]:
        mi = max(mi,get_max(nei)+1)
    dp[root] = mi
    return dp[root]
def main():
    n,m = map(int,input().split())
    
    for x in range(m):
        a,b = map(int,input().split())
        a-=1;b-=1
        tab[a].append(b)
    
    for x in range(n):
        get_max(x) 
    
    print(max(dp))
main()

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(1000000)
dp = [-1]*(100*1000+1)
tab = [[] for x in range(100*1000+1)]

def get_max(root):
    if(dp[root] > -1): return dp[root]
    
    mi = 0
    for nei in tab[root]:
        mi = max(mi,get_max(nei)+1)
    dp[root] = mi
    return dp[root]
def main():
    n,m = map(int,input().split())
    
    for x in range(m):
        a,b = map(int,input().split())
        a-=1;b-=1
        tab[a].append(b)
    
    for x in range(n):
        get_max(x) 
    
    print(max(dp))
main()
import math
a, b, h, m = map(int,input().split())
fine = math.radians(30h - 11 * m / 2)
c = math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(fine))
print(c)


### FIXED CODE ###

import math
a, b, h, m = map(int,input().split())
fine = math.radians(30 * h - 11 * m / 2)
c = math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(fine))
print(c)
N = input()
A = list(map(int,input().split()))
raw =sum(A)
con = 0

for i in A:
    if A[con] > A[con+1]:
        A[con+1] =  A[con]
        
    if A[con+1] == A[-1]:
        break

    con += 1

print(A)
ans = sum(A) - raw
print(ans)

### FIXED CODE ###

N = input()
A = list(map(int,input().split()))
raw =sum(A)
con = 0

if len(A) == 1:
    print(0)
    
else:
    for i in A:
        if A[con] > A[con+1]:
            A[con+1] =  A[con]
        
        if A[con+1] == A[-1]:
            break

        con += 1

    ans = sum(A) - raw
    print(ans)
from math import sqrt
N, M = map(int, input().split())
D = [0]*(M+2); R = [0]*(M)
for i in range(N):
    l, r = map(int, input().split())
    D[1] += 1
    D[r+1] -= 1
    if l <= r-l+1:
        continue
    D[r-l+2] -= 1
    D[l] += 1

    left = r-l+2; right = l
    for k in range(2, int(sqrt(r))+1):
        l0 = max((l+k-1) // k, left); r0 = min((r // k + 1, right))
        if l0 < r0:
            D[l0] += 1
            D[r0] -= 1
        right = l0

print(*R, *D)
tmp = 0
for i in range(1, M+1):
    tmp += D[i]
    R[i-1] += tmp
print(*R, sep='\n')

### FIXED CODE ###

# seishin.py
N, M = map(int, input().split())
D = [[] for i in range(M+1)]
for i in range(N):
    l, r = map(int, input().split())
    D[r-l+1].append(l)

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def add(k, x):
    while k <= M+1:
        data[k] += x
        k += k & -k

C = N
ans = []
for d in range(1, M+1):
    for l in D[d]:
        add(l, 1)
        add(l+d, -1)
        C -= 1

    cnt = C
    i = d
    while i <= M:
        cnt += get(i)
        i += d
    ans.append(cnt)
print(*ans, sep='\n')
S = input()
T = input()
count = 0
for n in range(3):
  if S[n] = T[n]:
    count += 1
print(count)


### FIXED CODE ###

S = input()
T = input()
count = 0
for n in range(3):
  if S[n] == T[n]:
    count += 1
print(count)
import sys
import math
if N == 1:
	print(T[0])
	sys.exit()
def GCD(a,b):
	if b == 0:
		return a
	return GCD(b,a%b)

N = int(input())
T = [int(input()) for _ in range(N)]

def SKS(a,b):
	return (a*b)//GCD(a,b)

for i in range(1,N):
	if i == 1:
		temp = SKS(T[0], T[1])
		continue

	temp = SKS(temp, T[i])

print(temp)

### FIXED CODE ###

N = int(input())
T = [int(input()) for _ in range(N)]

def Eucrid(a,b):
	if b == 0:
		return a
	return Eucrid(b,a%b)


ans = 1
for i in range(N):
	ans = (ans * T[i]) // Eucrid(ans, T[i])

print(ans)
n = int(input());
s = input();

if n % 2 !== 0:
  print("No")
else:
  t = s[n/2 - 1]
  if t * 2 == s:
    print("Yes")
  else:
    print("No");
    

### FIXED CODE ###

n = int(input());
s = input();

if n % 2 != 0:
  print("No")
else:
  t = s[:int(n/2)]
  if t * 2 == s:
    print("Yes")
  else:
    print("No");
n=int(input())
s=list(input())
d=0
for i in range(n):
  if n-i>=2:
    
    if s[i]=='A' and s[i+1]=='B' and s[i+2]=='C':
      d+=1
  
print(c)    


### FIXED CODE ###

n=int(input())
s=list(input())
d=0
for i in range(n):
  if n-(i+1)>=2:
    if s[i]=='A' and s[i+1]=='B' and s[i+2]=='C':
      d+=1
  else:
    pass
print(d)
n=int(input())
ans=0

if n==1:print(0);exit()


#12だったら[[2,2],[3,1]]みたいな、[素因数、次数]みたいに格納したい

import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,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]
def bunkai(n):
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist=eratosu( int(sqrt(n)) )
    for i in primelist:
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([n,1])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

a=bunkai(n)
ans=0
import bisect as bi
p=[1,3,6,10,15,21,28,36,45,55]
for l in a:
  q=l[1]
  ans+=bi.bisect_right(p,q)
print(ans)
  

### FIXED CODE ###

n=int(input())
ans=0

if n==1:print(0);exit()


#12だったら[[2,2],[3,1]]みたいな、[素因数、次数]みたいに格納したい

import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,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]
def bunkai(n):
    if n==2:
        return [[2,1]]
    if n==3:
        return [[3,1]]
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist=eratosu( int(sqrt(n)) )
    for i in primelist:
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

a=bunkai(n)

ans=0
import bisect as bi
p=[1,3,6,10,15,21,28,36,45,55]
for l in a:
  q=l[1]
  ans+=bi.bisect_right(p,q)
print(ans)
s=input().split()
n,m=int(s[0]),int(s[1])
l=[[] for i in range(100001)]
d=[{} for i in range(100001)]
inp=[]
for i in range(m):
    s=input().split()
    p,y=int(s[0]),int(s[1])
    inp.append((p,y))
    l[p].append(y)
for i in range(100001):
    l[i].sort()
for i in range(100001):
    cnt=1
    for j in l[i]:
        d[i][j]=cnt
        cnt+=1
for pa in inp:
    print(str(pa[0]).zfill(6)+str(d[pa[0]-1][pa[1]]).zfill(6))

### FIXED CODE ###

s=input().split()
n=int(s[0])
m=int(s[1])
l=[[] for i in range(100000)]
d=[{} for i in range(100000)]
inp=[]
for i in range(m):
    s=input().split()
    p=int(s[0])
    y=int(s[1])
    inp.append((p,y))
    l[p-1].append(y)
for i in range(100000):
    l[i].sort()
for i in range(100000):
    cnt=1
    for j in l[i]:
        d[i][j]=cnt
        cnt+=1
for pa in inp:
    L=pa[0]
    R=d[L-1][pa[1]]
    L=str(L)
    R=str(R)
    for i in range(6-len(L)):
        print("0",end="")
    print(L,end="")
    for i in range(6-len(R)):
        print("0",end="")
    print(R)
A,B = map(int,input())
if A<9 and B<9:
    print("Yay!")
else:
    print(":(")


### FIXED CODE ###

A,B = map(int,input().split())
if A<9 and B<9:
    print("Yay!")
else:
    print(":(")
a, b, c, d, e = [int(input) for i in range(5)]
k = int(input())
if e-a > k*4:
  print(":(")
elif e-b > k*3 or d-a > k*3:
  print(":(")
elif e-c > k*2 or d-b > k*2 or c-a > k*2:
  print(":(")
elif e-d > k or d-c > k or c-b > k or b-a > k:
  print(":(")
else:
  print("Yay!")

### FIXED CODE ###

a, b, c, d, e = [int(input()) for i in range(5)]
k = int(input())
if max(e-a, e-b, d-a, e-c, d-b, c-a, e-d, d-c, c-b, b-a) > k:
  print(":(")
else:
  print("Yay!")
from fractions import gcd
A,B,C,D=map(int, input().split())
A -= 1

cc = B//C - A//C
dd = B//D - A//D

E = C*D//fractions.gcd(C, D)
ee = B//E - A//E

print(B - A - cc - dd + ee)

### FIXED CODE ###

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

cc = B//C - A//C
dd = B//D - A//D

E = C*D//gcd(C, D)
ee = B//E - A//E

print(B - A - cc - dd + ee)
import sys
import math

sys.setrecursionlimit(5000)

A, B, Q = map(int, input().split())
LIMIT = 2*(10**10)
shrines = [-LIMIT] + [int(input()) for i in range(A)] + [LIMIT]
temples = [-LIMIT] + [int(input()) for j in range(B)] + [LIMIT]

def b_temp_search(num, idx):
    if num >= temples[idx] and num <= temples[idx+1]:
        return idx
    elif num < temples[idx]:
        if idx == 1:
            return 0
        return b_temp_search(num, math.ceil(idx/2))
    else:
        if idx == B:
            return B + 1
        return b_temp_search(num, math.ceil((B+idx)/2))

def b_sh_search(num, idx):
    if num >= shrines[idx] and num <= shrines[idx+1]:
        return idx
    elif num < shrines[idx]:
        if idx == 1:
            return 0
        return b_sh_search(num, math.ceil(idx//2))
    else:
        if idx == A:
            return A + 1
        return b_sh_search(num, math.ceil((A+idx)/2))

for k in range(Q):
    x = int(input())
    sh_idx = b_sh_search(x, math.ceil((A+2)//2))
    temp_idx = b_temp_search(x, math.ceil((B+2)//2))
    ptn1 = max(abs(x-shrines[sh_idx]), abs(x-temples[temp_idx]))
    ptn2 = max(abs(x-shrines[sh_idx+1]), abs(x-temples[temp_idx+1]))
    ptn3 = min((temples[temp_idx+1] - x)*2 + x - shrines[sh_idx], temples[temp_idx+1] - x + (x - shrines[sh_idx])*2)
    ptn4 = min((shrines[sh_idx+1] - x)*2 + x - temples[temp_idx], shrines[sh_idx+1] - x + (x - temples[temp_idx])*2)
    ans = min(ptn1, ptn2, ptn3, ptn4)
    print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
INF = 10**12
A, B, Q = map(int, input().split())
shrines = [-INF] + [int(input()) for _ in range(A)] + [INF]
temples = [-INF] + [int(input()) for _ in range(B)] + [INF]
for _ in range(Q):
  query = int(input())
  sh_pos = bisect_left(shrines, query)
  te_pos = bisect_left(temples, query)
  ans = INF
  for s in shrines[sh_pos-1:sh_pos+1]:
    for t in temples[te_pos-1:te_pos+1]:
      dis = min(abs(s-query)+abs(s-t),abs(t-query)+abs(t-s))
      ans = min(ans, dis)
  print(ans)