题目描述

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

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

输入格式

有多组测试数据。第一行输入一个整数 $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 \textbf{2}$）表示第 $i$ 个操作。

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

输出格式

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

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

样例解释

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

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