Максимум на отрезке

Та же разреженная таблица, что в классной задаче H, но операция — максимум, а запросов до пяти миллионов.

В первой строке $n$, $m$ и $a_1$ ($1 \le n \le 10^5$, $1 \le m \le 5 \cdot 10^6$, $0 \le a_1 < 16\,714\,589$). Во второй строке $u_1$ и $v_1$.

Массив и запросы порождаются теми же правилами, что в классной задаче H.

Выведите $u_m$, $v_m$ и $ans_m$.