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² 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.

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 tất cả các ô mà robot đi qua (nếu một ô đi qua nhiều lần thì số trong ô này luôn được cộng thêm vào tổng).

Dữ liệu: Vào từ 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.

Kết quả:

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 64 bít.