Bender

Time limit2sMemory limit512 MB

Summary

Choose parameters a, b, c of a linear congruential sequence so that n swaps of adjacent cups move the ball from position r to position l, or report Impossible.

Level: Hard8 of 10
Topics: Brute force, Implementation, Simulation, Math
Solved: No attempts yet

Problem

Robot Bender decided to open an attraction called <> to get rich. The attraction works as follows. Bender hides a ball under one of $k$ identical cups placed at positions 1 through $k$ , then quickly swaps some pairs of cups $n$ times, and after that asks you to guess which cup the ball is under now.

Bender is a robot, so he acts according to a fixed program. Bender builds a sequence of integers $x_i$ , where $x_1 = c$ and $x_i = a \cdot x_{i-1} + b$ for $i > 1$ .

At step $i$ , Bender swaps the cups at positions $(x_i \bmod k) + 1$ and $\left( (x_i + 1) \bmod k \right) + 1$ .

At the start, the robot hides the ball under the cup at position $r$ . Bender wants the ball to end up under the cup at position $l$ after $n$ swaps.

Find $a$ , $b$ , and $c$ such that the cup with the ball moves from position $r$ to position $l$ .

Input

The single line of the input file contains four integers $n$ , $k$ , $r$ , and $l$ ( $1 \le n \le 10^5$ ; $2 \le k \le 10$ ; $1 \le r, l \le k$ ).

Output

If no such numbers exist, print the single word <<Impossible>> to the output file. Otherwise, print three nonnegative integers $a$ , $b$ , and $c$ . The numbers must not exceed $1000$ .

Examples3

Example 1
Input
```
2 3 1 2
```
Expected output
```
0 0 1
```
Example 2
Input
```
3 4 2 4
```
Expected output
```
2 0 1
```
Example 3
Input
```
10 2 1 2
```
Expected output
```
Impossible
```