시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 360 97 75 28.846%

문제

1부터 N2까지 수가 지그재그 대각선 순서로 N*N 행렬에 채워져 있다. 아래 그림은 N=6일 때, 행렬의 모습이다.

1 2 6 7 15 16
3 5 8 14 17 26
4 9 13 18 25 27
10 12 19 24 28 33
11 20 23 29 32 34
21 22 30 31 35 36

토끼는 지금 1이 있는 칸에 있다. 토끼는 인접한 칸으로 점프할 수 있다. (위, 아래, 오른쪽, 왼쪽)

토끼가 점프한 방법이 주어졌을 때, 토끼가 방문한 칸에 있는 수의 합을 구하는 프로그램을 작성하시오. 같은 칸을 여러 번 방문할 경우에도, 방문할 때 마다 더해야 한다. 토끼가 행렬을 벗어나는 경우는 없다.

입력

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

둘째 줄에는 'U','D','L','R'로 이루어진 문자열이 주어진다. 이 문자열의 길이는 K이며, 토끼가 점프한 방향이다.

출력

첫째 줄에, 방문한 칸의 수의 합을 출력한다. 이 값은 32비트 정수를 넘을 수도 있다.

예제 입력 1

6 8
DDRRUULL

예제 출력 1

47
W3sicHJvYmxlbV9pZCI6IjMxMDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxYTBcdWIwN2NcdWM3NTggXHVjNzc0XHViM2Q5IiwiZGVzY3JpcHRpb24iOiI8cD4xXHViZDgwXHVkMTMwIE48c3VwPjI8XC9zdXA+XHVhZTRjXHVjOWMwIFx1YzIxOFx1YWMwMCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHViMzAwXHVhYzAxXHVjMTIwIFx1YzIxY1x1YzExY1x1Yjg1YyBOKk4gXHVkNTg5XHViODJjXHVjNWQwIFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgTj02XHVjNzdjIFx1YjU0YywgXHVkNTg5XHViODJjXHVjNzU4IFx1YmFhOFx1YzJiNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjE4JTtcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlOyB0ZXh0LWFsaWduOmNlbnRlcjtcIj4xPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlOyB0ZXh0LWFsaWduOmNlbnRlcjtcIj4yPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlOyB0ZXh0LWFsaWduOmNlbnRlcjtcIj42PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlOyB0ZXh0LWFsaWduOmNlbnRlcjtcIj43PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlOyB0ZXh0LWFsaWduOmNlbnRlcjtcIj4xNTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDozJTsgdGV4dC1hbGlnbjpjZW50ZXI7XCI+MTY8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4zPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjU8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+ODxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4xNDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4xNzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4yNjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjQ8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+OTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4xMzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4xODxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4yNTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4yNzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjEwPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjEyPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjE5PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjI0PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjI4PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjMzPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+MTE8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+MjA8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+MjM8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+Mjk8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+MzI8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+MzQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4yMTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4yMjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4zMDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4zMTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4zNTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj4zNjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVkMWEwXHViMDdjXHViMjk0IFx1YzljMFx1YWUwOCAxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWQxYTBcdWIwN2NcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM4MTBcdWQ1MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzcwNCwgXHVjNTQ0XHViNzk4LCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YzY3Y1x1Y2FiZCk8XC9wPlxyXG5cclxuPHA+XHVkMWEwXHViMDdjXHVhYzAwIFx1YzgxMFx1ZDUwNFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMWEwXHViMDdjXHVhYzAwIFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWNlNzhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM3NDQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVhY2JkXHVjNmIwXHVjNWQwXHViM2M0LCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHViNTRjIFx1YjljOFx1YjJlNCBcdWIzNTRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQxYTBcdWIwN2NcdWFjMDAgXHVkNTg5XHViODJjXHVjNzQ0IFx1YmM5N1x1YzViNFx1YjA5OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOLCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgMSAmbGU7IEsgJmxlOyAzMDAsMDAwKSBOXHVjNzQwIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQwNmNcdWFlMzAsIEtcdWIyOTQgXHVkMWEwXHViMDdjXHVhYzAwIFx1YzgxMFx1ZDUwNFx1ZDU1YyBcdWQ2OWZcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgJiMzOTtVJiMzOTssJiMzOTtEJiMzOTssJiMzOTtMJiMzOTssJiMzOTtSJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IEtcdWM3NzRcdWJhNzAsIFx1ZDFhMFx1YjA3Y1x1YWMwMCBcdWM4MTBcdWQ1MDRcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWNlNzhcdWM3NTggXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMzJcdWJlNDRcdWQyYjggXHVjODE1XHVjMjE4XHViOTdjIFx1YjExOFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCUk9KRVZJIiwiZGVzY3JpcHRpb24iOiI8cD5BIE4mdGltZXM7TiBtYXRyaXggaXMgZmlsbGVkIHdpdGggbnVtYmVycyAxIHRvIE48c3VwPjI8XC9zdXA+LCBkaWFnb25hbGx5IGluIGEgemlnLXphZyBmYXNoaW9uLiBUaGUgaWxsdXN0cmF0aW9uIGJlbG93IHNob3dzIG51bWJlcnMgaW4gdGhlIG1hdHJpeCBmb3IgTiA9IDYuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcmFiYml0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5NnB4OyB3aWR0aDoyMTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBhIHJhYmJpdCBpbiB0aGUgY2VsbCBjb250YWluaW5nIG51bWJlciAxLiBBIHJhYmJpdCBjYW4ganVtcCB0byBhIG5laWdoYm9yaW5nIGNlbGwgKHVwLCBkb3duLCBsZWZ0IG9yIHJpZ2h0KSBpZiB0aGF0IGNlbGwgZXhpc3RzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiBLIHZhbGlkIHJhYmJpdCBqdW1wcywgd3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIHN1bSBvZiBudW1iZXJzIG9mIGFsbCBjZWxscyB0aGF0IHJhYmJpdCB2aXNpdGVkIChhZGQgdGhlIG51bWJlciB0byB0aGUgc3VtIGVhY2ggdGltZSByYWJiaXQgdmlzaXRzIHRoZSBzYW1lIGNlbGwpLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEsgKDEgJmxlOyBOICZsZTsgMTAwMDAwLCAxICZsZTsgSyAmbGU7IDMwMDAwMCksIHRoZSBzaXplIG9mIHRoZSBtYXRyaXggYW5kIHRoZSBudW1iZXIgb2YgcmFiYml0IGp1bXBzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBLIGNoYXJhY3RlcnMgJiMzOTtVJiMzOTssICYjMzk7RCYjMzk7LCAmIzM5O0wmIzM5OyBhbmQgJiMzOTtSJiMzOTssIGRlc2NyaWJpbmcgdGhlIGRpcmVjdGlvbiBvZiBlYWNoIGp1bXAuIFRoZSBzZXF1ZW5jZSBvZiBqdW1wcyB3aWxsIG5vdCBsZWF2ZSB0aGUgbWF0cml4IGF0IGFueSBtb21lbnQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyLCB0aGUgc3VtIG9mIG51bWJlcnMgb24gdmlzaXRlZCBjZWxscy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhpcyBudW1iZXIgZG9lc24mIzM5O3QgYWx3YXlzIGZpdCBpbiAzMi1iaXQgaW50ZWdlciB0eXBlPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d