Một số học sinh đang tham gia một câu lạc bộ thể thao. Khi bắt đầu buổi tập, có $n$ người trong phòng gym, sau đó lần lượt $q$ người khác tham gia trong suốt buổi tập. Chiều cao của tất cả $n+q$ học sinh là khác nhau; hãy đánh số các học sinh từ $1$ đến $n+q$ theo thứ tự tăng dần chiều cao.

Trong buổi tập, các học sinh thực hiện các bài tập với một quả bóng. Các học sinh xếp thành một hàng ngang từ trái sang phải theo một thứ tự nào đó. Tùy vào thứ tự xếp hàng, một số cặp học sinh tạo thành cặp hợp lệ.

Một cặp học sinh đứng ở vị trí $i$ và $j$, với $i < j$, tạo thành một cặp hợp lệ nếu một trong hai điều kiện sau được thỏa mãn:

• học sinh ở vị trí $i$ là học sinh ngoài cùng bên trái trong số những học sinh thấp hơn học sinh ở vị trí $j$ và đứng bên trái của họ;
• học sinh ở vị trí $j$ là học sinh ngoài cùng bên phải trong số những học sinh thấp hơn học sinh ở vị trí $i$ và đứng bên phải của họ.

Ví dụ, nếu các học sinh với số $[6, 7, 3, 5, 1, 2]$ đang đứng thành một hàng, các cặp hợp lệ là $(6, 2)$, $(6, 7)$, $(7, 2)$, $(3, 2)$, $(3, 5)$, $(5, 2)$ và $(1, 2)$.

Bài tập có hai mức độ khó, mỗi mức có các cú ném hợp lệ riêng. Khi thực hiện bài tập ở bất kỳ mức độ khó nào, không được phép ném bóng cho một học sinh đã từng cầm bóng trong cùng một lượt tập.

Ở mức độ khó thứ nhất, một học sinh có thể ném bóng cho bất kỳ học sinh nào mà họ tạo thành cặp hợp lệ và thấp hơn họ. Ví dụ, nếu các học sinh với số $[6, 7, 3, 5, 1, 2]$ đang đứng thành một hàng, học sinh số $3$ chỉ có thể ném bóng cho học sinh số $2$, học sinh số $5$ có thể ném cho học sinh số $3$ và $2$, còn học sinh số $1$ không thể ném cho ai.

Ở mức độ khó thứ hai, một học sinh có thể ném bóng cho bất kỳ học sinh nào mà họ tạo thành cặp hợp lệ. Ví dụ, nếu các học sinh với số $[6, 7, 3, 5, 1, 2]$ đang đứng thành một hàng, học sinh số $3$ có thể ném bóng cho học sinh số $2$ và $5$, học sinh số $5$ có thể ném cho học sinh số $3$ và $2$, còn học sinh số $1$ có thể ném bóng cho học sinh số $2$.

Bài tập được thực hiện như sau. Huấn luyện viên chọn mức độ khó $t$. Một trong các học sinh nhận bóng và thực hiện một cú ném hợp lệ. Học sinh nhận bóng sau đó thực hiện một cú ném hợp lệ, và cứ thế tiếp tục. Các cú ném được thực hiện chừng nào còn có thể. Nếu có nhiều cú ném hợp lệ, có thể chọn bất kỳ cái nào, nhưng không được phép ném bóng cho một học sinh đã từng cầm bóng trong cùng một lượt tập. Những người tham gia buổi tập thực hiện các cú ném hợp lệ cho mức độ khó đã chọn theo cách tạo ra số lần ném tối đa.

Sau đó, $q$ lần, một học sinh nữa tham gia buổi tập. Họ đứng về phía bên phải hoặc bên trái của những người đang thực hiện bài tập. Sau đó, bài tập được thực hiện lại ở cùng mức độ khó.

Với tập hợp ban đầu của những người tham gia và sau mỗi lần thêm một học sinh mới, cần xác định số lần ném tối đa mà những người tham gia buổi tập có thể thực hiện.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 2$) — mức độ khó của bài tập.

Dòng thứ hai chứa hai số nguyên $n$ và $q$ ($1 \leq n \leq 10^{5}$, $0 \leq q \leq 2 \cdot 10^{5}$) — số lượng người tham gia ban đầu và số lượng người tham gia sẽ thêm vào.

Dòng thứ ba chứa $n$ số nguyên $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \leq a_{i} \leq n + q$) — số hiệu của những người tham gia ban đầu đang đứng trong hàng từ trái sang phải. Dữ liệu đảm bảo tất cả các số đều phân biệt.

$q$ dòng tiếp theo chứa số hiệu của những người tham gia thêm vào bài tập. Mỗi dòng chứa một ký tự 'L' hoặc 'R' và một số nguyên $x$ cách nhau bởi dấu cách ($1\le x\le n + q$). Ký tự 'L' có nghĩa là học sinh có số $x$ đứng ở bên trái của hàng, 'R' có nghĩa là đứng ở bên phải.

Dữ liệu đảm bảo rằng sau mỗi lần thêm, tất cả các số hiệu người tham gia đều phân biệt.

Dữ liệu ra

Dòng đầu tiên, in ra một số duy nhất — câu trả lời cho bài toán với $n$ người tham gia ban đầu và mức độ khó $t$.

Trong $q$ dòng tiếp theo, in ra một số nguyên mỗi dòng — câu trả lời cho bài toán sau khi thêm mỗi người trong số $q$ người tham gia và thực hiện bài tập ở cùng mức độ khó.

Ví dụ

Dữ liệu vào 1

1
3 2
6 3 2
L 8
R 4

Dữ liệu ra 1

2
2
3

Dữ liệu vào 2

2
3 2
6 3 2
L 8
R 4

Dữ liệu ra 2

2
2
4

Ghi chú

Trong ví dụ đầu tiên, tối ưu là bắt đầu bài tập, ví dụ, với người tham gia số 5. Cú ném đầu tiên có thể đến người tham gia số 3, cú ném thứ hai đến người tham gia số 2, và cú ném thứ ba đến người tham gia số 1. Thêm người tham gia số 8 vào bên trái không làm tăng số lần ném tối đa. Thêm người tham gia số 4 vào bên phải cho phép, bắt đầu từ người tham gia số 7, ném bóng lần lượt đến người tham gia số 6, 4, 3, 2 và 1.

Trong ví dụ thứ hai, cũng có thể bắt đầu với người tham gia số 5 và có bốn cú ném hợp lệ đến người tham gia số 3, 2, 7 và 6. Thêm người tham gia số 8 vào bên trái không làm thay đổi số lần ném tối đa, và thêm người tham gia số 4 vào bên phải cho phép, bắt đầu từ, ví dụ, số 7, ném bóng lần lượt đến người tham gia số 6, 4, 5, 3, 2 và 1.

Nhiệm vụ con