Description

That street is known as the “Ghost Street”. Ten years ago, it was one of the busiest areas in City A, but now no living person lives there.

Along the street, there are $n$ houses scattered here and there. Each house has a unique number between $1$ and $n$, painted in hellish black paint on broken tiles and crumbling bricks, faintly visible in the yellow dust.

It is said that the ghosts on this street are different from ghosts elsewhere. They like studying number theory and choose where to live based on properties of numbers, which is why they assigned a number to every house.

The newly appointed mayor of City A does not believe in such supernatural rumors. To find out the truth, he decides to install paranormal event monitors on this street.

There are $m$ events happening in order, as follows.

• Paranormal event: In the houses whose numbers are all prime factors of $x$, each such house experiences $y$ haunting occurrences. For mysterious reasons, $y$ may be $0$.
• Monitoring event: A monitor is installed. It monitors the houses whose numbers are all prime factors of $x$. When the accumulated total number of haunting occurrences reaches the threshold $y$, this monitor will trigger an alarm (if $y = 0$, then no matter which houses are being monitored, the next paranormal event will immediately trigger this monitor’s alarm). Haunting counts from different houses are tracked separately, and different monitors do not affect each other. All monitors are numbered consecutively starting from $1$.

Please report all alarms to the mayor, that is, after each paranormal event, output which monitors are triggered.

Input Format

The first line contains two positive integers $n$ and $m$, with $1 < n, m \le {10}^5$.

The next $m$ lines each contain three non-negative integers $op$, $x$, and $y'$. Here $op \in \{ 0, 1 \}$. If $op$ is $0$, it is a paranormal event; if $op$ is $1$, it is a monitoring event. It is guaranteed that $1 < x \le n$ and $0 \le y' < 2^{32}$. For mysterious reasons, you cannot directly obtain the real $y$. Let $k'$ be the number of monitors triggered by the previous paranormal event (if no paranormal event has happened yet, then $k' = 0$). The real $y$ is $y' \oplus k'$. The meanings of $x$ and $y$ in each event are as described above.

Output Format

For each paranormal event, output one line in order. The line starts with a non-negative integer $k$, representing the number of alarms triggered by this paranormal event, followed by $k$ integers in increasing order, representing the indices of the monitors that are triggered.

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

Hint

【Sample Explanation】

In this sample, the following events happen in order:

• Monitor $1$ is installed. It monitors houses numbered $2$ and $5$, with an alarm threshold of $2$.
• A paranormal event happens. House $5$ seems to be haunted, but the number of occurrences is $0$, so no alarms are triggered.
• A paranormal event happens. Houses $2$ and $3$ each have $1$ haunting occurrence. The accumulated count on monitor $1$ reaches $1$, but it has not triggered an alarm yet.
• A paranormal event happens. House $7$ has $1$ haunting occurrence, and no alarms are triggered.
• A paranormal event happens. Houses $3$ and $5$ each have $1$ haunting occurrence. The accumulated count on monitor $1$ reaches the threshold $2$, so it triggers an alarm.
• Monitor $2$ is installed. It monitors houses numbered $2$ and $3$, with an alarm threshold of $2$.
• A paranormal event happens. House $2$ has $1$ haunting occurrence. The accumulated count on monitor $2$ reaches $1$, but it has not triggered an alarm yet.
• Monitor $3$ is installed, but its threshold is $0$, so the next paranormal event will definitely trigger its alarm.
• A paranormal event happens. House $2$ has $2$ haunting occurrences. The accumulated count on monitor $2$ reaches $3$, exceeding its alarm threshold $2$, so it triggers an alarm. At the same time, monitor $3$ is also triggered.

【Source】

From the 2021 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2021).

Resources such as editorials can be found at https://github.com/yylidiw/thupc_0/tree/master.

Translated by ChatGPT 5