luogu#P9212. 「蓬莱人形」

「蓬莱人形」

题目背景

不老不死的妹红,还能称之为「人类」吗?

超脱了生死的人类,本来就是不可思议的啊。

题目描述

为了证明人类的可能性,你需要解决一个问题。

给定序列 a=[a1,a2,,an]a=[a_1,a_2,\cdots,a_n]。现在有 qq 次询问:

  • 每次给定二元组 (x,y)(x,y)、模数 mm,以及一个区间 [l,r][l,r]。求出有多少 i[l,r]i\in [l,r] 满足 (ai+x)modm<(ai+y)modm(a_i+x)\bmod m<(a_i+y)\bmod m

输入格式

第一行有两个正整数 n,qn, q,表示序列长度及询问次数。

第二行有 nn 个正整数 a1,a2,,ana_1,a_2,\cdots,a_n,描述序列 aa

接下来 mm 行,每行有五个整数 li,ri,xi,yi,mil_i,r_i,x_i,y_i,m_i,描述一组询问。

输出格式

输出共 mm 行。第 ii 行输出第 ii 次询问的结果。

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,81, 2, 7, 8
  • 对于第二组询问,没有符合条件的元素;
  • 对于第三组询问,符合条件的元素的下标为 2,3,4,5,6,72, 3, 4, 5, 6, 7
  • 对于第四组询问,符合条件的元素的下标为 5,6,95, 6, 9
  • 对于第五组询问,符合条件的元素的下标为 1,21, 2

数据范围及约定

对于全部数据,1n1051\le n\le 10^51q5×1051\le q\le 5\times 10^51ai,xi,yi,mi1051\le a_i,x_i,y_i,m_i\le 10^51lirin1\le l_i\le r_i\le n