Double Move

Η Alice και ο Bob παίζουν ένα παιχνίδι και η Claire τους βοηθάει. Το παιχνίδι αποτελείται από τρεις φάσεις.

Στην πρώτη φάση, η Alice και ο Bob κάνουν εναλλασσόμενες κινήσεις. Η Alice κινείται πρώτη. Σε κάθε κίνηση, ένας παίκτης δηλώνει την πρόθεσή του να πάρει μια πέτρα, αλλά αντί να πει ακριβώς ποια, αναφέρει δύο επιλογές. Είναι δυνατόν οι δύο επιλογές να είναι οι ίδιες. Είναι επίσης δυνατό να αναφερθούν πέτρες που είχαν ήδη αναφερθεί στις προηγούμενες κινήσεις. Κατά την πρώτη φάση δεν λαμβάνονται πέτρες - οι παίκτες απλώς δηλώνουν τις προθέσεις τους για τη δεύτερη φάση. Η πρώτη φάση τελειώνει όταν ~n + 1~ δηλώσεις έχουν έχουν γίνει.

Ακολουθεί ένα παράδειγμα πρώτης φάσης για ~n = 3~:

1. Alice: "Θα πάρω είτε την πέτρα ~1~ είτε την πέτρα ~3~".
2. Bob: "Θα πάρω είτε την πέτρα ~2~ είτε την πέτρα ~2~".
3. Alice: "Θα πάρω είτε την πέτρα ~3~ είτε την πέτρα ~2~".
4. Bob: "Θα πάρω είτε την πέτρα ~1~ είτε την πέτρα ~3~".

Στη δεύτερη φάση, για κάθε μία από τις ~n + 1~ δηλώσεις που έχουν γίνει, η Claire διαλέγει μία από τις δύο επιλογές λέγοντας "πρώτη" ("first") ή "δεύτερη" ("second"). Θα ονομάσουμε κάθε ακολουθία των επιλογών που κάνει η Claire ένα σενάριο. Σημειώστε ότι υπάρχουν ακριβώς ~2 \times 2 \times 2 \times \cdots \times 2 = 2^{n+1}~ πιθανά σενάρια. (Ακόμη και αν, σε κάποια δήλωση, η πρώτη και η δεύτερη επιλογή είναι η ίδια, θεωρούμε ότι η επιλογή "πρώτη" ή "δεύτερη" οδηγεί σε διαφορετικά σενάρια).

Ακολουθεί ένα από τα ~16~ σενάρια που θα μπορούσε να επιλέξει η Claire στο παραπάνω παράδειγμα:

1. "Πρώτο": Η Alice θα πάρει την πέτρα ~1~.
2. "Πρώτη": Ο Bob θα πάρει την πέτρα ~2~.
3. "Δεύτερη": Η Alice θα πάρει την πέτρα ~2~.
4. "Πρώτη": Ο Bob θα πάρει την πέτρα ~1~.

Τέλος, στην τρίτη φάση, η Alice και ο Bob αρχίζουν να παίρνουν πέτρες σύμφωνα με τις αποφάσεις της Claire. Ο πρώτος παίκτης που δεν μπορεί να κάνει την απαιτούμενη κίνηση - επειδή η αντίστοιχη πέτρα έχει ήδη ληφθεί - χάνει το παιχνίδι. Σημειώστε ότι εφόσον υπάρχουν ~n~ πέτρες και ~n+1~ κινήσεις, ένας από τους παίκτες πρέπει τελικά να χάσει το παιχνίδι.

Στο παραπάνω παράδειγμα, η Alice ξεκινάει παίρνοντας την πέτρα ~1~. Ο Μπομπ συνεχίζει παίρνοντας την πέτρα ~2~. Η Alice θέλει να συνεχίσει παίρνοντας την πέτρα ~2~, αλλά την έχει ήδη πάρει άλλος, οπότε η Alice χάνει το παιχνίδι και επομένως ο Bob κερδίζει.

Σας δίνεται ο αριθμός ~n~ και η κατάσταση του παιχνιδιού σε κάποιο σημείο κατά τη διάρκεια της πρώτης φάσης: μια ακολουθία ~k~ δηλώσεων που έχουν ήδη γίνει. Αυτές οι δηλώσεις μπορούν να είναι εντελώς αυθαίρετες.

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

