여러 학생이 스포츠 클럽에 참여하고 있습니다. 훈련 시작 시 체육관에는 $n$명이 있으며, 이후 세션 중에 $q$명이 한 명씩 추가로 합류합니다. $n+q$명의 학생들의 키는 모두 다릅니다. 키가 작은 순서대로 학생들에게 $1$부터 $n+q$까지 번호를 붙입니다.

훈련 중 학생들은 공을 사용하여 운동을 수행합니다. 학생들은 어떤 순서로든 왼쪽에서 오른쪽으로 일렬로 줄을 섭니다. 줄을 선 순서에 따라 일부 학생 쌍이 유효한 쌍을 이룹니다.

위치 $i$와 $j$에 서 있는 학생 쌍($i < j$)은 다음 두 조건 중 하나를 만족하면 유효한 쌍을 이룹니다.

• 위치 $i$에 있는 학생이 위치 $j$에 있는 학생보다 키가 작으면서 왼쪽에 있는 학생들 중 가장 왼쪽에 있는 학생인 경우;
• 위치 $j$에 있는 학생이 위치 $i$에 있는 학생보다 키가 작으면서 오른쪽에 있는 학생들 중 가장 오른쪽에 있는 학생인 경우.

예를 들어, 번호가 $[6, 7, 3, 5, 1, 2]$인 학생들이 줄을 서 있다면, 유효한 쌍은 $(6, 2)$, $(6, 7)$, $(7, 2)$, $(3, 2)$, $(3, 5)$, $(5, 2)$, $(1, 2)$입니다.

운동에는 두 가지 난이도가 있으며, 각 난이도에는 고유한 유효한 던지기가 있습니다. 어떤 난이도로 운동을 수행할 때, 현재 운동 중에 이미 공을 잡은 학생에게 공을 던지는 것은 금지됩니다.

첫 번째 난이도에서는, 학생이 자신과 유효한 쌍을 이루면서 자신보다 키가 작은 학생에게만 공을 던질 수 있습니다. 예를 들어, 번호가 $[6, 7, 3, 5, 1, 2]$인 학생들이 줄을 서 있다면, 번호 $3$인 학생은 번호 $2$인 학생에게만 공을 던질 수 있고, 번호 $5$인 학생은 번호 $3$과 $2$인 학생에게 던질 수 있으며, 번호 $1$인 학생은 아무에게도 공을 던질 수 없습니다.

두 번째 난이도에서는, 학생이 자신과 유효한 쌍을 이루는 모든 학생에게 공을 던질 수 있습니다. 예를 들어, 번호가 $[6, 7, 3, 5, 1, 2]$인 학생들이 줄을 서 있다면, 번호 $3$인 학생은 번호 $2$와 $5$인 학생에게 공을 던질 수 있고, 번호 $5$인 학생은 번호 $3$과 $2$인 학생에게 던질 수 있으며, 번호 $1$인 학생은 번호 $2$인 학생에게 공을 던질 수 있습니다.

운동은 다음과 같이 진행됩니다. 코치가 난이도 $t$를 선택합니다. 한 학생이 공을 잡고 유효한 던지기를 합니다. 공을 받은 학생이 다시 유효한 던지기를 하고, 이런 식으로 계속됩니다. 던지기는 더 이상 할 수 없을 때까지 수행됩니다. 유효한 던지기가 여러 개 있으면 그중 아무거나 선택할 수 있지만, 현재 운동 중에 이미 공을 잡은 학생에게 공을 던지는 것은 금지됩니다. 훈련 참가자들은 선택된 난이도에 대해 최대한 많은 던지기를 할 수 있도록 유효한 던지기를 수행합니다.

그런 다음 $q$번에 걸쳐 한 명의 학생이 추가로 훈련에 합류합니다. 그들은 이미 운동을 수행하고 있는 학생들의 오른쪽이나 왼쪽에 섭니다. 그 후 같은 난이도로 다시 운동을 수행합니다.

초기 참가자 집합과 각 새 학생이 추가된 후에 대해, 훈련 참가자들이 할 수 있는 최대 던지기 횟수를 구해야 합니다.

입력

첫 번째 줄에는 정수 $t$ ($1 \le t \le 2$)가 주어집니다. 이는 운동의 난이도입니다.

두 번째 줄에는 두 정수 $n$과 $q$ ($1 \leq n \leq 10^{5}$, $0 \leq q \leq 2 \cdot 10^{5}$)가 주어집니다. 이는 초기 참가자 수와 추가로 합류할 참가자 수입니다.

세 번째 줄에는 $n$개의 정수 $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \leq a_{i} \leq n + q$)가 주어집니다. 이는 왼쪽부터 오른쪽 순서로 처음에 줄을 서 있는 참가자들의 번호입니다. 모든 번호는 서로 다릅니다.

다음 $q$개 줄에는 운동에 합류하는 참가자의 정보가 주어집니다. 각 줄에는 문자 'L' 또는 'R'과 정수 $x$가 공백으로 구분되어 주어집니다 ($1\le x\le n + q$). 문자 'L'은 번호 $x$인 학생이 줄의 왼쪽에 서는 것을 의미하고, 'R'은 오른쪽에 서는 것을 의미합니다.

각 추가 이후 모든 참가자 번호는 서로 다릅니다.

출력

첫 번째 줄에는 초기 $n$명의 참가자와 운동 난이도 $t$에 대한 문제의 답을 출력합니다.

다음 $q$개 줄에는 $q$명의 참가자가 각각 추가된 후 같은 난이도로 운동을 수행했을 때의 답을 한 줄에 하나씩 출력합니다.

예제

입력 1

1
3 2
6 3 2
L 8
R 4

출력 1

2
2
3

입력 2

2
3 2
6 3 2
L 8
R 4

출력 2

2
2
4

참고

첫 번째 예제에서는, 예를 들어 번호 5인 참가자로 운동을 시작하는 것이 최적입니다. 첫 번째 던지기는 번호 3인 참가자에게, 두 번째는 번호 2인 참가자에게, 세 번째는 번호 1인 참가자에게 할 수 있습니다. 왼쪽에 참가자 8을 추가해도 최대 던지기 횟수는 증가하지 않습니다. 오른쪽에 참가자 4를 추가하면, 번호 7인 참가자부터 시작하여 순서대로 번호 6, 4, 3, 2, 1인 참가자에게 공을 던질 수 있습니다.

두 번째 예제에서도, 번호 5인 참가자로 시작하여 번호 3, 2, 7, 6인 참가자에게 네 번의 유효한 던지기를 할 수 있습니다. 왼쪽에 참가자 8을 추가해도 최대 던지기 횟수는 변하지 않으며, 오른쪽에 참가자 4를 추가하면, 예를 들어 번호 7부터 시작하여 순서대로 번호 6, 4, 5, 3, 2, 1인 참가자에게 공을 던질 수 있습니다.

서브태스크