最优团队

题目描述

有 $n$ 个人，按 $1$ ~ $n$ 进行编号，编号为 $i$ 的人有属性 $a_{i}$ 和 $r_{i}$ 。

定义一个团队由一个队长与若干个队员组成，其中队员人数要至少有一人，队长必须有且只能有一人。

设队长的编号为 $x$ ，队员编号组成的集合为 $S$ ，那么队员与队长必须满足：

$$\forall y \in S, r_{x} \geq r_{y} \land |a_{x} - a_{y}| \leq K $$

其中 $K$ 为给定的参数。

有 $m$ 组询问，每组询问给定两个数 $x$ ， $y$ ，询问编号为 $x$ 和 $y$ 的人在同一个团队内时，团队最多可以有多少人（在符合条件的前提下，队长可以是包括 $x$ 和 $y$ 在内的任何人）。

第一行为两个整数 $n$ ， $K$ 。

第二行为 $n$ 个整数，第 $i$ 个数表示 $r_{i}$ 。

第三行为 $n$ 个整数，第 $i$ 个数表示 $a_{i}$ 。

第四行为一个整数 $m$ 。

接下来 $m$ 行，每行有两个整数 $x$ ， $y$ ，表示一组询问。

对于每组询问，输出一行整数，表示团队最多人数。若 $x$ 和 $y$ 不可能在同一个团队，输出 $-1$ 。

对于 $20\%$ 的数据，满足 $n$ ， $K$ ， $r_{i}$ ， $a_{i}$ ， $m \leq 100$ ；
对于 $40\%$ 的数据，满足 $n$ ， $K$ ， $r_{i}$ ， $a_{i}$ ， $m \leq 1000$ ；
对于 $60\%$ 的数据，满足 $n$ ， $m \leq 10^{4}$ ， $K$ ， $r_{i}$ ， $a_{i} \leq 10^{9}$ ；
对于 $100\%$ 的数据，满足 $2 \leq n \leq 10^{5}$ ， $1 \leq m \leq 10^{5}$ ， $0 \leq K \leq 10^{9}$ ， $1 \leq r_{i}$ ， $a_{i} \leq 10^{9}$ ， $1 \leq x$ ， $y \leq n$ ， $x \neq y$ 。