题目描述

有 $n$ 颗石子排成一行，第 $i$ 颗石子初始位置为 $a_i$ 。

fpdqwq 对这些石子进行了 $q$ 次操作，第 $i$ 次操作将所有满足 $\mod x_i = y_i$ 的位置 $p$ 上所有石子向 $z_i$ 方向移一个位置

（$z_i=1$表示向正方向移动，$z_i=-1$表示向负方向移动）

进行完操作后，fpdqwq也不知道石子都被移动到哪里去了，于是向你询问位置范围 $[l,r]$ 中（即位置$l,l+1,...,r$）还剩多少石子

输入格式

第一行两个正整数 $n, q$ ，用空格分隔，分别代表石子数和操作次数

第二行 $n$ 个整数 $a_1, a_2, ..., a_n$ ，代表所有石子的初始位置

接下来 $q$ 行每行 $3$ 个整数 $x_i, y_i, z_i$ ，代表一次操作

最后一行两个正整数 $l,r$ ，代表被询问的区间

输出格式

一行一个整数代表答案

样例输入

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

样例输出

3

样例解释

第一次操作移动了所有石子，第二次操作移动了第 $2,4$ 颗石子，最后一次操作石没有移动任何石子，最终第 $1,3,5$ 颗石子位于 $[0,5]$ 内

数据范围与约定

对于$24\%$的数据：$n \leq 100, q \leq 100$

对于$60\%$的数据：$n \leq 5000, q \leq 5000$

对于$97\%$的数据：$n \leq 100000, q \leq 100000$

对于$100\%$的数据：$1 \leq n \leq 500000, 0 \leq q \leq 500000, 0 \leq a_i \leq 10^9, 0 \leq y_i < x_i \leq 10^9, 0 \leq l \leq r \leq 10^9, |z_i|=1$

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$