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

import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
adj = [set() for _ in range(N)]
roads = [[-1]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)


def calc_ans(start, end):
    dist = [[-1]*(N+1) for _ in range(N)]  # dist[i][j] iまで給油j会で行った時の残りの最大値
    dist[start][0] = L
    Q = [[0, start]]  # (給油回数、current node)
    while Q:
        kyuyu, cur_node = heapq.heappop(Q)
        if cur_node == end:
            return kyuyu
        remain = dist[cur_node][kyuyu]
        assert remain != -1
        for next in adj[cur_node]:
            # 給油せずにいく
            to_next = roads[cur_node][next]
            if dist[next][kyuyu] == -1:
                if to_next <= remain:  # 給油なしでいける
                    dist[next][kyuyu] = remain-to_next
                    heapq.heappush(Q, [kyuyu, next])
            else:
                cur_cost = dist[next][kyuyu]
                if to_next-remain > cur_cost:
                    dist[next][kyuyu] = to_next-cur_cost
                    Q.append([kyuyu, next])
                    heapq.heappush(Q, [kyuyu, next])
            #　給油していく
            if kyuyu+1 <= N and dist[next][kyuyu+1] == -1:
                dist[next][kyuyu+1] = L-to_next
                heapq.heappush(Q, [kyuyu+1, next])
            elif kyuyu+1 <= N:
                cur_cost = dist[next][kyuyu+1]
                if L-to_next > cur_cost:
                    dist[next][kyuyu] = L-to_next
                    heapq.heappush(Q, [kyuyu+1, next])

    return -1


Q = int(input())
query = [list(map(lambda x:int(x)-1, input().split())) for _ in range(Q)]

for s, t in query:
    print(calc_ans(s, t))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)
### BUGGY CODE ###

K = int(input())
count = 0
an = 0

if K%2 == 0 or K%2 ==0:
    print("-1")
    exit()
while True:
  an = (10*an + 7) % K
  count +=1
  if an == 0:
    print(count)
    break

### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = []
for k in range(N):
    x = a[k]^b[0]
    ok = True
    for i in range(N):
        if not b[i]^x == a[(k+i)%N]:
            ok = False
    if ok:
        ans.append((k,x))
for y in ans:
    print(*y)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
if A == B == [A[0]]*N:
    for i in range(N): 
        ans.append((i,a[i]^b[0]))
else:
    A += A    
    d = defaultdict(list)
    for i in range(N):
        d[B[i]].append(i)
    i = 0
    ans = []
    while i < N:
        ok = True
        for j in range(N):
            if B[N-j-1] != A[N-j-1+i]:
                if d[A[N-j-1]] == []:
                    i += N
                    ok = False
                    break
                else:
                    i += N - d[A[N-j-1+i]][-1] - 1
                    ok = False
                    break
        if ok:
            ans.append((i,a[i]^b[0]))
            if len(d[A[N-1+i]]) == 1:
                i += N
            else:
                i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)
### BUGGY CODE ###

b=list(map(int,input().split()))
L=[]
l=[]
LL=[]
for i in range(b[0]):
    LL.append(list(map(int,input().split())))
LL.sort(key=lambda x: x[0])
L=[LL[i][0] for i in range(b[0])]
l=[LL[i][1] for i in range(b[0])]
x=0
z=0
y=b[1]
while y>=0 and not L==[]:
    if L==[]:
        print(x-y*(-1)*w)
        z=1
        break
    else:
        y-=l[0]
        x+=l[0]*L[0]
        z=l[0]*L[0]
        w=L[0]
        l=l[1:]
        L=L[1:]
print(x-y*(-1)*w)

### FIXED CODE ###

b=list(map(int,input().split()))
LL=[]
for i in range(b[0]):
    LL.append(list(map(int,input().split())))
LL.sort()
x=0
z=0
y=b[1]
i=-1
while y>=0 and not LL==[]:
    i+=1
    if y<=LL[i][1]:
        print(x+LL[i][0]*y)
        break
    else:
        y-=LL[i][1]
        x+=LL[i][1]*LL[i][0]
