Khu du lịch sinh thái có n điểm tham quan đánh số từ 1 đến n. Có k lối mòn nối các điểm này với nhau thành một mạng lưới du lịch, cho phép khách từ một điểm, theo các lối mòn có thể tới điểm tham quan bất kỳ khác từ nơi mình đang đứng. Đường thứ \(j\) có độ dài \(d_j\), nối 2 điểm \(u_j\) và \(v_j\).
Để nâng cấp chất lượng phục vụ người ta quyết định lát đá một số lối đi sao cho từ một điểm tham quan có thể tới được điểm khác bằng đường đã lát. Số phiến đá khai thác được là \(m\) tấm, mỗi tấm có độ dài đơn vị. Như vậy để lát đoạn đường độ dài \(x\) cần đúng \(x\) tấm. Theo các lối này du khách chỉ có thể đi bộ. Ban Quản lý khu sinh thái muốn có thêm một số đường rộng có thể chạy minibus. Mỗi đường rộng cần số đá gấp \(p\) lần so với lát cho đường bộ. Mọi người muốn có được số đường rộng càng nhiều càng tốt nhưng vẫn phải đảm bảo từ một điểm tham quan có thể tới được điểm khác bằng đường đã lát.
Hãy xác định một cách lát đường thỏa mãn các yêu cầu đã nêu. Nếu không có cách lát thì đưa ra thông báo Impossible.

Input

• Dòng đầu tiên chứa 4 số nguyên \(n, k, m và p\) (\(1 \leq n, k\leq 10^5, 1 \leq m\leq 10^9,1 \leq p\leq 10^3\)),
• Dòng thứ \(i\) trong \(k\) dòng sau chứa \(3\) số nguyên \(u_i, v_i, d_i\) (\(1 \leq u_i,v_i\leq n, 1 \leq d_i\leq 10^6\)).
• Không có đoạn đường nào có hai điểm đầu và cuối trùng nhau, giữa 2 điểm khác nhau có không quá một đoạn đường nối trực tiếp. Các đường được đánh số từ \(1\) đến \(k\) theo trình tự nhập.

Output

• Nếu không có cách lát thì đưa ra thông báo Impossible. Nếu có cách lát thì dòng đầu tiên đưa ra 2 số nguyên \(p\) và \(q\) – số đường thường và đường rộng. Dòng thứ 2 đưa ra \(p\) số nguyên – các đường lát thường, dòng thứ 3 đưa ra q số nguyên – các đường lát rộng.

Example

4 4 10 2
1 2 3
3 4 5
1 3 1
3 2 1

1 2
2
3 4