Good Game

Ο Finn παίζει μια παρτίδα "Δυάρια και Τριάρια". Το "Δυάρια και Τριάρια" είναι ένα παιχνίδι για έναν παίχτη που παίζεται σε ένα μονοδιάστατο ταμπλό. Στην αρχική θέση, υπάρχουν ~N~ κύβοι διατεταγμένοι σε σειρά, με κάθε κύβο να έχει την ένδειξη ~A~ ή ~B~. Οι κύβοι αριθμούνται από το ~1~ έως το ~N~ από τα αριστερά προς τα δεξιά. Ο Finn επιτρέπεται να κάνει κινήσεις της ακόλουθης μορφής:

  ● Επιλέξτε ~2~ ή ~3~ συνεχόμενους κύβους που έχουν την ίδια ένδειξη. Αφαιρέστε τους από το ταμπλό.
  Ενώστε τους υπόλοιπους κύβους μεταξύ τους. Ξανα-αριθμήστε τους κύβους από από τα αριστερά προς τα δεξιά
  ξεκινώντας από τον αριθμό ~1~.

Ο Finn κερδίζει το παιχνίδι αν όλοι οι κύβοι αφαιρεθούν από το ταμπλό. Ο στόχος σας είναι να βοηθήσετε τον Finn να καθορίσει μια νικητήρια ακολουθία κινήσεων ή να καθορίσει αν το παιχνίδι δεν γίνεται να κερδιθεί.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τον ακέραιο αριθμό ~N~.

Η δεύτερη γραμμή της εισόδου θα περιέχει την σειμβολοσειρά ~S~ η οποία είναι η αρχική θέση του παιχνιδιού. Υπάρχουν ~N~ χαρακτήρες στη σειμβολοσειρά ~S~, και κάθε χαρακτήρας στο ~S~ είναι είτε ~A~ είτε ~B~.

Βαθμολογία

Βαθμοί	Περιορισμοί στο ~N~
3	~1 \le N \le 15~
6	~1 \le N \le 300~
7	~1 \le N \le 6\,000~
9	~1 \le N \le 10^6~

Έξοδος

Εάν υπάρχει μια νικητήρια ακολουθία κινήσεων, εκτυπώστε K, τον αριθμό των κινήσεων στη νικητήρια ακολουθία. Σε κάθε μια από τις επόμενες ~K~ γραμμές, εκτυπώστε ένα δείκτη ~i~, ακολουθούμενο από ένα κενό, ακολουθούμενο από έναν αριθμό ~j~, που δηλώνει μια κίνηση που θα αφαιρέσει τους κύβους που βρίσκονται εκείνη τη στιγμή στους δείκτες που ανήκουν στο κλειστό διάστημα ~[i, i+j-1]~.

Αν δεν υπάρχει νικητήρια ακολουθία κινήσεων, εκτυπώστε -1

Αν υπάρχουν πολλαπλές νικητήριες ακολουθίες κινήσεων, τότε, οποιαδήποτε νικητήρια ακολουθία θα γίνει δεκτή. Δεν υπάρχει λόγος να ελαχιστοποιήσετε ή να μεγιστοποιήσετε το ~K~.

Παράδειγμα

input

9
ABAABBBAA

possible output

4
6 2
3 2
2 2
1 3

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

Η έξοδος του παραδείγματος δηλώνει την παρακάτω νικητήρια ακολουθία:

  ~ABAAB\underline{BB}AA~
  ~AB\underline{AA}BAA~
  ~A\underline{BB}AA~
  ~\underline{AAA}~