Redoks

Ο Luka δεν προσέχει ξανά στην τάξη, ενώ ο δάσκαλος εξηγεί τις αντιδράσεις οξειδοαναγωγής. Αντί να προσέχει παίζει με αναλογικά καντράν.
Ένα αναλογικό καντράν είναι μια μικρή συσκευή που δείχνει πάντα ένα ψηφίο μεταξύ ~0~ και ~9~. Περιέχει επίσης ένα μικρό κουμπί που αυξάνει τον αριθμό κατά ~1~ (εκτός αν είναι ~9~, οπότε αλλάζει σε ~0~).
Ο Luka έχει ~N~ τέτοια καντράν στο γραφείο του, με αριθμό ~1~ έως ~N~ από αριστερά προς τα δεξιά, και δύο φύλλα χαρτιού για να γράψει.
Το παιχνίδι του Luka ξεκινά με τον ίδιο να ρυθμίζει τα καντράν σε κάποια αρχική διαμόρφωση, την οποία στη συνέχεια γράφει στο πρώτο φύλλο. Στη συνέχεια, ο Luka κάνει τα ακόλουθα ~M~ φορές:

• Επιλέγει δύο ακέραιους αριθμούς ~A~ και ~B~ ~(1 \le A \le B \le N)~ και τους γράφει στο πρώτο φύλλο.

• Υπολογίζει το άθροισμα των αριθμών στα καντράν που αριθμούνται από ~A~ μέχρι και ~B~ και γράφει το άθροισμα στο δεύτερο φύλλο.

• Πατάει το κουμπί μία φορά σε όλα τα καντράν που αριθμούνται από ~A~ μέχρι και ~B~.

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

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~ και ~M (1 \le N \le 250\,000,\;1 \le M \le 100\,000)~.
Η δεύτερη γραμμή περιέχει την αρχική διαμόρφωση των καντράν, ~N~ δεκαδικά ψηφία χωρίς κενά.To πρώτο ψηφίο είναι ο αριθμός αρχικά στο καντράν ~1~, το δεύτερο ψηφίο ο αριθμός στo καντράν ~2~ και ούτω καθεξής. Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει δύο ακέραιους αριθμούς ~A~ και ~B (1 \le A \le B \le N)~.

Έξοδος

Εκτυπώστε ~M~ γραμμές, τα αθροίσματα που υπολόγισε ο Luka, με τη σειρά που τα υπολόγισε.

Βαθμολογία

Στο ~30~% όλων των αρχείων δοκιμής, οι αριθμοί ~N~ και ~M~ θα είναι μικρότεροι από ~1000~.

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

input

4 3
1234
1 4
1 4
1 4

output

10
14
18

input

4 4
1234
1 1
1 2
1 3
1 4

output

1
4
9
16

input

7 5
9081337
1 3
3 7
1 3
3 7
1 3

output

17
23
1
19
5