Histogrami

Το ιστόγραμμα είναι μια γραφική αναπαράσταση μιας στατιστικής κατανομής δεδομένων. Με άλλα λόγια είναι μια συνάρτηση που αναθέτει μια θετική ακέραια τιμή σε κάθε αριθμό στο διάστημα ~0,\,1,\,2, \ldots,\,W - 1~. Για αυτήν την εργασία, περιγράφουμε ένα ιστόγραμμα με μια σειρά σημείων σε καρτεσιανό σύστημα συντεταγμένων τα οποία, διαδοχικά, καθορίζουν το άνω άκρο της περιοχής που περικλείει το ιστόγραμμα.

Πιο συγκεκριμένα, ορίζουμε ένα ιστόγραμμα πλάτους ~W~ με ζυγό αριθμό σημείων στη μορφή:

$$\displaystyle (x_0,\,y_1),\,(x_1,\,y_1),\,(x_1,\,y_2),\,(x_2,\,y_2),\,(x_2,\,y_3), \ldots,\,(x_{N/2-1},\,y_{N/2}),\,(x_{N/2},\,y_{N/2}).$$

Επομένως, ξεκινώντας από το πρώτο σημείο, για κάθε ζεύγος γειτονικών σημείων πρέπει να ισχύει ότι οι ~y~ συντεταγμένες τους είναι ίσες και ότι οι ~x~ συντεταγμένες τους είναι ίσες. Έτσι, το ιστόγραμμα αρχίζει και τελειώνει με οριζόντιο τμήμα, και μεταξύ τους εναλλάσσονται οριζόντια και κάθετα τμήματα.

Επιπλέον, ισχύουν τα ακόλουθα για το σχήμα ενός ιστογράμματος:

1. ~x_0 = 0~ - το ιστόγραμμα ξεκινά από τη γραμμή ~x = 0~.
2. ~x_{N/2} = W~ - το ιστόγραμμα τελειώνει στη γραμμή ~x = W~.
3. ~x_i < x_{i+1}~, για κάθε ~i = 1,\,2,\,\ldots,\,N/2 - 1~ - το ιστόγραμμα ορίζεται από αριστερά προς τα δεξιά και το το μήκος κάθε οριζόντιου τμήματος είναι τουλάχιστον ένα.
4. ~y_i > 0~ - το ύψος του ιστογράμματος είναι πάντα μεγαλύτερο από το μηδέν.
5. ~y_i \neq y_{i+1}~ - το μήκος κάθε κάθετου τμήματος είναι τουλάχιστον ένα.

Για ένα ιστόγραμμα ~H~, έστω ~y_H(x)~ το ύψος του ιστογράμματος στο διάστημα ~\langle x,x+1 \rangle~. Για παράδειγμα,η επιφάνεια που περικλείεται από το ιστόγραμμα μπορεί να υπολογιστεί με τον τύπο ~\sum_{x=0}^{W-1}y_H(x)~. Αν δίνονται δύο ιστογράμματα, ~H~ και ~H^{\prime}~, με ίσο πλάτος ~W~ (το οποίο μπορεί ενδεχομένως να οριστεί με διαφορετικό αριθμό σημείων), τότε μπορούμε να μετρήσουμε τη διαφορά μεταξύ αυτών των δύο ιστογραμμάτων με διάφορους τρόπους. Αυτό το μέτρο διαφοράς μεταξύ των δύο ιστογραμμάτων ονομάζεται επίσης ανακρίβεια του ιστογράμματος ~H^{\prime}~ σε σχέση με το ιστόγραμμα \(Η\). Σε αυτή την άσκηση, εξετάζουμε δύο διαφορετικούς τρόπους μέτρησης διαφορών μεταξύ δύο ιστογραμμάτων και τις ορίζουμε με τον εξής τρόπο:

$$\displaystyle diffcount(H^\prime, H) = \sum_{x=0}^{W-1}diff(y_H(x), y_{H^\prime}(x)), \;\; \text{ όπου } \;\; diff(y_1, y_2) = 0 \;\; \text{ εάν } \;\; y_1 = y_2, \;\; \text{ και } \;\; 1 \;\; \text{ διαφορετικά}. $$

$$\displaystyle abserror(H^\prime, H) = \sum_{x=0}^{W-1}|y_H(x) - y_{H^\prime}(x)| $$

Με άλλα λόγια, ο πρώτος τρόπος μετρά τον αριθμό τα μοναδιαία τμήματα ~\langle x,\,x + 1\rangle~ στα οποία τα δύο ιστογράμματα διαφέρουν, ενώ ο δεύτερος τρόπος είναι το άθροισμα των απόλυτων τιμών των διαφορών σε αυτά τα μεμονωμένα μοναδιαία τμήματα.

