题目描述

那条街有“鬼街”之称,十年前是 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$ 个从小到大排列的整数，表示触发的监控器的编号。

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

提示

【样例解释】

在本样例中，依次发生了以下事件：

• 安装了 $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$ 号监控器的报警也被触发。

【题目来源】

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 https://github.com/yylidiw/thupc_0/tree/master 查看。