小 $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)$ 秒醒来。当然，醒来后他会发出噪音。

给定所有人的信息，请写一个程序预测每个人将在什么时候醒来。

输入格式

第一行包含一个正整数 $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$。

输出格式

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

样例

输入

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

输出

5 1 6
5 6 10