Một nhóm học sinh đang nghiên cứu để chế tạo và lập trình một con robot. Các bạn đã tạo ra một sa bàn là một bảng hình chữ nhật kích thước \(N \times M\), với hàng được đánh số từ \(1\) đến \(N\) từ trên xuống dưới và cột được đánh số từ \(1\) đến \(M\) từ trái sang phải. Ô nằm ở vị trí giao của hàng \(X\) và cột \(Y\) gọi là ô \((X, Y)\). Ban đầu, robot được đặt ở góc trái trên của bảng, tức ô \((1, 1)\). Trên bảng, các bạn đã đặt \(K\) vật cản, vật cản thứ \(i\) được đặt ở ô \((X_i, Y_i)\).

Robot có thể được điều khiển bằng một chuỗi gồm \(Q\) lệnh. Lệnh thứ \(i\) trong các lệnh này sẽ yêu cầu robot đi theo hướng \(D_i\) (lên, xuống, sang trái, sang phải) \(C_i\) ô. Tuy nhiên, nếu thấy trước mặt là vật cản hoặc rìa của sa bàn, robot sẽ dừng lại và chuyển sang thực hiện lệnh tiếp theo trong chuỗi.

Các bạn học sinh đang lập trình để robot đánh dấu và tự đếm số lượng ô trên sa bàn mà nó đã đi qua ít nhất một lần. Tuy nhiên, các bạn không chắc chắn rằng mình đã lập trình đúng hay không. Do đó, các bạn cho bạn biết các thông tin về sa bàn, các vật cản và chuỗi lệnh mà robot cần thực thi, sau đó nhờ bạn tính toán chính xác số ô mà robot đã đi qua ít nhất một lần (tính cả ô xuất phát). Bạn hãy giúp nhóm học sinh thực hiện yêu cầu này nhé.

Input

• Dòng đầu tiên gồm bốn số nguyên \(N, M, K, Q\) (\(1 \le N, M \le 10^7\), \(N \times M \le 10^7\), \(0 \le K \le 3 \times 10^5\), \(1 \le Q \le 3 \times 10^5\)).
• \(K\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên dương \(X_i, Y_i\) (\(1 \le X_i \le N, 1 \le Y_i \le M\)). Dữ liệu đầu vào đảm bảo vị trí tất cả các vật cản đôi một phân biệt và ô \((1, 1)\) không có vật cản.
• \(Q\) dòng tiếp theo, dòng thứ \(i\) gồm một ký tự \(D_i\) và một số nguyên dương \(C_i\) (\(D_i \in \{L, R, U, D\}\), \(1 \le C_i \le 10^7\)):
  • Nếu \(D_i = U\), robot sẽ di chuyển lên trên.
  • Nếu \(D_i = D\), robot sẽ di chuyển xuống dưới.
  • Nếu \(D_i = L\), robot sẽ di chuyển sang trái.
  • Nếu \(D_i = R\), robot sẽ di chuyển sang phải.

Output

• Một số nguyên duy nhất là số ô mà robot đã đi qua ít nhất một lần.

Example

3 3 2 5
1 3
3 2
R 2
D 3
L 1
D 2
U 2

5

Scoring

• \(30\%\) số điểm có \(N = 1\).
• \(30\%\) số điểm khác có \(N, M \le 200\).
• \(20\%\) số điểm khác có \(N, M \le 3000\).
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.