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 \(\left\lfloor \dfrac{l_{x}}{2} \right\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 một nửa điểm sức mạnh của mình (phép chia làm tròn xuống) để 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òng đầu tiên chứa số nguyên \(t\) \((1 \leq t \leq 1000)\) thể hiện số test. Mỗi test 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 \times n, 0 \leq p, D \leq 10^{9})\).
• \(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})\).
• Tổng \(n\) trong tất cả các test không vượt quá \(10^{6}\).

Output

• Với mỗi test, 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\%\) số điểm): \(n, m \leq 10\).
• Subtask \(2\) (\(15\%\) số điểm): 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\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

14
Impossible
26