F. MCF
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a graph consisting of $$$n$$$ vertices and $$$m$$$ directed arcs. The $$$i$$$-th arc goes from the vertex $$$x_i$$$ to the vertex $$$y_i$$$, has capacity $$$c_i$$$ and weight $$$w_i$$$. No arc goes into the vertex $$$1$$$, and no arc goes from the vertex $$$n$$$. There are no cycles of negative weight in the graph (it is impossible to travel from any vertex to itself in such a way that the total weight of all arcs you go through is negative).

You have to assign each arc a flow (an integer between $$$0$$$ and its capacity, inclusive). For every vertex except $$$1$$$ and $$$n$$$, the total flow on the arcs going to this vertex must be equal to the total flow on the arcs going from that vertex. Let the flow on the $$$i$$$-th arc be $$$f_i$$$, then the cost of the flow is equal to $$$\sum \limits_{i = 1}^{m} f_i w_i$$$. You have to find a flow which minimizes the cost.

Sounds classical, right? Well, we have some additional constraints on the flow on every edge:

  • if $$$c_i$$$ is even, $$$f_i$$$ must be even;
  • if $$$c_i$$$ is odd, $$$f_i$$$ must be odd.

Can you solve this problem?

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 100$$$; $$$1 \le m \le 200$$$).

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains four integers $$$x_i$$$, $$$y_i$$$, $$$c_i$$$, and $$$w_i$$$ ($$$1 \le x_i \le n - 1$$$; $$$2 \le y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le c_i \le 100$$$; $$$-100 \le w_i \le 100$$$). These integers describe the $$$i$$$-th arc.

Additional constraints on the input:

  • there are no negative cycles in the graph.
Output

If a flow satisfying all of the constraints does not exist, print Impossible.

Otherwise, print two lines:

  • the first line should contain one word Possible;
  • the second line should contain $$$m$$$ integers $$$f_1, f_2, \dots, f_m$$$.

If there are multiple answers, print any of them. Note that the cost of the flow should be minimized.

Examples
Input
3 3
1 2 3 -10
1 2 3 -15
2 3 2 0
Output
Possible
1 1 2
Input
3 3
1 2 3 -10
1 2 3 -15
2 3 3 0
Output
Impossible
Input
3 3
1 2 3 -10
1 2 3 -15
2 3 4 0
Output
Possible
1 3 4
Input
6 7
5 6 9 -40
1 2 3 -10
1 4 5 20
4 5 7 30
2 5 1 -15
1 3 3 5
3 5 3 0
Output
Possible
5 1 1 1 1 3 3