시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB221662546128.282%

문제

소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수는 같다. 플레이어는 화살표(위, 아래, 왼쪽, 오른쪽)를 이용해 캐릭터를 아래와 같은 규칙으로 조정할 수 있다.

  • 캐릭터에게 지시한 방향이 빈 칸(박스나 벽이 아닌 곳)인 경우에는 그 칸으로 이동한다.
  • 지시한 방향에 박스가 있는 경우에는, 박스를 민다. 이 경우에는 박스가 이동할 칸도 비어있어야 한다.
  • 지시한 방향이 벽인 경우, 또는 박스가 있는데, 박스가 이동할 칸에 다른 박스나 벽이 있는 경우에는 키를 눌러도 캐릭터는 이동하지 않는다.

모든 박스를 목표점으로 이동시킨 경우에 게임은 끝난다. 게임이 끝난 후에 입력하는 키는 모두 무시된다.

준규는 소코반으로 고통받는 친구들을 위해서 소코반의 해를 찾는 프로그램을 작성하려고 한다. 하지만, 소코반의 해를 찾는 문제는 NP-hard와 PSPACE-complete에 속하고, 매우 어려운 문제이다. 따라서, 간단한 소코반 프로그램을 작성해보려고 한다.

사용자가 입력한 키가 순서대로 주어졌을 때, 게임이 어떻게 진행되는지를 구하는 프로그램을 작성하시오.

게임의 상태는 아래와 같은 문자로 나타낼 수 있다.

문자
. 빈 공간
#
+ 비어 있는 목표점
b 박스
B 목표점 위에 있는 박스
w 캐릭터
W 목표점 위에 있는 캐릭터

첫 번째 입력은 문제의 그림과 같다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 행과 열의 수 R, C가 주어진다. (4 ≤ R ≤ 15, 4 ≤ C ≤ 15) 다음 R개 줄에는 현재 게임의 상태가 주어진다. 모든 줄은 C개의 문자로 이루어져 있다. 마지막 줄에는 플레이어가 입력한 키가 순서대로 주어지며 길이는 최대 50이다. 위, 아래, 왼쪽, 오른쪽은 U, D, L, R로 나타낸다.

입력의 마지막 줄에는 0 0이 주어진다.

입력으로 주어지는 모든 데이터는 항상 캐릭터가 한 명이고, 박스의 수와 목표점의 수는 같다. 또, 목표점 위에 올라가 있지 않은 박스는 적어도 한 개 이며, 가장 바깥쪽 칸은 항상 벽이다.

출력

각각의 게임에 대해서, 게임 번호를 출력한 다음에 게임이 끝났으면 complete를, 아니면 incomplete를 출력한다. 그 다음 줄부터 R개 줄에는 게임의 상태를 출력한다.

예제 입력 1

8 9
#########
#...#...#
#..bb.b.#
#...#w#.#
#...#b#.#
#...++++#
#...#..##
#########
ULRURDDDUULLDDD
6 7
#######
#..####
#.+.+.#
#.bb#w#
##....#
#######
DLLUDLULUURDRDDLUDRR
0 0

예제 출력 1

