Eggscavation

Είναι ώρα για διακοπές! Είστε άρρωστοι και κουρασμένοι από τα ~C~ κοχύλια, οπότε αποφασίζετε να γίνετε συλλέκτης κοχυλιών.

Για τις διακοπές σας, αποφασίσατε να επισκεφτείτε το πανέμορφο νησιωτικό έθνος της Καρτεσίας. Είναι ξακουστό για την ύπαρξη μιας υπέροχης τετράγωνης παραλίας που αποτελείται από ένα ~N~ × ~N~ πλέγμα τετράγωνων κελιών. Έχετε φέρει το έμπιστο φτυάρι σας, το οποίο μπορεί να σκάψει ένα τετράγωνο υποπλέγμα ~K~ × ~K~ της παραλίας. Το φτυάρι σας, επειδή είναι έμπιστο, μπορεί να σκάψει μόνο ένα υποπλέγμα ~K~ × ~K~ που βρίσκεται εξ ολοκλήρου μέσα στην παραλία.

Υπάρχουν ~M~ άγνωστο είδη κοχυλιών που κρύβονται κάτω από ορισμένα κελιά του πλέγματος. Συγκεκριμένα για κάθε ~i~, υπάρχουν ~S_i~ κοχύλια από το ~i~-οστο είδος σε ~S_i~ θέσεις πλέγματος, με ~1 \le S_i \le 4~. Για κάθε ξεχωριστό είδος που σκάβετε και φέρνετε πίσω στο σπίτι, μπορείτε να τα πουλήσετε σε έναν επιστήμονα στην πατρίδα σας για ένα δολάριο. Πολλαπλά κοχύλια του ίδιου είδους δεν προσθέτουν επιπλέον αξία.

Τα πράγματα περιπλέκει ένα ένδοξο πουλί dodo που τρέχει γύρω από την παραλία. Σε μια δεδομένη στιγμή, μπορεί να αποφασίσει να θάψει ένα αυγό σε ένα κελί του πλέγματος (συμπεριλαμβανομένων των κελιών του πλέγματος που έχουν ήδη αυγά ή κοχύλια). Το κακό είναι ότι εάν το υποπλέγμα ~K~ × ~K~ που έχει σκάψει το φτυάρι σας περιλαμβάνει ένα αυγό dodo, οι επιστήμονες θα εκνευριστούν που βλάπτετε είδη που απειλούνται με εξαφάνιση και κανείς δεν θα σας πληρώσει τίποτα.

Στο τέλος, αποφασίζετε να καθίσετε αναπαυτικά, να επιστρέψετε στον προγραμματισμό και να προσομοιώσετε το σκάψιμο αντ' αυτού. Θα υπολογίσετε την πιθανότητα ότι η φτυαριά σας, όταν επιλεγεί ομοιόμορφα από όλες τις έγκυρες πιθανές φτυαριές, θα έχει τουλάχιστον ένα δεδομένο ελάχιστο κέρδος (για την εξόφληση των φοιτητικών δανείων σας) σε διαφορετικά χρονικά σημεία. Ποιος θέλει ούτως ή άλλως να ιδρώσει από το φτυάρισμα σε μια παραλία;

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο ακέραιους ~N~ και ~K~, (~1 \le N \le 2\,500~, ~1 \le K \le N~), το μέγεθος της παραλίας και το μέγεθος του φτυαριού αντίστοιχα.

Η δεύτερη γταμμή της εισόδου περιέχει τον ακέραιο ~M~ (~0 \le M \le 10^5~), τον αριθμό από τα είδη κοχυλιών. Οι επόμενες ~M~ γραμμές καθεμία αναπαριστά το είδος ~i~ και αποτελείται από τον ακέραιο ~S_i~ (~1 \le S_i \le 4~) ακολουθούμενο από ~2 \cdot S_i~ επιπλέον ακέραιους, που αναπαριστούντις θέσεις του πλέγματος (μεταξύ του (~1, 1~) και (~N, N~)) όπου τα ~S_i~ κοχύλια εκέινου του είδους είναι θαμμένα.

Η επόμενη γραμμή περιέχει το ~T~ (~1 \le T \le 10\,000~). Καθεμία από τις επόμενες ~T~ γραμμές αναπαριστά ένα συγκεκριμένο χρονικό σημείο (από το παλαιότερο στο νεότερο) και κάθε γραμμή έχει μία από τις ακόλουθες δύο μορφές:

• ~1~ ~A_i~ ~B_i~ (~1 \le A_i, B_i \le N~), που σημαίνει ότι ο dodo μόλις έθαψε ένα αυγό στο κελί (~A_i~, ~B_i~) του πλέγματος.

• ~2~ ~V_i~ (~1 \le V_i \le 10^9~), που σημαίνει ότι θα θέλαμε να υπολογίσουμε την πιθανότητα μια τυχαία φτυαριά σε αυτό το χρονικό σημείο έχει κέρδος σε δολλάρια ~\ge V_i~. Σημειώστε ότι κανένα αυγό ή κοχύλι δεν αφαιρείται ή πρστίθεται όταν υπολογίζεται αυτή η πιθανότητα.

Βαθμολογία

Για τουλάχιστον 15% της βαθμολογίας, ~N \le 40~ και όλες πράξεις ανανέωσης συμβαίνουν πριν από όλες της πράξεις ερώτησης.

Για επιπλέον 25% της βαθμολογίας, όλες πράξεις ανανέωσης συμβαίνουν πριν από όλες της πράξεις ερώτησης.

Έξοδος

Για κάθε ερώτηση, εκτυπώστε σε μία γραμμή την πιθανότητα μια τυχαία φτυαριά να περιέχει τουλάχιστον τον επιθυμητό αριθμό από διαφορετικά είδη κοχυλιών.

Παράδειγμα

input

4 2
3
3 1 1 2 3 4 2
3 1 4 2 3 3 2
4 2 1 2 4 4 1 4 4
6
2 2
2 3
1 2 3
2 2
2 3
2 4

output

0.88889
0.33333
0.44444
0.11111
0.00000

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

Αρχικά έχουμε την ακόλουθη διάταξη από κοχύλια (με τα πρώτα κοχύλια της εισόδου να είναι αριθμημένα ως ~1~ και ούτω καθεξής):

και το φτυάρι μας θα φτυαρίσει ένα τετράγωνο ~2~ x ~2~ από κελιά. Οπότε, υπάρχουν ~9~ πιθανές φτυαριές.

Με κανένα αυγό παρόν, ~8~ από τις ~9~ φτυαριές περιέχουν τουλάχιστον δύο είδη από κοχύλια και ~3~ από τις ~9~ φτυαριές περιέχουν τρία είδη κοχυλιών.

Ένα αυγό πέφτει μετά στο κελί που περιέχει το ~1, 2~.

Τότε, ~4~ από τις ~9~ φτυαριές περιέχουν τουλάχιστον δύο είδη από κοχύλια και κανένα αυγό και μόνο ~1~ φτυαριά (η πιο κάτω αριστερά φτυαριά) θα περιείχε και τα τρία είδη κοχυλιών και κανένα αυγό. Η τελική έξοδος υποδεικνύει ότι δεν υπάρχουν φτυαριές που περιέχουν ~4~ διαφορετικά είδη κοχυλιών.