토끼의 이동

1부터 N^2까지의 수가 N×N 행렬에 지그재그 대각선 순서로 채워져 있다. 다음 표는 N=6일 때의 행렬이다.

토끼는 처음에 숫자 1이 적힌 칸, 즉 왼쪽 위 칸에 있다. 한 번의 점프로 위, 아래, 왼쪽, 오른쪽으로 인접한 칸에 이동할 수 있다.

토끼가 점프한 방향이 주어졌을 때, 시작 칸을 포함해 토끼가 방문한 모든 칸에 적힌 수의 합을 구하라. 같은 칸을 여러 번 방문하면 방문할 때마다 그 칸의 수를 더한다. 주어진 이동은 항상 행렬 밖으로 나가지 않는다.

첫째 줄에 행렬의 크기 N과 점프 횟수 K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ 300,000)

둘째 줄에 길이가 K인 문자열이 주어진다. 각 문자는 U, D, L, R 중 하나이며, 각각 위, 아래, 왼쪽, 오른쪽으로 한 칸 이동함을 뜻한다.

시작 칸을 포함해 토끼가 방문한 칸에 적힌 수의 합을 출력한다. 이 값은 32비트 정수 범위를 넘을 수 있다.