Περνώντας την ώρα

Πρόβλημα

Το παιχνίδι Nim έχει τους ακόλουθους κανόνες: Υπάρχουν ~n~ στοίβες από πέτρες. Δύο παίκτες, παίζοντας εναλλάξ, επιλέγουν μια μη κενή στοίβα και αφαιρούν ένα (θετικό) αριθμό από πέτρες από αυτή. Ο παίκτης που δεν μπορεί να κάνει κάποια κίνηση (δηλαδή ο παίκτης που είναι η σειρά του όταν όλες οι στοίβες έχουν αδειάσει) χάνει.

Καθώς περιμένουν να εκπαιδευτεί ένα μοντέλο στην εργασία της Μηχανικής Μάθησης, η Αγγελική και ο Δημήτρης αποφασίζουν να παίξουν αυτό το παιχνίδι. Επειδή όμως για τη νίκη στο Nim υπάρχει γνωστή στρατηγική, αποφασίζουν να παίξουν μια παραλλαγή αυτού. Έτσι, σε κάθε γύρο παίζουν μόνο με τις στοίβες ενός συγκεκριμένου εύρους. Στην αρχή κάθε γύρου ο Δημήτρης μπορεί να αφαιρέσει κάποιες από τις στοίβες εντός του εύρους, αφήνοντας όμως τουλάχιστον 1. Προφανώς μπορεί και να μην αφαιρέσει καμία στοίβα. Σκοπός της αφαίρεσης είναι η Αγγελική, η οποία παίζει πάντα πρώτη, να μην μπορεί να κερδίσει.

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

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

Μορφή εισόδου

Η 1η γραμμή της εισόδου θα περιέχει 2 ακεραίους: Το πλήθος των στοιβών ~n~ και το πλήθος των γύρων ~q~. Η 2η γραμμή θα περιέχει ~n~ ακεραίους χωρισμένους ανά 2 μεταξύ τους, έστω ~a_1, a_2, ..., a_n~. Οι επόμενες ~q~ γραμμές θα περιέχουν 2 ακεραίους, το εύρος όπου θα παιχτεί ο γύρος. Αν η \(i-όστή\) από αυτές τις γραμμές περιέχει τους αριθμούς ~l_i, r_i~ τότε ο \(i-οστός\) γύρος θα πρέπει να παιχτεί στις στοίβες ~a_{l_i}, a_{l_i+1}, ..., a_{r_i}~.

Μορφή εξόδου

Για κάθε γύρο (σε καινούρια γραμμή):

• Αν ο Δημήτρης μπορεί να κερδίσει το πρόγραμμα πρέπει να τυπώνει 2 ακαιρέους χωρισμένους με ένα κενό: το μέγιστο πλήθος από στοίβες που μπορεί να αφαιρέσει και το πλήθος των διαφορετικών τρόπων που μπορεί να αφαιρέσει αυτόν τον αριθμό από στοίβες, modulo 998244353.
• Αν ο Δημήτρης δεν μπορεί να κερδίσει, το πρόγραμμα πρέπει να επιστρέφει -1.

Περιορισμοί

• ~1\le n, q \le 10^5~
• ~1 \le a_i\le 50~
• ~1 \le l_i, r_i \le n~

Hint: Αναζητήστε το πότε κάθε παίκτης μπορεί να νικήσει το παιχνίδι Nim

Παράδειγμα

Είσοδος

9 5
0 1 2 1 3 4 5 6 0
1 5
2 5
3 5
4 5
1 9

Έξοδος

4 1
2 1
0 1
-1
8 2