QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 2048 MB
统计

题目描述

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

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

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

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

下面有 $m$ 个事件依次发生。

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

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

输入格式

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

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

输出格式

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

样例数据

样例 1 输入

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

样例 1 输出

0
0
0
1 1
0
2 2 3

样例 1 解释

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

  • 安装了 $1$ 号监控器,监控编号为 $2$ 和 $5$ 的房子,报警阈值为 $2$。
  • 发生了一次灵异事件,$5$ 号房子似乎有闹鬼,但次数为 $0$,没有报警被触发。
  • 发生了一次灵异事件,$2$ 号和 $3$ 号房子发生了 $1$ 次闹鬼。$1$ 号监控器上的累计次数达到了 $1$,但尚未触发报警。
  • 发生了一次灵异事件,$7$ 号房子发生了 $1$ 次闹鬼,没有报警被触发。
  • 发生了一次灵异事件,$3$ 号和 $5$ 号房子发生了 $1$ 次闹鬼。$1$ 号监控器的累计次数达到阈值 $2$,触发报警。
  • 安装了 $2$ 号监控器,监控编号为 $2$ 和 $3$ 的房子,报警阈值为 $2$。
  • 发生了一次灵异事件,$2$ 号房子发生了 $1$ 次闹鬼。$2$ 号监控器的累计次数达到了 $1$,但尚未触发报警。
  • 安装了 $3$ 号监控器,不过其阈值为 $0$,所以下一次灵异事件必会触发其报警。
  • 发生了一次灵异事件,$2$ 号房子发生了 $2$ 次闹鬼。$2$ 号监控器的累计次数达到了 $3$,超过了其报警阈值 $2$,所以被触发了报警。同时 $3$ 号监控器的报警也被触发。