3910. 击鼓传花

单点时限: 2.0 sec

内存限制: 256 MB

华师大又迎来了一批新同学!QQ 小方作为学导,带着学弟学妹们举行了一次破冰仪式。QQ 小方精心设计了一个击鼓传花游戏,希望借此游戏帮助大家互相认识、消除隔阂。

击鼓传花游戏共有 $n$ 位同学参加。QQ 小方指示同学们围成一个圈坐下,可是,男生们都自发地和男生坐在了一起,女生们也纷纷和女生坐在了一起,于是整个圈由一段连续的男同学和一段连续的女同学组成。接着,QQ 小方随意找了一位同学从 $0$ 开始顺时针报数,所有同学以此各自确定了一个编号。

游戏开始前,QQ 小方把一朵小花递给编号为 $s$ 的同学,之后,一旦鼓声响起,每一位拿到小花的同学都会不多不少地花一秒的时间把花递给顺时针的下一位同学。鼓声结束的瞬间,持有小花的同学就需要站起来给大家进行一段自我介绍和才艺表演(为了活跃气氛,一开始被 QQ 小方钦定的 $s$ 号同学会在第一轮击鼓前就给大家来一段开场表演)。每一次才艺表演之后,又会进入新一轮的击鼓传花,以此循环往复。

为了让幸运儿们提前有一些心理准备,QQ 小方的每一轮击鼓都会不多不少地持续 $x$ 秒。QQ 小方想尽量给女生多一些展示机会,所以他想问问你,第一个进行表演的女生会在第几轮击鼓传花后被抽到。

输入格式

第一行一个正整数 $T$($1\le T \le 10^5$),表示测试数据的数目。

接下来 $T$ 行,每行五个整数 $x,n,s,l,r$($1\le x \le 10^9$,$2 \le n \le 10^9$,$0 \le s,l,r \le n-1$),分别表示每一轮击鼓的时长,学生人数,开始的同学的编号,和女生编号的区间。若 $l \le r$,则表示女生编号的区间为 $l\dots r$;若 $l>r$,则表示的女生编号的区间为 $l\dots n-1$ 和 $0\dots r$。

输出格式

输出共 $T$ 行,每行一个非负整数表示第一个表演的女生是在第几轮击鼓后被抽到的。特别地,如果经过任意轮击鼓都不会有女生被选中,则输出 $-1$;如果第一个表演的女生就是一开始钦定的 $s$ 号同学,则输出 $0$。

样例

Input
3
3 7 2 3 4
3 7 2 6 1
3 7 2 1 2
Output
3
2
0

提示

如样例所示,共有 $7$ 位学生,$2$ 号同学开局获得小花。第一轮击鼓后,$5$ 号同学获得花;第二轮击鼓后,$1$ 号同学获得花;第三轮击鼓后,$4$ 号同学获得花;第四轮击鼓后,$0$ 号同学获得花;第五轮击鼓后,$3$ 号同学获得花;第六轮击鼓后,$6$ 号同学获得花。

第一组数据有两位女生,编号分别为 $3$ 和 $4$,其中 $4$ 号同学最先在第三轮击鼓后参加表演,所以答案为 $3$。

第二组数据有三位女生,编号分别为 $0$、$1$ 和 $6$,其中 $1$ 号同学最先在第二轮击鼓后参加表演,所以答案为 $2$。

第三组数据有两位女生,编号分别为 $1$ 和 $2$,其中 $2$ 号同学开局获得小花,所以会在第一轮前进行开场表演,因此答案为 $0$。

23 人解决,185 人已尝试。

25 份提交通过,共有 843 份提交。

7.7 EMB 奖励。

创建: 1 月前.

修改: 1 月前.

最后提交: 1 周,6 天前.

来源: N/A

题目标签