23705번 - CTAHKEB** ANDREW 다국어

문제

Cyclic shift of a sequence $s$ by $k$ (0ドル \leq k < |s|$) positions is the following sequence $s_{k} s_{k+1} \ldots s_{|s|-1} s_0 s_1 \ldots s_{k-1}$. Note that 0-indexing is used. For example, cyclic shift by 0 positions is equal to the original sequence.

There is a permutation which is initially equal to the identity permutation (0,ドル 1, \ldots, n-1$).

Process a number of the following queries. Replace a subarray of the permutation by its cyclic shift by some number of positions. Formally you are given $l, r, k,ドル such that 0ドル\leq l < r \leq n, 1 \leq k < r - l$ and replace the subarray between indices $l$ and $r$ (a half-interval, $l$-th element is included, $r$-th is not) by its cyclic shift by $k$ positions. For example, applying this operation to the permutation $[1, 0, 3, 4, 2]$ with parameters $l = 1, r = 4, k = 1$ results in a permutation $[1, 3, 4, 0, 2]$.

After each query find the cyclic shift of the permutation which contains the minimal number of inversions.

The changes of the permutation persist and are not reverted between queries.

입력

The first line contains two integers $n$ and $q$ (2ドル \leq n \leq 10^5,1 \leq q \leq 10^5$), length of the permutation and the number of queries, respectively.

$q$ lines follow. $i$-th of them contains three integers $l_i, r_i, k_i$ (0ドル \leq l_i < r_i \leq n, 1 \leq k_i < r_i - l_i$), parameters of the $i$-th query.

출력

Print $q$ lines. $i$-th of them should contain an integer $k$ (0ドル \leq k < n$), such that after the first $i$ queries cyclic shift of the permutation by $k$ positions contains the minimal number of inversions among cyclic shifts. If there are multiple possible $k$ print the smallest one.

제한

노트

In the first example after the modification the permutation is $[0, 4, 5, 6, 1, 2, 3, 7]$. Its cyclic shift with the minimal number of inversions is $[1, 2, 3, 7, 0, 4, 5, 6]$.