### BUGGY CODE ###

import bisect

N, M = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
inputs = [[int(i) for i in input().split()] for _ in range(M)]

alist.sort()
inputs.sort(key=lambda x: x[1],reverse=True)

for i in inputs:
    index=bisect.bisect_left(alist, i[1])
    limit = index if index < i[0] else i[0]
    alist = [i[1]] * limit + alist[limit:]
    alist.sort()

print(sum(alist))


### FIXED CODE ###

import bisect

N, M = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
alist.sort()
inputs = [[int(i) for i in input().split()] for j in range(M)]
inputs.sort(key=lambda x:x[1], reverse=True)

for i in range(N):
    if len(inputs) == 0:
        break
    if inputs[0][1] > alist[i]:
        alist[i] = inputs[0][1]
        inputs[0][0] -= 1
        if inputs[0][0] == 0:
            inputs.pop(0)
    else:
        break
print(sum(alist))
### BUGGY CODE ###

import heapq

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

S,T = map(int,input().split())
S -= 1
T -= 1

q = []
heapq.heappush(q,[0,S])

while len(q) > 0:

    now = heapq.heappop(q)

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3]:
                heapq.heappush(q,[nd + 1 , i])

if far[T][0] == float("inf"):
    print (-1)
else:
    print (far[T][0] // 3)
    


### FIXED CODE ###

import heapq
from collections import deque

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

S,T = map(int,input().split())
S -= 1
T -= 1

q = deque([])
q.append([0,S])

while len(q) > 0:

    now = q.popleft()

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3] and far[i][(nd+1)%3] > far[np][nd%3] + 1:
                q.append([nd + 1 , i])
                nend[i][(nd+1)%3] = False

if far[T][0] == float("inf"):
    print (-1)
else:
    print (far[T][0] // 3)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
ans_list = []
for i in range(Q):
    l, r  = map(int, input().split())
    ans = 0
    for j in range(l-1, r-1):
        if S[j] == 'A':
            if S[j+1] == 'C':
                ans += 1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
ls = [0]
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        ls.append(ls[i] + 1)
    else:
        ls.append(ls[i])
for i in range(Q):
    l, r = map(int, input().split())
    print(ls[r-1] - ls[l-1])
### BUGGY CODE ###

def main() -> None:
    S = list(input())
    m = len(S)
    pre = len(S)
    while len(S) > 0:
        for i in range(len(S) - 1):
            if S[i] != S[i+1]:
                S.remove(S[i])
                S.remove(S[i])
                break

        # 抜けなかった
        if pre == len(S):
            break
        else:
            pre = len(S)

    # 最初の数から引けば抜いた数
    print(m - len(S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


def main() -> None:
    S = list(input())
    a = collections.Counter(S)
    zero = a['0']
    one = a['1']
    if zero >= one:
        print(one * 2)
    else:
        print(zero * 2)


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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

ans=0
n,a,b = map(int,(input().split()))

for i in range(n):
  ans+=cmb(n,i)%(10**9+7)
  ans%=(10**9+7)
ans-=cmb(n,a)
ans-=cmb(n,b)
print(ans)

### FIXED CODE ###

from functools import reduce
def cmb(r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod
n,a,b = map(int,(input().split()))
ans=0
mod=10**9+7

ans=pow(2,n,10**9+7)-1
ans-=cmb(a)
ans-=cmb(b)
print(ans%mod)
### BUGGY CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]

x_sorted = [0] * n
for i in range(q):
    p = px[i][0]
    x = px[i][1]
    x_sorted[p - 1] += x

# print(x_sorted)

start = 0
cost = dict() # コストテーブル
for i, j in ab:
    c = x_sorted[i - 1]
    cost[i - 1] = cost.get(i - 1, []) + [(j - 1, c)]

d = [0 for i in range(n)]
qq = [(d[0], 0)]
while qq:
    (du, u) = qq.pop() # 最短距離とその頂点
    for v, weight in cost.get(u, []):
        alt = du + weight
        d[v] = alt
        qq.append((alt, v))

ans = ''
for i in range(n):
    ans += str(d[i] + x_sorted[i]) + ' '

print(ans[:-1])


### FIXED CODE ###

from sys import stdin
from collections import defaultdict

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n - 1)]
    px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]

    g = defaultdict(list)
    for a, b in ab:
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    adder = defaultdict(int)
    for p, x in px:
        p -= 1
        adder[p] += x

    ans = [float('inf')] * n
    ans[0] = adder[0]
    qu = [0]

    while qu:
        cur = qu.pop()

        for target in g[cur]:
            if ans[target] == float('inf'):
                ans[target] = ans[cur] + adder[target]
                qu.append(target)

    for _ans in ans:
        print(_ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]


    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


def main():
    N, M, K = list(map(int, input().split()))
    U = UnionFind(N)
    FR = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        U.union(a - 1, b - 1)
        FR[a - 1].add(b - 1)
        FR[b - 1].add(a - 1)
    #BL = [set() for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        FR[c - 1].add(d - 1)
        FR[d - 1].add(c - 1)
    LS = {}
    for i in range(N):
        t = U.find(i)
        if t not in LS:
            LS[t] = set()
        LS[t].add(i)

    print(' '.join(str(len(LS[U.find(i)] - FR[i]) - 1) for i in range(N)))

main()


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]


    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


