Program

Ο Mirko προσπαθεί να κάνει αποσφαλμάτωση(debug) σε ένα κομμάτι του κώδικά του. Αρχικά δημιουργεί έναν πίνακα ~N~ ακεραίων και τον γεμίζει με μηδενικά. Στη συνέχεια καλεί επανειλημμένα την ακόλουθη διαδικασία (είναι τόσο καλός προγραμματιστής που την κωδικοποίησε και σε C++ και Pascal):

void something( int jump ) {
  int i = 0;
  while( i < N ) {
    seq[i] = seq[i] + 1;
    i = i + jump;
  }
}

procedure something( jump: longint );
var i : longint;
begin
  i := 0;
  while i < N do
  begin
    seq[i] := seq[i] + 1;
    i := i + jump;
  end;
end;

Όπως μπορείτε να δείτε, αυτή η διαδικασία αυξάνει όλα τα στοιχεία του πίνακα των οποίων οι δείκτες διαιρούνται από τη μεταβλητή ~jump~ κατά ένα.
Ο Mirko καλεί τη διαδικασία ακριβώς ~K~ φορές, χρησιμοποιώντας την ακολουθία ~X_1 X_2 X_3\ldots X_k~ ως ορίσματα.
Μετά από αυτό, ο Mirko έχει μια λίστα με ~Q~ ειδικά μέρη του πίνακα που πρέπει να ελέγξει για να επαληθεύσει ότι ο κώδικάς του λειτουργεί σωστά. Κάθε ένα από αυτά τα μέρη ορίζεται από δύο αριθμούς, ~L~ και ~R\;(L \le R)~, το αριστερό και το δεξί όριο του ειδικού τμήματος. Για να ελέγξει τον κώδικα, ο Mirko πρέπει να υπολογίσει το άθροισμα όλων των στοιχείων ~seq~ ενδιάμεσα συμπεριλαμβανομένων των ~L~ και ~R~. Με άλλα λόγια ~seq[L]\; +\; seq[L+1]\; +\; seq[L+2]\ldots\; +\; seq[R]~. Επειδή πρέπει να γνωρίζει την απάντηση εκ των προτέρων για να την ελέγξει, σας ζήτησε να τον βοηθήσετε.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς,το μέγεθος του πίνακα ~N\;(1 \le N \le 10^6)~, και τον αριθμό κλήσεων ~K\;(1 \le K \le 10^6)~, σε κάτι που κάνει ο Mirko.
Η δεύτερη γραμμή περιέχει ~K~ ακέραιους: ~X_1 X_2 X_3 \ldots X_k~, ορίσματα που μεταβιβάζονται στη διαδικασία. ~(1 \le X_i < N)~.
Η επόμενη γραμμή περιέχει τον ακέραιο αριθμό των ειδικών τμημάτων του πίνακα ~Q\;(1 \le Q \le 10^6)~, που πρέπει να ελέγξει ο Mirko.
Οι επόμενες ~Q~ στο πλήθος γραμμές περιέχουν δύο ακέραιους η κάθε μία ~L_i~ και ~R_i(0 \le L_i \le R_i < N)~, τα όρια κάθε ειδικού τμήματος.

Έξοδος

Η έξοδος πρέπει να περιέχει ακριβώς ~Q~ το πλήθος γραμμές. Η ~i~-οστή γραμμή πρέπει να περιέχει το άθροισμα των στοιχείων ~seq[L_i] \;+\; seq[L_{i+1}] \;+\; seq[L_{i+2}] \;+\; \ldots \;+\; seq[R_i]~.

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

input

10 4
1 1 2 1
3
0 9
2 6
7 7

output

35
18
3

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

Η διαδικασία καλείται με ορίσματα ~1,\;1,\;2,\;1~.
Μετά από αυτό, ο πίνακας περιέχει τις τιμές ~\{4,\;3,\;4,\;3,\;4,\;3,\;4,\;3,\;4,\;3\}~. Το άθροισμα των δεικτών ~2~ έως και ~6~ είναι ~4+3+4+3+4 = 18~.

input

11 3
3 7 10
3
0 10
2 6
7 7

output

8
2
1

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

Ο πίνακας είναι ~{3,\;0,\;0,\;1,\;0,\;0,\;1,\;1,\;0,\;1,\;1}~.

input

1000000 6
12 3 21 436 2 19
2
12 16124
692 29021

output

16422
28874