Description

You are given $3 \times N$ positive integers:

$A_1, A_2...A_n$

$B_1, B_2...B_n$

$C_1, C_2...C_n$

You are also given $M$ pairs of positive integers $S_i, T_i$. For each pair $S_i, T_i$, find a set of non-negative real solutions to the following system of equations:

$A_1X_1 + A_2X_2 + ... + A_nX_n = S_i$

$B_1X_1 + B_2X_2 + ... + B_nX_n = T_i$

such that $C_1X_1 + C_2X_2 + ... + C_nX_n$ is maximized.

Input Format

The first line contains two integers $N, M$.

The next $N$ lines each contain three positive integers $A_i, B_i, C_i$.

Constraints: $N \leq 10^5$, $M \leq 10^4$.

$1 \le A_i, B_i, C_i, S_i, T_i \le 1000000$.

Output Format

Output $M$ lines. The $i$-th line corresponds to $S_i, T_i$.

If the system has no solution, output IMPOSSIBLE.

Otherwise, output a real number rounded to five decimal places, representing the corresponding maximum value.

1 2
100 100 10
3 3
99 100

0.30000
IMPOSSIBLE

Hint

Translated by ChatGPT 5