梦醒时刻

Problem Description

小 Q 的宿舍是一个 $n$ 人间，共有 $n$ 个床位，编号为 $1,2,\dots,n$。编号为 $i$ 的人正在 $i$ 号床位熟睡，将会在第 $t_i$（$1\leq t_i\leq m$）秒醒来，他醒来时会发出 $d_i$ 分贝的噪音，但是因为房间的独特构造，只有编号在 $[l_i,r_i]$ 床位的人会听到他的噪音。每个人的睡眠深度不尽相同，第 $i$ 个人正处于第 $k_i$ 层梦境之中，他的噪音忍耐力一开始为 $g_i$，假设在第 $x$ 秒听到了合计 $y$ 分贝的噪音（如果同一时刻他收到了多份噪音，则合计值 $y$ 等于收到的所有噪音分贝值的异或和）：

• 如果 $y$ 不超过他的噪音忍耐力，则无事发生。
• 否则，他的梦境将会减少一层，并且噪音忍耐力将提升至 $y$。如果梦境层数减至 0，他将提前在第 $\min(t_i,x+1)$ 秒醒来。当然，醒来后他会发出噪音。 给定所有人的信息，请写一个程序预测每个人将在什么时候醒来。

Input

第一行包含一个正整数 $T$（$1\leq T\leq 500$），表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$（$2\leq n\leq 200\,000$, $1\leq m\leq 200\,000$），分别表示人数以及时间上限。 接下来 $n-1$ 行，每行六个正整数 $g_i,k_i,t_i,l_i,r_i,d_i$（$1\leq g_i\leq 10^9$, $1\leq k_i\leq n$, $1\leq t_i\leq m$, $i < l_i\leq r_i\leq n$, $1\leq d_i\leq 10^9$），分别表示每个人的初始噪音忍耐力、所处梦境层数、原定梦醒时刻、噪音作用范围以及噪音分贝值。 最后一行包含三个正整数 $g_n,k_n,t_n$（$1\leq g_n\leq 10^9$, $1\leq k_n\leq n$, $1\leq t_n\leq m$），表示最后一个人的初始噪音忍耐力、所处梦境层数以及原定梦醒时刻。 输入数据保证 $\sum n\leq 1\,500\,000$ 且 $\sum m\leq 1\,500\,000$。

Output

对于每组数据输出一行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个人的实际梦醒时刻。

Sample Input

2
3 10
1 1 5 2 3 9
2 3 1 3 3 7
4 2 10
3 10
1 1 5 2 3 9
8 1 10 3 3 7
4 2 10

Sample Output

5 1 6
5 6 10

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（7）