Mino ha deciso di intraprendere la carriera giornalistica iniziando il suo tirocinio negli Stati Uniti, presso la prestigiosa sede newyorkese della CNN.
Il suo compito è quello di pianificare gli spostamenti giornalieri di due troupe televisive a Manhattan.

Com’è noto, le strade di Manhattan formano concettualmente una griglia di righe (street) e di colonne (avenue).
La zona assegnata a Mino corrisponde a una griglia quadrata MxM, le cui righe e colonne sono entrambe numerate da 1 a M.

La CNN dispone di due troupe televisive, ciascuna dotata di una potente telecamera con zoom telescopico:

• la troupe R può muoversi soltanto lungo la prima colonna per riprendere ciò che succede nelle righe (street) della griglia;
• la troupe C può muoversi soltanto lungo la prima riga per riprendere ciò che avviene nelle colonne (avenue) della griglia.

Inizialmente, entrambe le troupe sono posizionate nell’incrocio che corrisponde alla prima riga e alla prima colonna.

Il costo di spostamente di una troupe, dalla posizione I alla posizione J, è misurato come il valore assoluto della differenza di posizione, ossia |I-J| (righe o colonne, a seconda della troupe).
In questo modo, una troupe che non si sposta ha correttamente costo pari a zero.

Ogni mattina Mino riceve la lista degli N eventi che andranno ripresi nella giornata, nell’ordine temporale previsto (ossia il primo evento è il primo ad accadere e così via).
Ciascun evento è identificato dalle sue coordinate r c a indicare che avverrà in corrispondenza dell’incrocio tra la riga (street) r e la colonna (avenue) c della griglia assegnata a Mino.

Tale evento potrà essere ripreso dalla troupe R, posizionandosi sulla riga r, oppure dalla troupe C, posizionandosi sulla colonna c.
Per la troupe scelta da Mino per riprendere quell’evento, verrà pagato un costo pari al suo eventuale spostamento dalla posizione corrente alla posizione di ripresa (come definito sopra).
Infatti, non è sempre necessario spostare una troupe per riprendere due eventi successivi.

Mino deve decidere quale delle due troupe va assegnata a ciascun evento da riprendere, in modo da minimizzare il costo totale, ovvero la somma dei costi di ognuna delle due troupe.
Aiutate Mino a ottenere il costo totale minimo.

Dati in Input

Il file input.txt è composto da N+1 righe, dove N è un intero positivo.
La prima riga contiene due interi positivi N e M che rappresentano rispettivamente il numero N di eventi da riprendere e il lato M della griglia (ossia ci sono M righe e M colonne).
Le successive N righe contengono gli eventi da riprendere nell’ordine temporale in cui si presenteranno.
La k-esima di tali righe è composta da due interi r e c separati da uno spazio per indicare che il k-esimo evento (in ordine temporale) avverrà in corrispondenza dell’incrocio tra la riga (street) r e la colonna (avenue) c.

Dati in Output

Il file output.txt è composto da N righe.
La k-esima di tali righe contiene un solo carattere: la lettera R (maiuscola) oppure la lettera C (maiuscola) per indicare che il k-esimo evento (in ordine temporale) va ripreso, rispettivamente, con la troupe R oppure con la troupe C.
La scelta operata in questo modo deve minimizzare il costo degli spostamenti delle due troupe per riprendere tutti gli eventi nel loro ordine dato.

Assunzioni

• 1 ≤ N, M ≤ 1000
• 1 ≤ r, c ≤ M

 

Esempi

Note

• Nel primo esempio sopra, il costo ottenuto da RRC è 5 (=3+1+1): in questo caso, tale costo è ottimo perché lo spostamento minimo per riprendere tutti gli eventi è proprio 5. Anche RRR è una risposta corretta in quanto il suo costo è 5. Bisogna specificarne una sola in output.
• Nel secondo esempio sopra, il costo ottenuto da CCCRRRR è ottimo perché è pari a 4 (=1+0+0+3+0+0+0). Notare che la sequenzaCCCCCCC produce invece un costo non ottimo, in quanto esso è pari a 5 (=1+0+0+1+1+1+1).
• Se una troupe viene spostata su una riga (o colonna), vi rimane fino all’eventuale spostamento successivo, su indicazione di Mino.