E2. 切奥普斯与一场比赛（困难版本）
每个测试点时间限制：$4$ 秒
每个测试点内存限制：$512$ 兆字节

这是该问题的困难版本。两个版本的区别在于，在此版本中 $m$ 是任意的。只有解决了该问题的所有版本，你才能进行 hack。

在古埃及有一场解题竞赛，有 $n$ 名参赛者，编号从 $1$ 到 $n$。每名参赛者来自某个城市；城市的编号从 $1$ 到 $m$。每个城市至少有一名参赛者。

第 $i$ 名参赛者具有力量 $a_i$、专长 $s_i$ 和智慧 $b_i$，满足 $b_i \ge a_i$。竞赛中的每道题都有一个难度 $d$ 和一个唯一的主题 $t$。第 $i$ 名参赛者会解出一道题，当且仅当满足以下条件之一：

• $a_i \ge d$，即他们的力量不小于题目的难度；或者
• $s_i = t$ 且 $b_i \ge d$，即他们的专长与题目的主题匹配，且他们的智慧不小于题目的难度。

切奥普斯希望选择题目，使得对于所有 $i < j$，来自城市 $i$ 的每名参赛者解出的题目数量严格大于来自城市 $j$ 的每名参赛者解出的题目数量。

请找出一组至多 $5n$ 道题目，其中所有题目的主题互不相同，使得切奥普斯的愿望得以满足；或者说明这是不可能的。

输入
每个测试包含多个测试用例。第一行包含整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。
每个测试用例的描述如下：

第一行包含两个整数 $n, m$（$2 \le m \le n \le 3 \cdot 10^5$）——参赛者人数和城市数量。

接下来的 $n$ 行描述参赛者。第 $i$ 行包含三个整数 $a_i, b_i, s_i$（$0 \le a_i, b_i, s_i \le 10^9$，$a_i \le b_i$）——第 $i$ 名参赛者的力量、智慧和专长。

接下来的 $m$ 行描述城市。在第 $i$ 行中，第一个整数为 $k_i$（$1 \le k_i \le n$）——来自城市 $i$ 的参赛者数量。随后跟着 $k_i$ 个整数 $q_{i,1}, q_{i,2}, \dots, q_{i,k_i}$（$1 \le q_{i,j} \le n$，$1 \le j \le k_i$）——这些参赛者的编号。保证每名参赛者恰好被提到一次。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

输出
对于每个测试用例，如果存在一组满足切奥普斯条件的题目，则第一行输出一个整数 $p$（$1 \le p \le 5n$）——你解中题目的数量。
接下来输出 $p$ 行，每行包含两个整数 $d$ 和 $t$（$0 \le d, t \le 10^9$）——对应题目的难度和主题。这些主题必须互不相同。
如果不存在满足切奥普斯愿望的题目集合，则输出 $-1$。

样例

输入

2
5 2
5 7 1
6 7 2
3 9 2
5 10 3
4 4 1
2 1 2
3 3 4 5
2 2
1 2 1
1 2 1
1 2
1 1

输出

7
6 4
6 5
5 6
5 7
4 8
4 9
7 1
-1