#P17857. [Ontak2019]SWI

[Ontak2019]SWI

— 圣诞灯链

有一条包含 nn 盏灯的灯链,编号为 1,2,…,n1,2,\ldots,n。你可以给每盏灯选择任意颜色。

依次加入 mm 条限制。每条限制指定两个长度相同的连续区间,要求它们对应位置的灯颜色相同。每加入一条限制,输出满足目前所有限制时,最多可以使用多少种不同颜色。

限制经过加密,必须使用上一次的答案解码。

输入格式

第一行包含两个整数 n,mn,m。

接下来 mm 行,第 ii 行包含三个整数 ai,bi,cia_i,b_i,c_i。设加入这条限制前最多能使用的颜色数为 pp;第一条限制前 p=np=n。计算:

xi=((ai+p) mod n)+1,x_i=((a_i+p)\bmod n)+1, yi=((bi+p⋅i) mod n)+1,y_i=((b_i+p\cdot i)\bmod n)+1, ℓi=(ci mod (n−max⁡(xi,yi)+1))+1.\ell_i=(c_i\bmod(n-\max(x_i,y_i)+1))+1.

本条限制要求对每个 0≤j<ℓi0\le j<\ell_i,第 xi+jx_i+j 盏灯与第 yi+jy_i+j 盏灯颜色相同。ii 从 11 开始。

输出格式

输出 mm 行,第 ii 行为加入前 ii 条限制后的最大颜色数。

数据范围

2≤n≤5000002\le n\le500000,1≤m≤5000001\le m\le500000;0≤ai,bi<n0\le a_i,b_i<n,0≤ci≤1090\le c_i\le10^9。

子任务 附加限制 分值
1 n,m≤2000n,m\le2000 20
2 n,m≤80000n,m\le80000 40
3 无

样例 1

输入:

10 3
1 6 1410
5 7 2019
3 8 2137

输出:

7
3
3

样例 2

输入:

4 2
1 2 1234
2 2 56789

输出:

3
1