Monkeyland là một trục số vô hạn với $n$ chú khỉ, được đánh số từ 1 đến $n$. Chú khỉ thứ $i$ ban đầu ở vị trí $p[i]$ trên trục số. Nhiều chú khỉ có thể cùng ở một vị trí ban đầu.
Pan có thể khiến mọi chú khỉ di chuyển bằng phép thuật đầy mê hoặc của mình! Cách mỗi chú khỉ di chuyển được xác định bởi một xâu $d$ có độ dài $n$, trong đó mỗi ký tự là L hoặc R. Gọi ký tự thứ $i$ của $d$ là $d[i]$.
Sau khi phép thuật được thi triển, chú khỉ thứ $i$ di chuyển như sau: Nếu $d[i] = \text{L}$, nó di chuyển sang trái một đơn vị. Nếu $d[i] = \text{R}$, nó di chuyển sang phải một đơn vị.
Mỗi ngày, Pan sẽ thi triển phép thuật đúng một lần. Nếu hai chú khỉ ở cùng một vị trí vào bất kỳ ngày nào (kể cả ngày đầu tiên), chúng sẽ trở thành bạn của nhau. Nếu Pan thi triển phép thuật trong $k$ ngày, hãy xác định số cặp khỉ sẽ trở thành bạn của nhau.
Dữ liệu vào
Chương trình của bạn phải đọc từ thiết bị nhập chuẩn. Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $k$ cách nhau bởi dấu cách. Dòng thứ hai của dữ liệu vào chứa $n$ số nguyên $p[1], p[2], \dots, p[n]$ cách nhau bởi dấu cách. Dòng thứ ba của dữ liệu vào chứa một xâu $d$ gồm $n$ ký tự $d[1], d[2], \dots, d[n]$.
Dữ liệu ra
Chương trình của bạn phải in ra thiết bị xuất chuẩn.
In ra một số nguyên duy nhất là số cặp khỉ sẽ trở thành bạn của nhau.
Dữ liệu ra chỉ nên chứa một số nguyên duy nhất. Không in thêm bất kỳ văn bản bổ sung nào như Enter a number hoặc The answer is.
Giới hạn
Với tất cả các trường hợp kiểm thử, dữ liệu vào sẽ thỏa mãn các giới hạn sau: $1 \le n \le 200\,000$ $1 \le k \le 10^9$ $1 \le p[i] \le 10^9$ với mọi $1 \le i \le n$ $d[i]$ là L hoặc R với mọi $1 \le i \le n$
Chương trình của bạn sẽ được kiểm thử trên các bộ dữ liệu thỏa mãn các hạn chế sau:
| Nhiệm vụ con | Điểm | Các hạn chế bổ sung |
|---|---|---|
| 0 | 0 | Các bộ kiểm thử mẫu |
| 1 | 6 | $n = 2$ |
| 2 | 13 | $d[1] = d[2] = \dots = d[n]$ |
| 3 | 10 | $n, k \le 200$ |
| 4 | 22 | $n, k \le 3000$ |
| 5 | 18 | $n \le 3000$ |
| 6 | 31 | Không có hạn chế bổ sung |
Ví dụ
Dữ liệu vào 1
2 1 1 3 RL
Dữ liệu ra 1
1
Giải thích mẫu 1
Có $n = 2$ chú khỉ và Pan thi triển phép thuật trong $k = 1$ ngày. Vào ngày đầu tiên, khỉ 1 di chuyển sang phải từ vị trí 1 đến vị trí 2, trong khi khỉ 2 di chuyển sang trái từ vị trí 3 đến vị trí 2. Vì chúng kết thúc ở cùng một vị trí vào ngày đầu tiên, chúng trở thành bạn của nhau. Do đó, có đúng 1 cặp khỉ trở thành bạn.
Dữ liệu vào 2
5 67 1 2 3 4 5 RRRRR
Dữ liệu ra 2
0
Giải thích mẫu 2
Có $n = 5$ chú khỉ và Pan thi triển phép thuật trong $k = 67$ ngày liên tiếp. Vì tất cả các chú khỉ đều có vị trí ban đầu khác nhau và mỗi chú khỉ di chuyển một đơn vị sang phải mỗi ngày khi phép thuật được thi triển, không có hai chú khỉ nào ở cùng một vị trí vào bất kỳ ngày nào. Do đó, không có cặp khỉ nào trở thành bạn.
Dữ liệu vào 3
6 7 1 1 8 16 18 22 RRLRLL
Dữ liệu ra 3
3
Dữ liệu vào 4
10 30 9 46 27 8 12 100 56 96 6 7 LRLRRLRRLR
Dữ liệu ra 4
5
Dữ liệu vào 5
4 2 3 4 4 6 LLRL
Dữ liệu ra 5
2
Giải thích mẫu 5
Có $n = 4$ chú khỉ và Pan thi triển phép thuật trong $k = 2$ ngày liên tiếp. Mỗi hình dưới đây mô tả Monkeyland như một trục số chỉ hiển thị các vị trí từ 1 đến 6. Mũi tên phía trên mỗi chú khỉ chỉ hướng mà nó sẽ di chuyển sau khi phép thuật được thi triển.
Vào ngày thứ 0, vị trí ban đầu của tất cả các chú khỉ được hiển thị trong hình dưới đây. Khỉ 2 và 3 vốn đã ở vị trí 4 trở thành bạn của nhau.
Sau khi phép thuật được thi triển vào ngày thứ 1, vị trí của tất cả các chú khỉ được hiển thị trong hình dưới đây. Khỉ 3 và 4 gặp nhau tại vị trí 5 và trở thành bạn của nhau.
Sau khi phép thuật được thi triển vào ngày thứ 2, vị trí của tất cả các chú khỉ được hiển thị trong hình dưới đây. Không có hai chú khỉ nào gặp nhau vào ngày này.
Do đó, có tổng cộng 2 cặp khỉ là bạn của nhau: Khỉ 2 và 3, cũng như khỉ 3 và 4.