题目描述

2026 丙午马年，某马术俱乐部管理着一片广袤的牧场。牧场被划分为 \(1000 \times 1000\) 的网格草地。

俱乐部共有 \(n\) 匹骏马在牧场上巡游，每匹马都有自己固定的活动区域——一个边平行于坐标轴的矩形。第 \(i\) 匹马的活动区域覆盖所有满足 \(x_{i, 1} \le x \le x_{i, 2}\) 且 \(y_{i, 1} \le y \le y_{i, 2}\) 的草地 \(\left(x, y\right)\)。

近日马匹偶有疲乏，需要轮换休息。现有 \(q\) 次查询，每次查询中有若干匹马暂时歇息，你需要计算至少被一匹仍在巡游的马覆盖的草地数量。询问之间独立。

输入格式

第一行输入一个整数 \(T\ (1 \le T \le 5)\)，表示数据组数。

对于每组数据：

第一行输入两个整数 \(n, q\ (1 \le n, q \le 10^5)\)，分别表示骏马的数量和查询次数。

接下来 \(n\) 行，每行四个整数 \(x_{i, 1}, x_{i, 2}, y_{i, 1}, y_{i, 2}\ (1 \le x_{i, 1} \le x_{i, 2} \le 1000, \ 1 \le y_{i, 1} \le y_{i, 2} \le 1000)\)，描述第 \(i\) 匹马的活动区域。

接下来 \(q\) 行，每行先输入一个整数 \(k_i\ (1 \le k_i \le 7)\)，随后 \(k_i\) 个互不相同的整数 \(p_{i, 1}, p_{i, 2}, \ldots, p_{i, k_i}\ (1 \le p_{i, j} \le n)\)，表示第 \(i\) 次查询中暂时歇息的马的编号。

输出格式

对于每组数据，输出一行 \(q\) 个整数，第 \(i\) 个整数表示第 \(i\) 个询问的答案。

样例输入

1
2 3
1 3 2 5
2 4 3 7
1 1
1 2
2 1 2

样例输出

15 12 0