Lanterns

Ο αγρότης John πήγε το κοπάδι των αγελάδων του μια βόλτα στις Άλπεις! Μετά από λίγο, ο ουρανός σκοτείνιασε και έπρεπε να σταματήσουν. Ωστόσο, παρέμειναν μερικές αγελάδες παγιδευμένες κατά μήκος της οροσειράς και εναπόκειται στον John να τις σώσει όλες!

Η οροσειρά που διασχίζουν οι αγελάδες αντιπροσωπεύεται από μια σειρά ~n~ κορυφών σε κάθετο επίπεδο ~2~ διαστάσεων. Θα ονομάσουμε αυτές τις κορυφές "κορυφές" ( "peaks"). Οι κορυφές αριθμούνται κατά σειρά από ~1~ έως ~n~, ταξινομημένα. H κάθε κορυφή ~i~ έχει συντεταγμένες ~(i, h_i)~. Η αξία ~h_i~ δηλώνει το υψόμετρο της κορυφής ~i~. Είναι σίγουρο ότι τα ~h_1, h_2, \cdots, h_n~ είναι αντίστοιχα των ~1 \cdots n~. (Αυτό σημαίνει ότι για κάθε ~j = 1, \cdots, n~, έχουμε ~h_i = j~ για ακριβώς κάθε ένα ~i \in (1, \cdots, n)~.)

Για κάθε ~i ( 1 \le i < n)~, οι κορυφές ~i~ και ~i+1~ συνδέονται με μια ευθεία γραμμή.

Καθώς έχει νυχτώσει, ο John δεν μπορεί να ταξιδέψει σε κανένα μέρος του βουνού, εκτός αν έχει τουλάχιστον ένα λειτουργικό φανάρι μαζί του. Ευτυχώς, υπάρχουν φανάρια διαθέσιμα για να αγοράσει. Για κάθε ~j (1 \le j \le k)~, το φανάρι ~j~ μπορεί να αγοραστεί στην κορυφή ~p_j~ για ~c_j~ francs.

Δυστυχώς, το φανάρι λειτουργεί μόνο όταν το τρέχον υψόμετρο του John βρίσκεται εντός του εύρους ~[a_j, b_j]~. Με άλλα λόγια όποτε το τρέχον υψόμετρο του John είναι αυστηρά μικρότερο από ~a_j~ ή αυστηρά μεγαλύτερο από ~b_j~, το φανάρι ~j~ δεν λειτουργεί. Σημειώστε ότι τα φανάρια δεν χαλάνε όταν βρίσκονται εκτός από το εύρος τους. Για παράδειγμα, όταν το υψόμετρο του John υπερβαίνει το ~b_j~, το φανάρι ~j~ θα σταματήσει να λειτουργεί, αλλά μόλις ο John επιστρέψει στο υψόμετρο ~b_j~ το φανάρι θα αρχίσει να λειτουργεί πάλι.

Εάν ο John βρίσκεται σε μια κορυφή ~p~ μπορεί να εκτελέσει μία από τις ακόλουθες τρεις ενέργειες:

• Μπορεί να αγοράσει ένα από τα φανάρια που είναι διαθέσιμα στην κορυφή ~p~. Μόλις αγοράσει ένα φανάρι, θα μπορεί να το χρησιμοποιεί για πάντα.
• Εάν ~p > 1~ μπορεί να περπατήσει μέχρι την κορυφή ~p - 1~.
• Εάν ~p < n~ μπορεί να περπατήσει μέχρι την κορυφή ~p + 1~.

Ο John δεν πρέπει ποτέ να κινείται χωρίς φανάρι που να λειτουργεί. Μπορεί να περπατήσει μόνο μεταξύ δύο γειτονικών κορυφών αν σε κάθε στιγμή της διαδρομής του, αν τουλάχιστον ένα από τα φανάρια που είναι ήδη δικά του μπορεί να λειτουργήσει. (Δεν χρειάζεται να είναι το ίδιο φανάρι σε όλη τη διαδρομή).

Για παράδειγμα, ας υποθέσουμε ότι ο αγρότης John βρίσκεται αυτή τη στιγμή σε μια κορυφή με υψόμετρο ~4~ και επιθυμεί να περπατήσει σε μια γειτονική κορυφή με υψόμετρο ~1~. Αν ο John έχει φανάρια που να λειτουργούν στις περιοχές υψομέτρου ~[1,3]~ και ~[3,4]~, αυτό θα του επιτρέψει να περπατήσει από την μια κορυφή στην άλλη. Ωστόσο, εάν ο John έχει φανάρια που λειτουργούν μόνο στις περιοχές ~[1,1]~ και ~[2,5]~, τότε ο John δεν θα μπορεί να περπατήσει ανάμεσα σε αυτές τις δύο κορυφές ακόμα: γιατί, για παράδειγμα, κανένα από τα φανάρια του δεν λειτουργεί σε υψόμετρο ~1.47~.

Ο σκοπός σας είναι να προσδιορίσετε τις απαντήσεις σε πολλές ανεξάρτητες ερωτήσεις.

