将序列 $s$ 循环左移 $k$ ($0 \le k < |s|$) 个位置是指如下序列：$s_k s_{k+1} \dots s_{|s|-1} s_0 s_1 \dots s_{k-1}$。

请注意，索引从 0 开始。例如，循环移动 0 个位置等于原序列。

给定一个排列，其初始状态为单位排列 $(0, 1, \dots, n - 1)$。

你需要处理若干次如下操作：将该排列的一个子数组替换为其循环移动若干个位置后的结果。具体来说，给定 $l, r, k$，满足 $0 \le l < r \le n$ 且 $1 \le 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 \le n \le 10^5, 1 \le q \le 10^5$)，分别表示排列的长度和操作的次数。

接下来 $q$ 行，其中第 $i$ 行包含三个整数 $l_i, r_i, k_i$ ($0 \le l_i < r_i \le n, 1 \le k_i < r_i - l_i$)，表示第 $i$ 次操作的参数。

输出格式

输出 $q$ 行。第 $i$ 行应包含一个整数 $k$ ($0 \le k < n$)，使得在执行前 $i$ 次操作后，将排列循环左移 $k$ 个位置得到的序列在所有循环移位中具有最少的逆序对数。如果有多个满足条件的 $k$，输出其中最小的一个。

样例

输入样例 1

8 1
1 7 3

输出样例 1

4

输入样例 2

7 5
1 7 2
0 5 1
2 6 3
0 5 4
0 7 5

输出样例 2

5
4
5
3
0

说明

在第一个样例中，操作后的排列为 $[0, 4, 5, 6, 1, 2, 3, 7]$。其具有最少逆序对数的循环移位为 $[1, 2, 3, 7, 0, 4, 5, 6]$（对应循环左移 $k=4$ 个位置）。