시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 1 0 0 0.000%

문제

평면 위에 점이 여러 개 주어진다. 이 점을 모두 지나는 지그재그 선을 찾으려고 한다. 이 때, 전환점(turning point)의 개수를 가장 적게 하려고 한다. 또, 전환점의 개수가 같은 경우에는 선의 길이가 가장 작은 것을 찾으려고 한다.

예를 들어, 아래와 같이 평면 위에 점이 9개가 있다고 하자.

지그재그 선은 여러 선분으로 이루어져 있고, 각 선분은 점을 두 개 이상 지나야 한다.

지그재그 선은 선이 꺽일 수 있는데, 이 꺽이는 지점을 전환점(turning point)라고 한다. 전환점은 주어진 점 위에 있을 수도 있고, 아닐 수도 있다.

왼쪽 지그재그 선의 길이: 8 + 3√2 ≃ 12.242641, 오른쪽 지그재그 선의 길이: 2√2 + (6 + 1/2) + 5√5/2 ≃ 14.918597

위의 그림은 주어진 점을 지나는 지그재그 선이고 두 선 모두 전환점의 개수는 3개이다. 왼쪽 지그재그 선의 길이는 오른쪽 지그재그 선의 길이보다 짧다. 또, 왼쪽 지그재그 선은 주어진 아홉 개의 점을 지나는 가장 짧은 지그재그 선이다.

전환점을 네 개 갖는 지그재그 선은 아래와 같다. 이 선의 길이는 위의 그림의 길이보다 짧지만, 전환점의 수가 더 많기 때문에 정답이 아니다.

아래와 같이 점이 7개 있고, 그 점을 잇는 두가지로 이었다고 하자. 이 때, 왼쪽의 길이가 오른쪽보다 더 길지만, 정답은 왼쪽 그림이 된다. 그 이유는 지그재그 선의 모든 선분은 점을 두 개 이상 지나야 하기 때문이다.

점이 주어졌을 때, 지그재그 선을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 점의 개수 n이 주어진다. 다음 n개의 줄에는 점의 좌표가 주어진다.

모든 좌표는 음이 아닌 정수이고, 공백으로 구분되어 있다. n은 2이상 10이하의 자연수이고, x,y좌표는 0이상 10이하의 정수이다. 점의 순서는 별 의미가 없다.

출력

각 테스트 케이스에 대해서, 가장 전환점을 갖는 지그재그 선 중 가장 짧은 것의 전환점의 개수와 길이를 출력한다. 선의 길이는 정답과의 오차가 0.0001까지 허용된다.

가장 작은 전환점의 개수는 최대 4개이며, 따라서 선분의 개수는 최대 5개가 된다.

예제 입력 1

2
0 0
10 9
4
0 0
3 1
0 3
3 3
10
2 2
4 2
6 2
2 4
4 4
6 4
2 6
4 6
6 6
3 3
10
0 0
2 0
4 0
0 2
2 2
4 2
0 4
2 4
4 4
6 8
9
0 0
1 0
3 0
0 1
1 1
3 1
0 2
1 2
2 2
10
0 0
1 0
0 1
1 1
9 9
9 10
10 9
10 10
0 2
10 8
10
0 0
0 10
2 0
2 1
2 7
2 10
5 1
6 7
9 2
10 9
0

예제 출력 1

0 13.45362405
1 18.48683298
3 24.14213562
4 24.94813673
3 12.24264069
3 60.78289622
3 502.7804353

힌트

첫 번째 데이터: 

두 번째 데이터: 

세 번째 데이터: 

네 번째 데이터: 

