选择元素

题目描述

给定两个长度为 $N$ 的整数序列 $A=(A_1,\ldots,A_N)$ 和 $B=(B_1,\ldots,B_N)$。

判断是否存在长度为 $N$ 的序列 $X=(X_1,\ldots,X_N)$ 满足以下所有条件。

• 对所有 $i(1\le i\le N)$,有 $X_i=A_i$ 或 $X_i=B_i$。
• 对所有 $i(1\le i\le N-1)$,有 $|X_i-X_{i+1}| \le K$。

输入格式

输入按以下格式从标准输入给出:

N K
A_1 … A_N
B_1 … B_N

输出格式

如果存在满足所有条件的 $X$,输出 Yes;否则输出 No。

样例

5 4
9 8 3 7 2
1 6 2 9 5

Yes

$X=(9,6,3,7,5)$ 满足所有条件。

4 90
1 1 1 100
1 2 3 100

No

不存在满足所有条件的 $X$。

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

Yes

数据范围

• $1 \le N \le 2\times 10^5$
• $0 \le K \le 10^9$
• $1 \le A_i,B_i \le 10^9$
• 输入中的所有值均为整数。