Trong mùa trung thu này, có một trò chơi được rất nhiều bạn trẻ ưa chuộng, trong đó có Jessie - một cao thủ gaming. Đó là trò chơi giải cứu công chúa. Với quyết tâm trở thành vua trò chơi thứ hai (sau Mutō Yūgi), Jessie quyết định sẽ đạt thành tích tốt nhất có thể trong trò chơi này. Trò chơi gồm ~n~ màn chơi và ~m~ cánh cổng. Cánh cổng thứ ~i~ đi từ màn ~v_i~ đến màn ~t_i~ (~v_i < t_i~) và được canh giữ bởi một con boss với điểm sức mạnh là ~l_i~. Công chúa bị nhốt tại một tòa lâu đài ở màn ~n~, để phá được tòa lâu đài và cứu công chúa ra, Jessie cần có điểm sức mạnh ít nhất là ~D~.

Jessie sẽ bắt đầu chơi từ màn ~1~ với điểm sức mạnh có sẵn là ~p~. Để vượt qua một cánh cổng đi từ màn ~v_x~ đến màn ~t_x~, Jessie buộc phải đối đầu với con boss canh giữ cánh cổng đó. Nếu điểm sức mạnh hiện tại của Jessie lớn hơn điểm của boss, Jessie sẽ đánh bại con boss và được tăng thêm ~\lfloor l_x/2 \rfloor~ điểm sức mạnh (phép chia làm tròn xuống). Ngược lại, Jessie sẽ phải hiến tế và mất đi ~\lfloor W/2 \rfloor~ điểm sức mạnh (với ~W~ là điểm sức mạnh hiện tại của cô) để con boss mở cánh cổng cho cô qua.

Bạn hãy giúp Jessie xác định xem liệu cô có thể giải cứu được công chúa không. Nếu được, Jessie cần biết điểm sức mạnh tối đa mà cô có thể đạt được là bao nhiêu.

Input

Dữ liệu vào gồm nhiều test case. Dòng đầu tiên chứa số nguyên ~t~ (~1 \leq t \leq 1\,000~) thể hiện số test case. Mỗi test case có dạng:

• Dòng đầu tiên chứa bốn số nguyên ~n, m, p, D~ (~2 \leq n \leq 10^6; 1 \leq m \leq 2 \cdot n;\, 0 \leq p, D \leq 10^9~) - lần lượt là số lượng màn chơi, số lượng cánh cổng, điểm sức mạnh có sẵn và điểm sức mạnh cần để phá tòa lâu đài cứu công chúa.

• ~m~ dòng sau, dòng thứ ~i~ chứa ba số nguyên ~l_i, v_i, t_i~ (~0 \leq l_i \leq 10^9;\, 1 \leq v_i < t_i \leq 10^6~) - lần lượt là điểm sức mạnh của boss và hai đầu của cánh cổng.

Tổng ~n~ trong tất cả các test case không vượt quá ~10^6~.

Output

Với mỗi test case, in ra Impossible nếu không thể giải cứu công chúa. Ngược lại, in ra điểm sức mạnh tối đa đạt được.

Scoring

• Subtask #1 (~15\%~): ~2 \leq n \leq 10~;
• Subtask #2 (~15\%~): Có ~n-1~ cánh cổng, cánh cổng thứ ~i~ cho phép đi đến màn chơi ~i+1~ sau khi hoàn thành màn chơi ~i~;
• Subtask #3 (~70\%~): Không có ràng buộc gì thêm.

Sample Input 1

3
2 1 10 10
9 1 2
2 1 10 10
10 1 2
5 6 10 24
7 1 2
10 2 3
12 2 5
3 1 3
11 3 4
17 3 5

Sample Output 1

14
Impossible
26

Notes

Ở test case thứ 3, để giải cứu công chúa, Jessie đã hoàn thành các màn chơi theo thứ tự ~1 \to 2 \to 3 \to 5~.