시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 309 81 60 28.169%

문제

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

힌트

W3sicHJvYmxlbV9pZCI6IjMxMDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxYTBcdWIwN2NcdWM3NTggXHVjNzc0XHViM2Q5IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHQxXHViZDgwXHVkMTMwIE48c3VwPjI8XC9zdXA+XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHViMzAwXHVhYzAxXHVjMTIwIFx1YzIxY1x1YzExY1x1Yjg1YyBOKk4gXHVkNTg5XHViODJjXHVjNWQwIFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgTj02XHVjNzdjIFx1YjU0YywgXHVkNTg5XHViODJjXHVjNzU4IFx1YmFhOFx1YzJiNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MTglO1wiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7IHRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDE8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7IHRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDI8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7IHRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDY8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7IHRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDc8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7IHRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDE1PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlOyB0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQxNjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDM8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0NTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQ4PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDE0PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDE3PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDI2PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0NDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQ5PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDEzPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDE4PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDI1PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDI3PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0MTA8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0MTI8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0MTk8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0MjQ8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0Mjg8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0MzM8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQxMTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQyMDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQyMzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQyOTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQzMjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQzNDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDIxPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDIyPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDMwPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDMxPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDM1PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDM2PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cclxuXHRcdWQxYTBcdWIwN2NcdWIyOTQgXHVjOWMwXHVhZTA4IDFcdWM3NzQgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1ZDFhMFx1YjA3Y1x1YjI5NCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjZTc4XHVjNzNjXHViODVjIFx1YzgxMFx1ZDUwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNjdjXHVjYWJkKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQxYTBcdWIwN2NcdWFjMDAgXHVjODEwXHVkNTA0XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQxYTBcdWIwN2NcdWFjMDAgXHViYzI5XHViYjM4XHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVhYzE5XHVjNzQwIFx1Y2U3OFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIzYzQsIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWI1NGMgXHViOWM4XHViMmU0IFx1YjM1NFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDFhMFx1YjA3Y1x1YWMwMCBcdWQ1ODlcdWI4MmNcdWM3NDQgXHViYzk3XHVjNWI0XHViMDk4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOLCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgMSAmbGU7IEsgJmxlOyAzMDAsMDAwKSBOXHVjNzQwIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQwNmNcdWFlMzAsIEtcdWIyOTQgXHVkMWEwXHViMDdjXHVhYzAwIFx1YzgxMFx1ZDUwNFx1ZDU1YyBcdWQ2OWZcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgJiMzOTtVJiMzOTssJiMzOTtEJiMzOTssJiMzOTtMJiMzOTssJiMzOTtSJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IEtcdWM3NzRcdWJhNzAsIFx1ZDFhMFx1YjA3Y1x1YWMwMCBcdWM4MTBcdWQ1MDRcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVjZTc4XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDMyXHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWIxMThcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzEwMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJST0pFVkkiLCJkZXNjcmlwdGlvbiI6IjxwPkEgTiZ0aW1lcztOIG1hdHJpeCBpcyBmaWxsZWQgd2l0aCBudW1iZXJzIDEgdG8gTjIsIGRpYWdvbmFsbHkgaW4gYSB6aWctemFnIGZhc2hpb24uIFRoZSBpbGx1c3RyYXRpb24gYmVsb3cgc2hvd3MgbnVtYmVycyBpbiB0aGUgbWF0cml4IGZvciBOID0gNi48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9yYWJiaXQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTk2cHg7IHdpZHRoOjIxM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgcmFiYml0IGluIHRoZSBjZWxsIGNvbnRhaW5pbmcgbnVtYmVyIDEuIEEgcmFiYml0IGNhbiBqdW1wIHRvIGEgbmVpZ2hib3JpbmcgY2VsbCAodXAsIGRvd24sIGxlZnQgb3IgcmlnaHQpIGlmIHRoYXQgY2VsbCBleGlzdHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIEsgdmFsaWQgcmFiYml0IGp1bXBzLCB3cml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGNhbGN1bGF0ZSB0aGUgc3VtIG9mIG51bWJlcnMgb2YgYWxsIGNlbGxzIHRoYXQgcmFiYml0IHZpc2l0ZWQgKGFkZCB0aGUgbnVtYmVyIHRvIHRoZSBzdW0gZWFjaCB0aW1lIHJhYmJpdCB2aXNpdHMgdGhlIHNhbWUgY2VsbCkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgSyAoMSAmbGU7IE4gJmxlOyAxMDAwMDAsIDEgJmxlOyBLICZsZTsgMzAwMDAwKSwgdGhlIHNpemUgb2YgdGhlIG1hdHJpeCBhbmQgdGhlIG51bWJlciBvZiByYWJiaXQganVtcHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHNlcXVlbmNlIG9mIEsgY2hhcmFjdGVycyAmIzM5O1UmIzM5OywgJiMzOTtEJiMzOTssICYjMzk7TCYjMzk7IGFuZCAmIzM5O1ImIzM5OywgZGVzY3JpYmluZyB0aGUgZGlyZWN0aW9uIG9mIGVhY2gganVtcC4gVGhlIHNlcXVlbmNlIG9mIGp1bXBzIHdpbGwgbm90IGxlYXZlIHRoZSBtYXRyaXggYXQgYW55IG1vbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGludGVnZXIsIHRoZSBzdW0gb2YgbnVtYmVycyBvbiB2aXNpdGVkIGNlbGxzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGlzIG51bWJlciBkb2VzbiYjMzk7dCBhbHdheXMgZml0IGluIDMyLWJpdCBpbnRlZ2VyIHR5cGU8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=