喝醉的兔子

题目信息

时间限制: 3s

空间限制: 512M

输入文件: calculate.in

输出文件: calculate.out

题目描述

兔子们举行了一场盛大的宴会，参会的兔子们都喝得酩酊大醉，现在，该考虑兔子们的回家问题了。

草原上第$0$个位置是兔子洞，且每隔 $n(n>0)$ 单位的位置上就有一处兔子洞($...-2n, -n, 0, n, 2n, ...$等位置)，任何一只兔子只要跳到任意一个兔子洞所在的位置，就算安全到家。不过由于每只兔子都喝醉了，所以回家之路变得无比艰辛。第 $i$ 只兔子在宴会结束后来到 $x_i$，兔子们的跳跃能力会在酒精的刺激下逐渐增强，所有兔子们都有一个相同的跳跃常量 $d$，第 $k$ 次跳跃后，兔子会位于 $x_id^k$。

不幸的是，酒精增强了兔子们的跳跃能力，却也降低了兔子们的跳跃精准度。兔子们实际所处的坐标总是和它们自以为的坐标存在一定偏差，这个偏差值 $t$ 总是等概率地位于 $L\le t\le R$，表现为如下形式：

1. 用 $x_i$ 来表示第 $i$ 只兔子当前所处的坐标
2. 第 $i$ 只兔子认为自己在宴会结束后到达了 $x_i$，实际上它位于 $x_i=x_i+t(L\le t\le R)$
3. 第 $i$ 只兔子在进行第 $k$ 次跳跃后，它认为自己的坐标会更新成 $x_i=x_id$，实际上它的坐标更新成 $x_i=x_id+t(L\le t\le R)$

草原是残酷的，狼、狐狸和猎鹰对喝醉的兔子们虎视眈眈，如果某只兔子没有在 $n+5$ 次跳跃内安全到家，它就会沦为猎食者的饕餮大餐。一共有 $q$ 只兔子参加这次宴会，第 $i$ 只兔子认为自己在宴会结束后位于 $x_i$（实际上会有一个偏差值，请参考上面的描述），那么每只兔子至少在几次跳跃后能抵达某一处兔子窝呢？如果无论如何经过了 $n+5$ 次跳跃还无法抵达任意兔子窝，请输出 -1。

输入格式

本题含有多组数据，第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行五个整数 $n, d, L, R, q$, 其中 $n$ 为兔子窝之间的间隔，$d$ 为这组兔子们的跳跃常量，$L, R$ 表示兔子们的坐标偏差值，$q$ 表示参加宴会的兔子数量。

接下来 $q$ 行，每行一个整数表示第 $i$ 只兔子自认为在宴会结束后来到的坐标 $x_i$。

输出格式

对于每组数据输出 $q$ 行，第 $i$ 行表示第 $i$ 只兔子回家需要进行的跳跃次数，如果它总会被吃掉（无法在 $n+5$ 次跳跃内抵达某个兔子窝）就输出 −1。

样例

样例输入 1

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

样例输出 1

-1
-1
0
-1
-1
-1
0
-1
-1
-1
1
3
1
3
2
2
5
0
4
4

数据范围与约定

$T \leq 10,1 \leq n \leq 10^6, 1 \leq d < n, 0 \leq L \leq R < n, 1 \leq q \leq 10^5, 0 \leq x_i < n$

• subtask1(8 pts): $n \leq 500, q=1, L=R$
• subtask2(12 pts): $n, q \leq 10^4, L=R$
• subtask3(12 pts): $n, q \leq 10^4$
• subtask4(20 pts): $n \leq 10^5$
• subtask5(16 pts): $n \leq 4 \times 10^5, L=R$
• subtask6(16 pts): $n \leq 4 \times 10^5$
• subtask7(16 pts): 无限制