#1457. 「THUPC 2021」鬼街

「THUPC 2021」鬼街

题目描述

那条街有“鬼街”之称,十年前是 A 市最繁华的地段之一,然而如今这里已无活人居住。

街边七零八落地排着 nn 座房子,每栋房子都有一个 11nn 之间的独一无二的编号,用仿佛来自地狱的黑漆涂在破瓦残砖上,在黄尘中隐隐若现。

传说,这条街上的鬼是与别处的鬼是不同的,它们喜欢研究数论,会根据数字的性质来选择自己的生活,所以它们才为每一栋房子都画上了编号。

新上任的 AA 市市长并不相信魑魅魍魉的传言,为了探清真相,他决定为这条街装上灵异事件监控器。

下面有 mm 个事件依次发生。

  • 灵异事件:在以 xx 的所有质因子为编号的房子里,都发生了 yy 次闹鬼。由于神秘的原因,次数 yy 可能为 00
  • 监控事件:有一个监控器被安装,其监控以 xx 的所有因子为编号的房子,当累计的闹鬼总次数达到阈值 yy 时,该监控器会触发报警(若 y=0y = 0,则不论被监控的房子是哪几栋,下一次灵异事件都会立即触发该监控器的报警)。不同房子发生的灵异事件次数会被分开统计,不同的监控器互不影响。所有的监控器被从 11 开始依次编号。

请将所有的报警反馈给市长,即每个灵异事件之后,有哪些监控器被触发。

输入格式

输入的第一行依次包含两个正整数 nnmm,保证 1<n,m1051 < n, m \le 10^5

接下来 mm 行,每行依次包含三个非负整数 opopxxyy'。其中 op{0,1}op \in \{ 0, 1 \},若 opop00,表示这是一个灵异事件;若 opop11,表示这是一个监控事件。保证 1<xn1 < x \le n0y<2320 \le y' < 2^{32}。由于神秘的原因,你无法直接得到真实的 yy,假设 kk' 为上一个灵异事件触发的监控器的数量(如果尚未有灵异事件发生,则 kk'00),真实的 yyyky' \oplus k'xxyy 在每个事件中的具体含义如上所述。

输出格式

对于每一个灵异事件,依次输出一行。行首是一个非负整数 kk,表示这个灵异事件触发的报警数量,之后是 kk 个从小到大排列的整数,表示触发的监控器的编号。

样例

20 9
1 10 2
0 5 0
0 6 1
0 7 1
0 15 1
1 12 3
0 8 0
1 5 0
0 8 2

0
0
0
1 1
0
2 2 3

在本样例中,依次发生了以下事件:

  • 安装了 11 号监控器,监控编号为 2255 的房子,报警阈值为 22
  • 发生了一次灵异事件,55 号房子似乎有闹鬼,但次数为 00,没有报警被触发。
  • 发生了一次灵异事件,22 号和 33 号房子发生了 11 次闹鬼。11 号监控器上的累计次数达到了 11,但尚未触发报警。
  • 发生了一次灵异事件,77 号房子发生了 11 次闹鬼,没有报警被触发。
  • 发生了一次灵异事件,33 号和 55 号房子发生了 11 次闹鬼。11 号监控器的累计次数达到阈值 22,触发报警。
  • 安装了 22 号监控器,监控编号为 2233 的房子,报警阈值为 22
  • 发生了一次灵异事件,22 号房子发生了 11 次闹鬼。22 号监控器的累计次数达到了 11,但尚未触发报警。
  • 安装了 33 号监控器,不过其阈值为 00,所以下一次灵异事件必会触发其报警。
  • 发生了一次灵异事件,22 号房子发生了 22 次闹鬼。22 号监控器的累计次数达到了 33,超过了其报警阈值 22,所以被触发了报警。同时 33 号监控器的报警也被触发。