Boxes

Στις μέρες μας, σχεδόν οποιοδήποτε αντικείμενο μπορεί να αγοραστεί και να πωληθεί μέσω διαδικτύου. Το πρόβλημα είναι η αποστολή του. Για να μπορεί να αποσταλλεί, το αντικείμενο πρέπει πρώτα να συσκευαστεί προσεκτικά σε ένα χαρτοκιβώτιο για την προστασία του.

Τα αντικείμενα ποικίλουν σε μέγεθος και σχήμα και έτσι η εύρεση ενός κιβωτίου με το κατάλληλο μέγεθος μπορεί να αποτελέσει πρόβλημα. Εάν το χαρτοκιβώτιο είναι πολύ μικρό, το αντικείμενο δεν θα χωρέσει. Αν το χαρτοκιβώτιο είναι υπερβολικά μεγάλο, τα έξοδα αποστολής του θα είναι υψηλότερα και είναι επίσης πιο πιθανό το αντικείμενο να μετακινηθεί μέσα στο χαρτοκιβώτιο με αποτέλεσμα να σπάσει.

Οι κατασκευαστές χαρτοκιβωτίων προσφέρουν ένα προκαθορισμένο σύνολο στάνταρ μεγεθών κιβωτίων. Η δουλειά σας είναι να βρείτε από τα στάνταρ μεγέθη χαρτοκιβωτίων αυτό με τον μικρότερο όγκο στο οποίο μπορεί να χωρέσει ένα αντικείμενο.

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

Είσοδος

Η πρώτη γραμμή εισόδου θα περιέχει έναν ακέραιο αριθμό ~n~, ~0 < n < 1000~, τον αριθμό των διαφορετικών μεγεθών των διαθέσιμων χαρτοκιβωτίων. Οι επόμενες ~n~ γραμμές θα περιέχουν τρεις ακέραιους αριθμούς η καθεμία , δίνοντας το μήκος, το πλάτος και το ύψος ενός χαρτοκιβώτιου. Η επόμενη γραμμή θα περιέχει έναν ακέραιο αριθμό ~m~, ~0 < m < 1000~, τον αριθμό των αντικειμένων που πρέπει να συσκευαστούν. Οι επόμενες ~m~ γραμμές θα περιέχουν τρεις ακέραιους η καθεμία, που αντιστοιχούν στο μήκος, το πλάτος και το ύψος ενός αντικειμένου. Όλες οι διαστάσεις θα είναι σε χιλιοστά και θα κυμαίνονται από ~1~ ~mm~ έως ~2000~ ~mm~.

Έξοδος

Η έξοδος πρέπει να αποτελείται από ~m~ γραμμές, μία για κάθε αντικείμενο της εισόδου. Για κάθε αντικείμενο, εξάγετε μια γραμμή που να περιέχει έναν ακέραιο αριθμό, τον όγκο (σε ~mm^{3}~) του μικρότερου χαρτοκιβώτιου στο οποίο χωράει το αντικείμενο. Ένα μέγεθος χαρτοκιβώτιου μπορεί να επαναχρησιμοποιηθεί για οποιονδήποτε αριθμό αντικειμένων. Εάν ένα αντικείμενο δεν χωράει σε κανένα χαρτοκιβώτιο, εξάγετε σε μια γραμμή: ~Item\;does\;not\;fit~.

Παράδειγμα

input

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

output

6
24
24
60
Item does not fit.