Mnogomet

~2N~ άτομα παίζουν ποδόσφαιρο, χωρισμένα σε δύο ομάδες. Κάθε παίκτης φορά ένα φόρεμα με το λογότυπο της ομάδας και έναν μοναδικό (στην ομάδα) θετικό ακέραιο από 1 έως και ~N~. Για κάθε παίκτη, γνωρίζουμε την ακρίβειά του, το σύνολο των συμπαικτών στους οποίους μπορεί να δώσει τη μπάλα (~F~) και το σύνολο των αντιπάλων που μπορούν να του πάρουν την μπάλα (~E~). Όταν ένας παίκτης έχει στη κατοχή του τη μπάλα, μετά από ακριβώς ένα δευτερόλεπτο θα συμβεί ένα από τα ακόλουθα γεγονότα:

• ο παίκτης δίνει τη μπάλα σε έναν τυχαίο συμπαίκτη από το σετ ~F~,
• ένας τυχαίος αντίπαλος από το σετ ~E~ του παίρνει την μπάλα,
• ο παίκτης επιχειρεί ένα σουτ στο τέρμα.
  Εάν ο παίκτης επιχειρήσει ένα σουτ, η πιθανότητα να πετύχει ένα γκολ είναι ίση με την ακρίβειά του. Μετά το σουτ, είτε ήταν επιτυχημένο είτε όχι, η μπάλα δίνεται στον παίκτη νούμερο 1 από την αντίπαλη ομάδα.
  Οι πιθανότητες διαφορετικών γεγονότων είναι στην αναλογία ~|F|\;:\;|E|\;:\;1~, με τη σειρά αυτή, και εξαρτώνται μόνο από τον παίκτη που έχει αυτή τη στιγμή την μπάλα (το ~|S|~ καθορίζει το μέγεθος του σετ ~S~ που αντιστοιχεί στον τρέχοντα παίκτη), όχι σε οποιαδήποτε προηγούμενα γεγονότα στο παιχνίδι. Η λέξη "τυχαία" σημαίνει ότι όλοι οι παίκτες από το σετ ~F~ (ή ~E~) έχουν την ίδια πιθανότητα να περάσουν (ή να πάρουν) την μπάλα από τον παίκτη που έχει αυτήν τη στιγμή την μπάλα. Ο χρόνος που περνάει μια μπάλα χωρίς να είναι στην κατοχή ενός παίκτη είναι αμελητέος.
  Ο αγώνας ξεκινά με τον παίκτη 1 από την πρώτη ομάδα που έχει την κατοχή της μπάλας και τελειώνει είτε όταν μία ομάδα έχει πετύχει R γκολ είτε όταν περάσουν T δευτερόλεπτα, όποιο συμβεί πρώτο. Για κάθε πιθανό τελικό σκορ, προσδιορίστε την πιθανότητα ο αγώνας να τελειώσει με αυτό. Η παρακάτω εικόνα απεικονίζει τη διάταξη του παίκτη για το δεύτερο παράδειγμα δοκιμής:

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τρεις θετικούς ακέραιους αριθμούς: ~N~ ~(1 \le ~N~ \le 100)~, τον αριθμό των παικτών σε κάθε ομάδα, R ~(1 \le R \le 10)~, τον αριθμό των γκολ που απαιτούνται για τη νίκη και T ~(1 \le T \le 500)~, η μέγιστη διάρκεια του αγώνα.
Οι ακόλουθες ~N~ γραμμές περιέχουν περιγραφές των παικτών της πρώτης ομάδας, μία ανά γραμμή, ενώ οι επόμενες ~N~ γραμμές περιέχουν περιγραφές των παικτών της δεύτερης ομάδας. Η περιγραφή ενός παίκτη αποτελείται από έναν πραγματικό αριθμό ~p~ ~(0 \le p \le 1)~, την ακρίβεια του παίκτη, ακολουθούμενο από δύο θετικούς ακέραιους, ~nF~ ~(0 \le nF \le N - 1)~ και nE ~(0 \le nE \le N)~, τα μεγέθη των συνόλων ~F~ και ~E~, αντίστοιχα, ακολουθούμενα από ~nF + nE~ ετικέτες παικτών που αντιπροσωπεύουν τα ίδια τα σύνολα ~F~ και ~E~ (με αυτή τη σειρά), όλα διαχωρισμένα με χώρο. Σημειώστε ότι οι ετικέτες από το ~F~ αντιπροσωπεύουν παίκτες από τη μία ομάδα και οι ετικέτες από το ~E~ την άλλη ομάδα. Το σετ ~F~ δεν θα περιέχει την ετικέτα του προγράμματος αναπαραγωγής που περιγράφεται αυτήν τη στιγμή.

