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.
Find the optimal order to perform the operations, so that after all operations, the sum of all elements in the sequence is maximized.
## Input
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:
The 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.
For 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.
It's guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \times 10^5$.
## Output
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.
[samples]
## Note
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$.
For 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$.