Harryxun/stf_run huggingface dataset:
import math
C,D,A,B =map(int,input().split())
la =[D//A,(C-1)//A]
lb =[D//B,(C-1)//B]
lcm = A*B //math.gcd(A,B)
lab =[D//lcm,(C-1)//lcm]

ans = la[0] +lb[0] -la[1] -lb[1] -(lab[0]-lab[1])
print(D-C+1-ans)

### FIXED CODE ###


def gcd(x,y): #x<y
    if x==0:
        return y
    else:
        return gcd(y%x,x)



C,D,A,B =map(int,input().split())
la =[D//A,(C-1)//A]
lb =[D//B,(C-1)//B]
lcm = A*B //gcd(A,B)
lab =[D//lcm,(C-1)//lcm]

ans = la[0] +lb[0] -la[1] -lb[1] -(lab[0]-lab[1])
print(D-C+1-ans)
m=input()
n=input()
count=0;
for i in range(len(m))
    if m[i] != n[i] :
         count+ = 1
print(count)

### FIXED CODE ###

m=input()
n=input()
count=0;
for i in range(len(m)):
    if m[i]!=n[i] :
         count+=1
print(count)
N = str(input())
flag = 0
for i in range(len(N)):
    if int(N[i]) == 7:
        print ('Yes')
        flag = 1
        break
101if flag == 0:
    print ('No')

### FIXED CODE ###

N = str(input())
flag = 0
for i in range(len(N)):
    if int(N[i]) == 7:
        print ('Yes')
        flag = 1
        break
if flag == 0:
    print ('No')
S = input()
N = int(input())
Q = [input().split() for _ in range(N)]
start = ''
end = ''

# Sの向きを定義1:前から0:後ろから
direct = 0
for i in range(N):
  if Q[i][0] =='1':
    direct^=1
  else:
    if direct == int(Q[i][1])-1:
      start += Q[i][2]
      print('start',start)
    else:
      end += Q[i][2]
      print('end',end)
      
ans = start[::-1]+S+end
print(ans) if direct == 0 else print(ans[::-1])

### FIXED CODE ###

S = input()
N = int(input())
Q = [input().split() for _ in range(N)]
start = ''
end = ''

# Sの向きを定義1:前から0:後ろから
direct = 0
for i in range(N):
  if Q[i][0] =='1':
    direct^=1
  else:
    if direct == int(Q[i][1])-1:
      start += Q[i][2]
    else:
      end += Q[i][2]
      
ans = start[::-1]+S+end
print(ans) if direct == 0 else print(ans[::-1])
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
a = list(map(int, input().split()))

dp = [[-1 for k in range(N*(N+1)//2+1)] for n in range(1000+1)]

def generate_substring(a):
    for i in range(N):
        for j in range(i, N):
            yield a[i:j+1]

def find_max_and(i, k):

    if dp[i][k] >= 0:
        return dp[i][k];
    
    if i == N_SUBSTR:
        res = 0xFFFF
    elif k == 0:
        res = find_max_and(i + 1, k)
    else:
        a = find_max_and(i + 1, k)
        b = find_max_and(i + 1, k - 1) & scores[i]
        
        res = b if a == 0xFFFF else max(a, b)

    dp[i][k] = res
    return res

scores = list(map(sum, generate_substring(a)))
N_SUBSTR = len(scores)
print(find_max_and(0, K))



### FIXED CODE ###

# -*- coding: utf-8 -*-
import statistics

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

def argmin(z):
    min_idx = 0
    min_val = 10000
    for k, v in enumerate(z):
        if min_val > v:
            min_idx = k
            min_val = v
    return min_idx, min_val

m = statistics.mean(a)
z = [abs(b - m) for b in a]

k, v = argmin(z)
print(k)
def read():
    N, K = map(int, input().strip().split())
    A = map(int, input().strip().split())
    return N, K, A


def binary_digits(x):
    digit = 0
    while x > 0:
        x >>= 1
        digit += 1
    return digit


def maximum_X(N, K, A):
    digitK = binary_digits(K)
    counts = []
    bitmask = 1
    for d in range(digitK):
        count = 0
        for i in range(N):
            if A[i] & bitmask == bitmask:
                count += 1
        counts.append(count)
        bitmask <<= 1

    X = 0
    bitmask = 1
    for d in range(digitK):
        if counts[d] * 2 < N:
            X += bitmask
        bitmask <<= 1
    return X


def f(x, A):
    y = 0
    for a in A:
        y += (x ^ a)
    return y


def solve(N, K, A):
    X = maximum_X(N, K, A)
    return f(X, A)


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    L = max(K, max(A), 1).bit_length()
    k = [0 for i in range(L)]
    i = 0
    while K:
        k[i] += K & 1
        i += 1
        K >>= 1
    b = [0 for i in range(L)]
    for a in A:
        i = 0
        x = a
        while x:
            b[i] += x & 1
            i += 1
            x >>= 1
    k = k[::-1]
    b = b[::-1]
    # dp[i][1]: 上位iビットがKと等しいときの最大値
    # dp[i][0]: 上位iビットがKより小さいときの最大値
    dp = [[-1, -1] for i in range(L+1)]
    dp[0][1] = 0
    for i in range(L):
        if dp[i][0] >= 0:
            dp[i+1][0] = (dp[i][0] << 1) + max(b[i], N-b[i])
        if dp[i][1] >= 0:
            if k[i] == 1:
                dp[i+1][0] = max(dp[i+1][0], (dp[i][1] << 1) + b[i])
                dp[i+1][1] = (dp[i][1] << 1) + (N-b[i])
            else:
                dp[i+1][1] = (dp[i][1] << 1) + (b[i])
    return max(dp[L][1], dp[L][0])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
mod = 10 ** 9 + 7
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, i))
    edges[b - 1].append((a - 1, i))
l = [0 for i in range(n)]
def dfs(cur, x):
    res = 1
    for i in edges[cur]:
        if i[1] != x:
            res += dfs(i[0], i[1])
    l[x] = res
    return res
dfs(0, -1)
l2 = [1]
i2 = pow(2, mod - 2, mod)
for i in range(n):
    l2.append(l2[-1] * i2 % mod)
cnt = 0
for i in l:
    cnt += (1 - l2[i]) * (1 - l2[n - i])
print((-n * i2 - l2[-1] + cnt + 1) % mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, i))
    edges[b - 1].append((a - 1, i))
l = [0 for i in range(n)]
def dfs(cur, x):
    res = 1
    for i in edges[cur]:
        if i[1] != x:
            res += dfs(i[0], i[1])
    l[x] = res
    return res
dfs(0, -1)
l2 = [1]
i2 = pow(2, mod - 2, mod)
for i in range(n):
    l2.append(l2[-1] * i2 % mod)
cnt = 0
for i in l:
    cnt += (1 - l2[i]) * (1 - l2[n - i])
print((-n * i2 - l2[-1] + cnt + 1) % mod)
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int main()
{
    int N; cin >> N;
    vector<int> h(N);
    for(auto &&item : h) cin >> item;
    vector<int> c(N);
    c.at(0) = 0; c.at(1) = abs(h.at(1) - h.at(0));
    for(int i = 2; i < N; i++) c.at(i) = min(c.at(i - 1) + abs(h.at(i) - h.at(i - 1)), c.at(i - 2) + abs(h.at(i) - h.at(i - 2)));
    cout << c.at(N - 1) << endl;
    return 0;
}

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
DP = [float('inf')] * N
DP[0] = 0
DP[1] = abs(H[1] - H[0])
for i in range(2, N):
    DP[i] = min(DP[i - 1] + abs(H[i] - H[i - 1]), DP[i - 2] + abs(H[i] - H[i - 2]))
print(DP[N - 1])
a=input()
c=False
f=False
for i in range(len(a))
  if c==True:
    if a[i]=='F':
    f=True
  else:
    if a[i]=='C':
    c=True
if c==True and f==True:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a=input()
c=False
f=False
for i in range(len(a)):
    if c==True:
        if a[i]=='F':
            f=True
    else:
        if a[i]=='C':
            c=True
if c==True and f==True:
    print("Yes")
else:
    print("No")
import math
num = int(input().replace(" ", ""))
squreRoot = math.sqrt(num)
return squreRoot == int(squreRoot)

### FIXED CODE ###

import math
num = int(input().replace(" ", ""))
squreRoot = math.sqrt(num)
print('Yes' if squreRoot == int(squreRoot) else 'No')
a,b = tuple(map(int,input().split()))

if a=<0 and b>=0:
  print("Zero")
elif a<0 and b<0:
  if (b-a+1)%2==0:
  	print("Positive")
  else:
    print("Negative")
elif a>0 and b>0:
  print("Positive")


### FIXED CODE ###

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

if a<=0 and b>=0:
  print("Zero")
elif a<0 and b<0:
  if (b-a+1)%2==0:
  	print("Positive")
  else:
    print("Negative")
elif a>0 and b>0:
  print("Positive")
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9 + 7

def prod(X):
    ans = 1
    for x in X:
        ans = ans * x % M
    return ans

def solve():
    # Case 1: N == K
    if N == K:
        return prod(A)

    # Case 2: ans is negative
    if all(a < 0 for a in A) and K % 2 == 1:
        return prod(sorted(A)[-K:])

    # Case 3: ans is positive
    posA = np.int64(sorted([a for a in A if a >= 0]))
    negA = np.int64(sorted([a for a in A if a < 0]))

    ans = 1
    if K % 2 == 1: # keep the largest positive
        ans = ans * posA[-1] % M
        posA = posA[:-1]
    
    pos_pairs = posA[0::2] * posA[1::2]
    neg_pairs = negA[0::2] * negA[1::2]
    pairs = np.concatenate([pos_pairs, neg_pairs], axis=0)
    pairs = np.sort(pairs)[-K//2:].tolist()
    ans = ans * prod(pairs) % M
    return ans

print(solve())
        


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9 + 7

def prod(X):
    ans = 1
    for x in X:
        ans = ans * x % M
    return ans

def solve():
    # Case 1: N == K
    if N == K:
        return prod(A)

    # Case 2: ans is negative
    if all(a < 0 for a in A) and K % 2 == 1:
        return prod(sorted(A)[-K:])

    # Case 3: ans is positive
    posA = np.int64(sorted([a for a in A if a >= 0]))
    negA = np.int64(sorted([a for a in A if a < 0]))

    ans = 1
    if K % 2 == 1: # Keep the largest positive
        ans = ans * posA[-1] % M
        posA = posA[:-1]
    
    # Construct largest value by pairing items
    if len(posA) % 2 == 1: # Discard the one with smallest absolute value
        posA = posA[1:]
    if len(negA) % 2 == 1: # Discard the one with smallest absolute value
        negA = negA[:-1]
    pos_pairs = posA[0::2] * posA[1::2]
    neg_pairs = negA[0::2] * negA[1::2]
    pairs = np.concatenate([pos_pairs, neg_pairs], axis=0).tolist()
    pairs = sorted(pairs, reverse=True)[:K//2]
    ans = ans * prod(pairs) % M

    return ans

print(solve())
n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
for i in range(2**n):
	sum_v=0
	sum_c=0
	for j in range(n):
		if (i>>j)&1:
			sum_v+=v[j]
			sum_c+=c[j]
			ans.append[sum_v-sum_c]
print(max(ans))

### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
sum_v=0
sum_c=0
for i in range(n):
	if v[i]-c[i]>=0:
		sum_v+=v[i]
		sum_c+=c[i]
		ans.append(sum_v-sum_c)
try:
	print(max(ans))
except ValueError:
	print("0")
N, M = [int(x) for x in input().strip().split(" ")]

vs = set()
def dfs_w(v, d, t):
    # dfs while版 
    r = -1
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            path.pop()
        else:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u == t:
                    if r != -1:
                        r = min(len(path)//3, r)
                    else:
                        r = len(path)//3
                if u in vs:
                    continue
                stack += [-v, u]
    return r

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

s, t = [int(x) for x in input().strip().split(" ")]
print(dfs_w(s, d, t))


### FIXED CODE ###

s = input().strip()
from collections import defaultdict
d = defaultdict(int)
for c in s:
    d[c] += 1
for k in d:
    if d[k] != 2:
        print("No")
        break
else:
    print("Yes")
def calc():
    min_sub = 100000
    N = int(input())
    num = list(map(int, input().split()))
    for i in range(1,N):
        S1 = num[:i]
        S2 = num[i:]
        sub = abs(sum(S1)-sum(S2))
        if min_sub > sub:
            min_sub = sub
    print(min_sub)

N = int(input())
W = [int(i) for i in input().split()]
calc(N, W)

### FIXED CODE ###

N = int(input())
W = [int(i) for i in input().split()]
a = []
for i in range(N - 1):
    a.append(abs(sum(W[:i+1]) - sum(W[i+1:])))

print(min(a))
n=int(input()
print((n-1)//111+111))

### FIXED CODE ###

n=int(input())
print((((n-1)//111)+1)*111)
N=int(input())
arr=map(int, input().split())
for i in range(n,0,-1):
    arr[i-1] = sum(arr[i-1::i]) % 2
print(sum(a))
print(' '.join([str(i+1) for i,j in enumerate(arr) if j == 1]))

### FIXED CODE ###

def main():
    n = int(input())
    A = [0] + list(map(int, input().rstrip().split()))
    for i in range(n // 2, 0, -1):  # second half: no multiples
        A[i] = sum(A[i::i]) % 2
    ans = [i for i, j in enumerate(A) if j]
    print(len(ans))  # all cells: [1] -> len() (much faster than sum())
    print(*ans)


if __name__ == "__main__":
    main()
S = input()
if S[2] == 'f' and S[3] == 'f' and S[4] == 'e' and S[5] == 'e':
  print('Yes')
else:
  pirnt('No')

### FIXED CODE ###

S = input()
if S[2] == S[3] and S[4] == S[5]:
  print('Yes')
else:
  print('No')
for _ in range(int(input()):
    a=int(input())+int(input())
    print(a if a < 10**80 else 'overflow')

### FIXED CODE ###

for _ in range(int(input())):
    a=int(input())+int(input())
    print(a if a < 10**80 else 'overflow')
from collections import Counter
n, m = map(int, input().split())
A = []
for i in range(m):
    x, y = map(int, input().split())
    A.append(x)
    A.append(y)
C = sorted(Counter(A).most_common(), reverse = True, key = lambda x: x[1])
for i in range(n):
    print(C[i][1])

### FIXED CODE ###

n, m = map(int, input().split())
A = [0] * n

for i in range(m):
    x, y = map(int, input().split())
    A[x-1] += 1
    A[y-1] += 1

for i in range(n):
    print(A[i])
while True:
     a=list(map(int, input().split()))
     if a = [0,0]:
          break
     a.sort()
     print(a[0],a[1])
     


### FIXED CODE ###

while True:
     a,b=map(int, input().split())
     x=[a,b]
     if a ==0 and b==0:break
     x.sort()
     print(x[0],x[1])
n,m=map(int,input().split())
l=list(map(int,input().split()))

if m==1:
  print(0)
else:
  num=n-1
  sl=sorted(l)

  dsl=[abs(sl[i+1]-sl[i]) for i in range(m-1)]

  for i in range(num):
    ml=max(dsl)
    dsl.remove(ml)
  
  print(sum(dsl))


### FIXED CODE ###

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

if n>=m:
  print(0)
else:
  num=n-1
  sl=sorted(l)

  dsl=[abs(sl[i+1]-sl[i]) for i in range(m-1)]

  dsl=sorted(dsl)
  print(sum(dsl[0:len(dsl)-num]))
def d(n):
  while n%2 == 0:
    n /= 2
    ans += 1
  return ans

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

print(t)
    


### FIXED CODE ###

n = input()
result = sum(list(map(int,str(n))))
print(result)
#!~/anaconda3/bin/python

import sys

args=sys.argv
S=args[1]
if S[0] == S[1]:
        if S[1] == S[2]:
                print("No")
        else:
                print("Yes")
else:
        print("Yes")

### FIXED CODE ###

S=list(input())

if S[0] == S[1]:
        if S[1] == S[2]:
                print("No")
        else:
                print("Yes")
else:
        print("Yes")
import sys
x, y = map(int, input().split())


def power_func(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


def comb(n, k, p):
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


w = (x + y) / 3
b = (- x + 2*y) // 3

if w.is_integer():
    w = int(w)
else:
    print(0)
    sys.exit()

a = min(b, w-b)
ans = comb(w, a, 10**9+7)
print(ans)


### FIXED CODE ###

r = int(input())
print(r**2)
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
 
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
         for j in len(que):
        #while len(que) > 0:
            u[j] = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
 
 
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

### FIXED CODE ###

n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
   s,t = map(int,raw_input().strip().split(' '))
   if color[s] == color[t]:
     print 'yes'
   else:
     print 'no'
import numpy as np
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
s = ''
for i in range(N):
    s += str(i+1) * A[i]
B = np.array(list(map(int, s)), np.int64).reshape([H,W])

for i in range(H):
    if i % 2 == 0:
        print(*B[i])
    else:
        print(*B[i][::-1])
        

### FIXED CODE ###

import numpy as np
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
B = np.zeros([H,W], np.int64)
ind = 0
for i in range(H):
    for j in range(W):
        if A[ind] == 0:
            ind += 1
        B[i,j] = ind+1
        A[ind] -= 1

for i in range(H):
    if i % 2 == 0:
        print(*B[i])
    else:
        print(*B[i][::-1])
N, M = map(int, input().split())

G = [[]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1] = b-1
    G[b-1] = a-1

visited = [0]*N
visited[0] = 1

def dfs(v, visited):
    if 0 not in visited:
        return 1

    ans = 0
    for i in G[v]:
        if visited[i] == 0:
            visited[i] = 1
            ans += dfs(i, visited)
            visited[i] = 0

    return ans

print(dfs(0, visited))

### FIXED CODE ###


import itertools

N, M = map(int, input().split())
adj_matrix = [[0]* N for _ in range(N)]

for i in range(M): #隣接行列
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)
s = input()

ans = True
if s[0] != "A":
    ans = False
    #print("s[0] is not A")
else:
    cnt_C = 0
    length = len(s)

    n = 1
    for check_char in s[1:]:
        print(check_char)
        
        if check_char.islower() is False:
            if check_char != "C" or n == 1 or n == (length - 1):
                ans = False
                break
            
            cnt_C += 1
        
        n += 1

if cnt_C != 1:
    ans = False

if ans:
    print("AC")
else:
    print("WA")

### FIXED CODE ###

"""
B - AcCepted
文字列 S が与えられます。S のそれぞれの文字は英大文字または英小文字です。 S
が次の条件すべてを満たすか判定してください。

S の先頭の文字は大文字の A である。
Sの先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1
個含まれる。
以上の A, C を除く S のすべての文字は小文字である。
"""

s = input()

cnt_C = 0
ans = True
if s[0] != "A":
    ans = False
    #print("s[0] is not A")
else:
    length = len(s)

    n = 1
    for check_char in s[1:]:
        #print(check_char)
        
        if check_char.islower() is False:
            if check_char != "C" or n == 1 or n == (length - 1):
                ans = False
            
            cnt_C += 1
        
        n += 1

if cnt_C != 1:
    ans = False

if ans:
    print("AC")
else:
    print("WA")
import math
x, y = map(int, input().split())
print((x * y) // math.gcd(x, y))


### FIXED CODE ###

from fractions import gcd
x, y = map(int, input().split())
print((x * y) // gcd(x, y))
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
    def __delitem__(self, idx):
        self[idx] = self._default
    def __getitem__(self, idx):
        return self.data[idx + self._size]
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
    def __len__(self):
        return self._len
    def query(self, start, stop):
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

import sys
z=sys.stdin.readline
n,k=map(int,z().split())
M=1048576
s=SegmentTree([0]*M)
for i in range(n):
    a=int(z())
    v,w=0,M
    if a>k:v=a-k
    if a+k+1<M:w=a+k+1
    s[a]=1+s.query(v,w)
print(s.query(0,M))

### FIXED CODE ###

print("ACL"*int(input()))
import math

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

under_a = a -1
cd_gcd = math.gcd(c, d)

b_mul = b - (b//c)-(b//d)+(b//(c*d//cd_gcd))
under_a_mul = under_a - (under_a//c)-(under_a//d)+(under_a//(c*d//cd_gcd))

print(int(b_mul-under_a_mul))

### FIXED CODE ###

import fractions

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

under_a = a -1
cd_gcd = fractions.gcd(c, d)

b_mul = b - (b//c)-(b//d)+(b//(c*d//cd_gcd))
under_a_mul = under_a - (under_a//c)-(under_a//d)+(under_a//(c*d//cd_gcd))

print(int(b_mul-under_a_mul))
n,k = map(int, input().strip().split())
d = list(input().split())


n,k = map(int,input().strip().split())
d = list(input().split())
for x in range(n,100000):
    for y in d:
        if y in str(x):
            break
    else:
        print(x)
        break

### FIXED CODE ###

n,k = map(int,input().strip().split())
d = list(input().split())
for x in range(n,100000):
    for y in d:
        if y in str(x):
            break
    else:
        print(x)
        break
a,b=map(int,raw_input().split())
print a*b,(a+b)*2

### FIXED CODE ###

[a,b]=map(int,input().split())
print(a*b,(a+b)*2)
x=int(input())
happiness = 0
if x>=500:
    ans = divmod(x,500)
    happiness += 1000*ans[0]
    x = ans[1]

if x>=5:
    ans =divmod(x,5)
    happiness += 5*ans[0]

print(happiness)

### FIXED CODE ###

s=input()
if s[2]==s[3] and s[4]==s[5]:
    print('Yes')
else:
    print('No')
N_A_B = list(map(int, input().split()))
ball = ""
num = 10 ** 100
for i in range(num):
  if (len(ball) >= N_A_B[0]):
    break
  ball += "A" * N_A_B[1]
  if (len(ball) >= N_A_B[0]):
    break
  ball += "B" * N_A_B[2]
  if (len(ball) > N_A_B[0]):
    break

print(ball[:N_A_B[0]].count("A"))


### FIXED CODE ###

NAB = list(map(int, input().split()))
N = NAB[0]
A = NAB[1]
B = NAB[2]
ans = ( N//(A+B)) * A

if N%(A+B) <= A:
  ans += N%(A+B)
else:
  ans += A

print(ans)
x,y,z=map(int,input().split())
li=[z,x,y]
print(" ".join(li))

### FIXED CODE ###

x,y,z=map(int,input().split())
li=[z,x,y]
print(" ".join(map(str,li)))
X = int(input())
DP = [0]*100001
DP[100] = 1
DP[101] = 1
DP[102] = 1
DP[103] = 1
DP[104] = 1
DP[105] = 1

for i in range(106, 100001):
    if any(DP[i-100], DP[i-101], DP[i-102], DP[i-103], DP[i-104], DP[i-105]):
        DP[i] = 1
print(DP[W])

### FIXED CODE ###

X = int(input())
flag = 1
if X < 100:
  flag = 0
else:
  a = X%100
  b = a%10
  c = (a-b)/10
  count = 2*c
  if 1 <= b <= 5:
    count += 1
  elif 6<= b <= 9:
    count += 2
  if X//100 < count:
    flag = 0
print(flag)