The street is known as "Ghost Street." Ten years ago, it was one of the most prosperous areas in City A, but today, no living person resides there.

There are $n$ houses lined up along the street, each with a unique number between $1$ and $n$ painted in black, as if from hell, on the dilapidated bricks and tiles, faintly visible through the yellow dust.

Legend has it that the ghosts on this street are different from those elsewhere; they enjoy studying number theory and choose their dwellings based on the properties of the numbers, which is why they painted numbers on every house.

The newly appointed mayor of City A does not believe in these rumors of ghosts and monsters. To uncover the truth, he decided to install paranormal activity monitors on this street.

There are $m$ events that occur sequentially:

• Paranormal event: In every house whose number is a prime factor of $x$, $y$ hauntings occur. For mysterious reasons, the number of hauntings $y$ may be $0$.
• Monitoring event: A monitor is installed to track houses whose numbers are factors of $x$. When the total accumulated number of hauntings reaches the threshold $y$, the monitor triggers an alarm (if $y = 0$, the monitor will trigger an alarm immediately upon the next paranormal event, regardless of which houses are being monitored). The number of hauntings in different houses is tracked separately, and different monitors do not affect each other. All monitors are numbered sequentially starting from $1$.

Please report all alarms to the mayor; that is, after each paranormal event, list which monitors have been triggered.

Input

The first line of the input contains two positive integers $n$ and $m$, where $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 represents a paranormal event; if $op$ is $1$, it represents 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 true $y$. Let $k'$ be the number of monitors triggered by the previous paranormal event (if no paranormal event has occurred yet, $k'$ is $0$). The true $y$ is $y' \oplus k'$. The meanings of $x$ and $y$ in each event are as described above.

Output

For each paranormal event, output one line. The first number in the line is a non-negative integer $k$, representing the number of alarms triggered by this event, followed by $k$ integers in ascending order, representing the IDs of the triggered monitors.

Examples

Input 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

Output 1

0
0
0
1 1
0
2 2 3

Note 1

In this example, the following events occur sequentially:

• Monitor $1$ is installed, tracking houses with numbers $2$ and $5$, with an alarm threshold of $2$.
• A paranormal event occurs; house $5$ seems to have a haunting, but the count is $0$, so no alarm is triggered.
• A paranormal event occurs; houses $2$ and $3$ have $1$ haunting each. The accumulated count on monitor $1$ reaches $1$, but the alarm is not yet triggered.
• A paranormal event occurs; house $7$ has $1$ haunting; no alarm is triggered.
• A paranormal event occurs; houses $3$ and $5$ have $1$ haunting each. The accumulated count on monitor $1$ reaches the threshold $2$, triggering the alarm.
• Monitor $2$ is installed, tracking houses with numbers $2$ and $3$, with an alarm threshold of $2$.
• A paranormal event occurs; house $2$ has $1$ haunting. The accumulated count on monitor $2$ reaches $1$, but the alarm is not yet triggered.
• Monitor $3$ is installed, but its threshold is $0$, so the next paranormal event will definitely trigger its alarm.
• A paranormal event occurs; house $2$ has $2$ hauntings. The accumulated count on monitor $2$ reaches $3$, exceeding its alarm threshold of $2$, so the alarm is triggered. At the same time, the alarm for monitor $3$ is also triggered.