~2N~ người đang chơi bóng đá (bóng đá), chia thành hai đội. Mỗi người chơi mặc một chiếc váy có logo của đội và một số nguyên dương duy nhất (trong đội) nằm trong khoảng từ ~1~ đến ~N~. Đối với mỗi cầu thủ, chúng tôi biết độ chính xác của anh ta, nhóm đồng đội mà anh ta có thể chuyền bóng cho ~(F)~ và nhóm đối thủ có thể lấy bóng từ anh ta ~(E)~. Khi một cầu thủ có bóng, sau đúng 1 giây, một trong các hiện tượng sau sẽ xảy ra:

• người chơi chuyền bóng cho một đồng đội ngẫu nhiên trong tập F,
• một đối thủ ngẫu nhiên ở set ~E~ lấy bóng từ anh ta,
• cầu thủ cố gắng sút vào khung thành.

Nếu người chơi thực hiện cú sút, xác suất ghi bàn sẽ bằng độ chính xác của anh ta. Sau khi thực hiện cú sút, dù thành công hay không, bóng sẽ được trao cho cầu thủ số 1 của đội đối phương.

Xác suất của các sự kiện khác nhau tỉ lệ với |F| : |E| : 1, theo thứ tự và chỉ phụ thuộc vào người chơi hiện đang sở hữu bóng (|S| xác định kích thước của bộ S tương ứng với người chơi hiện tại), không phụ thuộc vào bất kỳ sự kiện nào trước đó trong trò chơi. Từ “ngẫu nhiên” có nghĩa là tất cả các cầu thủ trong tập ~F~ (hoặc ~E~) đều có cùng xác suất được chuyền (hoặc lấy) bóng bởi (từ) cầu thủ hiện đang sở hữu bóng. Thời gian bóng nằm ngoài tầm kiểm soát của một cầu thủ là không đáng kể.

Trận đấu bắt đầu với cầu thủ ~1~ của đội đầu tiên sở hữu bóng và kết thúc khi một đội ghi được ~R~ bàn thắng hoặc khi trôi qua ~T~ giây, tùy điều kiện nào xảy ra trước. Đối với mỗi tỷ số cuối cùng có thể xảy ra, hãy xác định xác suất trận đấu sẽ kết thúc với tỷ số đó. Hình ảnh sau đây minh họa cách sắp xếp trình phát cho ví dụ thử nghiệm thứ hai:

Input

• Dòng đầu tiên chứa 3 số nguyên dương: ~N~ ~(1 ≤ N ≤ 100)~, số cầu thủ của mỗi đội, ~R~ ~(1 \le R \le 10)~, số bàn thắng cần thiết để giành chiến thắng và ~T~ ~(1 \le T ≤ 500)~, thời lượng tối đa của trận đấu.
• ~N~ dòng tiếp theo chứa mô tả về các cầu thủ của đội thứ nhất, mỗi dòng một dòng, trong khi ~N~ dòng tiếp theo sau đó chứa mô tả về các cầu thủ của đội thứ hai. Mô tả về một người chơi bao gồm một số thực ~p~ ~(0 \le p \le 1)~, độ chính xác của người chơi, theo sau là hai số nguyên dương ~nF~ ~(0 \le nF \le N - 1)~ và ~nE~ ~(0 \le nE \le N)~, kích thước của các bộ ~F~ và ~E~ tương ứng, theo sau là nhãn trình phát ~nF~ + ~nE~ đại diện cho chính các bộ ~F~ và ~E~ (theo thứ tự đó), tất cả đều được phân tách bằng dấu cách. Lưu ý rằng nhãn từ ~F~ đại diện cho người chơi của một đội và nhãn từ ~E~ của đội kia. Tập ~F~ sẽ không chứa nhãn của người chơi hiện đang được mô tả.

Output

• Trận đấu về mặt lý thuyết có thể kết thúc với một trong các kết quả cuối cùng ~R*(R+2)~ khác nhau. Với mỗi kết quả, xuất ra xác suất xảy ra dưới dạng số thực, mỗi kết quả trên một dòng. Sắp xếp kết quả trước tiên theo số bàn thắng mà đội thứ nhất ghi được, sau đó là số bàn thắng mà đội thứ hai ghi được, theo thứ tự tăng dần. Chênh lệch cho phép so với giá trị chính xác của mỗi xác suất là ~0,000001~.

Sample Input 1

1 1 2
0.5 0 1 1
0.5 0 1 1

Sample Output 1

0.56250
0.18750
0.25000

Sample Input 2

2 2 5
0.0 1 2 2 1 2
1.0 0 0
0.5 1 0 2
0.5 1 0 1

Sample Output 2

0.2578125
0.2812500
0.0703125
0.1718750
0.1640625
0.0234375
0.0156250
0.0156250

Làm rõ ví dụ đầu tiên:

Ngôi sao biểu thị cầu thủ sở hữu bóng ngay từ đầu. Trận đấu chỉ kéo dài ~T = 2~ nước đi hoặc cho đến khi có người ghi được ~R = 1~ bàn thắng. Vì ~N = 1~ nên trận đấu chỉ có hai người chơi, người này đấu với người kia. Cả hai cầu thủ đều có độ chính xác là ~0,5~, nghĩa là mỗi người có 50% cơ hội ghi bàn khi cố gắng sút, sau đó bóng được trao cho đối phương.

Chúng ta hãy gắn nhãn người chơi màu xám là ~A~ và người chơi màu trắng là ~B~. Theo những giả định này, chỉ có ~6~ trận đấu có thể xảy ra. Mỗi trong số chúng được mô tả trong bảng dưới đây, với xác suất, mô tả và kết quả tương ứng:

Bằng cách tính tổng các xác suất cho các kết quả cuối cùng cụ thể, chúng ta thu được giải pháp sau: