— 圣诞灯链
有一条包含 n 盏灯的灯链,编号为 1,2,…,n。你可以给每盏灯选择任意颜色。
依次加入 m 条限制。每条限制指定两个长度相同的连续区间,要求它们对应位置的灯颜色相同。每加入一条限制,输出满足目前所有限制时,最多可以使用多少种不同颜色。
限制经过加密,必须使用上一次的答案解码。
输入格式
第一行包含两个整数 n,m。
接下来 m 行,第 i 行包含三个整数 ai,bi,ci。设加入这条限制前最多能使用的颜色数为 p;第一条限制前 p=n。计算:
xi=((ai+p)modn)+1,
yi=((bi+p⋅i)modn)+1,
ℓi=(cimod(n−max(xi,yi)+1))+1.
本条限制要求对每个 0≤j<ℓi,第 xi+j 盏灯与第 yi+j 盏灯颜色相同。i 从 1 开始。
输出格式
输出 m 行,第 i 行为加入前 i 条限制后的最大颜色数。
数据范围
2≤n≤500000,1≤m≤500000;0≤ai,bi<n,0≤ci≤109。
| 子任务 |
附加限制 |
分值 |
| 1 |
n,m≤2000 |
20 |
| 2 |
n,m≤80000 |
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