410582: GYM104059 C Chaotic Construction

The city Gircle has only one street, and that street is cyclic. This was very convenient in times when people didn't carry a device with compass, GPS and detailed maps around in their pockets, because you only have to walk in one direction and will certainly arrive at your destination. Since Gircle's founding a lot of time has passed. Civil engineers now know a lot more about road network design and most people have immediate access to reliable and accurate navigation systems. However, the passage of time also affected the old street surface and more and more cracks and potholes appeared.

The local government has finally decided to improve the situation, but preserving the city's historic appeal and building new streets are unfortunately mutually exclusive. Because tourism is vital for Gircle's economy, the government's only viable option for improving the situation is to renovate segments of the street when necessary. Gircle's street is very narrow, so a construction site at a street segment makes it impossible for citizens to pass that segment or even leave or enter it.

As a member of the Gircle Construction and Planning Commission (GCPC), you always know when one of the $$$n$$$ street segments is closed or reopened. Naturally, the citizens expect you to tell them whether the trips they want to do are currently possible.

Figure 1. Depiction of the query "? 9 7" in the sample input.

The input consists of:

• One line with two integers $$$n$$$ ($$$2 \leq n \leq 10^5$$$) and $$$q$$$ ($$$1 \leq q \leq 10^5$$$), the number of street segments and the number of events. No street segment is initially closed.
• $$$q$$$ lines, each describing an event. Each event is described in one of the following ways:
  • "- a": Segment $$$a$$$ ($$$1 \leq a \leq n$$$) is closed. It is guaranteed that segment $$$a$$$ was open before.
  • "+ a": Segment $$$a$$$ ($$$1 \leq a \leq n$$$) is reopened. It is guaranteed that segment $$$a$$$ was closed before.
  • "? a b": A person asks you if it is possible to go from segment $$$a$$$ to segment $$$b$$$ ($$$1 \leq a, b \leq n \text{ and } a\neq b$$$).

For each event of the form "? a b", print one line containing the word "possible", if it is possible to move from segment $$$a$$$ to segment $$$b$$$, or "impossible" otherwise. If $$$a$$$ or $$$b$$$ are currently closed, the answer is "impossible".

10 12
? 1 5
- 2
- 8
? 9 2
? 9 8
? 9 7
? 6 7
? 3 7
? 1 9
? 9 1
+ 8
? 10 3

possible
impossible
impossible
impossible
possible
possible
possible
possible
possible