1207 : 流画溢彩

Description

有一个长度为 \(n\) 的序列，一开始序列中的所有元素均为 \(0\)。另外还有 \(m\) 个操作，其中第 \(i\) 个操作会将序列中第 \(l_i\) 个元素的值改为 \(x_i\)，以及将序列中第 \(r_i\) 个元素的值改为 \(y_i\)。每个操作必须恰好执行一次。

求执行操作的最优顺序，使得所有操作执行完成后，序列中所有元素之和最大。

Input

有多组测试数据。第一行输入一个整数 \(T\) 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 \(n\) 和 \(m\)（\(2 \leq n, m \leq 5 \times 10^5\)）表示序列的长度和操作的个数。

对于接下来 \(m\) 行，第 \(i\) 行输入四个整数 \(l_i\)，\(x_i\)，\(r_i\) 和 \(y_i\)（\(1 \leq l_i<r_i \leq n\)，\(1 \leq x_i,y_i \leq 2\)）表示第 \(i\) 个操作。

保证所有数据 \(n\) 之和与 \(m\) 之和均不超过 \(5 \times 10^5\)。

Output

每组数据首先输出一行一个整数，表示执行操作后，所有元素的最大和。接下来输出一行 \(m\) 个由单个空格分隔的整数 \(a_1, a_2, \cdots, a_m\) 表示执行操作的最优顺序，其中 \(a_i\) 表示第 \(i\) 次执行的操作的编号。从 \(1\) 到 \(m\) 的每个整数（含两端）必须恰好出现一次。若有多种合法答案，您可以输出任意一种。

Sample

2
4 4
1 1 2 2
3 2 4 1
1 2 3 2
2 1 4 1
4 2
3 2 4 1
1 2 3 1

7
4 1 3 2
5
2 1

Hint

对于第一组样例数据，按 \(4, 1, 3, 2\) 的顺序执行操作后，序列变为 \(\{2, 2, 2, 1\}\)，元素之和为 \(7\)。

对于第二组样例数据，按 \(2, 1\) 的顺序执行操作后，序列变为 \(\{2, 0, 2, 1\}\)，元素之和为 \(5\)。

Source

Author

SUA