Một ma trận vuông kích thước N x N được điền đầy bởi các số nguyên từ 1 đến ~N^2~ theo đường zig-zag. Ví dụ, với N=6 ta có ma trận dưới đây:

Có một robot đứng tại ô chứa số 1. Robot này có thể chuyển động theo 4 hướng (trên, dưới, trái, phải) đến ô khác chung cạnh nếu như ô này tồn tại.

Yêu cầu:

Cho dãy K lần chuyển động của robot. Viết chương trình xác định tổng của các số trong các ô mà robot đi qua (nếu một ô đi qua nhiều lần thì số trong ô này được cộng nhiều lần vào tổng)

Dữ liệu: File MATRIX.INP

• Dòng đầu tiên chứa hai số ngyên dương N và K (1≤N≤100000, 1≤K≤ 300000) lần lượt là kích thước của ma trận và số bước chuyển động của robot.

• Dòng thứ hai là dãy K ký tự 'U', 'D','L',R' mô tả các bước chuyển động ('U' - lên trên, 'D' - xuống dưới,'L' -sang trái,'R'-sang phải). Biết rằng với các hướng chuyển động này, robot không ra khỏi ma trận tại bất kỳ một bước nào.

Dữ liệu: File MATRIX.OUT

Một số nguyên dương là tổng các số trong các ô mà robot đi qua. Kết quả đảm bảo luôn là số nguyên 32 bit.

Sample Input 1

6 8
DDRRUULL

Sample Output 1

47

Sample Input 2

3 8
DDRRUULL

Sample Output 2

41

Sample Input 3

6 10
RRRRRDDDDD

Sample Output 3

203

Với sự chăm chỉ, những con kiến đã xây dựng được một thị trấn được gọi là thị trấn kiến. Thị trấn này xây dựng giống như một ma trận với H đường phố ngang và V đường phố dọc tạo thành VxH điểm giao cắt. Tất nhiên, loài kiến rất ghét nước nên mỗi khi có mưa thì thị trấn kiến trở nên hỗn loạn. Chính quyền thị trấn phải đặt một số cái dù ở một số điểm giao cắt để các con kiến trú ẩn. Tuy vậy chỉ có N điểm giao cắt được trang bị dù.

Khi bắt đầu mưa, tất cả các con kiến ở các ngã tư khác nhau bắt đầu chạy dọc theo các đường phố đến ngã tư gần nó nhất mà có dù. Tuy nhiên có một vài điểm giao cắt có nhiều hơn một điểm giao cắt có dù gần nó nhất. Những con kiến ở các giao cắt này sẽ không biết được cần phải chạy tới đâu do vậy chúng sẽ đứng yên và chịu ướt. Các điểm giao cắt như vậy được gọi là các điểm ướt.

Ví dụ, nếu thị trấn kiến có 10 đường phố ngang và 10 đường phố dọc, có 4 điểm giao cắt có ô thì các điểm có dấu '?' là các điểm ướt (hình dưới):

Yêu cầu:

Viết chương trình xác định số lượng các điểm ướt ở thị trấn kiến.

Dữ liệu: File MARVO.INP

• Dòng đầu tiên ghi hai số nguyên H và V là số lượng đường phố ngang và dọc của thị trấn kiến (1 ≤ 𝐻, 𝑉 ≤ 30000). Các đường phố ngang đánh số từ 1 đến H, các đường phố dọc đánh số từ 1 đến V.

• Dòng thứ hai chứa số nguyên N (1≤N≤10) là số lượng các điểm giao cắt có dù.

• N dòng tiếp theo, mỗi dòng ghi hai số nguyên h và v với ý nghĩa là tại điểm giao cắt hàng h với cột v có một cái ô

Dữ liệu: File MARVO.OUT

Một số nguyên duy nhất là số lượng các điểm ướt ở thị trấn kiến

Sample Input

10 10
4
4 4
4 6
6 4
9 9

Sample Output

19