W3sicHJvYmxlbV9pZCI6IjM4OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgXHVjODEwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjODEwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM5YzBcdWIwOThcdWIyOTQgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM4MDRcdWQ2NThcdWM4MTAodHVybmluZyBwb2ludClcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWM4MDRcdWQ2NThcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgXHVjODEwXHVjNzc0IDlcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC96MS5wbmdcIiBzdHlsZT1cIndpZHRoOiAxNjFweDsgaGVpZ2h0OiAxNDNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWMxMjBcdWJkODRcdWM3NDAgXHVjODEwXHVjNzQ0IFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1YzljMFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NDAgXHVjMTIwXHVjNzc0IFx1YWViZFx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzQgXHVhZWJkXHVjNzc0XHViMjk0IFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM4MDRcdWQ2NThcdWM4MTAodHVybmluZyBwb2ludClcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4MDRcdWQ2NThcdWM4MTBcdWM3NDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YzU0NFx1YjJkMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3oyLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDQ4NnB4OyBoZWlnaHQ6IDEzN3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2N2NcdWNhYmQgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzQ6IDggKyAzJnJhZGljOzIgXHUyMjQzIDEyLjI0MjY0MSwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0OiAyJnJhZGljOzIgKyAoNiArIDFcLzIpICsgNSZyYWRpYzs1XC8yIFx1MjI0MyAxNC45MTg1OTc8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjODEwXHVjNzQ0IFx1YzljMFx1YjA5OFx1YjI5NCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMTIwXHVjNzc0XHVhY2UwIFx1YjQ1MCBcdWMxMjAgXHViYWE4XHViNDUwIFx1YzgwNFx1ZDY1OFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgM1x1YWMxY1x1Yzc3NFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YmNmNFx1YjJlNCBcdWM5ZTdcdWIyZTQuIFx1YjYxMCwgXHVjNjdjXHVjYWJkIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzU0NFx1ZDY0OSBcdWFjMWNcdWM3NTggXHVjODEwXHVjNzQ0IFx1YzljMFx1YjA5OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgwNFx1ZDY1OFx1YzgxMFx1Yzc0NCBcdWIxMjQgXHVhYzFjIFx1YWMxNlx1YjI5NCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMTIwXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuIFx1Yzc3NCBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NTggXHVhZTM4XHVjNzc0XHViY2Y0XHViMmU0IFx1YzllN1x1YzljMFx1YjljYywgXHVjODA0XHVkNjU4XHVjODEwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWIzNTQgXHViOWNlXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3ozLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE0OHB4OyBoZWlnaHQ6IDk4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjODEwXHVjNzc0IDdcdWFjMWMgXHVjNzg4XHVhY2UwLCBcdWFkZjggXHVjODEwXHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWI0NTBcdWFjMDBcdWM5YzBcdWI4NWMgXHVjNzc0XHVjNWM4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YjU0YywgXHVjNjdjXHVjYWJkXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWJjZjRcdWIyZTQgXHViMzU0IFx1YWUzOFx1YzljMFx1YjljYywgXHVjODE1XHViMmY1XHVjNzQwIFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NzQgXHViNDFjXHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NTggXHViYWE4XHViNGUwIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWM4MTBcdWM3NDQgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjOWMwXHViMDk4XHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvejQucG5nXCIgc3R5bGU9XCJ3aWR0aDogNDI3cHg7IGhlaWdodDogNzRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODEwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhYThcdWI0ZTAgXHVjODhjXHVkNDVjXHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwLCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gblx1Yzc0MCAyXHVjNzc0XHVjMGMxIDEwXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YWNlMCwgeCx5XHVjODhjXHVkNDVjXHViMjk0IDBcdWM3NzRcdWMwYzEgMTBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM4MTBcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IFx1YmNjNCBcdWM3NThcdWJiZjhcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAwXHVjN2E1IFx1YzgwNFx1ZDY1OFx1YzgxMFx1Yzc0NCBcdWFjMTZcdWIyOTQgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjODNcdWM3NTggXHVjODA0XHVkNjU4XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YzgxNVx1YjJmNVx1YWNmY1x1Yzc1OCBcdWM2MjRcdWNjMjhcdWFjMDAgMC4wMDAxXHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM4MDRcdWQ2NThcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCA0XHVhYzFjXHVjNzc0XHViYTcwLCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjMTIwXHViZDg0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgNVx1YWMxY1x1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViMzcwXHVjNzc0XHVkMTMwOiZuYnNwOzxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvemgxLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE2M3B4OyBoZWlnaHQ6IDE2NnB4O1wiIFwvPjxcL3A+XHJcbjxwPlxyXG5cdFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViMzcwXHVjNzc0XHVkMTMwOiZuYnNwOzxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvemgyLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE1OHB4OyBoZWlnaHQ6IDE2NHB4O1wiIFwvPjxcL3A+XHJcbjxwPlxyXG5cdFx1YzEzOCBcdWJjODhcdWM5ZjggXHViMzcwXHVjNzc0XHVkMTMwOiZuYnNwOzxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvemgzLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE2MnB4OyBoZWlnaHQ6IDE2MnB4O1wiIFwvPjxcL3A+XHJcbjxwPlxyXG5cdFx1YjEyNCBcdWJjODhcdWM5ZjggXHViMzcwXHVjNzc0XHVkMTMwOiZuYnNwOzxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvemg0LnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE1OHB4OyBoZWlnaHQ6IDE2MXB4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzg5NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlppZ3phZyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gc2V2ZXJhbCBwb2ludHMgb24gYSBwbGFuZSwgbGV0JnJzcXVvO3MgdHJ5IHRvIHNvbHZlIGEgcHV6emxlIGNvbm5lY3RpbmcgdGhlbSB3aXRoIGEgemlnemFnIGxpbmUuIFRoZSBwdXp6bGUgaXMgdG8gZmluZCB0aGUgemlnemFnIGxpbmUgdGhhdCBwYXNzZXMgdGhyb3VnaCBhbGwgdGhlIGdpdmVuIHBvaW50cyB3aXRoIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0dXJucy4gTW9yZW92ZXIsIHdoZW4gdGhlcmUgYXJlIHNldmVyYWwgemlnemFnIGxpbmVzIHdpdGggdGhlIG1pbmltdW0gbnVtYmVyIG9mIHR1cm5zLCB0aGUgc2hvcnRlc3Qgb25lIGFtb25nIHRoZW0gc2hvdWxkIGJlIGZvdW5kLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgY29uc2lkZXIgbmluZSBwb2ludHMgZ2l2ZW4gaW4gRmlndXJlIDEwLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3oxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0M3B4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MTYxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEwOiBHaXZlbiBuaW5lIHBvaW50czxcL3A+XHJcblxyXG48cD5BIHppZ3phZyBsaW5lIGlzIGNvbXBvc2VkIG9mIHNldmVyYWwgc3RyYWlnaHQgbGluZSBzZWdtZW50cy4gSGVyZSwgdGhlIHJ1bGUgcmVxdWVzdHMgdGhhdCBlYWNoIGxpbmUgc2VnbWVudCBzaG91bGQgcGFzcyB0aHJvdWdoIHR3byBvciBtb3JlIGdpdmVuIHBvaW50cy48XC9wPlxyXG5cclxuPHA+QSB6aWd6YWcgbGluZSBtYXkgdHVybiBhdCBzb21lIG9mIHRoZSBnaXZlbiBwb2ludHMgb3IgYW55d2hlcmUgZWxzZS4gVGhlcmUgbWF5IGJlIHNvbWUgZ2l2ZW4gcG9pbnRzIHBhc3NlZCBtb3JlIHRoYW4gb25jZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC96aXphLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5MHB4OyB3aWR0aDo1NDRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMTE6IFppZ3phZyBsaW5lcyB3aXRoIHRocmVlIHR1cm5pbmcgcG9pbnRzLjxcL3A+XHJcblxyXG48cD5Ud28gemlnemFnIGxpbmVzIHdpdGggdGhyZWUgdHVybmluZyBwb2ludHMgYXJlIGRlcGljdGVkIGluIEZpZ3VyZSAxMSAoYSkgYW5kIChiKSBmb3IgdGhlIHNhbWUgc2V0IG9mIGdpdmVuIHBvaW50cyBzaG93biBpbiBGaWd1cmUgMTAuIFRoZSBsZW5ndGggb2YgdGhlIHppZ3phZyBsaW5lIGluIEZpZ3VyZSAxMSAoYSkgaXMgc2hvcnRlciB0aGFuIHRoYXQgaW4gRmlndXJlIDExIChiKS4gSW4gZmFjdCwgdGhlIGxlbmd0aCBvZiB0aGUgemlnemFnIGxpbmUgaW4gRmlndXJlIDExIChhKSBpcyB0aGUgc2hvcnRlc3Qgc28gdGhhdCBpdCBpcyB0aGUgc29sdXRpb24gZm9yIHRoZSBuaW5lIHBvaW50cyBnaXZlbiBpbiBGaWd1cmUgMTAuPFwvcD5cclxuXHJcbjxwPkFub3RoZXIgemlnemFnIGxpbmUgd2l0aCBmb3VyIHR1cm5pbmcgcG9pbnRzIGlzIGRlcGljdGVkIGluIEZpZ3VyZSAxMi4gSXRzIGxlbmd0aCBpcyBzaG9ydGVyIHRoYW4gdGhvc2UgaW4gRmlndXJlIDExLCBob3dldmVyLCB0aGUgbnVtYmVyIG9mIHR1cm5pbmcgcG9pbnRzIGlzIGdyZWF0ZXIgdGhhbiB0aG9zZSBpbiBGaWd1cmUgMTEsIGFuZCB0aHVzLCBpdCBpcyBub3QgdGhlIHNvbHV0aW9uLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3ppemEyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyMnB4OyB3aWR0aDoxNjVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMTI6IFppZ3phZyBsaW5lIHdpdGggZm91ciB0dXJuaW5nIHBvaW50cy48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIHR3byB6aWd6YWcgbGluZXMgdGhhdCBwYXNzZXMgYW5vdGhlciBzZXQgb2YgZ2l2ZW4gcG9pbnRzIGRlcGljdGVkIGluIEZpZ3VyZSAxMyAoYSkgYW5kIChiKS48XC9wPlxyXG5cclxuPHA+Qm90aCBoYXZlIHRoZSBzYW1lIG51bWJlciBvZiB0dXJuaW5nIHBvaW50cywgYW5kIHRoZSBsaW5lIGluIChhKSBpcyBsb25nZXIgdGhhbiB0aGF0IGluIChiKS4gSG93ZXZlciwgdGhlIHNvbHV0aW9uIGlzIChhKSwgYmVjYXVzZSBvbmUgb2YgdGhlIHNlZ21lbnRzIG9mIHRoZSB6aWd6YWcgbGluZSBpbiAoYikgcGFzc2VzIG9ubHkgb25lIGdpdmVuIHBvaW50LCB2aW9sYXRpbmcgdGhlIHJ1bGUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wveml6YTMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTA3cHg7IHdpZHRoOjQ0NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxMzogWmlnemFnIGxpbmUgd2l0aCB0d28gdHVybmluZyBwb2ludHMgKGEpLCBhbmQgbm90IGEgemlnemFnIGxpbmUgY29uY2VybmVkIChiKS48XC9wPlxyXG5cclxuPHA+WW91ciBqb2IgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgc29sdmVzIHRoaXMgcHV6emxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIGRhdGFzZXRzLCBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyBvbmUgemVyby4gRWFjaCBkYXRhc2V0IGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdC48XC9wPlxyXG5cclxuPHByZT5cclxublxyXG54PHN1Yj4xPFwvc3ViPiB5PHN1Yj4xPFwvc3ViPlxyXG4uLi5cclxueDxzdWI+bjxcL3N1Yj4geTxzdWI+bjxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD5FdmVyeSBpbnB1dCBpdGVtIGluIGEgZGF0YXNldCBpcyBhIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyLiBJdGVtcyBpbiBhIGxpbmUgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS48XC9wPlxyXG5cclxuPHA+biBpcyB0aGUgbnVtYmVyIG9mIHRoZSBnaXZlbiBwb2ludHMuIHg8c3ViPms8XC9zdWI+IGFuZCB5PHN1Yj5rPFwvc3ViPiAoayA9IDEsIC4uLiwgbikgaW5kaWNhdGUgdGhlIHBvc2l0aW9uIG9mIHRoZSBrLXRoIHBvaW50LiBUaGUgb3JkZXIgb2YgdGhlIHBvaW50cyBpcyBtZWFuaW5nbGVzcy4gWW91IGNhbiBhc3N1bWUgdGhhdCAyICZsZTsgbiAmbGU7IDEwLCAwICZsZTsgeDxzdWI+azxcL3N1Yj4gJmxlOyAxMCwgYW5kIDAgJmxlOyB5PHN1Yj5rPFwvc3ViPiAmbGU7IDEwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0dXJuaW5nIHBvaW50cyBhbmQgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgemlnemFnIGxpbmUgd2l0aCB0aGF0IG51bWJlciBvZiB0dXJuaW5nIHBvaW50cyBzaG91bGQgYmUgcHJpbnRlZCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UgaW4gYSBsaW5lLiBUaGUgbGVuZ3RoIHNob3VsZCBiZSBpbiBhIGRlY2ltYWwgZnJhY3Rpb24gd2l0aCBhbiBlcnJvciBsZXNzIHRoYW4gMC4wMDAxICg9IDEuMCAmdGltZXM7IDEwPHN1cD4mbWludXM7NDxcL3N1cD4pLjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSBtaW5pbXVtIG51bWJlciBvZiB0dXJuaW5nIHBvaW50cyBpcyBhdCBtb3N0IGZvdXIsIHRoYXQgaXMsIHRoZSBudW1iZXIgb2YgbGluZSBzZWdtZW50cyBpcyBhdCBtb3N0IGZpdmUuPFwvcD5cclxuXHJcbjxwPlRoZSBleGFtcGxlIHNvbHV0aW9ucyBmb3IgdGhlIGZpcnN0IGZvdXIgZGF0YXNldHMgaW4gdGhlIHNhbXBsZSBpbnB1dCBhcmUgZGVwaWN0ZWQgaW4gRmlndXJlIDE0IGFuZCAxNS48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC96aXphNC5wbmdcIiBzdHlsZT1cImhlaWdodDo2OTBweDsgd2lkdGg6NjEzcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==