def main():
    N, M, K = list(map(int, input().split()))
    U = UnionFind(N)
    FR = [0] * N
    for _ in range(M):
        a, b = map(int, input().split())
        U.union(a - 1, b - 1)
        FR[a - 1] += 1
        FR[b - 1] += 1
    r = [0] * N
    LS = {}
    for i in range(N):
        t = U.find(i)
        if t not in LS:
            LS[t] = set()
        LS[t].add(i)
        r[i] = -U.parents[t] - 1 - FR[i]
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c - 1, d - 1
        if d in LS[U.find(c)]:
            r[c] -= 1
            r[d] -= 1
    print(' '.join(str(i) for i in r))

main()
### BUGGY CODE ###

import bisect
import sys
def main():
    input = sys.stdin.readline
    s = input()[:-1]
    t = input()[:-1]
    S = "abcdefghijklmnopqrstuvwxyz"
    A = [[] for k in range(26)]
    for k in range(len(s)):
        A[S.index(s[k])].append(k+1)
    ans = 0
    now = 0
    for k in range(len(t)):
        a = S.index(t[k])
        if len(A[a]) == 0:
            print(-1)
            exit(0)
        if A[a][-1] <= now:
            ans += len(s)
            now = A[a][0]
        else:
            for l in range(len(A[a])):
    #            print(A[S.index(t[k])][l]>now)
                if A[a][l] > now:
                    now = A[a][l]
                    break
    print(ans+now)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from bisect import bisect_right as bisect
def main():
    input = sys.stdin.readline
    s = input()[:-1]
    t = input()[:-1]
#    S = "abcdefghijklmnopqrstuvwxyz"
    A = [[] for k in range(26)]
    for k in range(len(s)):
        A[ord(s[k])-97] += [k+1]
    ans = 0
    now = 0
    for k in range(len(t)):
        a = ord(t[k]) - 97
        if len(A[a]) == 0:
            print(-1)
            exit(0)
        if A[a][-1] <= now:
            ans += len(s)
            now = A[a][0]
        else:
            now = A[a][bisect(A[a],now)]
    print(ans+now)

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

import sys
import statistics
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
X = list(map(int, input().split()))
mid = N // 2 - 1

