Orehnjaca

Αυτές τις μέρες το τηλεοπτικό στούντιο ξεκίνησε τα γυρίσματα μιας ακόμη νέας σεζόν της εκπομπής μαγειρικής του Jamie Oliver. Αυτή τη σεζόν, ο Jamie σχεδιάζει να παρουσιάσει τις απολαύσεις της κροατικής κουζίνας στον κόσμο. Στο πρώτο επεισόδιο, ο μάστερ σεφ έχει ψήσει ένα ρολό καρυδιάς μήκους $L$ μέτρων, το μακρύτερο που έχει ψηθεί ποτέ σε αυτό το μέρος του κόσμου.
Μετά από ώρες ιδρώτα και μόχθου στην κουζίνα, αποφάσισε να ανταμείψει κάθε έναν από τους $N$ πιστούς του θεατές στο στούντιο.
Έχει ψιλοκόψει το ρολό καρυδιάς σε κομμάτια μήκους ενός μέτρου και τα σημείωσε με αριθμούς από 1 έως $L$, από αριστερά προς τα δεξιά. Κάθε θεατής έχει λάβει ένα μοναδικό αναγνωριστικό αριθμού (έναν θετικό ακέραιο από το 1 έως το $N$), καθώς και ένα χαρτί με δύο ακέραιους αριθμούς, τον $P$ και τον $K$. Στη συνέχεια, κάθε θεατής είχε τη δυνατότητα να πάρει όλα τα κομμάτια από το $P$-οστό μέχρι και το $K$-οστό. Οι θεατές είχαν τη δυνατότητα να πάρουν το μερίδιό τους με τη σειρά των αριθμών ταυτότητάς τους (πρώτα ο θεατής 1, ακολουθούμενος από τον θεατή 2 κ.λπ.). Αυτή η παραγγελία είχε ως αποτέλεσμα ορισμένοι θεατές να λάβουν λιγότερα κομμάτια από αυτά που αρχικά πίστευαν ότι θα έπαιρναν. Η παρακάτω εικόνα αντιστοιχεί στο πρώτο παράδειγμα δοκιμής:

Γράψτε ένα πρόγραμμα για να προσδιορίσετε ποιος θεατής περίμενε να πάρει τα περισσότερα κομμάτια γλυκού καρυδιάς και ποιος θεατής πήρε πραγματικά τα περισσότερα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο $L$ $(1\le L\le 1000)$, το μήκος του ρολού καρυδιάς.
Η δεύτερη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό $N$ $(1\le N\le 1000)$, τον αριθμό των θεατών.
Κάθε μία από τις ακόλουθες γραμμές $N$ περιέχει δύο θετικούς ακέραιους $P_i$ και $K_i$ $(1\le P_i\le K_i\le L,i=1\dots N)$, τις τιμές $P$ και $K$ όπως περιγράφονται στη δήλωση προβλήματος για τον θεατή με αριθμό $i$.

Έξοδος

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

Βαθμολογία

Εάν ο πρώτος αριθμός είναι σωστός, η λύση κερδίζει το $60$% των πόντων για αυτήν την περίπτωση δοκιμής και εάν ο δεύτερος αριθμός είναι σωστός, η λύση λαμβάνει το $40$% των πόντων για αυτήν την περίπτωση δοκιμής.

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

input

10
3
2 4
7 8
6 9

output

3
1

input

10
3
1 3
5 7
8 9

output

1
1

input

10
5
1 1
1 2
1 3
1 4
7 8

output

4
5