Ghost Street Event Monitoring

A mysterious street once famed as the most bustling part of City A a decade ago is now abandoned. However, the houses still bear a unique, haunting number from 1 to n drawn in eerie black paint. Local lore tells that the ghosts inhabiting these houses are not like other apparitions – they have a fascination for number theory. Their choice of a house to haunt depends on the prime factors of certain numbers!

The city mayor, skeptical of supernatural tales, has installed paranormal monitors on the street to investigate these eerie happenings. There are m events occurring sequentially. An event can be one of the following:

• Ghost Event: Given two numbers x and y, for every house whose number is equal to one of the prime factors of x, the ghost incident counter increases by y (note that y may be 0).
• Monitor Installation Event: A new monitor is installed. This monitor watches the houses whose numbers are the prime factors of a given x. It has a threshold y and will sound an alarm as soon as any one of the monitored houses accumulates ghost incident counts greater than or equal to y. Special case: if y = 0, then no matter which houses are monitored, the next ghost event will trigger the alarm immediately. Each monitor is assigned an ID sequentially starting from 1 and each monitor counts ghost incidents for its houses independently.

After each ghost event, report the IDs of the monitors that are triggered by that event. If no monitor triggers, output -1 for that ghost event.

Note: The prime factors of a number are expressed in LaTeX as, for example, the prime factors of \(x\) are given by \(P(x)\). In this problem, when a ghost event with parameter \(x\) occurs, the houses with numbers in \(P(x)\) (and \(1 \le p \le n\)) are updated.

inputFormat

The first line contains two integers n and m separated by a space, indicating the number of houses and the number of events, respectively.

Each of the following m lines represents an event in one of the following formats:

• If the event is a ghost event, the line begins with 1 followed by two integers x and y.
• If the event is a monitor installation event, the line begins with 2 followed by two integers x and y.

For each monitor installation event, the prime factors of \(x\) (denoted as \(P(x)\)) determine the house numbers being monitored. For each ghost event, the prime factors of \(x\) determine which houses to update.

outputFormat

For each ghost event (in the order they appear), output a single line containing the IDs of the monitors that triggered as a result of that ghost event. The IDs should be output in ascending order and separated by a single space. If no monitor triggers after a ghost event, output -1.

sample

6 6
2 6 0
1 8 2
2 15 5
1 10 3
1 9 2
1 10 2

1
-1
-1
2