Για κάθε ~1 \le j \le k~ που ικανοποιεί τη σχέση ~a_j \le h_{p_j} \le b_j~, ας υποθέσουμε ότι ο John ξεκινά την αναζήτησή του στην κορυφή ~p_j~ αγοράζοντας φανάρι ~j~. Για να ψάξει σε ολόκληρη την οροσειρά, πρέπει στη συνέχεια, να επισκεφθεί κάθε μία από τις ~n~ κορυφές τουλάχιστον μία φορά εκτελώντας επανειλημμένα μία από τις τρεις παραπάνω ενέργειες. Για κάθε ένα ~j~, καθορίστε τον ελάχιστο συνολικό αριθμό francs που ο John πρέπει να ξοδέψει για να ψάξει σε ολόκληρη την οροσειρά. (Αυτό το κόστος περιλαμβάνει και την αρχική αγορά φαναριού ~j~.)

Είσοδος

Η πρώτη γραμμή περιέχει τα ~n~ και ~k (1 \le n \le 2\,000,\,1\le \le 2\,000)~ - τον αριθμό των κορυφών του βουνού και τα διαθέσιμα φανάρια, αντίστοιχα.

Η δεύτερη γραμμή περιέχει ~n~ ακέραιους, χωρισμένους με κενό, τους ~h_1, h_2, \cdots, h_n (1 \le h_i \le n)~: το υψόμετρο κάθε κορυφής. Είναι βέβαιο ότι οι τιμές ~h_i~ είναι αντίστοιχες με τις τιμές από ~1~ μέχρι ~n~.

H γραμμή ~j~ - των επόμενων ~k~ γραμμών περιέχει τέσσερεις ακέραιους, χωρισμένους με κενό, ~p_j, c_j, a_j~ και ~b_j (1 \le p_j \le n,\,1 \le c_j \le 10^6,\,1 \le a_j \le b_j \le n)~ - την κορυφή του βουνού στην οποία μπορούν τα φανάρια ~j~ να αγοραστούν, το κόστος και το εύρος λειτουργίας, κάθε φαναριού αντίστοιχα.

Έξοδος

Για κάθε ~j (1 \le j \le k)~ τυπώνετε στην έξοδο μ'ια γραμμή:

• Αν το ~h_{p_j}~ είναι έξω από το διάστημα ~e \,[a_j, b_j]~, η έξοδος είναι ~-1~.
• Αλλιώς, αν ο John δεν μπορεί να ψάξει όλοκληρη την οροσειρά με το πρώτο αγορασμένο φανάρι ~j~, η έξοδος είναι ~-1~.
• Αλλιώς, η έξοδος είναι το ελάχιστο συνολικό ποσό σε francs που ο John χρειάζεται να ξοδέψει για να ψάξει ολόκληρη την οροσειρά στο καθορισμένο διάστημα, αν ξεκινήσει αγοράζοντας το φανάρι ~j~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~9~	~n \le 20~ και ~k \le 6~
~2~	~12~	~n \le 70~ και ~k \le 70~
~3~	~23~	~n \le 300, k \le 300~ και ~h_i = i~, για όλα τα ~1\le i \le n~
~4~	~16~	~n \le 300, k \le 300~
~5~	~40~	Κανένας επιπλέον περιορισμός.

Παράδειγμα

input

7 8
4 2 3 1 5 6 7
3 1 2 4
1 2 1 3
4 4 1 7
6 10 1 7
6 20 6 6
6 30 5 5
7 40 1 6
7 50 7 7

output

7
-1
4
10
30
-1
-1
-1

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

Αν ο John αρχίσει αγοράζοντας το φανάρι ~1~ στην κορυφή ~3~, μπορεί να κάνει τις ακόλουθες ενέργειες, με την εξής σειρά:

• να περπατήσει αριστερά ~2~ φορές στη κορυφή ~1~
• να αγοράσει το φανάρι ~2~
• να περπατήσει δεξιά στη κορυφή ~4~
• να αγοράσει το φανάρι ~3~
• να περπατήσει δεξιά στη κορυφή ~7~

Σε αυτό το σημείο, ο John έχει επισκεφτεί κάθε κορυφή τουλάχιστον μία φορά και ξόδεψε συνολικά ~1 + 2 + 4 = 7~ francs.

Ο John δεν μπορεί να ξεκινήσει αγοράζοντας τα φανάρια ~2~, ~6~ ή ~7~, αφού δεν λειτουργούν στο υψόμετρο στο οποίο μπορούν να αγοραστούν. Έτσι, οι απαντήσεις για καθένα από αυτά τα φανάρια είναι ~-1~.

Εάν ο John αρχίσει αγοράζοντας τα φανάρια ~3~ ή ~4~, μπορεί να επισκεφθεί όλες τις κορυφές χωρίς να αγοράσει επιπλέον φανάρια.

Αν ο John αρχίσει αγοράζοντας το φανάρι ~5~, μπορεί επισης να αγοράσει το φανάρι ~4~ αργότερα.

Αν ο John αρχίσει αγοράζοντας το φανάρι ~8~, θα κολλήσει στην κορυφή ~7~. Ακόμα και αν αγοράσει το φανάρι ~7~, επίσης δεν θα μπορεί να περπατήσει από την κορυφή ~7~ στην κορυφή ~6~.