The airport has $a+b$ parking stands. Among them, $a$ stands are connected to the terminal by boarding bridges, allowing passengers to board directly. The other $b$ stands are not connected to the terminal, so passengers must take a shuttle bus to board the aircraft.

Undoubtedly, the experience of taking a shuttle bus is very poor, so every passenger who takes a shuttle bus generates a certain amount of unhappiness.

Given the number of passengers, boarding time, and departure time for each aircraft, each aircraft must choose an available parking stand at its boarding time. All passengers will complete boarding at this time, and the aircraft will remain at that stand until its departure time.

If an aircraft departs at time $x$, the parking stand it occupied becomes available at time $x$.

The airport management wants to minimize the total passenger unhappiness. To achieve this, an aircraft can switch its parking stand between its boarding time and departure time.

Suppose an aircraft switches from stand A to stand B starting at time $x$. Then stand A becomes available at time $x+1$. Such a switch is possible if and only if stand B is available at time $x+1$.

Input

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. For each test case:

The first line contains three non-negative integers $n, a, b$, representing the number of aircraft, the number of stands with boarding bridges, and the number of stands without boarding bridges, respectively.

The second line contains a floating-point number $p$, with at most two decimal places.

The next $n$ lines each contain three positive integers $x, s, t$, describing the number of passengers, the boarding time, and the departure time for an aircraft.

Output

For each test case, output a single integer representing the minimum total unhappiness.

If it is impossible to arrange a valid schedule for all aircraft to complete boarding, output impossible.

Examples

Input 1

2
3 1 1
0.5
1 1 5
1 1 5
1 1 5
6 2 2
0.5
4 1 4
4 2 7
8 4 8
8 4 8
10 5 9
1 7 9

Output 1

impossible
7

Note

Aircraft are numbered starting from $1$.

At time $1$, aircraft $1$ is assigned to boarding bridge A, and passengers begin boarding. Currently, aircraft $1$ is at boarding bridge A.

At time $2$, aircraft $2$ is assigned to boarding bridge B, and passengers begin boarding. Currently, aircraft $1$ is at boarding bridge A, and aircraft $2$ is at boarding bridge B.

At time $3$, aircraft $2$ switches to shuttle bus stand A; at this moment, boarding bridge B is not yet available.

At time $4$, aircraft $1$ departs, aircraft $2$ arrives at shuttle bus stand A, aircraft $3$ is assigned to boarding bridge A, and aircraft $4$ is assigned to boarding bridge B. Passengers for $3$ and $4$ begin boarding. After boarding is complete, aircraft $3$ switches to shuttle bus stand B; at this moment, neither boarding bridge A nor boarding bridge B is available.

At time $5$, aircraft $3$ arrives at shuttle bus stand B, boarding bridge A becomes available, and aircraft $5$ is assigned to boarding bridge A to begin boarding. Currently: $5$ is at boarding bridge A, $4$ is at boarding bridge B, $3$ is at shuttle bus stand B, and $2$ is at shuttle bus stand A.

At time $7$, aircraft $2$ departs, and aircraft $6$ is assigned to shuttle bus stand A.

The total unhappiness is $7 = 1$ (passengers of aircraft $6$ take a shuttle bus) $+ 4 \times 0.5$ (aircraft $2$ switches stands) $+ 8 \times 0.5$ (aircraft $3$ switches stands).