Problem H
Straight Road Communications

Image by Meridy Scott (Pixabay); Used under license

Rumour has it that the roads in the Australian outback run straight for enormous distances. On one such road, we have placed $N$ pairs of twins, such that nobody is separated by more than $B$ kilometers from their twin. Each person is supplied with a radio that can be set to one of $I$ different channels, which are numbered $1, 2, \ldots , I$. Twins want to talk continuously to each other, but they never wish to talk to anybody else. If they choose to communicate on $\textrm{channel }i$, it must be the case that nobody whose distance from either twin is less than or equal to $B$ kilometers is also using that channel, or the interference will ruin both communications.

Given the location of each person (in kilometers from the start of the road), and given $I$ and $B$, is it possible for all communications to occur without interference — if each person sets their radio channel suitably?

Input

The first line of input contains three space-separated positive integers, $N$, $I$ and $B$, in that order. We guarantee $N \leq 100$, $I \leq 100$ and $B \leq 20$.

The remaining $N$ lines of input each contain two positive integers separated by a space. Each such line gives the locations of a pair of twins, where a location is the number of kilometers from the start of the road. We guarantee that the distance between a person and their twin is between $1$ and $B$, inclusive, and that no two people are the same distance from the start of the road. The road length is at most $2\, 000$ kilometers.

Output

Output a single line, containing either “possible” or “impossible”. The answer is “possible” if, and only if, there is some way for each person to set their radio channel such that their twin is using the same channel, but nobody within $B$ kilometers of either of them is using the same channel.

In the first example below, the first set of twins can use $\textrm{channel }1$, the second set can use $\textrm{channel }2$, and the third set can use $\textrm{channel }1$. In the second example, since everyone is limited to $\textrm{channel } 1$, there is no way to avoid interference between the first pair of twins and the second pair.

3 2 4
1 3
4 2
8 12

possible

3 1 4
1 3
4 2
8 12

impossible