Ανεξάρτητα από τον τρόπο με τον οποίο παίζουν η Alice και ο Bob, η Claire είναι εξίσου πιθανό να επιλέξει καθένα από τα ~2^{n+1}~ πιθανά σενάρια. Η Alice και ο Bob το γνωρίζουν αυτό και επομένως όταν παίζουν βέλτιστα, προσπαθούν και οι δύο να ελαχιστοποιήσουν τον αριθμό των σεναρίων στα οποία χάνουν.

Υποθέστε ότι η Alice και ο Bob θα παίξουν το υπόλοιπο του παιχνιδιού όπως περιγράφεται παραπάνω. Για καθέναν από τους δύο παίκτες βρείτε τον αριθμό των σεναρίων στα οποία κερδίζουν το παιχνίδι.

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς, χωρισμένους με κενό διάστημα, ~n~ και \(k (1 \le n \le 35,\,0 \le k \l n+1)\): τον αριθμό των πετρωμάτων και τον αριθμό των δηλώσεων που έχουν ήδη γίνει.

Η υπόλοιπη είσοδος αποτελείται από ~k~ γραμμές, κάθε μία από τις οποίες περιγράφει μία δήλωση, με τη σειρά με την οποία έγιναν. Κάθε μία από αυτές τις γραμμές περιέχει δύο ακέραιους αριθμούς, χωρισμένους με κενό διάστημα: τους αριθμούς δύο πετρωμάτων (και οι δύο μεταξύ ~1~ και ~n~, κλειστό διάστημα, και όχι απαραίτητα διαφορετικοί).

Σημειώστε ότι όταν ~k < n + 1~ ο επόμενος παίκτης που θα κάνει δήλωση εξαρτάται από την ισοτιμία του ~k~.

Έξοδος

Εξάγετε μια γραμμή με δύο ακέραιους αριθμούς, χωρισμένους με κενό διάστημα: τον αριθμό των σεναρίων στα οποία κερδίζει η Alice και τον αριθμό των σεναρίων στα οποία κερδίζει ο Bob, υποθέτοντας ότι και οι δύο παίκτες παίζουν για το υπόλοιπο του παιχνιδιού όπως περιγράφεται στη δήλωση.

Σημειώστε ότι το άθροισμα των δύο αριθμών που εκτυπώνετε πρέπει να είναι ίσο με ~2^{n+1}~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~15~	~n \le 4~
~2~	~34~	~n \le 10~
~3~	~20~	~n \le 25~
~4~	~10~	~k = 0~
~5~	~21~	Κανένας επιπλέον περιορισμός.

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

input

3 4
1 3
2 2
3 2
1 3

output

4 12

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

Το πρώτο παράδειγμα αντιστοιχεί στο παράδειγμα από τη δήλωση του προβλήματος. Δεν υπάρχουν άλλες δηλώσεις που πρέπει να γίνουν, οπότε πρέπει απλώς να δούμε πόσες από τις πιθανές αποφάσεις της Claire οδηγούν στη νίκη της Alice και πόσες από αυτές οδηγούν στη νίκη του Bob. Η Alice θα κερδίσει αν η Claire διαλέξει την πέτρα ~1~ γι' αυτήν στην πρώτη κίνηση και την πέτρα ~3~ γι' αυτήν στη δεύτερη κίνηση, και θα χάσει σε όλες τις άλλες περιπτώσεις.

input

2 0

output

4 4

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

Στο δεύτερο παράδειγμα, αν η Alice ξεκινήσει δηλώνοντας "~1\,1~", ο Bob θα συνεχίσει δηλώνοντας "~2\,2~" και ό,τι κι αν δηλώσει η Alice στην τρίτη κίνηση, θα χάσει, καθώς η Claire θα πρέπει να διαλέξει την πέτρα ~1~ για την πρώτη κίνηση και την πέτρα ~2~ για τη δεύτερη κίνηση και δεν θα μείνουν πέτρες για την Alice στην τρίτη κίνηση. Ωστόσο, αυτή δεν είναι η βέλτιστη πρώτη κίνηση για την Alice: αντίθετα, θα πρέπει να ξεκινήσει δηλώνοντας "~1\,2~". Τότε, ανεξάρτητα από το τι κάνει ο Bob στη δεύτερη κίνηση και τι κάνει η Alice στην τρίτη κίνηση, ο καθένας από αυτούς θα κερδίσει σε ~4~ από τις ~8~ περιπτώσεις.