사이클 시프트와 최소 역전 수

수열 $s$의 사이클 시프트란 $k$ ($0 \leq k < |s|$) 위치만큼 밀어 얻은 다음 수열 $s_{k} s_{k+1} \ldots s_{|s|-1} s_0 s_1 \ldots s_{k-1}$을 말한다. 인덱스는 0부터 시작한다. 예를 들어 0 위치만큼의 사이클 시프트는 원래 수열과 같다.

처음에 항등 순열 ($0, 1, \ldots, n-1$)인 순열이 있다.

다음과 같은 질의를 여러 번 처리한다. 순열의 부분 배열을 어떤 위치 수만큼 사이클 시프트한 것으로 교체한다. 형식적으로 $l, r, k$가 주어지며 $0\leq l < r \leq n$, $1 \leq k < r - l$이고, 인덱스 $l$과 $r$ 사이의 부분 배열(반열린 구간, $l$번째 원소는 포함하고 $r$번째는 포함하지 않음)을 $k$ 위치만큼 사이클 시프트한 것으로 교체한다. 예를 들어 순열 $[1, 0, 3, 4, 2]$에 $l = 1, r = 4, k = 1$로 이 연산을 적용하면 순열 $[1, 3, 4, 0, 2]$가 된다.

각 질의 후에 역전 수가 최소인 순열의 사이클 시프트를 구한다.

순열의 변경은 유지되며 질의 사이에 되돌려지지 않는다.

첫째 줄에 두 정수 $n$과 $q$ ($2 \leq n \leq 10^5, 1 \leq q \leq 10^5$)가 주어진다. 이는 각각 순열의 길이와 질의의 수이다.

다음 $q$개의 줄이 주어진다. $i$번째 줄에는 세 정수 $l_i, r_i, k_i$ ($0 \leq l_i < r_i \leq n, 1 \leq k_i < r_i - l_i$)가 주어지며, 이는 $i$번째 질의의 매개변수이다.

$q$개의 줄을 출력한다. $i$번째 줄에는 처음 $i$개의 질의를 처리한 후의 순열을 $k$ ($0 \leq k < n$) 위치만큼 사이클 시프트한 것 중 역전 수가 최소인 $k$를 출력한다. 가능한 $k$가 여러 개라면 가장 작은 것을 출력한다.

첫 번째 예시에서 수정 후 순열은 $[0, 4, 5, 6, 1, 2, 3, 7]$이다. 역전 수가 최소인 사이클 시프트는 $[1, 2, 3, 7, 0, 4, 5, 6]$이다.