Cokolade

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

Στο μαγαζί υπάρχουν ~n~ διαφορετικές σοκολάτες και η ~i~-οστή από αυτές έχει την τιμή ~c_i~. Η Lana και ο Fran θέλουν να αγοράσουν ~m~ σοκολάτες.

Η Fran βρήκε έναν τρόπο να μοιράσει το κόστος στο κατάστημα:

• Εάν η σοκολάτα είναι φθηνότερη από ~k~ kunas, η Lana θα την πληρώσει.
• Διαφορετικά, η Lana θα πληρώσει ~k~ kunas και η Fran θα πληρώσει τα υπόλοιπα, δηλαδή ~c_i - k~ kunas.

Ας συμβολίσουμε το ~l~ ως το ποσό που πρέπει να πληρώσει η Lana και το ~f~ ως το ποσό που πρέπει να πληρώσει η Fran. Η Lana, δυσαρεστημένη με τη συμφωνία της Fran, θέλει να πειράξει την Fran και να επιλέξει τις σοκολάτες, ώστε η τιμή της έκφρασης ~l - f~ να είναι όσο το δυνατόν μικρότερη. Επειδή η Fran διστάζει και δεν ξέρει πόσες θέλει να αγοράσει, η Lana θέλει να μάθει την ελάχιστη τιμή της έκφρασης ~l - f~ για ~q~ διαφορετικούς αριθμούς ~k_i~ και ~m_i~.

Βοηθήστε την να επιλέξει τις σοκολάτες και προσδιορίστε την ελάχιστη τιμή της έκφρασης ~l - f~ για κάθε ένα από τα ερωτήματα ~q~.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~n~ και ~q~ ~(1 \le n, q \le 10^5)~, τον αριθμό των σοκολατών και τον αριθμό των ερωτημάτων.

Η δεύτερη γραμμή περιέχει ~n~ ακέραιους ~c_1,\,c_2, \cdots, c_q~ ~(1 \le c_i \le 10^9)~, οι τιμές των επιμέρους σοκολατών, κατά σειρά.

Οι ακόλουθες ~q~ γραμμές περιέχουν ακέραιους αριθμούς ~k_i~ και ~m_i~ ~(1 \le k_i \le 10^9,\,1 \le m_i \le n)~, το όριο της Fran και ο αριθμός των σοκολατών που πρόκειται να αγοράσουν.

Έξοδος

Εκτυπώστε ~q~ γραμμές. Στην ~i~-οστή γραμμή εκτυπώστε την απάντηση για το ~i~-οστό ερώτημα της Lana.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~n, q \le 1000,\,c_i,\,k_i \le 10^6~
2	20	~k_1 = \cdots = k_n~
3	35	Κανένας επιπλέον περιορισμός.

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

input

5 2
1 9 22 10 19
18 4
5 2

output

34
-21

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

Στο πρώτο ερώτημα, η Lana μπορεί να πάρει σοκολάτες με τιμές ~1, 9, 22~ και ~10~. Η Lana θα πληρώσει ~38~ kunas και η Fran ~4~ kunas. Η απάντηση είναι ~38 - 4 = 34~.

Στο δεύτερο ερώτημα, η Lana θα επιλέξει σοκολάτες με τιμές ~22~ και ~19~. Η Lana θα πληρώσει ~10~ kunas και η Fran θα πληρώσει ~31~ kunas. Η απάντηση είναι ~10 - 31 = -21~.

input

7 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 5

output

4
16
7
1

input

3 3
5 6 7
10 1
5 3
3 3

output

5
12
0