Harryxun/stf_run huggingface dataset:
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    D = set(map(int, input().split()))
    ok = [i for i in range(10) if i not in D]
    N = str(N)
    l = len(N)
    if {i for i in range(int(N[0]), 10)} <= D:
        if ok[0] == 0:
            ans = ok[1] * 10 ** l
            print(ans)
    else:
        ans = 0
        for c in N:
            ans *= 10
            idx = bisect_left(ok, int(c))
            ans += ok[idx]
        print(ans)




if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    D = set(map(int, input().split()))
    while True:
        check = True
        for c in str(N):
            if int(c) in D:
                check = False
        if check:
            print(N)
            return
        N += 1


if __name__ == "__main__":
    main()
N = int(input())
S1 = input()
S2 = input()
p = 10 ** 9 + 7
dp = [0] * (N + 1)
if S1[0] == S2[0]:
  dp[0] = 3
else:
  dp[0] = 6
for i in range(1, N + 1):
  if S1[i] == S1[i - 1]:
    dp[i] = dp[i - 1]
  elif S1[i - 1] == S2[i - 1]:
    dp[i] = dp[i - 1] * 2 % p
  elif S1[i] == S2[i]:
    dp[i] = dp[i - 1]
  else:
    dp[i] = dp[i - 1] * 3 % p
print(dp[N])


### FIXED CODE ###

N = int(input())
S1 = input()
S2 = input()
p = 10 ** 9 + 7
dp = [0] * N
if S1[0] == S2[0]:
  dp[0] = 3
else:
  dp[0] = 6
for i in range(1, N):
  if S1[i] == S1[i - 1]:
    dp[i] = dp[i - 1]
  elif S1[i - 1] == S2[i - 1]:
    dp[i] = dp[i - 1] * 2 % p
  elif S1[i] == S2[i]:
    dp[i] = dp[i - 1]
  else:
    dp[i] = dp[i - 1] * 3 % p
print(dp[-1])
# -*- coding: utf-8 -*-
from heapq import heappop, heappush
def inpl(): return map(int, input().split())
N = int(input())

X = []
Y = []

for i in range(N):
    x, y = inpl()
    X.append((i, x))
    Y.append((i, y))

X = sorted(X, key=lambda x: x[1])
Y = sorted(Y, key=lambda y: y[1])

G = [[] for _ in range(N)]
for i in range(N-1):
    Xa, Xb = X[i], X[i+1]
    Ya, Yb = Y[i], Y[i+1]
    G[Xa[0]].append([Xb[0], Xb[1]-Xa[1]])
    G[Xb[0]].append([Xa[0], Xb[1]-Xa[1]])
    
    G[Ya[0]].append([Yb[0], Yb[1]-Ya[1]])
    G[Yb[0]].append([Ya[0], Yb[1]-Ya[1]])

visited = [False]*N
Q = [(0, 0)]
ans = 0

while Q:
    c, n = heappop(Q)
    if visited[n]:
        continue
    visited[n] = True
    ans += c
    
    for m, d in G[n]:
        if visited[m]:
            continue
        else:
            heappush(Q, (d, m))

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from math import factorial

N, M = [int(n) for n in input().split()]
if abs(N-M) == 0:
    result = factorial(N)**2 * 2
elif abs(N-M) == 1:
    result = factorial(N) * factorial(M)
else:
    result = 0
    
print(result % (10**9 + 7))
import queue
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1,i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    que = queue.Queue()
    que.put(start)
    while not que.empty():
        v = que.get()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            que.put(nv)
    d.append(dist)
d = np.array(d).flatten()
for i in range(1,n):
    print(int(np.count_nonzero(d==i)/2))

### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
nmax = 10**6
mod = 10**9+7
fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i] %mod

def ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

ncr_pre()
k = ni()
s = input()
n = len(s)
ans= 0
for i in range(k+1):
    ans=(ans+ ncr(n+k-i-1,n-1)*pow(25,k-i,mod)*pow(26,i,mod) )%mod
print(ans)


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
nmax = 2*10**6+2
mod = 10**9+7
fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i] %mod

def ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

ncr_pre()
k = ni()
s = input()
n = len(s)
ans= 0
for i in range(k+1):
    ans=(ans+ ncr(n+k-i-1,n-1)*pow(25,k-i,mod)*pow(26,i,mod) )%mod
