P16678 [CSPro 27] 防疫大数据

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。 近期，国内 COVID-19 疫情多点散发，西西艾弗岛的防疫形势也异常严峻。西西艾弗岛疫情防控指挥部决定在岛上建立一套疫情风险监测系统。 这套风险监测系统的主要功能是，收集手机用户到访地区的信息，根据用户的到访地区，判断用户的疫情风险。具体而言，在每天夜里， 西西艾弗岛大数据运行管理中心都会收到一批手机用户到访地区的信息，以及当天疫情风险地区的信息。数据中心需要根据这些信息， 生成一份存在风险的手机用户的名单，提供给疫情防控指挥部，以便进行后续的疫情防控工作。

为了简化和便于处理问题，我们用连续的整数来表示日期，例如 -1、0、1、2 就是连续的 4 个日期。每日收到的漫游数据分为若干条，每条表示某一个用户在某日到访过某地区，记为：$\langle d, u, r \rangle$，其中，$u$ 表示用户，$r$ 表示地区，它们都是一个正整数；$d$ 表示日期，是一个整数。每日收到的漫游数据中，可能会有这样的数据，需要在处理的过程中考虑： - 延迟数据：即在某日收到的漫游数据中，日期小于当日的日期。例如，在 2 日收到的某条漫游数据，内容是某用户在 1 日到访过某地区； - 重复数据：即在某日收到的漫游数据中，可能存在两条完全相同的数据； - 多地访问数据：即在某日收到的漫游数据中，存在两条数据，其日期和用户相同，但地区不同。 每日收到的疫情风险地区的信息，是一个列表，列表中的每个元素表示某个地区在某日被列为疫情风险地区。收到该消息的当日起 7 日内，该地区处于风险状态。即对于地区 $r$，我们称 $r$ 在 $d$ 日处于风险状态，当且仅当存在一个日期 $d_0 \in (d - 7, d]$，在 $d_0$ 日收到地区 $r$ 的风险信息。例如，在 1 日收到地区 1 的风险信息，表示自 1 日（包含）至 8 日（不包含）地区 1 处于风险状态。如果分别在 1 日和 6 日收到地区 1 的风险信息，那么意味着地区 1 自 1 日（包含）至 13 日（不包含）持续处于风险状态。 每日生成的存在风险的手机用户的名单，是一个列表，列表中的每个元素表示某个用户被认为存在疫情风险。我们认为，同时满足下列条件的用户，会被列入当日生成的风险名单： - 该用户在近 7 日内曾经出现在接收到的漫游数据中，并且近 7 日内有到访某个地区的记录； - 该用户在近 7 日内到访的地区在到访的那一日处于风险状态； - 上述存在风险的地区自到访日至生成名单当日持续处于风险状态。 形式化地，在 $d$ 日生成的风险名单中，用户 $u$ 被列入风险名单，当且仅当： 存在一个日期 $d_0 \in (d - 7, d]$，存在一条 $d_0$ 日收到的漫游数据 $\langle d_1, u, r \rangle$，使得 - $d_1 \in (d - 7, d]$，并且 - 对于任意的 $D \in [d_1, d]$，地区 $r$ 在 $D$ 日处于风险状态。 例如，在第 0 日收到下列漫游数据： $\langle 0, 1, 1 \rangle$；$\langle -1, 1, 1 \rangle$；$\langle -1, 2, 1 \rangle$；$\langle 0, 2, 2 \rangle$ 又在第 0 日收到了 1 号地区为风险地区的消息，那么此后第 0 日（包含）至第 7 日（不包含），1 号地区都处于风险状态。 在第 0 日生成的风险名单中，用户 1 被列入风险名单，因为用户 1 在第 0 日到访了 1 号地区。用户 2 不被列入风险名单，因为用户 2 在第 0 日到访了 2 号地区，但是在第 0 日 2 号地区不是风险地区；虽然用户 2 在第 -1 日到访了 1 号地区，但是在第 -1 日 1 号地区不是风险地区。 假设在第 1 日，又收到下列漫游数据： $\langle 0, 3, 1 \rangle$；$\langle 1, 2, 2 \rangle$；$\langle 1, 3, 2 \rangle$ 同时没有收到新的风险地区的消息，那么在第 1 日生成的风险名单中，用户 1 和 3 被列入风险名单，因为刚收到的信息显示用户 3 在第 0 日到访了 1 号地区，而用户 1 在第 0 日到访了 1 号地区，且在第 1 日 1 号地区仍处于风险状态，虽然第 1 日没有收到用户 1 的漫游数据，但是仍然将用户 1 列入风险名单。 假设后续没有收到更多漫游数据和风险地区信息，直到第七日，收到下列漫游数据： $\langle 5, 4, 1 \rangle$ 同时没有收到新的风险地区的消息，此时，没有用户被列入风险名单。例如对于用户 4，虽然在第 5 日到访了 1 号地区，但是生成风险名单的当日，1 号地区已经不是风险地区。 假设在第 8 日，没有收到更多的漫游数据，但是收到了 1 号地区为风险地区的消息，那么在第 8 日生成的风险名单中，也没有用户被列入风险名单。因为在第 7 日，地区 1 不处于风险状态，用户 4 在第 5 日到访了 1 号地区，虽然第 5 日和本日（第 8 日）地区 1 处于风险状态，但是，由于不满足持续处于风险状态的条件，用户 4 不被列入风险名单。