Game 1: incomplete
#########
#...#...#
#..bb...#
#...#.#.#
#...#.#.#
#...+W+B#
#...#b.##
#########
Game 2: complete
#######
#..####
#.B.B.#
#.w.#.#
##....#
#######
W3sicHJvYmxlbV9pZCI6IjQ1NzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWNmNTRcdWJjMTgiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZXhhbXBsZS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTc4cHg7IHdpZHRoOjIwMHB4XCIgXC8+XHVjMThjXHVjZjU0XHViYzE4XHVjNzQwIDE5ODJcdWIxNDRcdWM1ZDAgXHVjNzdjXHViY2Y4XHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWFjOGNcdWM3ODRcdWM3M2NcdWI4NWMsIFx1Yzc3Y1x1YmNmOFx1YzViNFx1Yjg1YyBcdWNjM2RcdWFjZTBcdWM5YzBcdWFlMzBcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1Y2U5MFx1YjlhZFx1ZDEzMFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjYzNkXHVhY2UwIFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzE1XHVjMmE0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWJhYTlcdWQ0NWNcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNjJlXHVhZTMwXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHViYWE5XHVkNDVjXHVjODEwXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWJjMTVcdWMyYTRcdWM3NTggXHVjMjE4XHViMjk0IFx1YWMxOVx1YjJlNC4gXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1ZDY1NFx1YzBiNFx1ZDQ1YyhcdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQpXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWNlOTBcdWI5YWRcdWQxMzBcdWI5N2MgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM3M2NcdWI4NWMgXHVjODcwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjZTkwXHViOWFkXHVkMTMwXHVjNWQwXHVhYzhjIFx1YzljMFx1YzJkY1x1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3NzQgXHViZTQ4IFx1Y2U3OChcdWJjMTVcdWMyYTRcdWIwOTggXHViY2JkXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWFjZjMpXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFkZjggXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjOWMwXHVjMmRjXHVkNTVjIFx1YmMyOVx1ZDVhNVx1YzVkMCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgXHViYzE1XHVjMmE0XHViOTdjIFx1YmJmY1x1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1Y2U3OFx1YjNjNCBcdWJlNDRcdWM1YjRcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM5YzBcdWMyZGNcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzc0IFx1YmNiZFx1Yzc3OCBcdWFjYmRcdWM2YjAsIFx1YjYxMFx1YjI5NCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1Y2U3OFx1YzVkMCBcdWIyZTRcdWI5NzggXHViYzE1XHVjMmE0XHViMDk4IFx1YmNiZFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1ZDBhNFx1Yjk3YyBcdWIyMGNcdWI3ZWNcdWIzYzQgXHVjZTkwXHViOWFkXHVkMTMwXHViMjk0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YmMxNVx1YzJhNFx1Yjk3YyBcdWJhYTlcdWQ0NWNcdWM4MTBcdWM3M2NcdWI4NWMmbmJzcDtcdWM3NzRcdWIzZDlcdWMyZGNcdWQwYTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWIwNWRcdWIwOWNcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOWMgXHVkNmM0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjI5NCBcdWQwYTRcdWIyOTQgXHViYWE4XHViNDUwIFx1YmIzNFx1YzJkY1x1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTAwXHVhZGRjXHViMjk0IFx1YzE4Y1x1Y2Y1NFx1YmMxOFx1YzczY1x1Yjg1YyBcdWFjZTBcdWQxYjVcdWJjMWJcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQ0IFx1YzcwNFx1ZDU3NFx1YzExYyBcdWMxOGNcdWNmNTRcdWJjMThcdWM3NTggXHVkNTc0XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWMxOGNcdWNmNTRcdWJjMThcdWM3NTggXHVkNTc0XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWJiMzhcdWM4MWNcdWIyOTQmbmJzcDtOUC1oYXJkXHVjNjQwIFBTUEFDRS1jb21wbGV0ZVx1YzVkMCBcdWMxOGRcdWQ1NThcdWFjZTAsIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MjRcdWM2YjQgXHViYjM4XHVjODFjXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWMxOGNcdWNmNTRcdWJjMTggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzZhOVx1Yzc5MFx1YWMwMCBcdWM3ODVcdWI4MjVcdWQ1NWMgXHVkMGE0XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjOGNcdWM3ODRcdWM3NzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YzljNFx1ZDU4OVx1YjQxOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjUwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MjAlXCI+XHViYjM4XHVjNzkwPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQwJVwiPlx1YjczYjxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+LjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHViZTQ4IFx1YWNmNVx1YWMwNDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4jPFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWJjYmQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+KzxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHViZTQ0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWJhYTlcdWQ0NWNcdWM4MTA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+YjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHViYzE1XHVjMmE0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPkI8XC90ZD5cclxuXHRcdFx0PHRkPlx1YmFhOVx1ZDQ1Y1x1YzgxMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmMxNVx1YzJhNDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD53PFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWNlOTBcdWI5YWRcdWQxMzA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+VzxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHViYWE5XHVkNDVjXHVjODEwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZTkwXHViOWFkXHVkMTMwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzU4IFx1YzIxOCBSLCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDQgJmxlOyBSICZsZTsgMTUsIDQgJmxlOyBDICZsZTsgMTUpIFx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM5MDRcdWM3NDAgQ1x1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1ZDBhNFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgNTBcdWM3NzRcdWIyZTQuJm5ic3A7XHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzQwIFUsIEQsIEwsIFJcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwIDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Y2U5MFx1YjlhZFx1ZDEzMFx1YWMwMCBcdWQ1NWMgXHViYTg1XHVjNzc0XHVhY2UwLCBcdWJjMTVcdWMyYTRcdWM3NTggXHVjMjE4XHVjNjQwIFx1YmFhOVx1ZDQ1Y1x1YzgxMFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVhYzE5XHViMmU0LiBcdWI2MTAsIFx1YmFhOVx1ZDQ1Y1x1YzgxMCBcdWM3MDRcdWM1ZDAgXHVjNjJjXHViNzdjXHVhYzAwIFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViYzE1XHVjMmE0XHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVhYzFjIFx1Yzc3NFx1YmE3MCwgXHVhYzAwXHVjN2E1IFx1YmMxNFx1YWU2NVx1Y2FiZCBcdWNlNzhcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YmNiZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVhYzhjXHVjNzg0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzhjXHVjNzg0IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViMmU0XHVjNzRjXHVjNWQwIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwYWNcdWM3M2NcdWJhNzQgY29tcGxldGVcdWI5N2MsIFx1YzU0NFx1YjJjOFx1YmE3NCBpbmNvbXBsZXRlXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgUlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDU3NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNva29iYW4iLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZXhhbXBsZS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTc4cHg7IHdpZHRoOjIwMHB4XCIgXC8+U29rby1iYW4gaXMgYSBKYXBhbmVzZSB3b3JkIGZvciBhIHdhcmVob3VzZSB3b3JrZXIsIGFuZCB0aGUgbmFtZSBvZiBhIGNsYXNzaWMgY29tcHV0ZXIgZ2FtZSBjcmVhdGVkIGluIHRoZSAxOTgwcy4gSXQgaXMgYSBvbmUtcGxheWVyIGdhbWUgd2l0aCB0aGUgZm9sbG93aW5nIHByZW1pc2UuIEEgc2luZ2xlIHdvcmtlciBpcyBpbiBhbiBlbmNsb3NlZCB3YXJlaG91c2Ugd2l0aCBvbmUgb3IgbW9yZSBib3hlcy4gVGhlIGdvYWwgaXMgdG8gbW92ZSB0aG9zZSBib3hlcyB0byBhIHNldCBvZiB0YXJnZXQgbG9jYXRpb25zLCB3aXRoIHRoZSBudW1iZXIgb2YgdGFyZ2V0IGxvY2F0aW9ucyBlcXVhbGxpbmcgdGhlIG51bWJlciBvZiBib3hlcy4gVGhlIHBsYXllciBpbmRpY2F0ZXMgYSBkaXJlY3Rpb24gb2YgbW90aW9uIGZvciB0aGUgd29ya2VyIHVzaW5nIHRoZSBhcnJvdyBrZXlzICh1cCwgZG93biwgbGVmdCwgcmlnaHQpLCBhY2NvcmRpbmcgdG8gdGhlIGZvbGxvd2luZyBydWxlcy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JZiB0aGUgaW5kaWNhdGVkIGRpcmVjdGlvbiBvZiBtb3Rpb24gZm9yIHRoZSB3b3JrZXIgbGVhZHMgdG8gYW4gZW1wdHkgbG9jYXRpb24gKGkuZS4sIG9uZSB0aGF0IGRvZXMgbm90IGhhdmUgYSBib3ggb3Igd2FsbCksIHRoZSB3b3JrZXIgYWR2YW5jZXMgYnkgb25lIHN0ZXAgaW4gdGhhdCBkaXJlY3Rpb24uPFwvbGk+XHJcblx0PGxpPklmIHRoZSBpbmRpY2F0ZWQgZGlyZWN0aW9uIG9mIG1vdGlvbiB3b3VsZCBjYXVzZSB0aGUgd29ya2VyIHRvIG1vdmUgaW50byBhIGJveCwgYW5kIHRoZSBsb2NhdGlvbiBvbiB0aGUgb3RoZXIgc2lkZSBvZiB0aGUgYm94IGlzIGVtcHR5LCB0aGVuIGJvdGggdGhlIHdvcmtlciBhbmQgdGhlIGJveCBtb3ZlIG9uZSBzcG90IGluIHRoYXQgZGlyZWN0aW9uIChpLmUuLCB0aGUgd29ya2VyIHB1c2hlcyB0aGUgYm94KS48XC9saT5cclxuXHQ8bGk+SWYgdGhlIGluZGljYXRlZCBkaXJlY3Rpb24gb2YgbW90aW9uIGZvciBhIG1vdmUgd291bGQgY2F1c2UgdGhlIHdvcmtlciB0byBtb3ZlIGludG8gYSB3YWxsLCBvciB0byBtb3ZlIGludG8gYSBib3ggdGhhdCBoYXMgYW5vdGhlciBib3ggb3IgYSB3YWxsIG9uIGl0cyBvcHBvc2l0ZSBzaWRlLCB0aGVuIG5vIG1vdGlvbiB0YWtlcyBwbGFjZSBmb3IgdGhhdCBrZXlzdHJva2UuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGdvYWwgaXMgdG8gc2ltdWx0YW5lb3VzbHkgaGF2ZSBhbGwgYm94ZXMgb24gdGhlIHRhcmdldCBsb2NhdGlvbnMuIEluIHRoYXQgY2FzZSwgdGhlIHBsYXllciBpcyBzdWNjZXNzZnVsIChhbmQgYXMgYSBmb3JtYWxpdHksIGFsbCBmdXJ0aGVyIGtleXN0cm9rZXMgd2lsbCBiZSBpZ25vcmVkKS48XC9wPlxyXG5cclxuPHA+VGhlIGdhbWUgaGFzIGJlZW4gc3R1ZGllZCBieSBjb21wdXRlciBzY2llbnRpc3RzIChpbiBmYWN0LCBvbmUgZ3JhZHVhdGUgc3R1ZGVudCB3cm90ZSBoaXMgZW50aXJlIFBoLkQuIGRpc3NlcnRhdGlvbiBhYm91dCB0aGUgYW5hbHlzaXMgb2Ygc29rb2JhbikuIFVuZm9ydHVuYXRlbHksIGl0IHR1cm5zIG91dCB0aGF0IGZpbmRpbmcgYSBzb2x1dGlvbiBpcyB2ZXJ5IGRpZmZpY3VsdCBpbiBnZW5lcmFsLCBhcyBpdCBpcyBib3RoIE5QLWhhcmQgYW5kIFBTUEFDRS1jb21wbGV0ZS4gVGhlcmVmb3JlLCB5b3VyIGdvYWwgd2lsbCBiZSBhIHNpbXBsZXIgdGFzazogc2ltdWxhdGluZyB0aGUgcHJvZ3Jlc3Mgb2YgYSBnYW1lIGJhc2VkIHVwb24gYSBwbGF5ZXImIzM5O3Mgc2VxdWVuY2Ugb2Yga2V5c3Ryb2tlcy4gRm9yIHRoZSBzYWtlIG9mIGlucHV0IGFuZCBvdXRwdXQsIHdlIGRlc2NyaWJlIHRoZSBzdGF0ZSBvZiBhIGdhbWUgdXNpbmcgdGhlIGZvbGxvd2luZyBzeW1ib2xzOjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NTAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoyMCVcIj5TeW1ib2w8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6NDAlXCI+TWVhbmluZzxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+LjxcL3RkPlxyXG5cdFx0XHQ8dGQ+ZW1wdHkgc3BhY2U8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+IzxcL3RkPlxyXG5cdFx0XHQ8dGQ+d2FsbDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4rPFwvdGQ+XHJcblx0XHRcdDx0ZD5lbXB0eSB0YXJnZXQgbG9jYXRpb248XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+YjxcL3RkPlxyXG5cdFx0XHQ8dGQ+Ym94PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPkI8XC90ZD5cclxuXHRcdFx0PHRkPmJveCBvbiBhIHRhcmdldCBsb2NhdGlvbjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD53PFwvdGQ+XHJcblx0XHRcdDx0ZD53b3JrZXI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+VzxcL3RkPlxyXG5cdFx0XHQ8dGQ+d29ya2VyIG9uIGEgdGFyZ2V0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIGluaXRpYWwgY29uZmlndXJhdGlvbiBkaWFncmFtbWVkIGF0IHRoZSBiZWdpbm5pbmcgb2YgdGhpcyBwcm9ibGVtIGFwcGVhcnMgYXMgdGhlIGZpcnN0IGlucHV0IGNhc2UgYmVsb3cuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGdhbWUgYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgaW50ZWdlcnMgUiBhbmQgQywgd2hlcmUgNCAmbGU7IFIgJmxlOyAxNSByZXByZXNlbnRzIHRoZSBudW1iZXIgb2Ygcm93cywgYW5kIDQgJmxlOyBDICZsZTsgMTUgcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIGNvbHVtbnMuIE5leHQgd2lsbCBiZSBSIGxpbmVzIHJlcHJlc2VudGluZyB0aGUgUiByb3dzIGZyb20gdG9wIHRvIGJvdHRvbSwgd2l0aCBlYWNoIGxpbmUgaGF2aW5nIHByZWNpc2VseSBDIGNoYXJhY3RlcnMsIGZyb20gbGVmdC10by1yaWdodC4gRmluYWxseSwgdGhlcmUgaXMgYSBsaW5lIGNvbnRhaW5pbmcgYXQgbW9zdCA1MCBjaGFyYWN0ZXJzIGRlc2NyaWJpbmcgdGhlIHBsYXllciYjMzk7cyBzZXF1ZW5jZSBvZiBrZXlzdHJva2VzLCB1c2luZyB0aGUgc3ltYm9scyBVLCBELCBMLCBhbmQgUiByZXNwZWN0aXZlbHkgZm9yIHVwLCBkb3duLCBsZWZ0LCBhbmQgcmlnaHQuIFlvdSBtdXN0IHJlYWQgdGhhdCBlbnRpcmUgc2VxdWVuY2UgZnJvbSB0aGUgaW5wdXQsIGV2ZW4gdGhvdWdoIGEgcGFydGljdWxhciBnYW1lIG1pZ2h0IGVuZCBzdWNjZXNzZnVsbHkgcHJpb3IgdG8gdGhlIGVuZCBvZiB0aGUgc2VxdWVuY2UuIFRoZSBkYXRhIHNldCBlbmRzIHdpdGggdGhlIGxpbmUgMCAwLjxcL3A+XHJcblxyXG48cD5XZSB3aWxsIGd1YXJhbnRlZSB0aGF0IGVhY2ggZ2FtZSBoYXMgcHJlY2lzZWx5IG9uZSB3b3JrZXIsIGFuIGVxdWFsIG51bWJlciBvZiBib3hlcyBhbmQgbG9jYXRpb25zLCBhdCBsZWFzdCBvbmUgaW5pdGlhbGx5IG1pc3BsYWNlZCBib3gsIGFuZCBhbiBvdXRlcm1vc3QgYm91bmRhcnkgY29uc2lzdGluZyBlbnRpcmVseSBvZiB3YWxscy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBnYW1lLCB5b3Ugc2hvdWxkIGZpcnN0IG91dHB1dCBhIGxpbmUgaWRlbnRpZnlpbmcgdGhlIGdhbWUgbnVtYmVyLCBiZWdpbm5pbmcgYXQgMSwgYW5kIGVpdGhlciB0aGUgd29yZCBjb21wbGV0ZSBvciBpbmNvbXBsZXRlLCBkZXNpZ25hdGluZyB3aGV0aGVyIG9yIG5vdCB0aGUgcGxheWVyIHN1Y2Nlc3NmdWxseSBjb21wbGV0ZWQgdGhhdCBnYW1lLiBGb2xsb3dpbmcgdGhhdCBzaG91bGQgYmUgYSByZXByZXNlbnRhdGlvbiBvZiB0aGUgZmluYWwgYm9hcmQgY29uZmlndXJhdGlvbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d