King's Ruins

Problem Description

The first king of Byteland was buried with his $n$ knights a thousand years ago. In the ruins, the archaeologists have found $n$ stone tablets in a row, labeled by $1,2,\dots,n$ from left to right. Each stone tablet belongs to a knight. On the surface of the $k$-th stone tablet, five numbers are describing the ability of the $k$-th knight in five aspects:

• The wind ability $w$, denoting how fast the knight is.
• The guard ability $g$, denoting how many attacks can be defended by the knight.
• The ice ability $i$, denoting the power of ice crystal cast by the knight.
• The flame ability $f$, denoting the power of fire cast by the knight.
• The light ability $l$, denoting the power of thunder cast by the knight. Little Q is visiting the stone tablets from left to right, according to the labels from $1$ to $n$. After visiting a stone tablet, before moving right to the next one, he can choose to take a photo with it or do nothing. Little Q estimates the value of each stone tablet, he wants to maximize the total value that he takes photos with, and the knight corresponding to the next photo is always not weaker than the current one. Here the $x$-th knight is considered not to be weaker than the $y$-th knight if and only if $w_x\geq w_y$, $g_x\geq g_y$, $i_x\geq i_y$, $f_x\geq f_y$ and $l_x\geq l_y$. There are so many stone tablets that Little Q can not determine which to take photos with. Please write a program to help him.

Input

The first line contains a single integer $T$ ($1 \leq T \leq 5$), the number of test cases. For each test case: The first line contains a single integer $n$ ($1 \leq n \leq 50\,000$), denoting the number of stone tablets. In the next $n$ lines, the $k$-th line contains six integers $w_k$, $g_k$, $i_k$, $f_k$, $l_k$ and $v_k$ ($1\leq w_k,g_k,i_k,f_k,l_k\leq n$, $1\leq v_k\leq 10\,000$), describing the $k$-th stone tablet, $v_k$ denoting the value of the photo with it.

Output

For each test case, output $n$ lines, the $k$-th ($1\leq k\leq n$) of which containing an integer, denoting the maximum total value when the last photo is taken with the $k$-th stone tablet.

Sample Input

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

Sample Output

30
40
90
140

Source

2023“钉耙编程”中国大学生算法设计超级联赛（3）