Đẩy Robot

View as PDF

Submit solution


Points: 2000 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type

n ô vuông được đánh số từ 1 đến n từ trái sang phải. Ô vuông thứ i được đánh dấu bởi kí tự s_{i}. Ban đầu tất cả các ô vuông mỗi ô vuông đều có một con robot.

_minhduc có thể đẩy các con robot ấy q lần.

Lần đẩy thứ i sẽ có hai kí tự lần lượt là t_{i}d_{i}, trong đó d_{i}L hoặc R. Khi _minhduc đẩy robot, tất cả các con robot có đứng ở ô vuông có kí tự t_{i} sẽ bị đẩy sang trái nếu d_{i}L, sẽ bị đẩy sang phải nếu d_{i}R.

Tuy nhiên khi _minhduc đẩy các con robot đang đứng ở ô vuông thứ 1 sang trái hoặc đẩy các con robot đang đứng ở ô vuông thứ n sang phải thì các con robot đó đột nhiên biến mất.

Yêu Cầu: Bạn hãy đếm số con robot chưa bị biến mất sau khi _minhduc đẩy các con robot ấy q lần.

Input

  • Dòng đầu tiên chứa hai số nguyên dương nq (1 \leq n, q \leq 2 \times 10^{5}).
  • Dòng tiếp theo chứa chuỗi s (độ dài của xâu không quá n và chỉ chứa chữ cái tiếng Anh in hoa).
  • Dòng tiếp theo chứa hai giá trị là t_{i}d_{i} (1 \leq i \leq q), mỗi bộ đôi giá trị cách nhau một dòng.
  • t_{i} chỉ chứa chữ cái tiếng Anh in hoa và d_{i} chỉ tồn tại hai giá trị là L hoặc R.

Output

  • In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

  • Subtask 1 (50\% số điểm): Có n, q \leq 100.
  • Subtask 2 (50\% số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
3 4
ABC
A L
B L
B R
A R
Output
2
Note
  • Ban đầu tất cả các con robot hiện còn đang ở mỗi ô vuông.
  • Lần đẩy đầu tiên, con đứng ở ô vuông đầu tiên bị biến mất.
  • Lần đẩy thứ hai, con đứng ở ô vuông thứ hai bị đẩy sang bên trái và đứng ở ô vuông đầu tiên.
  • Lần đẩy thứ ba, không con nào bị đẩy.
  • Lần đẩy cuối cùng, con đứng ở ô vuông đầu tiên bị đẩy sang bên phải.
    Như vậy còn 2 con chưa bị biến mất.

Comments


  • 3
    161007thanhhiu 8:48 p.m. 25 sep, 2023

    tại s test bày lại ra 3 vậy
    10 15
    SNCZWRCEWB
    B R
    R R
    E R
    W R
    Z L
    S R
    Q L
    W L
    B R
    C L
    A L
    N L
    E R
    Z L
    S L

    1 reply