for i in range(N):
    print(statistics.median(X[:i]+X[i+1:]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
X = list(map(int, input().split()))
X_sorted = sorted(X)
L = X_sorted[N//2-1]
R = X_sorted[N//2]


for x in X:
    print(L if x >= R else R)
### BUGGY CODE ###

import sys
import bisect
N, M = map(int, input().split())
A = sorted(map(int, input().split()))
for _ in range(M):
    b, c = map(int, sys.stdin.readline().split())
    x = bisect.bisect_left(A, c)
    y = min(x, b)
    A = [c] * y + A[y:]
    if x != y:
        A.sort()
print(sum(A))

### FIXED CODE ###

import sys
import bisect
N, M = map(int, input().split())
A = sorted(map(int, input().split()))
CB = [None] * M
for i in range(M):
    b, c = map(int, sys.stdin.readline().split())
    CB[i] = (c, b)
CB.sort(reverse=True)

i = 0
ans = 0
for c, b in CB:
    x = bisect.bisect_left(A, c, i)
    count = min(x - i, b)
    ans += c * count
    i += count
for j in range(i, N):
    ans += A[j]
print(ans)
### BUGGY CODE ###

N,K,Q = [int(i) for i in input().split(" ")]
A = [int(input()) for _ in range(Q)]
point = [K for i in range(N)]

for _,q in enumerate(A):
    for n,p in enumerate(point):
        if q == (n+1):
            continue
        else:
            point[n] = p-1

for i in point:
    if 0 < i:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q = [int(i) for i in input().split(" ")]
A = [int(input()) for _ in range(Q)]
point = [K for i in range(N)]

for q in A:
    point[q-1]+=1
for i in list(map(lambda x: x - Q,point)):
    if 0 < i:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import collections

n = int(input())
s = list(input())

l = collections.Counter(s[:1])
r = collections.Counter(s[2:])
key = set()
for i in range(n-2):
    for j in range(10):
        for k in range(10):
            if l[str(j)] > 0 and r[str(k)] > 0:
                key.add('{}{}{}'.format(j,s[i+1],k))
    l[str(s[i+1])] += 1
    r[str(s[i+2])] -= 1
print(len(key))


### FIXED CODE ###

n = int(input())
s_list = list(input())

ans = 0
for i in range(1000):
    key = str(i).zfill(3)
    k = 0
    t = key[k]
    for s in s_list:
        if t == s:
            k += 1
            if k == 3:
                ans += 1
                break
            t = key[k]
print(ans)
### BUGGY CODE ###

H,W,D=map(int,raw_input().split())
C={}
for i in range(H):
	A=map(int,raw_input().split())
	cnt=1
	for j in A:
		C[j]=(i+1,cnt)
		cnt+=1


Q=input()
memo={}
for i in range(Q):
	L,R=map(int,raw_input().split())

	if (L,R) in memo:
		print memo[(L,R)]
		continue
	ans=0
	for j in range(L,R,D):
		ans+=abs(C[j][0]-C[j+D][0])+abs(C[j][1]-C[j+D][1])
		memo[(j,j+D)]=abs(C[j][0]-C[j+D][0])+abs(C[j][1]-C[j+D][1])
	memo[(L,R)]=ans
	print ans


### FIXED CODE ###

H,W,D=map(int,raw_input().split())
C={}
for i in range(H):
	A=map(int,raw_input().split())
	cnt=1
	for j in A:
		C[j]=(i+1,cnt)
		cnt+=1

dist=[ 0 for i in range(H*W+1) ]

for i in range(1,H*W+1):
	if i<=D:
		continue
	dist[i]=dist[i-D]+abs(C[i-D][0]-C[i][0])+abs(C[i-D][1]-C[i][1])
	

Q=input()
for i in range(Q):
	L,R=map(int,raw_input().split())
	print dist[R]-dist[L]
### BUGGY CODE ###

import bisect
a,b,q = map(int,input().split())
x = [int(input()) for i in range(a)]
y = [int(input()) for i in range(b)]
x.sort()
y.sort()
xx = [0]*a
yy = [0]*b
for i in range(a):
    n = bisect.bisect_left(y,x[i])
    o = 1<<61
    p = 1<<61
    try:
        o = abs(y[n]-x[i])
    except:
        pass
    try:
        p = abs(y[n-1]-x[i])
    except:
        pass
    xx[i] = min(o,p)

for i in range(b):
    n = bisect.bisect_left(x,y[i])
    o = 1<<61
    p = 1<<61
    try:
        o = abs(x[n]-y[i])
    except:
        pass
    try:
        p = abs(x[n-1]-y[i])
    except:
        pass
    yy[i] = min(o,p)

for i in range(q):
    z = int(input())
    ans = 1<<61
    n = bisect.bisect_left(x, z)
    if n<a:
        tmp = abs(x[n]-z)+xx[n]
        ans = min(ans,tmp)
    if n>0:
        tmp = abs(x[n-1]-z)+xx[n-1]
        ans = min(ans,tmp)

    n = bisect.bisect_left(y, z)
    if n<b:
        tmp = abs(y[n]-z)+yy[n]
        ans = min(ans,tmp)
    if n>0:
        tmp = abs(y[n-1]-z)+yy[n-1]
        ans = min(ans,tmp)
    print(ans)


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
a,b,q = map(int,input().split())
x = [int(input()) for i in range(a)]
y = [int(input()) for i in range(b)]
osoi = [int(input()) for i in range(q)]
x.sort()
y.sort()
xx = [0]*a
yy = [0]*b
n = 0
for i in range(a):
    while n < b-1 and abs(x[i]-y[n]) > abs(x[i]-y[n+1]):
        n+=1
    xx[i] = abs(x[i]-y[n])
n = 0
for i in range(b):
    while n < a-1 and abs(y[i]-x[n]) > abs(y[i]-x[n+1]):
        n+=1

    yy[i] = abs(y[i]-x[n])

for i in range(q):
    z = osoi[i]
    ans = 1<<61
    n = bisect.bisect_left(x, z)
    if n<a:
        tmp = abs(x[n]-z)+xx[n]
        ans = min(ans,tmp)
    if n>0:
        tmp = abs(x[n-1]-z)+xx[n-1]
        ans = min(ans,tmp)

    n = bisect.bisect_left(y, z)
    if n<b:
        tmp = abs(y[n]-z)+yy[n]
        ans = min(ans,tmp)
    if n>0:
        tmp = abs(y[n-1]-z)+yy[n-1]
        ans = min(ans,tmp)
    print(ans)
### BUGGY CODE ###

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


def make_divisors(n):

    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1

    return lower_divisors + upper_divisors[::-1]


def gcd(a, b):

    if a == 0:
        return b
    else:
        return gcd(b%a, a)


da = make_divisors(A)
common_divisors = []

for d in da:
    if B % d == 0:
        common_divisors.append(d)

cd = set(common_divisors)
lim = common_divisors[-1]
for i in common_divisors[1:]:
    a = 2
    cur = a * i
    while cur <= lim:
        if cur in cd:
            cd.remove(cur)
        a += 1
        cur = a * i

print(len(cd))
        



### FIXED CODE ###

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

import math

def is_prime(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False

    return True


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1

    return lower_divisors + upper_divisors[::-1]


def gcd(a, b):

    if a == 0:
        return b
    else:
        return gcd(b%a, a)


da = make_divisors(A)
common_divisors = []

for d in da:
    if B % d == 0:
        common_divisors.append(d)

ans = [1 if is_prime(x) else 0 for x in common_divisors]
print(sum(ans))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = {i for i in range(N)}
    while 1:
        days += 1
        gamed = [0]*N
        tmp = set()
        for i in nxt:
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
                tmp.add(i)
                tmp.add(j)
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break
        nxt = tmp
    print(days)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

n,m = map(int,input().split())
ans = 0
for i in range(n):
    if m > 2:
        m -= 2
        ans += 1
    else:
        break
ans += (m//4)
print(ans)    


### FIXED CODE ###

n,m = map(int,input().split())
ans = 0
if m >= 2 * n :
    ans += n
    m -= 2 * n
else:
    ans += m//2
    m = 0    
ans += (m//4)
print(ans)