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ỗi 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.

Input

Dữ liệu vào từ file văn bản LNDASH.INP gồm:

• Dòng đầu ghi ba số \(N\), \(T\) và \(Q\) (\(N \leq 10^6\); \(T \leq 10^9\));
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(T_i\) (\(0 \leq T_i \leq T\)) và một kí tự \(C_i\) (là một trong ba kí tự /, -, \). Với điều kiện \(T_1 < T_2 < \ldots < T_N\);
• \(Q\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(L_i\), \(R_i\) (\(0 \leq L_i \leq R_i \leq T\)).

Output

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.

Example

3 5 2
1 /
3 -
4 \
1 5
2 4

5.242641
2.414214

Scoring

• \(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 \leq 1000\);
• \(30\%\) số điểm bài thi: \(T \leq 10^6\);
• \(10\%\) số điểm bài thi: không có ràng buộc gì thêm.