Problem Statement

There are $N$ competitive programmers. The $i$-th competitive programmer belongs to University $A_i$, is good at Subject $B_i$, and has a power of $C_i$.

Consider a team consisting of some of the $N$ people. Let us call such a team a dream team if both of the following conditions are satisfied:

• Any two people belonging to the team belong to different universities.
• Any two people belonging to the team are good at different subjects.

Let $k$ be the maximum possible number of members of a dream team. For each $i=1,2,\ldots,k$, solve the following question.

Question: find the maximum sum of power of people belonging to a dream team consisting of $i$ people.

Constraints

• $1 \leq N \leq 3\times 10^4$
• $1 \leq A_i,B_i \leq 150$
• $1 \leq C_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N

Output

Let $k$ be the maximum possible number of members of a dream team. Print $k$ in the first line. Then, print $k$ more lines, each containing the answer to the question for $i=1,2,\ldots,k$, in this order.