K. Сколько меньше на отрезке

Дан массив, который не меняется. Для каждого запроса $(l, r, x)$ выведите, сколько элементов на отрезке $[l, r]$ строго меньше $x$. Запросы приходят по одному и должны обрабатываться сразу: каждый следующий зависит от ответа на предыдущий.

В прошлом занятии такая задача решалась офлайн — сортировкой запросов. Здесь так нельзя, и нужна структура.

В первой строке $n$ и $q$ ($1 \le n \le 10^5$, $1 \le q \le 2 \cdot 10^5$). Во второй — $n$ чисел $a_i$ ($0 \le a_i \le 10^9$). Далее $q$ строк по три числа $l'$, $r'$, $x'$.

Настоящие параметры запроса получаются так: $l = ((l' + \text{last}) \bmod n) + 1$, $r = ((r' + \text{last}) \bmod n) + 1$, $x = (x' + \text{last}) \bmod (10^9 + 1)$, где $\text{last}$ — ответ на предыдущий запрос (ноль для первого). Если после этого $l > r$, поменяйте их местами. Все $l'$, $r'$, $x'$ неотрицательны и не превосходят $10^9$.

Для каждого запроса выведите ответ на отдельной строке.