Planete

Η Ευρωπαϊκή Διαστημική Υπηρεσία διαθέτει ~N~ τηλεσκόπια που παρατηρούν μακρινούς πλανήτες. Ταξινόμησαν φαινόμενα ~M~ διαφορετικών τύπων. Παρατήρησαν ότι κάθε μέρα σε κάθε πλανήτη συμβαίνει ακριβώς ένα είδος φαινομέμου. Μετρούν τα φαινόμενα σε ημέρες επειδή ανακάλυψαν ότι κάθε ένα από αυτά διαρκεί τουλάχιστον μία ημέρα και το πολύ ~365~. Τα φαίνομενα διαρκούν μόνο πλήρεις αριθμούς ημερών, ποτέ δεν διαρκούν κλασματικό μέρος της ημέρας. Κάθε φαινόμενο του ίδιου τύπου διαρκεί ακριβώς τον ίδιο αριθμό ημερών κάθε φορά που λαμβάνει χώρα, ανεξάρτητα από τον πλανήτη στον οποίο συμβαίνει.
Μετά από πολλά χρόνια παρατήρησης, θέλησαν να αναλύσουν τα δεδομένα. Τα τηλεσκόπια κατέγραψαν όλες τις παρατηρήσεις, αλλά δυστυχώς ξέχασαν να γράψουν τη χρονιά που έγιναν οι εκάστοτε παρατηρήσεις! Κάθε καταχώρηση του τηλεσκοπίου περιλαμβάνει την ημερομηνία έναρξης, την ημερομηνία τερματισμού και το πλήθος των φαινομένων, κάθε τύπου, που παρατηρήθηκαν. Δεδομένων όλων των παρατηρήσεων για όλους τους πλανήτες, υπολογίστε τη διάρκεια κάθε είδους φαινομένου. Σημειώστε ότι τα τηλεσκόπια είναι εξαιρετικά ακριβή και αρχίζουν να λειτουργούν ακριβώς όταν ένα φαινόμενο ξεκινά και τελειώνουν όταν ένα φαινόμενο -όχι απαραίτητα το ίδιο- ολοκληρώνεται.

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

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους αριθμούς ~N~ και ~M\;(1 \le N, M \le 200)~, τον αριθμό των τηλεσκοπίων και τον αριθμό των τύπων φαινομένων αντίστοιχα. Οι επόμενες ~N~ γραμμές περιέχουν ~M + 4~ αριθμούς η καθεμία:

"~D_1 D_1 \; M_1 M_1 \; D_2 D_2 \; M_2 M_2 \; F_1 \; F_2 \ldots F_M~"

Όπου ~D_1 D_1\; M_1 M_1\; (01 \le DD \le 31,\; 01 \le MM \le 12)~ είναι η ημερομηνία έναρξης, ~D_2 D_2\; M_2 M_2\;~ η ημερομηνία τερματισμού και ~F_i\;(0 \le F_i \le 200)~ ο αριθμός φορών που παρατηρήθηκε ο τύπος φαινομένου ~I~.

Έξοδος

Το πρόγραμμα θα εμφανίζει στην οθόνη μια γραμμή που θα περιέχει ~M~ το πλήθος αριθμούς,τις διάρκειες των τύπων φαινομένων. Εάν υπάρχουν περισσότερες από μία λύσεις, εμφανίστε οποιαδήποτε από αυτές. Εάν δεν υπάρχει καμία λύση, εμφανίστε "~-1~".

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

input

1 1 
16 02 03 03 1

output

5

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

Το τηλεσκόπιο παρατήρησε ένα φαινόμενο τύπου ~1~ μεταξύ 26 Φεβρουαρίου και 3 Μαρτίου. Η μόνη δυνατή εξήγηση είναι ότι τα φαινόμενα τύπου ~1~ διαρκούν ~5~ ημέρες.

input

1 1 
16 02 03 03 2

output

185

input

3 3
22 03 01 10 9 10 10
05 05 16 12 1 7 10
20 06 15 01  4 9 10

output

102
204
125