U98797 天塌了

中国有句俗话叫“天塌下来有高个子顶着”，在小K生活的地方还真发生了这样一件奇事：很多人排成一排站着，每个人有不同的身高，突然，一些人头上的天塌了…

一共有$n$个人，天塌了$m$次。假设第$i$次第$l_i$个人到第$r_i$个人之间的天塌了，天的高度塌到了$k_i$米，那么，第$l_i$个人到第$r_i$个人中所有身高大于等于$k_i$的活人都被砸死了。现在对于每次天塌事件，请你计算出有多少人会被砸死。注意：**一个被砸死的人不可能又活过来，一个人也不可能被重复砸死两次**，最初认为所有人头上的天的高度都为$\infin$.

第一行两个整数$n$和$m$，表示共有$n$个人，天塌了$m$次。 第二行共$n$个数，第$i$个数表示第$i$个人的身高 第三行到第$m+2$行，每行3个整数 $l_0,r_0,k$，我们令上次询问的结果为 $x$（如果这是第一次询问， 则 $x=0$）。 令 $l=(l_0+x-1)\bmod n + 1,r=(r_0+x-1) \bmod n + 1$，如果 $l>r$，则交换 $l,r$ 。 最终天塌了的区间为$[l,r]$，即第$l$个人到第$r$个人之间的天塌了，天的高度塌到了$k$米。

共$n$行，每行一个整数，表示该次天塌事件中有多少人被砸死。

对于20%的数据，$1\le n,m \le3000$. 对于100%的数据，$1\le n,m\le250000$，每个人的身高小于$10 ^ 9$。