Trò chơi LineDash

Trong trò chơi LineDash có một nhân vật trên mặt phẳng tọa độ $Oxy$. Có 3 cách điều khiển nhân vật dựa trên 3 loại kí tự /, –, \ với ý nghĩa:

• Loại / : Nếu nhân vật đang ở tọa độ $(x, y)$ thì sau khi nhận lệnh này nhân vật sẽ di chuyển đến $(x+1, y+1)$;
• Loại – : Nếu nhân vật đang ở tọa độ $(x, y)$ thì sau khi nhận lệnh này nhân vật sẽ di chuyển đến $(x+1, y)$;
• Loại \ : Nếu nhân vật đang ở tọa độ $(x, y)$ thì sau khi nhận lệnh này nhân vật sẽ di chuyển đến $(x+1, y-1)$.

Ban đầu nhân vật xuất phát ở $(0, 0)$ và di chuyển theo chiều ngang nếu không nhận được lệnh. Tại một số thời điểm, người chơi sẽ ra lệnh đổi hướng và nhân vật sẽ di chuyển về hướng đó cho đến khi nhận được lệnh mới. Điểm sẽ tích lũy theo quãng đường đi được. Có $N$ lần nhận lệnh, lần thứ $i$ nhân vật nhận lệnh $C_i$ tại thời điểm $T_i$. Mỗi khi nhận một lệnh, nhân vật sẽ di chuyển theo lộ trình của lệnh đó cho đến khi nhận lệnh kế tiếp. Biết rằng nhân vật di chuyển trong $T$ giây và thời gian thực hiện một lệnh là $1$ giây.

Yêu cầu: Cho danh sách các lệnh điều khiển và một số câu hỏi, mỗi câu hỏi là một khoảng thời gian $[L, R]$. Hãy cho biết từ thời gian $L$ đến thời gian $R$ nhân vật đi được quãng đường là bao nhiêu.

Vào từ file văn bản LNDASH.INP gồm:

• Dòng đầu ghi ba số $N$, $T$ và $Q$ $(N, Q \le 10^5;\ T \le 10^9)$;
• $N$ dòng tiếp theo, mỗi dòng chứa một số nguyên $T_i$ $(0 \le T_i \le T)$ và một kí tự $C_i$ (là một trong ba kí tự /, –, \). Cho biết $T_1 < T_2 < \dots < T_n$;
• $Q$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $L_i, R_i$ $(0 \le L_i \le R_i \le T)$.

Ghi ra file văn bản LNDASH.OUT gồm $Q$ dòng, dòng thứ $i$ chứa kết quả của truy vấn thứ $i$ sau khi làm tròn đến 6 chữ số sau dấu phẩy thập phân.

• 20% số điểm bài thi: $N = 0$;
• 20% số điểm bài thi: $N = 1$ và không có lệnh -;
• 20% số điểm bài thi: $N, T, Q \le 1000$;
• 30% số điểm bài thi: $T \le 10^6$;
• 10% số điểm bài thi: không có ràng buộc nào thêm.