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?

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.

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.