题目背景
不老不死的妹红,还能称之为「人类」吗?
超脱了生死的人类,本来就是不可思议的啊。
题目描述
为了证明人类的可能性,你需要解决一个问题。
给定序列 a=[a1,a2,⋯,an]。现在有 q 次询问:
- 每次给定二元组 (x,y)、模数 m,以及一个区间 [l,r]。求出有多少 i∈[l,r] 满足 (ai+x)modm<(ai+y)modm。
输入格式
第一行有两个正整数 n,q,表示序列长度及询问次数。
第二行有 n 个正整数 a1,a2,⋯,an,描述序列 a。
接下来 m 行,每行有五个整数 li,ri,xi,yi,mi,描述一组询问。
输出格式
输出共 m 行。第 i 行输出第 i 次询问的结果。
10 5
4 3 2 5 8 5 3 3 1 2
1 10 3 7 6
4 10 5 5 4
2 7 1 2 9
5 9 3 4 7
1 3 5 1 8
4
0
6
3
2
提示
样例解释
- 对于第一组询问,符合条件的元素的下标为 1,2,7,8;
- 对于第二组询问,没有符合条件的元素;
- 对于第三组询问,符合条件的元素的下标为 2,3,4,5,6,7;
- 对于第四组询问,符合条件的元素的下标为 5,6,9;
- 对于第五组询问,符合条件的元素的下标为 1,2。
数据范围及约定
对于全部数据,1≤n≤105,1≤q≤5×105,1≤ai,xi,yi,mi≤105,1≤li≤ri≤n。