F. Best Player
time limit per test
3 с
memory limit per test
512 megabytes
input
standard input
output
standard output

The 17th Culinary Combat Professional Contest (CCPC) has ended, and the event organizers will select the best player of this competition.

There are $$$n$$$ players numbered from $$$1$$$ to $$$n$$$ who participated in this competition and played a total of $$$m$$$ 1 vs 1 duels:

  • The opponents in the $$$i$$$-th duel are players $$$a_i$$$ and $$$b_i$$$;
  • Each duel consists of a first half and a second half:
    • In the first half of the duel, the score of player $$$a_i$$$ is $$$x_i$$$, and the score of player $$$b_i$$$ is $$$y_i$$$;
    • In the second half of the duel, the exact scores of the two players $$$a_i$$$ and $$$b_i$$$ are uncertain now, but the sum of the scores is $$$z_i$$$;
    • A player's score in a duel equals to the sum of the first half score and the second half score. In other words, in the $$$i$$$-th duel, the possible scores for $$$a_i$$$ and $$$b_i$$$ are $$$x_i + p_i$$$ and $$$y_i + q_i$$$ respectively, where $$$0 \leq p_i,q_i \leq z_i, p_i + q_i = z_i$$$.

Note that all scores are non-negative integers, and each player has participated in at least one duel.

A player's final score is: the maximum score achieved in duels he participated. A player will win the best player award if and only if his final score is strictly larger than any other player's final score.

Due to the uncertainty of the scores in the second half of the $$$m$$$ duels, the best player may also be different. Please find all the players who could possibly be the best player.

Input

The input contains multiple testcases.

The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^5$$$), denoting the number of testcases.

For each testcase:

The first line contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 2 \times 10^5$$$, $$$1 \leq m \leq 2 \times 10^5$$$), denoting the number of players and duels.

The $$$i$$$-th of the next $$$m$$$ lines contains $$$5$$$ integers $$$a_i$$$, $$$b_i$$$, $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$, $$$0 \leq x_i, y_i, z_i \leq 10^5$$$), of which meanings are described above. It is guaranteed that each player participates in at least one duel.

It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ over all test cases exceeds $$$2\times 10^5$$$.

Output

For each testcase:

The first line output a single integer $$$k$$$, denoting the number of players who could possibly be the best player.

The second line output $$$k$$$ integers listed in ascending order, denoting the player numbers who could possibly be the best player. Specially, when $$$k=0$$$ either output an empty line or not will be considered correct.

Example
Input
2
3 2
1 2 2 3 6
2 3 6 6 2
4 4
1 2 2 4 1
2 3 2 3 0
3 4 4 1 2
1 4 1 1 1
Output
3
1 2 3
2
2 3
Note

In the first testcase of the example, all three players could possibly be the best player. Player $$$1$$$ can be the best player only in the following case:

  • In the first duel, player $$$1$$$ scores $$$2 + 6 = 8$$$, player 2 scores $$$3 + 0 = 3$$$;
  • In the second duel, player $$$2$$$ scores $$$6 + 1 = 7$$$, player $$$3$$$ scores $$$6 + 1 = 7$$$.

In this case, player $$$1$$$'s final score is $$$8$$$, player $$$2$$$'s final score is $$$\max(3, 7) = 7$$$, and player $$$3$$$'s final score is $$$7$$$, so player $$$1$$$ is the best player.