从标准输入读入数据。 输入的第一行包含一个正整数 $n$，表示总共输入数据的天数。 接下来是 $n$ 组数据，依次表示自第 0 日开始每一天的输入数据。 对于第 $i$ 日的一组数据，其第一行内，包含空格分隔的两个非负整数 $r_i$、$m_i$，以及 $r_i$ 个正整数 $p_{i,j}$（$i = 0, 1, \ldots, (n-1)$，$j = 1, 2, \ldots, r_i$），分别表示当日收到的风险地区信息的数量、当日收到的漫游数据的条目数量，以及当日收到的风险地区的列表。 每组数据接下来有 $m_i$ 行，每行包含空格分隔的一个整数和两个正整数 $d_{i,j}$、$u_{i,j}$、$r_{i,j}$（$j = 1, 2, \ldots, m_i$），分别表示一条漫游数据中的日期、用户和地区。

输出到标准输出。 输出 $n$ 行，自第 0 天起，按顺序输出各日运算产生的疫情风险名单。每行包含空格分隔的若干整数。其中第一个整数表示当天的日期，接下来的各个整数为按从小到大排序的存在风险的用户列表。

### 样例 1 解释 本样例数据即为题目描述中所叙述的情况。 ### 子任务 对于前 20% 的数据，有 $r_i = m_i = 0, (i = 1, 2, \ldots (n-1))$； 对于前 40% 的数据，有 $r_i = 0, (i = 1, 2, \ldots (n-1))$； 对于前 70% 的数据，对所有的 $i$ 与 $j$，都有 $p_{i,j} \leq 400$，$u_{i,j} \leq 400$，且 $r_{i,j} \leq 400$；并且对所有的 $i$，都有 $r_i \leq 300$，且 $m_i \leq 300$； 对于 100% 的数据，对所有的 $i$ 与 $j$，都有 $1 \leq p_{i,j} \leq 10^9$，$1 \leq u_{i,j} \leq 10^9$，$1 \leq r_{i,j} \leq 10^9$，且 $-10^5 \leq d_{i,j} \leq i$；对所有的 $i \in [0, n)$，都有 $0 \leq r_i \leq 1000$，且 $0 \leq m_i \leq 1000$；对所有的 $i \in [0, n)$，和任意的 $j_1, j_2 \in [1, r_i]$，$j_1 \neq j_2$，都有 $p_{i,j_1} \neq p_{i,j_2}$。