{"raw_statement":[{"iden":"statement","content":"There is a sequence of length $n$. At the beginning, all elements in the sequence equal to $0$. There are also $m$ operations, where the $i$-th operation will change the value of the $l_i$-th element in the sequence to $x_i$, and also change the value of the $r_i$-th element in the sequence to $y_i$. Each operation must be performed exactly once.\n\nFind the optimal order to perform the operations, so that after all operations, the sum of all elements in the sequence is maximized."},{"iden":"input","content":"There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $m$ ($2 \\leq n, m \\leq 5 \\times 10^5$) indicating the length of the sequence and the number of operations.\n\nFor the following $m$ lines, the $i$-th line contains four integers $l_i$, $x_i$, $r_i$ and $y_i$ ($1 \\leq l_i<r_i \\leq n$, $1 \\leq x_i,y_i \\leq 2$) indicating the $i$-th operation.\n\nIt's guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \\times 10^5$."},{"iden":"output","content":"For each test case, first output one line containing one integer, indicating the maximum sum of all elements in the sequence after all operations. Then output another line containing $m$ integers $a_1, a_2, \\cdots, a_m$ separated by a space, indicating the optimal order to perform the operations, where $a_i$ is the index of the $i$-th operation to be performed. Each integer from $1$ to $m$ (both inclusive) must appear exactly once. If there are multiple valid answers, you can output any of them."},{"iden":"note","content":"For the first sample test case, after performing operations $4, 1, 3, 2$ in order, the sequence becomes $\\{2, 2, 2, 1\\}$. The sum of all elements is $7$.\n\nFor the second sample test case, after performing operations $2, 1$ in order, the sequence becomes $\\{2, 0, 2, 1\\}$. The sum of all elements is $5$."}],"translated_statement":null,"sample_group":[["2\n4 4\n1 1 2 2\n3 2 4 1\n1 2 3 2\n2 1 4 1\n4 2\n3 2 4 1\n1 2 3 1","7\n4 1 3 2\n5\n2 1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}