Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Equations
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1076 Accepted: 103

Description

Given 3 × n positive integers:

A1,     A2,     A3,     ...     An;
B1,     B2,     B3,     ...     Bn;
C1,     C2,      C3,     ...     Cn;

and a set of m pairs of integer < Si, Ti >, your task is to find a non-negative real solution for the following equations:

A1X1 + A2X2 + A3X3 + ... + AnXn = Si
B1X1 + B2X2 + B3X3 + ... + BnXn = Ti

that maximizes C1X1 + C2X2 + C3X3 + ... + CnXn

Input

The first line contains two numbers n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 10000).
The following n lines each contain three integers Ai, Bi, Ci (1 ≤ Ai, Bi, Ci ≤ 10000). The next m lines each contain two integers Si and Ti (1 ≤ Si, Ti ≤ 10000).

Output

For each pair < Si, Ti >, output the maximum value or IMPOSSIBLE if no solution exists.

Sample Input

```2 2
2 2 2
3 1 1
4 2
4 1
```

Sample Output

```2.00000
IMPOSSIBLE
```

Source

[Submit]   [Go Back]   [Status]   [Discuss]