Byteland 的第一位国王在一千年前与他的 $n$ 位骑士一同下葬。在遗迹中，考古学家发现了 $n$ 块排成一行的石碑，从左到右依次编号为 $1, 2, \dots, n$。每块石碑都属于一位骑士。在第 $k$ 块石碑的表面，有五个数字描述了第 $k$ 位骑士在五个方面的能力：

• 风能力 $w$，表示骑士的速度。
• 守卫能力 $g$，表示骑士能防御的攻击次数。
• 冰能力 $i$，表示骑士施展的冰晶威力。
• 火能力 $f$，表示骑士施展的火焰威力。
• 光能力 $l$，表示骑士施展的雷电威力。

Little Q 正按照从 $1$ 到 $n$ 的编号顺序从左到右参观这些石碑。在参观完一块石碑后，在移动到下一块石碑之前，他可以选择为该石碑拍照或什么都不做。Little Q 对每块石碑的价值进行了评估，他希望最大化他所拍摄照片的总价值，并且要求下一张照片对应的骑士总是“不弱于”当前照片对应的骑士。

在此处，若且唯若 $w_x \ge w_y$，$g_x \ge g_y$，$i_x \ge i_y$，$f_x \ge f_y$ 且 $l_x \ge l_y$，则称第 $x$ 位骑士不弱于第 $y$ 位骑士。

由于石碑数量众多，Little Q 无法确定该拍摄哪些石碑。请编写一个程序来帮助他。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。对于每个测试用例： 第一行包含一个整数 $n$ ($1 \le n \le 50\,000$)，表示石碑的数量。 接下来的 $n$ 行中，第 $k$ 行包含六个整数 $w_k, g_k, i_k, f_k, l_k$ 和 $v_k$ ($1 \le w_k, g_k, i_k, f_k, l_k \le n, 1 \le v_k \le 10\,000$)，描述第 $k$ 块石碑，其中 $v_k$ 表示拍摄该石碑照片的价值。

输出格式

对于每个测试用例，输出 $n$ 行，第 $k$ 行 ($1 \le k \le n$) 包含一个整数，表示以第 $k$ 块石碑作为最后一张照片时所能获得的最大总价值。

样例

输入 1

1
4
1 2 1 2 1 30
2 1 2 1 2 40
3 3 3 3 3 50
2 3 3 2 4 100

输出 1

30
40
90
140