Kolekcija

Ο Igor έχει μια τεράστια συλλογή από λαϊκές επιτυχίες στον υπολογιστή του, που περιέχει ~N~ τραγούδια αριθμημένα από 1 έως ~N~.

Η συλλογή είναι τόσο μεγάλη που δεν είναι δυνατό να εμφανιστούν όλα τα τραγούδια ταυτόχρονα στην οθόνη του. Εξαιτίας αυτού, ενώ παίζει ένα τραγούδι, στην οθόνη εμφανίζονται μόνο ~\mathbf{K}~ διαδοχικά τραγούδια από τη συλλογή. Φυσικά, τα \(Κ\) συνεχόμενα τραγούδια περιλαμβάνουν απαραίτητα το τραγούδι που παίζει αυτή τη στιγμή.

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

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

Σημείωση: Η λύση μπορεί να μην είναι μοναδική.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~ και ~K~ ~(1 \le K < N < 1\,000\,000\,000)~, τον αριθμό των τραγουδιών της συλλογής και τον αριθμό των τραγουδιών που εμφανίζονται.
Η δεύτερη γραμμή περιέχει τον ακέραιο αριθμό ~M~ ~(1 \le M \le 300\,000)~, τον αριθμό των τραγουδιών που θα ακούσει ο Igor.
Οι επόμενες \(Μ\) γραμμές περιέχουν τους δείκτες των τραγουδιών που θα ακούσει ο Igor. Όλοι οι αριθμοί θα είναι μεταξύ ~1~ και ~N~ και κανένα τραγούδι δεν θα εμφανιστεί περισσότερες από μία φορές.

Έξοδος

Η έξοδος πρέπει να αποτελείται από ~M+1~ γραμμές.
Στην πρώτη γραμμή εξάγετε τον ελάχιστο δυνατό αριθμό αρχείων για πρόσβαση κατά την αναπαραγωγή της λίστας αναπαραγωγής του Igor.
Μετά από αυτό, για κάθε τραγούδι ~S~, με τη σειρά που δίνονται, εξάγετε ένα ζεύγος ακεραίων ~A~ και ~B~, που σημαίνει ότι κατά την αναπαραγωγή του τραγουδιού ~S~, τα τραγούδια ~A~ έως ~B~ (συμπεριλαμβανομένου) εμφανίζονται στην οθόνη. Τα ~A~ και ~B~ πρέπει να ικανοποιούν τις συνθήκες ~1 \le A \le S \le B \le N~, και ~B - A + 1 = K~.

Βαθμολόγηση

Μια έξοδος που δεν είναι απολύτως σωστή, αλλά η πρώτη γραμμή (ο μικρότερος αριθμός αρχείων προς πρόσβαση) είναι σωστή, θα βαθμολογηθεί με ~50~% των βαθμών για αυτήν τη δοκιμαστική περίπτωση.

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

input

10 3
5
4
5
8
7
6

output

5
4 6
4 6
6 8
6 8
6 8

input

15 4
6
6
14
11
3
8
5

output

10
3 6
11 14
11 14
3 6
5 8
3 6

input

1000 301
3
300
500
700

output

401
300 600
350 650
400 700