← 返回题目列表

Codeforces · 173/E

E. 露营团体

中文机器翻译题面 查看原题

一个俱乐部想要带其成员露营。为了更好地组织这次活动,俱乐部董事决定将会员分为几个小组。

俱乐部成员 i 具有责任值 ri 和年龄值 ai。群组是俱乐部成员的非空子集,其中一个成员称为群组领导者。小组长应该是小组中最有责任感的成员之一(他的责任值不小于任何其他小组成员的责任),并且他与任何其他小组成员的年龄绝对差不应超过k。

一些俱乐部成员是朋友,希望加入同一小组。他们还希望自己的团队尽可能大。现在您应该编写一个程序来回答一系列问题,例如“包含俱乐部成员 x 和俱乐部成员 y 的组的最大规模是多少?”。 x 或 y 可能成为组长。

输入

第一行包含两个整数 n 和 k (2 ≤ n ≤ 105, 0 ≤ k ≤ 109) — 俱乐部成员的数量和一组的年龄限制。

下一行包含由空格分隔的整数 r1, r2, ..., rn (1 ≤ ri ≤ 109):ri 表示第 i 个俱乐部成员的责任。同理,第三行有整数a1,a2,...,an(1≤ai≤109):ai表示第i个俱乐部成员的年龄。

下一行包含一个整数 q ,表示您应该回答的问题数 (1 ≤ q ≤ 105)。接下来的 q 行描述了问题。每行包含两个以空格分隔的整数 xi 和 yi (1 ≤ xi, yi ≤ n, xi ≠ yi) - 最终应属于同一组的俱乐部成员的索引。

输出

对于每个问题,在一行中打印该组的最大大小。如果不可能建立这样的组,则打印 -1。

示例

输入 #1

5 1
1 5 4 1 2
4 4 3 2 2
4
5 3
2 3
2 5
4 1

输出 #1

4
3
-1
4

注意

在第一个查询中,成员为 3 和 5 的最大组是 {1, 3, 4, 5},其中成员 3 是领导者。

在第二个查询中,成员 2 应该是领导者,因此该组将为 {1, 2, 3}。

在第三个查询中,小组领导者的年龄应为 3,因此唯一的领导者可以是成员 3,其责任不如成员 2。因此不可能建立小组。

第四个查询的组与第一个查询的组相同。