print(ans)
N=int(input())
Ls=input().split()
mx=max(Ls)
start=0
for i in Ls:
  start+=(N-int(i))
if start>mx:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=int(input())
Ls=input().split()#str
L=[int(i) for i in Ls]
mx=max(L);L.remove(mx)
all=0
for j in L:all+=j
if all>mx:print("Yes")
else:print("No")
import sys

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

p=list(map(int,input().split()))
c=list(map(int,input().split()))

check=[0 for i in range(n)]

if max(c)<0:
    print(max(c))
    sys.exit()

ans=0

for i in range(n):
    if check[i]==0:
        cnt=0
        check[i]=1
        li=[i]
        pc=p[i]-1
        while pc!=i:
            check[pc]=1
            li.append(pc)
            pc=p[pc]-1
        sumli=0
        for j in li:
            sumli+=c[j]
        add=0
        ki=k
        if k>len(li):
            if sumli>0:
                ki=(ki-1)%len(li)+1
                add=sumli*((k-ki)//len(li))
            else:
                ki=len(li)
        for w in range(1,ki+1):
            sumwmax=0
            sumw=0
            for j in range(w):
                sumw+=c[li[j]]
            for j in range(len(li)):
                sumw=sumw-c[li[j]]+c[li[(j+w)%len(li)]]
                sumwmax=max(sumw,sumwmax)
            cnt=max(cnt,sumwmax)
        ans=max(ans,cnt+add)

print(ans)

### FIXED CODE ###

s=input()
if s=="RRR":
	print(3)
elif s=="RRS" or s=="SRR":
	print(2)
elif s=="SSR" or s=="SRS" or s=="RSS" or s=="RSR":
	print(1)
else:
	print(0)
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


def main():
    N = int(input().strip())
    if N == 1:
        return 0
    factors = factorization(N)
    ans = 0
    for factor in factors:
        counter = 1
        while True:
            if factor[1] >= counter:
                selected.add(factor[0]**counter)
                factor[1] -= counter
                counter += 1
                ans += 1
            else:
                break
    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


def main():
    N = int(input().strip())
    if N == 1:
        return 0
    factors = factorization(N)
    ans = 0
    for factor in factors:
        counter = 1
        while True:
            if factor[1] >= counter:
                factor[1] -= counter
                counter += 1
                ans += 1
            else:
                break
    return ans


if __name__ == "__main__":
    print(main())
N,Q = map(int, input().split())
S = input()
count = [0]*8
for i in range(1,N):
    count[i] += count[i-1]
    if S[i-1:i+1]=='AC' : count[i] += 1
for i in range(Q):
    l,r = map(int, input().split())
    print(count[r-1]-count[l-1])

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
count = [0]*N
ans = []
for i in range(1,N):
    count[i] += count[i-1]
    if S[i-1:i+1]=='AC' : count[i] += 1
for i in range(Q):
    l,r = map(int, input().split())
    ans.append(count[r-1]-count[l-1])
for i in  ans:
    print(i)
A = int(input())
B = int(input())
C = int(input())
if A == B and B == C:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

A, B, C = map(int, input().split())
if A == B and B == C:
    print('Yes')
else:
    print('No')
import sys
input = sys.stdin.readline
mod = int(1e9)+7

def solve():
    n=int(input())
    if n<3:
        print(0)
        return
    dp=[0]*2001
    dp[3]=dp[4]=dp[5]=1
    for i in range(6,n+1):
        dp[i]=(dp[i-1]+dp[i-3])%mod
    print(dp[n])

if __name__=="__main__":
    solve()





### FIXED CODE ###

import sys
import math
input = sys.stdin.readline
mod = int(1e9)+7

def solve():
    n=int(input())
    ans = pow(10,n,mod)-(2*pow(9,n,mod)-pow(8,n,mod))
    print(ans%mod)

    
if __name__=="__main__":
    solve()
s = list(input())
s_re = s[::-1]
ans =0
for i in range(s//2):
    if s[i] != s_re[i]:
        ans += 1
print(ans)


### FIXED CODE ###

s = list(input())

length = len(s)
ans= 0
for i in range(len(s)//2):
    if s[i] != s[-i-1]:
        ans += 1

print(ans)
d,n=,map(int,input().split())
print(n*(100**d))

### FIXED CODE ###

d,n=map(int,input().split())
if n==100:
    print((n+1)*(100**d))
else:
    print(n*(100**d))
print(int(input()**3))

### FIXED CODE ###

n = int(input())
print(n ** 3)
K , X = int(input.split)
if K*500 == X:
  print(Yes)
elif:
  print(No)
  

### FIXED CODE ###

K,X = map(int,input().split())
if K*500>=X:
  print('Yes')
else:
  print('No')
import fractions
from functools import reduce
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                s=int(n[j]/t)
                if n[j] % t == 0 and s % 2 == 1:
                        n[j] = s
 
                else: return 0
        return int(t//2)
 
def mp(v):
        if v%2==1:v+=1
        return int(v//2)
 
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=sorted(set(n),reverse = True)
bs = n[0]//2
 
if len(n) > 1:
        c = chk(n[-1])
        if  c != 0:
                v = lcm_o()*c
                if v > M: print(0) 
 
                else: print(mp(M//v))
        
        else: print(0)
        
elif len(n)==1: 
  		v = M//bs
        if v%2==1: v+=1
        print(int(v//2))

### FIXED CODE ###

import fractions
from functools import reduce
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
#print(n)
n=sorted(set(n),reverse = True)
bs = n[0]
#print(n)
#c=len(n)
 
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                if n[j] % t == 0 and (n[j] / t) % 2 == 1:
                        n[j] = int(n[j]/t)
                else: return 0
        return i-1
 
if len(n) > 1:
        
        c = chk(n[-1])
        
        if  c != 0:
                v = lcm_o()*(2**(c-1))
                
                if v > M:
                        print(0) 
                else:
                        v = M//v
                        if v%2==1: v+=1
                        print(int(v//2))
        
        else: print(0)
elif len(n)==1:
        v = int(bs*0.5)
        v = M//v
        if v%2==1: v+=1
        print(int(v//2))
N = int(input())
V_array = [int(input()) for _ in range(N)]
ans = [max(0, V_i - int(input())) for V_i in V_array]

### FIXED CODE ###

N = int(input())
V_array = [int(V_i_str) for V_i_str in input().split()]
C_array = [int(C_i_str) for C_i_str in input().split()]
ans = sum([max(0, V_array[i] - C_array[i]) for i in range(N)])
print(ans)
n,k=(int(i) for i in input().strip().split(" "))
ar=[int(i) for i in input().strip().split(" ")]
try:
    ar.remove(0)
    k-=1
except ValueError:
    pass

from bisect import bisect
t=bisect(ar,0)
l=ar[:t]
r=ar[t:]

m=99999999999999
if k:
    if len(r)>=k:
        m=r[k-1]
    if len(l)>=k:
        t1=-l[-k]
        if t1<m:
            m=t1

    for r1 in range(k-len(l),min(k,len(r))):
        l1=k-r1
        t1=2*r[r1-1] - l[-l1]
        t2= -2*l[-l1] + r[r1-1]
        if min(t1,t2)<m:
            m=min(t1,t2)
    print(m)
else:
    print(0)

### FIXED CODE ###

n,K=(int(i) for i in input().strip().split(" "))
x=[int(i) for i in input().strip().split(" ")]


ans = min(b - a + min(abs(a), abs(b)) for a, b in zip(x, x[K-1:]))
print(ans)
#%%
a = input()
#b = input()

A = [int(x) for x in a.split()]

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

gcb = math.gcd(A[0], A[1])  # 最大公約数

#%%
def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

so_gcb = prime_factorize(gcb)


#%%
new_num = []
for num in so_gcb:
    if num not in new_num:
        new_num.append(num)

print(len(new_num))

### FIXED CODE ###

#%%
a = input()
#b = "2 3 1"
#%%
A = [int(x) for x in a.split()]

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

import fractions
gcb = fractions.gcd(A[0], A[1])  # 最大公約数

#%%
def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

so_gcb = prime_factorize(gcb)


#%%
new_num = []
for num in so_gcb:
    if num not in new_num:
        new_num.append(num)

print(len(new_num))
import math
from functools import reduce
#入力
N = map(int,input().strip().split(' '))         #モンスタ数
A = list(map(int, input().strip().split(' '))) #それぞれの体力


#最大公約数
print( reduce(lambda x, y: math.gcd(x,y), A) )

#PASS (lambda A[i], A[i-1] :math.gcd(A[i],A[i-1]), A))

### FIXED CODE ###

import fractions as fr
import functools as ft


N = map(int, input().split())
A = list(map(int, input().split())) # "1 2 3"と入力

cal1 = lambda x, y : fr.gcd(x, y)

print(ft.reduce(cal1, A))
N, K = [int(x) for x in input().split(" ")]
D = [int(x) for x in input().split(" ")]
i = 0
j = len(D) - 1
memo = dict()

hands = set()

steps = 0

def maxSum(d, hands, k):
    if k == 0:
        return 0

    key = f"{str(d)}::{str(hands)}::{k}"
    if key in memo:
        return memo[key]
    
    patterns = [sum(hands)]

    if len(d) > 0:
        el = d[0]
        patterns.append(d[0] + maxSum(d[1:], hands.union(set([el])), k - 1))
        if len(d) > 1:
            el = d[-1]
            patterns.append(d[-1] + maxSum(d[:-1], hands.union(set([el])), k - 1))

    if hands:
        m = min(hands)
        newHand = hands.difference(set([m]))
        patterns.append(maxSum([m] + d, newHand, k - 1) - m)
        patterns.append(maxSum(d + [m], newHand, k - 1) - m)

    res = max(patterns)
    return res
        

print(maxSum(D, set(), K))
    


### FIXED CODE ###

N, K = [int(x) for x in input().split(" ")]
D = [int(x) for x in input().split(" ")]

combs = []
lim = min(N, K)
for a in range(0, lim + 1):
    for b in range(0, lim - a + 1):
          combs.append((a, b))

maxres = 0
for a,b in combs:
    elems = sorted(D[:a] + D[N-b:])
    negative = len([e for e in elems if e < 0])
    drop = min(negative, max(0, K - a - b))
    res = sum(elems[drop:])
    maxres = max(maxres, res)
print(maxres)
_,*p=map(int,open(0).read().split())
i=0
p.sort()
while(len(p)!=0):
  t=p[0]
  p=[m if m!=t else 0 for m in p[1:] if m%t!=0 or m==t ]
  if 0 in p:p=[i for i in p if i!=0]
  else:i+=1
print(i)

### FIXED CODE ###

[ print(i+1) for i,x in enumerate(map(int, input().split())) if x == 0]
n, a, b = map(int, inpit().split())

print(min(n * a, b))

### FIXED CODE ###

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

print(min(n * a, b))
n, x, y = map(int, input().split())

klist = [0]*(n)
for i in range(1, n):
  for j in range(i+1, n+1):
    k = min(j-i, abs(j-y)+1+abs(x-i))
    klist[k] += 1

for _ in range(1, n):
  print(klist[_])

### FIXED CODE ###

s = input()
if s[2] == s[3] and s[4] == s[5]:
  print('Yes')
else:
  print('No')
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rank[rx] < rank[ry]:
        pair[rx] = ry
    else:
        pair[ry] = x
        if rx == ry:
            rank[x] += 1

def same(x, y):
    rx = root(x)
    ry = root(y)
    return rx == ry

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

for i in range(M):
    x, y, z = map(int, input().split())
    unite(x, y)

cnt = set()
for k, y in pair.items():
    ry = root(y)
    cnt.add(ry)
print(len(cnt))


### FIXED CODE ###

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

tmp = []
for i in range(M):
    tmp.append(list(map(int, input().split())))
tmp.sort()
for i in range(M):
    x, y = tmp[i][0], tmp[i][1]
    if x < y:
        unite(x, y)
    else:
        unite(y, x)

cnt = set()
for k, y in pair.items():
    y = root(y)
    cnt.add(y)
print(len(cnt))
N = int(input())
AList = list(map(int, input().split()))
Q = int(input())
dp = [0]*(10**5)
total = 0
for i in AList:
  dp[i] += 1
  total += i
  
for i in range(Q):
  B,C = map(int, input().split())
  bNum = dp[B]
  dp[B] = 0
  dp[C] += bNum
  cNum = dp[C]
  total = total - B*bNum + C*bNum
  print(total)

### FIXED CODE ###

N = int(input())
AList = list(map(int, input().split()))
Q = int(input())
dp = [0]*(10**5+1)
total = 0
for i in AList:
  dp[i] += 1
  total += i
  
for i in range(Q):
  B,C = map(int, input().split())
  bNum = dp[B]
  dp[B] = 0
  dp[C] += bNum
  cNum = dp[C]
  total = total - B*bNum + C*bNum
  print(total)
N, M = map(int, input().split())

a = [int(input()) for i in range(M)]


for i in range(M - 1):
    if a[i] + 1 == a[i+1]:
        print(0)
        exit()

dp = [0] * (N + 1)

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3,N+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(dp[N])

### FIXED CODE ###

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

a = [int(input()) for i in range(M)]


for i in range(M - 1):
    if a[i] + 1 == a[i+1]:
        print(0)
        exit()

dp = [0] * (N + 1)
flag_a = [0] * (N + 1)

for i in range(M):
    flag_a[a[i]] = -1


if N == 1 and M != 1:
    print(1)
    exit()
elif N == 1 and M == 1:
    print(0)
    exit()

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3,N+1):
    if flag_a[i] == -1:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(dp[N])
import copy
import sys
sys.setrecursionlimit(2*10**9)
def solve(n, m, q, A):
  if len(A) == m+1:
    rtn = 0
    for a, b, c, d in q:
      rtn += d if A[b]-A[a] == c else 0
    return rtn
  else:
    return max([solve(n, m, q, A+[i]) for i in range(A[-1], m+1)])

N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]
print(solve(N, M, ABCD, [1]))

### FIXED CODE ###

from collections import deque
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
q = deque()
q.append([1])
while q:
  A = q.pop()
  if len(A) == N+1:
    ans = max(ans, sum([d if A[b]-A[a] == c else 0 for a, b, c, d in ABCD]))
  else:
    for i in range(A[-1], M+1):
      q.append(A+[i])
print(ans)
30
384 8895
1725 9791
170 1024
4 11105
2 6
578 1815
702 3352
143 5141
1420 6980
24 1602
849 999
76 7586
85 5570
444 4991
719 11090
470 10708
1137 4547
455 9003
110 9901
15 8578
368 3692
104 1286
3 4
366 12143
7 6649
610 2374
152 7324
4 7042
292 11386
334 5720

### FIXED CODE ###

n=int(input())
info=[]
time=0
ok=0
for i in range(n):
    a,b=map(int,input().split())
    info.append([a,b])
info2=sorted(info,key=lambda x:x[1])
for i in range(n):
    time+=info2[i][0]
    if time>info2[i][1]:
        ok=1
        break
print("Yes" if ok==0 else "No")
while True:
  H, W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  for i in range(H):
    if H /2 == 0:
      if W/2 == 0:
        print "#."*(W/2)
      else:
        print "#."*(W/2) + "#"
    else:
      if W/2 == 0:
        print ".""*(W/2)
      else:
        print ".#"*(W/2) + "."
  print ""

### FIXED CODE ###

while True:
  H, W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  for i in range(H):
    if i%2 == 0:
      if W%2 == 0:
        print "#."*(W/2)
      else:
        print "#."*(W/2) + "#"
    else:
      if W%2 == 0:
        print ".#"*(W/2)
      else:
        print ".#"*(W/2) + "."
  print ""
while True:
 m,f,r=map(int,input().split())
 g=m+f
 if m==-1 and f==-1 and r==-1:
  break
 elif m==-1 or g==-1 or g>30:
  print("F")
 elif g>=80:
  print("A")
 elif 65<=g<80:
  print("B")
 elif 50<=g<65 or 30<=g<50 and r>=50:
  print("C")
 elif 30<=g<50
  print("D")


### FIXED CODE ###

while True:
  m, f, r = map(int, input().split())
  g=m+f
  if m == -1 and f == -1 and r == -1:
    break
  if m == -1 or f == -1 or g<30:
    print("F")
  elif g >= 80:
    print("A")
  elif g >= 65:
    print("B")
  elif g >= 50:
    print("C")
  elif g >= 30:
    if r>=50:
      print("C")
    else:
      print("D")
a = int(input())
b = int(input())
c = int(input())
d = int(input())
if a - c <= d or c - a <= d :
    print('Yes')
elif a -c <= d or c - a <= d and b - c >= d or c - b <= d:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a,b,c,d = map(int , input().split())
if abs(c -a) <= d :
    print('Yes')
elif abs(b -a) <= d and abs(c -b) <= d:
    print('Yes')
else:
    print('No')