Γράψτε ένα πρόγραμμα που, για ένα δεδομένο ιστόγραμμα \(Η\), σύνολο σημείων ~S~ και τρόπο μέτρησης ανακρίβειας, θα μπορεί να βρει και να εξάγει το ιστόγραμμα ~H^\prime~ που χρησιμοποιεί μόνο σημεία από το σύνολο ~S~ στον ορισμό του και έχει την ελάχιστη δυνατή ανακρίβεια σε σχέση με το δεδομένο ιστόγραμμα ~H~.

Εικόνα ~1~: Απεικόνιση του ιστογράμματος και του συνόλου ~S~ και στις δύο περιπτώσεις δοκιμής που δίνονται παρακάτω και οι λύσεις για τον πρώτο και τον δεύτερο τρόπο μέτρησης της ανακρίβειας.

Ο ορισμός του ιστογράμματος ~H^\prime~ πρέπει να συμμορφώνεται με όλες τις προαναφερθείσες συνθήκες (για παράδειγμα, εκεί δεν πρέπει να υπάρχουν δύο συνεχόμενα οριζόντια τμήματα στον ορισμό του ιστογράμματος ~H^\prime~), και κάθε σημείο στον ορισμό πρέπει να είναι ένα από τα σημεία του συνόλου ~S~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N,\,M,\,G\,(2 \le N \le 100\,000,\,2 \le M \le 100\,000,\,1 \le G \le 2,\,N~ ζυγός~)~, αντίστοιχα: ο συνολικός αριθμός σημείων στον ορισμό του ιστογράμματος \(Η\), αριθμός των σημείων στο σύνολο ~S~ και τον αριθμό που καθορίζει ποια είναι η μέθοδος μέτρησης της ανακρίβειας που χρησιμοποιείται: 1 για diffcount και 2 για abserror.

Καθεμία από τις ακόλουθες ~N~ γραμμές περιέχει ακέραιους αριθμούς ~X~ και ~Y~ ~(0 \le X \le 10^6, 1 \le Y \le 10^6)~ - συντεταγμένες ενός σημείου από τον ορισμό του ιστογράμματος \(Η\). Ο ορισμός του ιστογράμματος θα συμμορφώνεται με όλες τις συνθήκες από τη δήλωση της άσκησης.

Κάθε μία από τις ακόλουθες γραμμές ~M~ περιέχει ακέραιους αριθμούς ~X~ και ~Y~ ~(0 \le X \le 10^6, 1 \le Y \le 10^6)~ - συντεταγμένες ενός σημείου από το σύνολο ~S~. Όλα τα σημεία στο σύνολο ~S~ θα είναι διαφορετικά μεταξύ τους, αλλά μπορεί να ταιριάζουν με σημεία από τον ορισμό του ιστογράμματος ~H~.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει τη μικρότερη δυνατή ανακρίβεια ~D~. Η δεύτερη γραμμή εξόδου πρέπει να περιέχει έναν άρτιο ακέραιο ~L~ - τον συνολικό αριθμό σημείων στον ορισμό του απαιτούμενου βέλτιστου ιστογράμματος. Σε καθεμία από τις ακόλουθες γραμμές ~L~, εξάγετε δύο ακέραιους αριθμούς ~X~ και ~Y~ - συντεταγμένες του σημείου στον ορισμό του ιστογράμματος.

Ο ορισμός του ιστογράμματος πρέπει να συμμορφώνεται με όλες τις συνθήκες της άσκησης.

Σημείωση: Η λύση μπορεί να μην είναι μοναδική, αλλά τα δεδομένα εισόδου θα είναι τέτοια ώστε πάντα να υπάρχει τουλάχιστον μία λύση.

Βαθμολογία

Εάν ο ορισμός του ιστογράμματος είναι εσφαλμένος ή δεν εξήχθει, αλλά η πρώτη γραμμή εξόδου είναι σωστή (ελάχιστη ανακρίβεια), η λύση σας θα λάβει το 70% των συνολικών πόντων για αυτήν την περίπτωση δοκιμής.
Σε περιπτώσεις δοκιμών αξίας ~50~ βαθμών, θα ισχύει ~G = 1~. Σε μέρος αυτών των δοκιμαστικών υποθέσεων αξίας ~25~ βαθμών, θα ισχύει επιπλέον ~M \le 5\,000~. Σε περιπτώσεις δοκιμών αξίας ~50~ βαθμών, θα ισχύει ~G = 2~. Σε μέρος αυτών των δοκιμαστικών υποθέσεων αξίας ~25~ βαθμών, θα ισχύει επιπλέον ~M \le 5\,000~.

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

input

10 12 1
0 2
2 2
2 3
4 3
4 1
5 1
5 5
9 5
9 2
10 2
0 4
0 6
3 3
3 6
9 4
9 1
5 3
5 5
10 5
9 2
10 1
8 5

output

5
6
0 6
3 6
3 3
5 3
5 5
10 5

input

10 12 2
0 2
2 2
2 3
4 3
4 1
5 1
5 5
9 5
9 2
10 2
0 4
0 6
3 3
3 6
9 4
9 1
5 3
5 5
10 5
9 2
10 1
8 5

output

14
4
0 4
9 4
9 1
10 1