Έξοδος

Ο αγώνας μπορεί θεωρητικά να τελειώσει με ένα από τα ~R * (R + 2)~ διαφορετικά τελικά αποτελέσματα. Για κάθε αποτέλεσμα, βγάζετε την πιθανότητα πραγματοποίησής του ως πραγματικός αριθμός, μία πιθανότητα ανά γραμμή. Ταξινομήστε τα αποτελέσματα πρώτα με τον αριθμό των γκολ που σημείωσε η πρώτη ομάδα και μετά με τον αριθμό των γκολ που σημείωσε η δεύτερη ομάδα, με αύξουσα σειρά. Η επιτρεπόμενη διαφορά από την ακριβή τιμή για κάθε πιθανότητα είναι ~0,000001~.

Παραδείγματα

input

1 1 2
0.5 0 1 1
0.5 0 1 1

output

0.56250
0.18750
0.25000

Επεξήγηση του 1ου παραδείγματος:

Το αστέρι υποδηλώνει τον παίκτη που κατέχει την μπάλα στην αρχή. Ο αγώνας διαρκεί μόνο για ~T = 2~ κινήσεις ή μέχρι κάποιος να σκοράρει ~R = 1~ γκολ. Εφόσον ~N = 1~, υπάρχουν μόνο δύο παίκτες στον αγώνα, που παίζουν ο ένας εναντίον του άλλου. Και οι δύο παίκτες έχουν ακρίβεια 0,5, που σημαίνει ότι ο καθένας έχει ~50~% πιθανότητες να πετύχει ένα γκολ όταν προσπαθεί να σουτάρει, μετά το οποίο η μπάλα δίνεται στον αντίπαλο.

Ας χαρακτηρίσουμε τον γκρίζο παίκτη ως ~A~ και τον λευκό παίκτη ως ~B~. Σύμφωνα με αυτές τις υποθέσεις, υπάρχουν μόνο 6 πιθανοί αγώνες. Καθένα από αυτά περιγράφεται στον παρακάτω πίνακα, με την αντίστοιχη πιθανότητα, περιγραφή και αποτέλεσμα:

0.~25~	Ο Α αποφασίζει να σουτάρει και σκοράρει!	1:0
~0.25 \cdot 0.25~	Ο Α αποφασίζει να σουτάρει, αλλά αστοχεί. Ο B αποφασίζει να σουτάρει και σκοράρει!	0:1
~0.25 \cdot 0.25~	Ο Α αποφασίζει να σουτάρει, αλλά αστοχεί. Ο Β αποφασίζει να σουτάρει, αλλά επίσης αστοχεί.	0:0
~0.5 \cdot 0.25~	Ο Α χάνει την μπάλα από τον Β. Ο Β αποφασίζει να σουτάρει και σκοράρει!	0:1
~0.5 \cdot 0.5~	Ο Α χάνει την μπάλα από τον Β. Ο Β χάνει την μπάλα από τον Α.	0:0
~0.5 * 0.25~	Ο Α χάνει την μπάλα από τον Β. Ο Β αποφασίζει να σουτάρει, αλλά αστοχεί	0:0

Αθροίζοντας τις πιθανότητες για συγκεκριμένα τελικά αποτελέσματα, παίρνουμε την ακόλουθη λύση:

0:0	~0.25 \cdot 0.25 + 0.5 \cdot 0.5 + 0.5 \cdot 0.25~	~0.5625~
0:1	~0.25 \cdot 0.25 + 0.5 \cdot 0.25~	~0.1875~
1:0	~0.25~	~0.25~

input

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

output

0.2578125
0.2812500
0.0703125
0.1718750
0.1640625
0.0234375
0.0156250
0.0156250