Wielu uczniów uczestniczy w klubie sportowym. Na początku treningu na siłowni jest $n$ osób, a następnie podczas sesji dołącza do nich kolejno $q$ kolejnych osób. Wzrosty wszystkich $n+q$ uczniów są różne; ponumerujmy uczniów od $1$ do $n+q$ w kolejności rosnącego wzrostu.

Podczas treningu uczniowie wykonują ćwiczenia z piłką. Uczniowie ustawiają się w rzędzie od lewej do prawej w pewnej kolejności. W zależności od kolejności, w jakiej są ustawieni, niektóre pary uczniów tworzą \textit{pary poprawne}.

Para uczniów stojących na pozycjach $i$ i $j$, gdzie $i < j$, tworzy parę poprawną, jeśli spełniony jest jeden z dwóch poniższych warunków:

• uczeń na pozycji $i$ jest najdalej na lewo stojącym uczniem spośród tych, którzy są niżsi od ucznia na pozycji $j$ i stoją po jego lewej stronie;
• uczeń na pozycji $j$ jest najdalej na prawo stojącym uczniem spośród tych, którzy są niżsi od ucznia na pozycji $i$ i stoją po jego prawej stronie.

Na przykład, jeśli uczniowie o numerach $[6, 7, 3, 5, 1, 2]$ stoją w rzędzie, to poprawne pary to $(6, 2)$, $(6, 7)$, $(7, 2)$, $(3, 2)$, $(3, 5)$, $(5, 2)$ i $(1, 2)$.

Ćwiczenie ma dwa poziomy trudności, każdy z własnymi \textit{poprawnymi rzutami}. Podczas wykonywania ćwiczenia na dowolnym poziomie trudności zabronione jest rzucanie piłki do ucznia, który już trzymał piłkę podczas bieżącego ćwiczenia.

Na pierwszym poziomie trudności uczeń może rzucić piłkę do dowolnego ucznia, z którym tworzy parę poprawną i który jest od niego niższy. Na przykład, jeśli uczniowie o numerach $[6, 7, 3, 5, 1, 2]$ stoją w rzędzie, uczeń o numerze $3$ może rzucić piłkę tylko do ucznia o numerze $2$, uczeń o numerze $5$ może rzucić do uczniów o numerach $3$ i $2$, a uczeń o numerze $1$ nie może rzucić piłki do nikogo.

Na drugim poziomie trudności uczeń może rzucić piłkę do dowolnego ucznia, z którym tworzy parę poprawną. Na przykład, jeśli uczniowie o numerach $[6, 7, 3, 5, 1, 2]$ stoją w rzędzie, uczeń o numerze $3$ może rzucić piłkę do uczniów o numerach $2$ i $5$, uczeń o numerze $5$ może rzucić do uczniów o numerach $3$ i $2$, a uczeń o numerze $1$ może rzucić piłkę do ucznia o numerze $2$.

Ćwiczenie wykonuje się w następujący sposób. Trener wybiera poziom trudności $t$. Jeden z uczniów bierze piłkę i wykonuje poprawny rzut. Uczeń, który otrzymuje piłkę, następnie wykonuje poprawny rzut, i tak dalej. Rzuty wykonuje się tak długo, jak to możliwe. Jeśli istnieje wiele poprawnych rzutów, można wybrać dowolny z nich, ale zabronione jest rzucanie piłki do ucznia, który już trzymał piłkę podczas bieżącego ćwiczenia. Uczestnicy treningu wykonują poprawne rzuty na wybranym poziomie trudności w taki sposób, aby wykonać jak największą liczbę rzutów.

Następnie $q$ razy do treningu dołącza kolejny uczeń. Staje on albo po prawej, albo po lewej stronie już ćwiczących. Po tym ćwiczenie jest wykonywane ponownie na tym samym poziomie trudności.

Dla początkowego zestawu uczestników oraz po dodaniu każdego nowego ucznia należy wyznaczyć maksymalną liczbę rzutów, jaką mogą wykonać uczestnicy treningu.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 2$) — poziom trudności ćwiczenia.

Drugi wiersz zawiera dwie liczby całkowite $n$ i $q$ ($1 \leq n \leq 10^{5}$, $0 \leq q \leq 2 \cdot 10^{5}$) — początkową liczbę uczestników oraz liczbę uczestników, którzy dołączą.

Trzeci wiersz zawiera $n$ liczb całkowitych $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \leq a_{i} \leq n + q$) — numery uczestników początkowo stojących w rzędzie od lewej do prawej. Gwarantuje się, że wszystkie liczby są różne.

Kolejne $q$ wierszy zawiera numery uczestników dołączających do ćwiczenia. Każdy wiersz zawiera znak 'L' lub 'R' oraz liczbę całkowitą $x$ oddzielone spacją ($1\le x\le n + q$). Litera 'L' oznacza, że uczeń o numerze $x$ staje po lewej stronie rzędu, a 'R' – po prawej.

Gwarantuje się, że po każdym dodaniu wszystkie numery uczestników są różne.

Wyjście

W pierwszym wierszu wypisz jedną liczbę — odpowiedź do zadania dla początkowych $n$ uczestników i poziomu trudności $t$.

W kolejnych $q$ wierszach wypisz po jednej liczbie całkowitej — odpowiedź do zadania po dodaniu każdego z $q$ uczestników i wykonaniu ćwiczenia na tym samym poziomie trudności.

Przykład

Wejście 1

1
3 2
6 3 2
L 8
R 4

Wyjście 1

2
2
3

Wejście 2

2
3 2
6 3 2
L 8
R 4

Wyjście 2

2
2
4

Uwagi

W pierwszym przykładzie optymalne jest rozpoczęcie ćwiczenia, na przykład, od uczestnika o numerze 5. Pierwszy rzut może być do uczestnika o numerze 3, drugi do uczestnika o numerze 2, a trzeci do uczestnika o numerze 1. Dodanie uczestnika 8 po lewej stronie nie zwiększa maksymalnej liczby rzutów. Dodanie uczestnika 4 po prawej stronie pozwala, zaczynając od uczestnika o numerze 7, kolejno rzucać piłkę do uczestników o numerach 6, 4, 3, 2 i 1.

W drugim przykładzie można również rozpocząć od uczestnika o numerze 5 i uzyskać cztery poprawne rzuty do uczestników o numerach 3, 2, 7 i 6. Dodanie uczestnika 8 po lewej stronie nie zmienia maksymalnej liczby rzutów, a dodanie uczestnika 4 po prawej stronie pozwala, zaczynając na przykład od numeru 7, kolejno rzucać piłkę do uczestników o numerach 6, 4, 5, 3, 2 i 1.

Podzadania