Inspektor

Μια νέα πόλη μόλις εγκαινιάστηκε σε μια μικρή χώρα. Ως συνήθως, ο Μίρκο έχει εξασφαλίσει τη θέση του προϊστάμενου εφοριακού. Καθήκον του είναι να διασφαλίζει την επάρκεια των λογιστικών σε όλες τις διαφορετικές εταιρείες της πόλης. Υπάρχουν $N$ επιχειρηματικά γραφεία κατά μήκος του κεντρικού δρόμου, με αριθμό από 1 έως $N$ από αριστερά προς τα δεξιά. Όλα τα γραφεία είναι άδεια στην αρχή. με τον καιρό, οι εταιρείες θα μετακινηθούν μέσα και έξω από αυτά τα γραφεία. Από καιρό σε καιρό, ο Mirko θα περνάει από μερικά από τα γραφεία και θα επιθεωρεί τα λογιστικά μόνο μιας εταιρείας, της πιο πλούσιας αυτή τη στιγμή σε αυτά τα γραφεία.

Μια εταιρεία που εισέρχεται περιγράφεται από τέσσερις ακέραιους αριθμούς:

• T – η ημέρα μετακόμισης, αριθμημένη από τα εγκαίνια της πόλης (που είναι η ημέρα 1),
• K – ο αριθμός γραφείου,
• Z – το ημερήσιο κέρδος της εταιρείας (μπορεί να είναι αρνητικό εάν η εταιρεία χάνει χρήματα),
• S – υπόλοιπο του λογαριασμού της εταιρείας την ημέρα μετακίνησης.

Εάν υπάρχει ήδη εταιρεία στο γραφείο K, αυτή η εταιρεία αποχωρεί όταν μετακομίσει η νέα εταιρεία.
Η νέα εταιρεία δεν ανοίγει για επαγγελματικούς λόγους (ή αποκτά κέρδη) παρά μόνο την επόμενη μέρα της μετακόμισης.
Η επίσκεψη επιθεώρησης του Mirko περιγράφεται από τρεις ακέραιους αριθμούς:

• T – η ημέρα της επιθεώρησης, αριθμημένη από τα εγκαίνια της πόλης,
• A και Β – ο Mirko θα περάσει από όλα τα γραφεία με αριθμούς μεταξύ του A και του B, κλειστό διάστημα.

Δεδομένου ότι η Mirko εργάζεται μόνο στο τέλος της ημέρας, όλες οι εταιρείες θα έχουν ήδη ολοκληρώσει τις εργασίες τους και θα έχουν καταγράψει κέρδη για την ημέρα μέχρι τη στιγμή της επίσκεψης του Mirko.
Βοηθήστε τον Mirko, γράφοντας ένα πρόγραμμα, να βρει, για κάθε βόλτα, το υπόλοιπο του λογαριασμού της πιο πλούσιας εταιρείας που περνάει αυτή τη στιγμή ο Mirko.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο θετικούς ακέραιους, $N(1\le N\le 100000)$ και $M(1\le M300000)$, τον αριθμό των γραφείων και των συμβάντων, αντίστοιχα.
Καθεμία από τις ακόλουθες γραμμές $M$ περιέχει μια περιγραφή ενός συμβάντος, μορφοποιημένη είτε ως "1 T K Z S" (για μετακόμιση εταιρείας), είτε ως "2 T A B" (για τη βόλτα επιθεώρησης του Mirko).
Όλα τα συμβάντα δίνονται χρονολογικά, και το πολύ ένα γεγονός θα συμβαίνει κάθε μέρα (δηλαδή, το $T$ θα αυξάνεται αυστηρά). Ο αριθμός ημέρας του τελευταίου συμβάντος θα είναι μικρότερος από ${10}^6$ και οι απόλυτες τιμές όλων των αριθμών $Z$ και $S$ θα είναι μικρότερες από ${10}^6$.

Έξοδος

Για κάθε βόλτα του Mirko τυπώστε μια γραμμή που περιέχει το υπόλοιπο του λογαριασμού της εταιρείας που θα ελέγξει ο Mirko ή τη λέξη «nema» (χωρίς εισαγωγικά) εάν όλα τα γραφεία από τα οποία θα περάσει είναι άδεια.

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

input

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

output

12
17

input

3 6
1 1 1 4 -2
1 2 2 2 6
2 3 3 1
2 4 3 1
1 5 3 -6 20
2 6 2 3

output

8
10
14

input

5 9
1 1 5 4 -5
2 2 3 5
1 3 4 6 9
2 4 1 2
1 6 2 2 3
2 8 2 1
1 9 4 0 17
2 10 5 5
2 11 1 4

output

-1
nema
7
31
17