#include <vector>
#include <iostream>
#include <functional>
#include <stack>
#include <array>
#include <limits>
#include <cmath>
#include <chrono>
struct SDL_Point {
int x, y;
} ;
namespace pathfinders {
enum class Heuristic : unsigned char {
kManhattan, // Best for 4-directional
kDiagonal, // Best for 8-directional
kChebyshev, // Diagonal with `D = D2 = 1`
kOctile, // Diagonal with `D = 1, D2 = std::sqrt(2)`
kEuclidean, // Works for any directions
kConstantZero, // `g << h`, reverts into Dijkstra
kContantInf, // `g >> h`, reverts into Greedy Best-First-Search
} ;
enum class MovementType : bool {
k4Directional,
k8Directional,
} ;
enum class Status : unsigned char {
kInvalidSrc,
kInvalidDest,
kBlockedSrc,
kBlockedDest,
kCoincidents,
kSuccess,
kFailure,
} ;
struct Cell {
int x, y;
inline bool operator== ( Cell const & other) const { return x == other.x && y == other.y ; }
inline Cell operator+ ( Cell const & other) const { return { x + other.x , y + other.y } ; }
inline Cell operator- ( Cell const & other) const { return { x - other.x , y - other.y } ; }
friend inline std:: ostream & operator<< ( std:: ostream & os, Cell const & self) { return os << '(' << self.x << ", " << self.y << ')' ; }
static inline SDL_Point cltopt( Cell const & self) { return { self.x , self.y } ; }
static inline Cell pttocl( SDL_Point const & pt) { return { pt.x , pt.y } ; }
static double getG( Cell const & distance) ;
template < Heuristic H>
typename std:: enable_if_t < H == Heuristic:: kManhattan , double >
static getH( Cell const & lhs, Cell const & rhs) ;
template < Heuristic H>
typename std:: enable_if_t < H == Heuristic:: kChebyshev , double >
static getH( Cell const & lhs, Cell const & rhs) ;
template < Heuristic H>
typename std:: enable_if_t < H == Heuristic:: kOctile , double >
static getH( Cell const & lhs, Cell const & rhs) ;
template < Heuristic H>
typename std:: enable_if_t < H == Heuristic:: kEuclidean , double >
static getH( Cell const & lhs, Cell const & rhs) ;
template < Heuristic H>
typename std:: enable_if_t < H == Heuristic:: kConstantZero , double >
static constexpr inline getH( Cell const & lhs, Cell const & rhs) { return 0 ; }
template < Heuristic H>
typename std:: enable_if_t < H == Heuristic:: kContantInf , double >
static constexpr inline getH( Cell const & lhs, Cell const & rhs) { return std:: pow ( 10 , 307 ) ; } // Might cause overflow
struct Data; // Forward declaration to prevent "incomplete type" compilation error
private :
template < Heuristic H, unsigned short int Dsq, unsigned short int D2sq> // Floating-point template parameter is nonstandardC/C++(605)
typename std:: enable_if_t < H == Heuristic:: kDiagonal , double >
static getH( Cell const & lhs, Cell const & rhs) ;
} ;
struct Cell:: Data {
Cell parent;
double g, h, f = std:: numeric_limits < double > :: max ( ) ;
} ;
struct Result {
const Status status;
std:: stack < Cell> path;
Result( Status status, std:: stack < Cell> path = { } ) : status( status) , path( path) { }
inline Result( Status status, Cell const & cell) : status( status) { path.push ( cell) ; }
} ;
/**
* @brief Implementation of A* pathfinding algorithm.
* @see https://w...content-available-to-author-only...s.org/a-search-algorithm/
*/
template < Heuristic H = Heuristic:: kManhattan , MovementType M = MovementType:: k4Directional >
class ASPF {
public :
ASPF( std:: vector < std:: vector < int >> const & grid) ;
~ASPF( ) = default ;
void setBegin( Cell const & begin) ;
void setEnd( Cell const & end) ;
Result search( Cell const & src, Cell const & dest) const ;
Result quicksearch( Cell const & src, Cell const & dest) const ;
private :
bool isValid( Cell const & cell) const ;
bool isUnblocked( Cell const & cell) const ;
bool isUnblocked( Cell const & parent, Cell const & successor) const ;
std:: stack < Cell> getPath( std:: vector < std:: vector < Cell:: Data >> const & cellData, Cell const & dest) const ;
static inline constexpr auto getDirections( ) {
if constexpr( M == MovementType:: k4Directional ) {
return std:: array < Cell, 4 > { {
{ 1 , 0 } , { - 1 , 0 } , { 0 , 1 } , { 0 , - 1 } ,
} } ;
} else {
return std:: array < Cell, 8 > { {
{ 1 , 0 } , { - 1 , 0 } , { 0 , 1 } , { 0 , - 1 } ,
{ 1 , 1 } , { 1 , - 1 } , { - 1 , 1 } , { - 1 , - 1 } ,
} } ;
}
}
std:: vector < std:: vector < int >> const & mGrid;
Cell mBegin, mEnd;
static inline constexpr auto mDirections = getDirections( ) ;
} ;
/**
* @brief Implementation of Dijkstra pathfinding algorithm (reverted from A* search algorithm by setting heuristic `h` to constant `0`).
* @see https://c...content-available-to-author-only...e.com/questions/83618/best-heuristic-for-a
* @see https://t...content-available-to-author-only...d.edu/~amitp/GameProgramming/Heuristics.html
*/
template < MovementType M = MovementType:: k4Directional >
using DJPF = ASPF< Heuristic:: kConstantZero , M> ;
/**
* @brief Implementation of Greedy Best-First-Search pathfinding algorithm (reverted from A* search algorithm by setting heuristic `h` to be much higher than `g` so that `g` do not contribute to `f`).
* @see https://t...content-available-to-author-only...d.edu/~amitp/GameProgramming/Heuristics.html
*/
template < MovementType M = MovementType:: k4Directional >
using GBFSPF = ASPF< Heuristic:: kContantInf , M> ;
} ;
double pathfinders:: Cell :: getG ( Cell const & cell) {
return std:: sqrt ( std:: pow ( cell.x , 2 ) + std:: pow ( cell.y , 2 ) ) ;
}
template < pathfinders:: Heuristic H>
typename std:: enable_if_t < H == pathfinders:: Heuristic :: kManhattan , double >
pathfinders:: Cell :: getH ( Cell const & cell, Cell const & dest) {
return std:: abs ( cell.x - dest.x ) + std:: abs ( cell.y - dest.y ) ;
}
template < pathfinders:: Heuristic H, unsigned short int Dsq, unsigned short int D2sq>
typename std:: enable_if_t < H == pathfinders:: Heuristic :: kDiagonal , double >
pathfinders:: Cell :: getH ( Cell const & cell, Cell const & dest) {
auto dx = std:: abs ( cell.x - dest.x ) ;
auto dy = std:: abs ( cell.y - dest.y ) ;
return std:: sqrt ( Dsq) * std:: max ( dx, dy) + ( std:: sqrt ( D2sq) - std:: sqrt ( Dsq) ) * std:: min ( dx, dy) ;
}
template < pathfinders:: Heuristic H>
typename std:: enable_if_t < H == pathfinders:: Heuristic :: kChebyshev , double >
pathfinders:: Cell :: getH ( Cell const & cell, Cell const & dest) {
return getH< Heuristic:: kDiagonal , 1 , 1 > ( cell, dest) ;
}
template < pathfinders:: Heuristic H>
typename std:: enable_if_t < H == pathfinders:: Heuristic :: kOctile , double >
pathfinders:: Cell :: getH ( Cell const & cell, Cell const & dest) {
return getH< Heuristic:: kDiagonal , 1 , 2 > ( cell, dest) ;
}
template < pathfinders:: Heuristic H>
typename std:: enable_if_t < H == pathfinders:: Heuristic :: kEuclidean , double >
pathfinders:: Cell :: getH ( Cell const & cell, Cell const & dest) {
return std:: sqrt ( std:: pow ( cell.x - dest.x , 2 ) + std:: pow ( cell.y - dest.y , 2 ) ) ;
}
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
pathfinders:: ASPF < H, M> :: ASPF ( std:: vector < std:: vector < int >> const & grid) : mGrid( grid) {
setBegin( { 0 , 0 } ) ;
setEnd( { 0 , 0 } ) ;
}
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
bool pathfinders:: ASPF < H, M> :: isValid ( Cell const & cell) const {
return static_cast < int > ( mBegin.x ) <= cell.x && cell.x <= static_cast < int > ( mEnd.x ) && static_cast < int > ( mBegin.y ) <= cell.y && cell.y <= static_cast < int > ( mEnd.y ) ;
}
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
bool pathfinders:: ASPF < H, M> :: isUnblocked ( Cell const & cell) const {
return mGrid[ cell.y ] [ cell.x ] ! = 0 ;
}
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
bool pathfinders:: ASPF < H, M> :: isUnblocked ( Cell const & cell, Cell const & successor) const {
return mGrid[ successor.y ] [ successor.x ] ! = 0 ;
}
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
std:: stack < pathfinders:: Cell > pathfinders:: ASPF < H, M> :: getPath ( std:: vector < std:: vector < Cell:: Data >> const & cellData, Cell const & dest) const {
std:: stack < Cell> path;
auto curr = dest;
while ( ! ( cellData[ curr.y - mBegin.y ] [ curr.x - mBegin.x ] .parent == curr) ) {
path.push ( curr) ;
curr = cellData[ curr.y - mBegin.y ] [ curr.x - mBegin.x ] .parent ;
}
path.push ( curr) ;
return path;
}
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
void pathfinders:: ASPF < H, M> :: setBegin ( Cell const & begin) {
mBegin = {
std:: max ( 0 , begin.x ) ,
std:: max ( 0 , begin.y ) ,
} ;
}
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
void pathfinders:: ASPF < H, M> :: setEnd ( Cell const & end) {
mEnd = {
std:: min ( static_cast < int > ( mGrid.front ( ) .size ( ) ) - 1 , end.x ) ,
std:: min ( static_cast < int > ( mGrid.size ( ) ) - 1 , end.y ) ,
} ;
}
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
pathfinders:: Result pathfinders:: ASPF < H, M> :: search ( Cell const & src, Cell const & dest) const {
if ( mGrid.empty ( ) ) return Result( Status:: kFailure ) ;
if ( ! isValid( src) ) return Result( Status:: kInvalidSrc ) ;
if ( ! isValid( dest) ) return Result( Status:: kInvalidDest ) ;
if ( ! isUnblocked( src) ) return Result( Status:: kBlockedSrc ) ;
if ( ! isUnblocked( dest) ) return Result( Status:: kBlockedDest ) ;
if ( src == dest) return Result( Status:: kCoincidents ) ;
// Note that index-based operations on two following lists require substracting `mBegin` to match `mGrid`
// Initialize closed list
std:: vector < std:: vector < bool >> closedList( mEnd.y - mBegin.y + 1 , std:: vector < bool > ( mEnd.x - mBegin.x + 1 , false ) ) ; // `false` means not visited (and vice versa)
// Initialize cell data list
std:: vector < std:: vector < Cell:: Data >> cellDataList( mEnd.y - mBegin.y + 1 , std:: vector < Cell:: Data > ( mEnd.x - mBegin.x + 1 , Cell:: Data { } ) ) ;
// Initialize starting node parameters
auto & srcData = cellDataList[ src.y - mBegin.y ] [ src.x - mBegin.x ] ;
srcData.f = 0 ;
srcData.parent = src;
// Initialize open list
std:: stack < Cell> openList; // For operations at O(1) time complexity
openList.push ( src) ; // Place the starting cell on the open list
double g, h, f;
while ( ! openList.empty ( ) ) {
g = h = f = 0 ;
auto parent = openList.top ( ) ;
openList.pop ( ) ; // Remove cell from open list
closedList[ parent.y - mBegin.y ] [ parent.x - mBegin.x ] = true ; // Add cell to closed list
// Generate all successors
for ( const auto & direction : mDirections) {
auto successor = parent + direction;
if ( ! isValid( successor) ) continue ;
// If successor is destination, search is considered successful
if ( successor == dest) {
cellDataList[ successor.y - mBegin.y ] [ successor.x - mBegin.x ] .parent = parent;
return Result( Status:: kSuccess , getPath( cellDataList, dest) ) ;
}
// Ignore if successor is already on the closed list or is blocked
if ( ! closedList[ successor.y - mBegin.y ] [ successor.x - mBegin.x ] && isUnblocked( successor) ) {
g = cellDataList[ parent.y - mBegin.y ] [ parent.x - mBegin.x ] .g + Cell:: getG ( direction) ;
h = Cell:: getH < H> ( successor, dest) ;
f = g + h;
auto & successorData = cellDataList[ successor.y - mBegin.y ] [ successor.x - mBegin.x ] ;
// Add successor to the open list if successor is not on the open list or provides a better path
if ( successorData.f == std:: numeric_limits < double > :: max ( ) || successorData.f > f) {
openList.push ( successor) ;
// Update successor data
successorData.f = f;
successorData.g = g;
successorData.h = h;
successorData.parent = parent;
}
}
}
}
// Search is considered unsuccessful if the open list is emptied before destination cell is found
return Result( Status:: kFailure ) ;
}
/**
* @note Only returns direction.
*/
template < pathfinders:: Heuristic H, pathfinders:: MovementType M>
pathfinders:: Result pathfinders:: ASPF < H, M> :: quicksearch ( Cell const & src, Cell const & dest) const {
// Pre-checks as usual
if ( mGrid.empty ( ) ) return Result( Status:: kFailure ) ;
if ( ! isValid( src) ) return Result( Status:: kInvalidSrc ) ;
if ( ! isValid( dest) ) return Result( Status:: kInvalidDest ) ;
if ( ! isUnblocked( src) ) return Result( Status:: kBlockedSrc ) ;
if ( ! isUnblocked( dest) ) return Result( Status:: kBlockedDest ) ;
if ( src == dest) return Result( Status:: kCoincidents ) ;
double fc = std:: numeric_limits < double > :: min ( ) ;
Cell directionc;
for ( const auto & direction : mDirections) {
auto successor = src + direction;
if ( ! isValid( successor) || ! isUnblocked( successor) ) continue ;
if ( successor == dest) return Result( Status:: kSuccess , direction) ; // If successor is destination, search is considered successful
// Calculate `f` value of successor
double f = std:: sqrt ( std:: pow ( direction.x , 2 ) + std:: pow ( direction.y , 2 ) ) + Cell:: getH < H> ( successor, dest) ;
// Cache the successor if it provides a better path
if ( f > fc) {
fc = f;
directionc = direction;
}
}
// Search is considered unsuccessful if the open list is emptied before destination cell is found
return fc == std:: numeric_limits < double > :: min ( ) ? Result( Status:: kFailure ) : Result( Status:: kSuccess , directionc) ;
}
template class pathfinders:: ASPF < pathfinders:: Heuristic :: kManhattan , pathfinders:: MovementType :: k4Directional > ;
#define RUN(h, m, t) \
do {\
double sum = 0;\
\
auto obj = pathfinders::ASPF<h, m>(vec);\
obj.setBegin(src - range);\
obj.setEnd(src + range);\
\
for (int i = 0; i < times; ++i) {\
auto start = std::chrono::high_resolution_clock::now();\
\
auto res = obj.search(src, dest);\
auto dir = obj.quicksearch(src, dest);\
\
auto end = std::chrono::high_resolution_clock::now();\
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);\
sum += duration.count();\
}\
\
std::cout << static_cast<int>(h) << "-" << static_cast<int>(m) << " : " << sum / times << " ms" << std::endl;\
} while (0);
#define RUNM(h, t) \
RUN(h, pathfinders::MovementType::k4Directional, t);\
RUN(h, pathfinders::MovementType::k8Directional, t);
#define RUNHM(t) \
do {\
RUNM(pathfinders::Heuristic::kManhattan, t)\
RUNM(pathfinders::Heuristic::kChebyshev, t)\
RUNM(pathfinders::Heuristic::kOctile, t)\
RUNM(pathfinders::Heuristic::kEuclidean, t)\
RUNM(pathfinders::Heuristic::kConstantZero, t)\
RUNM(pathfinders::Heuristic::kContantInf, t)\
} while (0);
/* * * * * * */
int main( void ) {
std:: vector < std:: vector < int >> vec = {
{ { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , } } ,
{ { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , } } ,
{ { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , } } ,
{ { 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 ,
5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 0 , 0 , 0 , 0 , 0 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 0 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , 5889 , } } ,
{ { 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , 5889 , 0 , 0 , 5889 , } } ,
{ { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , } } ,
{ { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , } } ,
{ { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , } } ,
{ { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , } } ,
{ { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , } } ,
} ;
// input is not inverted
const pathfinders:: Cell src = { 1120 / 32 , 384 / 32 } ;
const pathfinders:: Cell dest = { 32 / 32 , 384 / 32 } ;
const pathfinders:: Cell range = { std:: numeric_limits < short > :: max ( ) , std:: numeric_limits < short > :: max ( ) } ;
constexpr std:: size_t times = 1e2 ;
std:: cout << "Running tests for t = " << times << std:: endl ;
RUNHM( t) ;
// for (int i = 0; i < times; ++i) {
// auto obj = pathfinders::ASPF<h, m>(vec);
// obj.setBegin(src - range);
// obj.setEnd(src + range);
// auto start = std::chrono::high_resolution_clock::now();
// auto res = obj.search(src, dest);
// auto dir = obj.quicksearch(src, dest);
// auto end = std::chrono::high_resolution_clock::now();
// auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
// sum += duration.count();
// }
// std::cout << static_cast<int>(h) << "-" << static_cast<int>(m) << " : " << sum / times << " ms" << std::endl;
// std::cout << "Execution time: " << duration.count() << " ms" << std::endl;
// std::cout << "Status: " << static_cast<int>(res.status) << std::endl;
// auto path = res.path;
// while (path.size() > 1) {
// std::cout << "(" << path.top().x << ", " << path.top().y << ") -> ";
// path.pop();
// }
// std::cout << path.top() << std::endl;
// std::cout << "Status-dir: " << static_cast<int>(dir.status) << std::endl;
// std::cout << dir.path.top().x << ", " << dir.path.top().y << std::endl;
return 0 ;
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8YXJyYXk+CiNpbmNsdWRlIDxsaW1pdHM+CiNpbmNsdWRlIDxjbWF0aD4KCiNpbmNsdWRlIDxjaHJvbm8+CgoKc3RydWN0IFNETF9Qb2ludCB7CiAgICBpbnQgeCwgeTsKfTsKbmFtZXNwYWNlIHBhdGhmaW5kZXJzIHsKICAgIGVudW0gY2xhc3MgSGV1cmlzdGljIDogdW5zaWduZWQgY2hhciB7CiAgICAgICAga01hbmhhdHRhbiwgICAvLyBCZXN0IGZvciA0LWRpcmVjdGlvbmFsCiAgICAgICAga0RpYWdvbmFsLCAgIC8vIEJlc3QgZm9yIDgtZGlyZWN0aW9uYWwKICAgICAgICBrQ2hlYnlzaGV2LCAgIC8vIERpYWdvbmFsIHdpdGggYEQgPSBEMiA9IDFgCiAgICAgICAga09jdGlsZSwgICAvLyBEaWFnb25hbCB3aXRoIGBEID0gMSwgRDIgPSBzdGQ6OnNxcnQoMilgCiAgICAgICAga0V1Y2xpZGVhbiwgICAvLyBXb3JrcyBmb3IgYW55IGRpcmVjdGlvbnMKICAgICAgICBrQ29uc3RhbnRaZXJvLCAgIC8vIGBnIDw8IGhgLCByZXZlcnRzIGludG8gRGlqa3N0cmEKICAgICAgICBrQ29udGFudEluZiwgICAvLyBgZyA+PiBoYCwgcmV2ZXJ0cyBpbnRvIEdyZWVkeSBCZXN0LUZpcnN0LVNlYXJjaAogICAgfTsKCiAgICBlbnVtIGNsYXNzIE1vdmVtZW50VHlwZSA6IGJvb2wgewogICAgICAgIGs0RGlyZWN0aW9uYWwsCiAgICAgICAgazhEaXJlY3Rpb25hbCwKICAgIH07CgogICAgZW51bSBjbGFzcyBTdGF0dXMgOiB1bnNpZ25lZCBjaGFyIHsKICAgICAgICBrSW52YWxpZFNyYywKICAgICAgICBrSW52YWxpZERlc3QsCiAgICAgICAga0Jsb2NrZWRTcmMsCiAgICAgICAga0Jsb2NrZWREZXN0LAogICAgICAgIGtDb2luY2lkZW50cywKCiAgICAgICAga1N1Y2Nlc3MsCiAgICAgICAga0ZhaWx1cmUsCiAgICB9OwoKICAgIHN0cnVjdCBDZWxsIHsKICAgICAgICBpbnQgeCwgeTsKCiAgICAgICAgaW5saW5lIGJvb2wgb3BlcmF0b3I9PShDZWxsIGNvbnN0JiBvdGhlcikgY29uc3QgeyByZXR1cm4geCA9PSBvdGhlci54ICYmIHkgPT0gb3RoZXIueTsgfQogICAgICAgIGlubGluZSBDZWxsIG9wZXJhdG9yKyhDZWxsIGNvbnN0JiBvdGhlcikgY29uc3QgeyByZXR1cm4geyB4ICsgb3RoZXIueCwgeSArIG90aGVyLnkgfTsgfQogICAgICAgIGlubGluZSBDZWxsIG9wZXJhdG9yLShDZWxsIGNvbnN0JiBvdGhlcikgY29uc3QgeyByZXR1cm4geyB4IC0gb3RoZXIueCwgeSAtIG90aGVyLnkgfTsgfQogICAgICAgIGZyaWVuZCBpbmxpbmUgc3RkOjpvc3RyZWFtJiBvcGVyYXRvcjw8KHN0ZDo6b3N0cmVhbSYgb3MsIENlbGwgY29uc3QmIHNlbGYpIHsgcmV0dXJuIG9zIDw8ICcoJyA8PCBzZWxmLnggPDwgIiwgIiA8PCBzZWxmLnkgPDwgJyknOyB9CgogICAgICAgIHN0YXRpYyBpbmxpbmUgU0RMX1BvaW50IGNsdG9wdChDZWxsIGNvbnN0JiBzZWxmKSB7IHJldHVybiB7IHNlbGYueCwgc2VsZi55IH07IH0KICAgICAgICBzdGF0aWMgaW5saW5lIENlbGwgcHR0b2NsKFNETF9Qb2ludCBjb25zdCYgcHQpIHsgcmV0dXJuIHsgcHQueCwgcHQueSB9OyB9CgogICAgICAgIHN0YXRpYyBkb3VibGUgZ2V0RyhDZWxsIGNvbnN0JiBkaXN0YW5jZSk7CgogICAgICAgIHRlbXBsYXRlIDxIZXVyaXN0aWMgSD4KICAgICAgICB0eXBlbmFtZSBzdGQ6OmVuYWJsZV9pZl90PEggPT0gSGV1cmlzdGljOjprTWFuaGF0dGFuLCBkb3VibGU+CiAgICAgICAgc3RhdGljIGdldEgoQ2VsbCBjb25zdCYgbGhzLCBDZWxsIGNvbnN0JiByaHMpOwoKICAgICAgICB0ZW1wbGF0ZSA8SGV1cmlzdGljIEg+CiAgICAgICAgdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IEhldXJpc3RpYzo6a0NoZWJ5c2hldiwgZG91YmxlPgogICAgICAgIHN0YXRpYyBnZXRIKENlbGwgY29uc3QmIGxocywgQ2VsbCBjb25zdCYgcmhzKTsKCiAgICAgICAgdGVtcGxhdGUgPEhldXJpc3RpYyBIPgogICAgICAgIHR5cGVuYW1lIHN0ZDo6ZW5hYmxlX2lmX3Q8SCA9PSBIZXVyaXN0aWM6OmtPY3RpbGUsIGRvdWJsZT4KICAgICAgICBzdGF0aWMgZ2V0SChDZWxsIGNvbnN0JiBsaHMsIENlbGwgY29uc3QmIHJocyk7CgogICAgICAgIHRlbXBsYXRlIDxIZXVyaXN0aWMgSD4KICAgICAgICB0eXBlbmFtZSBzdGQ6OmVuYWJsZV9pZl90PEggPT0gSGV1cmlzdGljOjprRXVjbGlkZWFuLCBkb3VibGU+CiAgICAgICAgc3RhdGljIGdldEgoQ2VsbCBjb25zdCYgbGhzLCBDZWxsIGNvbnN0JiByaHMpOwoKICAgICAgICB0ZW1wbGF0ZSA8SGV1cmlzdGljIEg+CiAgICAgICAgdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IEhldXJpc3RpYzo6a0NvbnN0YW50WmVybywgZG91YmxlPgogICAgICAgIHN0YXRpYyBjb25zdGV4cHIgaW5saW5lIGdldEgoQ2VsbCBjb25zdCYgbGhzLCBDZWxsIGNvbnN0JiByaHMpIHsgcmV0dXJuIDA7IH0KCiAgICAgICAgdGVtcGxhdGUgPEhldXJpc3RpYyBIPgogICAgICAgIHR5cGVuYW1lIHN0ZDo6ZW5hYmxlX2lmX3Q8SCA9PSBIZXVyaXN0aWM6OmtDb250YW50SW5mLCBkb3VibGU+CiAgICAgICAgc3RhdGljIGNvbnN0ZXhwciBpbmxpbmUgZ2V0SChDZWxsIGNvbnN0JiBsaHMsIENlbGwgY29uc3QmIHJocykgeyByZXR1cm4gc3RkOjpwb3coMTAsIDMwNyk7IH0gICAvLyBNaWdodCBjYXVzZSBvdmVyZmxvdwoKICAgICAgICBzdHJ1Y3QgRGF0YTsgICAvLyBGb3J3YXJkIGRlY2xhcmF0aW9uIHRvIHByZXZlbnQgImluY29tcGxldGUgdHlwZSIgY29tcGlsYXRpb24gZXJyb3IKCiAgICAgICAgcHJpdmF0ZToKICAgICAgICAgICAgdGVtcGxhdGUgPEhldXJpc3RpYyBILCB1bnNpZ25lZCBzaG9ydCBpbnQgRHNxLCB1bnNpZ25lZCBzaG9ydCBpbnQgRDJzcT4gICAvLyBGbG9hdGluZy1wb2ludCB0ZW1wbGF0ZSBwYXJhbWV0ZXIgaXMgbm9uc3RhbmRhcmRDL0MrKyg2MDUpCiAgICAgICAgICAgIHR5cGVuYW1lIHN0ZDo6ZW5hYmxlX2lmX3Q8SCA9PSBIZXVyaXN0aWM6OmtEaWFnb25hbCwgZG91YmxlPgogICAgICAgICAgICBzdGF0aWMgZ2V0SChDZWxsIGNvbnN0JiBsaHMsIENlbGwgY29uc3QmIHJocyk7CiAgICB9OwoKICAgIHN0cnVjdCBDZWxsOjpEYXRhIHsKICAgICAgICBDZWxsIHBhcmVudDsKICAgICAgICBkb3VibGUgZywgaCwgZiA9IHN0ZDo6bnVtZXJpY19saW1pdHM8ZG91YmxlPjo6bWF4KCk7CiAgICB9OwoKICAgIHN0cnVjdCBSZXN1bHQgewogICAgICAgIGNvbnN0IFN0YXR1cyBzdGF0dXM7CiAgICAgICAgc3RkOjpzdGFjazxDZWxsPiBwYXRoOwoKICAgICAgICBSZXN1bHQoU3RhdHVzIHN0YXR1cywgc3RkOjpzdGFjazxDZWxsPiBwYXRoID0ge30pIDogc3RhdHVzKHN0YXR1cyksIHBhdGgocGF0aCkge30KICAgICAgICBpbmxpbmUgUmVzdWx0KFN0YXR1cyBzdGF0dXMsIENlbGwgY29uc3QmIGNlbGwpIDogc3RhdHVzKHN0YXR1cykgeyBwYXRoLnB1c2goY2VsbCk7IH0KICAgIH07CgogICAgLyoqCiAgICAgKiBAYnJpZWYgSW1wbGVtZW50YXRpb24gb2YgQSogcGF0aGZpbmRpbmcgYWxnb3JpdGhtLgogICAgICogQHNlZSBodHRwczovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLnMub3JnL2Etc2VhcmNoLWFsZ29yaXRobS8KICAgICovCiAgICB0ZW1wbGF0ZSA8SGV1cmlzdGljIEggPSBIZXVyaXN0aWM6OmtNYW5oYXR0YW4sIE1vdmVtZW50VHlwZSBNID0gTW92ZW1lbnRUeXBlOjprNERpcmVjdGlvbmFsPgogICAgY2xhc3MgQVNQRiB7CiAgICAgICAgcHVibGljOgogICAgICAgICAgICBBU1BGKHN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPGludD4+IGNvbnN0JiBncmlkKTsKICAgICAgICAgICAgfkFTUEYoKSA9IGRlZmF1bHQ7CgogICAgICAgICAgICB2b2lkIHNldEJlZ2luKENlbGwgY29uc3QmIGJlZ2luKTsKICAgICAgICAgICAgdm9pZCBzZXRFbmQoQ2VsbCBjb25zdCYgZW5kKTsKCiAgICAgICAgICAgIFJlc3VsdCBzZWFyY2goQ2VsbCBjb25zdCYgc3JjLCBDZWxsIGNvbnN0JiBkZXN0KSBjb25zdDsKICAgICAgICAgICAgUmVzdWx0IHF1aWNrc2VhcmNoKENlbGwgY29uc3QmIHNyYywgQ2VsbCBjb25zdCYgZGVzdCkgY29uc3Q7CgogICAgICAgIHByaXZhdGU6CiAgICAgICAgICAgIGJvb2wgaXNWYWxpZChDZWxsIGNvbnN0JiBjZWxsKSBjb25zdDsKICAgICAgICAgICAgYm9vbCBpc1VuYmxvY2tlZChDZWxsIGNvbnN0JiBjZWxsKSBjb25zdDsKICAgICAgICAgICAgYm9vbCBpc1VuYmxvY2tlZChDZWxsIGNvbnN0JiBwYXJlbnQsIENlbGwgY29uc3QmIHN1Y2Nlc3NvcikgY29uc3Q7CgogICAgICAgICAgICBzdGQ6OnN0YWNrPENlbGw+IGdldFBhdGgoc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8Q2VsbDo6RGF0YT4+IGNvbnN0JiBjZWxsRGF0YSwgQ2VsbCBjb25zdCYgZGVzdCkgY29uc3Q7CgogICAgICAgICAgICBzdGF0aWMgaW5saW5lIGNvbnN0ZXhwciBhdXRvIGdldERpcmVjdGlvbnMoKSB7CiAgICAgICAgICAgICAgICBpZiBjb25zdGV4cHIoTSA9PSBNb3ZlbWVudFR5cGU6Oms0RGlyZWN0aW9uYWwpIHsKICAgICAgICAgICAgICAgICAgICByZXR1cm4gc3RkOjphcnJheTxDZWxsLCA0Pnt7CiAgICAgICAgICAgICAgICAgICAgICAgIHsgMSwgMCB9LCB7IC0xLCAwIH0sIHsgMCwgMSB9LCB7IDAsIC0xIH0sCiAgICAgICAgICAgICAgICAgICAgfX07CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIHJldHVybiBzdGQ6OmFycmF5PENlbGwsIDg+e3sKICAgICAgICAgICAgICAgICAgICAgICAgeyAxLCAwIH0sIHsgLTEsIDAgfSwgeyAwLCAxIH0sIHsgMCwgLTEgfSwKICAgICAgICAgICAgICAgICAgICAgICAgeyAxLCAxIH0sIHsgMSwgLTEgfSwgeyAtMSwgMSB9LCB7IC0xLCAtMSB9LAogICAgICAgICAgICAgICAgICAgIH19OwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICBzdGQ6OnZlY3RvcjxzdGQ6OnZlY3RvcjxpbnQ+PiBjb25zdCYgbUdyaWQ7CiAgICAgICAgICAgIENlbGwgbUJlZ2luLCBtRW5kOwoKICAgICAgICAgICAgc3RhdGljIGlubGluZSBjb25zdGV4cHIgYXV0byBtRGlyZWN0aW9ucyA9IGdldERpcmVjdGlvbnMoKTsKICAgIH07CgogICAgLyoqCiAgICAgKiBAYnJpZWYgSW1wbGVtZW50YXRpb24gb2YgRGlqa3N0cmEgcGF0aGZpbmRpbmcgYWxnb3JpdGhtIChyZXZlcnRlZCBmcm9tIEEqIHNlYXJjaCBhbGdvcml0aG0gYnkgc2V0dGluZyBoZXVyaXN0aWMgYGhgIHRvIGNvbnN0YW50IGAwYCkuCiAgICAgKiBAc2VlIGh0dHBzOi8vYy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZS5jb20vcXVlc3Rpb25zLzgzNjE4L2Jlc3QtaGV1cmlzdGljLWZvci1hCiAgICAgKiBAc2VlIGh0dHBzOi8vdC4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZC5lZHUvfmFtaXRwL0dhbWVQcm9ncmFtbWluZy9IZXVyaXN0aWNzLmh0bWwKICAgICovCiAgICB0ZW1wbGF0ZSA8TW92ZW1lbnRUeXBlIE0gPSBNb3ZlbWVudFR5cGU6Oms0RGlyZWN0aW9uYWw+CiAgICB1c2luZyBESlBGID0gQVNQRjxIZXVyaXN0aWM6OmtDb25zdGFudFplcm8sIE0+OwoKICAgIC8qKgogICAgICogQGJyaWVmIEltcGxlbWVudGF0aW9uIG9mIEdyZWVkeSBCZXN0LUZpcnN0LVNlYXJjaCBwYXRoZmluZGluZyBhbGdvcml0aG0gKHJldmVydGVkIGZyb20gQSogc2VhcmNoIGFsZ29yaXRobSBieSBzZXR0aW5nIGhldXJpc3RpYyBgaGAgdG8gYmUgbXVjaCBoaWdoZXIgdGhhbiBgZ2Agc28gdGhhdCBgZ2AgZG8gbm90IGNvbnRyaWJ1dGUgdG8gYGZgKS4KICAgICAqIEBzZWUgaHR0cHM6Ly90Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5kLmVkdS9+YW1pdHAvR2FtZVByb2dyYW1taW5nL0hldXJpc3RpY3MuaHRtbAogICAgKi8KICAgIHRlbXBsYXRlIDxNb3ZlbWVudFR5cGUgTSA9IE1vdmVtZW50VHlwZTo6azREaXJlY3Rpb25hbD4KICAgIHVzaW5nIEdCRlNQRiA9IEFTUEY8SGV1cmlzdGljOjprQ29udGFudEluZiwgTT47Cn07CgoKCmRvdWJsZSBwYXRoZmluZGVyczo6Q2VsbDo6Z2V0RyhDZWxsIGNvbnN0JiBjZWxsKSB7CiAgICByZXR1cm4gc3RkOjpzcXJ0KHN0ZDo6cG93KGNlbGwueCwgMikgKyBzdGQ6OnBvdyhjZWxsLnksIDIpKTsKfQoKdGVtcGxhdGUgPHBhdGhmaW5kZXJzOjpIZXVyaXN0aWMgSD4KdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IHBhdGhmaW5kZXJzOjpIZXVyaXN0aWM6OmtNYW5oYXR0YW4sIGRvdWJsZT4KcGF0aGZpbmRlcnM6OkNlbGw6OmdldEgoQ2VsbCBjb25zdCYgY2VsbCwgQ2VsbCBjb25zdCYgZGVzdCkgewogICAgcmV0dXJuIHN0ZDo6YWJzKGNlbGwueCAtIGRlc3QueCkgKyBzdGQ6OmFicyhjZWxsLnkgLSBkZXN0LnkpOwp9Cgp0ZW1wbGF0ZSA8cGF0aGZpbmRlcnM6OkhldXJpc3RpYyBILCB1bnNpZ25lZCBzaG9ydCBpbnQgRHNxLCB1bnNpZ25lZCBzaG9ydCBpbnQgRDJzcT4KdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IHBhdGhmaW5kZXJzOjpIZXVyaXN0aWM6OmtEaWFnb25hbCwgZG91YmxlPgpwYXRoZmluZGVyczo6Q2VsbDo6Z2V0SChDZWxsIGNvbnN0JiBjZWxsLCBDZWxsIGNvbnN0JiBkZXN0KSB7CiAgICBhdXRvIGR4ID0gc3RkOjphYnMoY2VsbC54IC0gZGVzdC54KTsKICAgIGF1dG8gZHkgPSBzdGQ6OmFicyhjZWxsLnkgLSBkZXN0LnkpOwogICAgcmV0dXJuIHN0ZDo6c3FydChEc3EpICogc3RkOjptYXgoZHgsIGR5KSArIChzdGQ6OnNxcnQoRDJzcSkgLSBzdGQ6OnNxcnQoRHNxKSkgKiBzdGQ6Om1pbihkeCwgZHkpOwp9Cgp0ZW1wbGF0ZSA8cGF0aGZpbmRlcnM6OkhldXJpc3RpYyBIPgp0eXBlbmFtZSBzdGQ6OmVuYWJsZV9pZl90PEggPT0gcGF0aGZpbmRlcnM6OkhldXJpc3RpYzo6a0NoZWJ5c2hldiwgZG91YmxlPgpwYXRoZmluZGVyczo6Q2VsbDo6Z2V0SChDZWxsIGNvbnN0JiBjZWxsLCBDZWxsIGNvbnN0JiBkZXN0KSB7CiAgICByZXR1cm4gZ2V0SDxIZXVyaXN0aWM6OmtEaWFnb25hbCwgMSwgMT4oY2VsbCwgZGVzdCk7Cn0KCnRlbXBsYXRlIDxwYXRoZmluZGVyczo6SGV1cmlzdGljIEg+CnR5cGVuYW1lIHN0ZDo6ZW5hYmxlX2lmX3Q8SCA9PSBwYXRoZmluZGVyczo6SGV1cmlzdGljOjprT2N0aWxlLCBkb3VibGU+CnBhdGhmaW5kZXJzOjpDZWxsOjpnZXRIKENlbGwgY29uc3QmIGNlbGwsIENlbGwgY29uc3QmIGRlc3QpIHsKICAgIHJldHVybiBnZXRIPEhldXJpc3RpYzo6a0RpYWdvbmFsLCAxLCAyPihjZWxsLCBkZXN0KTsKfQoKdGVtcGxhdGUgPHBhdGhmaW5kZXJzOjpIZXVyaXN0aWMgSD4KdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IHBhdGhmaW5kZXJzOjpIZXVyaXN0aWM6OmtFdWNsaWRlYW4sIGRvdWJsZT4KcGF0aGZpbmRlcnM6OkNlbGw6OmdldEgoQ2VsbCBjb25zdCYgY2VsbCwgQ2VsbCBjb25zdCYgZGVzdCkgewogICAgcmV0dXJuIHN0ZDo6c3FydChzdGQ6OnBvdyhjZWxsLnggLSBkZXN0LngsIDIpICsgc3RkOjpwb3coY2VsbC55IC0gZGVzdC55LCAyKSk7Cn0KCnRlbXBsYXRlIDxwYXRoZmluZGVyczo6SGV1cmlzdGljIEgsIHBhdGhmaW5kZXJzOjpNb3ZlbWVudFR5cGUgTT4KcGF0aGZpbmRlcnM6OkFTUEY8SCwgTT46OkFTUEYoc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8aW50Pj4gY29uc3QmIGdyaWQpIDogbUdyaWQoZ3JpZCkgewogICAgc2V0QmVnaW4oeyAwLCAwIH0pOwogICAgc2V0RW5kKHsgMCwgMCB9KTsKfQoKdGVtcGxhdGUgPHBhdGhmaW5kZXJzOjpIZXVyaXN0aWMgSCwgcGF0aGZpbmRlcnM6Ok1vdmVtZW50VHlwZSBNPgpib29sIHBhdGhmaW5kZXJzOjpBU1BGPEgsIE0+Ojppc1ZhbGlkKENlbGwgY29uc3QmIGNlbGwpIGNvbnN0IHsKICAgIHJldHVybiBzdGF0aWNfY2FzdDxpbnQ+KG1CZWdpbi54KSA8PSBjZWxsLnggJiYgY2VsbC54IDw9IHN0YXRpY19jYXN0PGludD4obUVuZC54KSAmJiBzdGF0aWNfY2FzdDxpbnQ+KG1CZWdpbi55KSA8PSBjZWxsLnkgJiYgY2VsbC55IDw9IHN0YXRpY19jYXN0PGludD4obUVuZC55KTsKfQoKdGVtcGxhdGUgPHBhdGhmaW5kZXJzOjpIZXVyaXN0aWMgSCwgcGF0aGZpbmRlcnM6Ok1vdmVtZW50VHlwZSBNPgpib29sIHBhdGhmaW5kZXJzOjpBU1BGPEgsIE0+Ojppc1VuYmxvY2tlZChDZWxsIGNvbnN0JiBjZWxsKSBjb25zdCB7CiAgICByZXR1cm4gbUdyaWRbY2VsbC55XVtjZWxsLnhdICE9IDA7Cn0KCnRlbXBsYXRlIDxwYXRoZmluZGVyczo6SGV1cmlzdGljIEgsIHBhdGhmaW5kZXJzOjpNb3ZlbWVudFR5cGUgTT4KYm9vbCBwYXRoZmluZGVyczo6QVNQRjxILCBNPjo6aXNVbmJsb2NrZWQoQ2VsbCBjb25zdCYgY2VsbCwgQ2VsbCBjb25zdCYgc3VjY2Vzc29yKSBjb25zdCB7CiAgICByZXR1cm4gbUdyaWRbc3VjY2Vzc29yLnldW3N1Y2Nlc3Nvci54XSAhPSAwOwp9Cgp0ZW1wbGF0ZSA8cGF0aGZpbmRlcnM6OkhldXJpc3RpYyBILCBwYXRoZmluZGVyczo6TW92ZW1lbnRUeXBlIE0+CnN0ZDo6c3RhY2s8cGF0aGZpbmRlcnM6OkNlbGw+IHBhdGhmaW5kZXJzOjpBU1BGPEgsIE0+OjpnZXRQYXRoKHN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPENlbGw6OkRhdGE+PiBjb25zdCYgY2VsbERhdGEsIENlbGwgY29uc3QmIGRlc3QpIGNvbnN0IHsKICAgIHN0ZDo6c3RhY2s8Q2VsbD4gcGF0aDsKICAgIGF1dG8gY3VyciA9IGRlc3Q7CgogICAgd2hpbGUgKCEoY2VsbERhdGFbY3Vyci55IC0gbUJlZ2luLnldW2N1cnIueCAtIG1CZWdpbi54XS5wYXJlbnQgPT0gY3VycikpIHsKICAgICAgICBwYXRoLnB1c2goY3Vycik7CiAgICAgICAgY3VyciA9IGNlbGxEYXRhW2N1cnIueSAtIG1CZWdpbi55XVtjdXJyLnggLSBtQmVnaW4ueF0ucGFyZW50OwogICAgfQoKICAgIHBhdGgucHVzaChjdXJyKTsKICAgIHJldHVybiBwYXRoOwp9Cgp0ZW1wbGF0ZSA8cGF0aGZpbmRlcnM6OkhldXJpc3RpYyBILCBwYXRoZmluZGVyczo6TW92ZW1lbnRUeXBlIE0+CnZvaWQgcGF0aGZpbmRlcnM6OkFTUEY8SCwgTT46OnNldEJlZ2luKENlbGwgY29uc3QmIGJlZ2luKSB7CiAgICBtQmVnaW4gPSB7CiAgICAgICAgc3RkOjptYXgoMCwgYmVnaW4ueCksCiAgICAgICAgc3RkOjptYXgoMCwgYmVnaW4ueSksCiAgICB9Owp9Cgp0ZW1wbGF0ZSA8cGF0aGZpbmRlcnM6OkhldXJpc3RpYyBILCBwYXRoZmluZGVyczo6TW92ZW1lbnRUeXBlIE0+CnZvaWQgcGF0aGZpbmRlcnM6OkFTUEY8SCwgTT46OnNldEVuZChDZWxsIGNvbnN0JiBlbmQpIHsKICAgIG1FbmQgPSB7CiAgICAgICAgc3RkOjptaW4oc3RhdGljX2Nhc3Q8aW50PihtR3JpZC5mcm9udCgpLnNpemUoKSkgLSAxLCBlbmQueCksCiAgICAgICAgc3RkOjptaW4oc3RhdGljX2Nhc3Q8aW50PihtR3JpZC5zaXplKCkpIC0gMSwgZW5kLnkpLAogICAgfTsKfQoKdGVtcGxhdGUgPHBhdGhmaW5kZXJzOjpIZXVyaXN0aWMgSCwgcGF0aGZpbmRlcnM6Ok1vdmVtZW50VHlwZSBNPgpwYXRoZmluZGVyczo6UmVzdWx0IHBhdGhmaW5kZXJzOjpBU1BGPEgsIE0+OjpzZWFyY2goQ2VsbCBjb25zdCYgc3JjLCBDZWxsIGNvbnN0JiBkZXN0KSBjb25zdCB7CiAgICBpZiAobUdyaWQuZW1wdHkoKSkgcmV0dXJuIFJlc3VsdChTdGF0dXM6OmtGYWlsdXJlKTsKICAgIAogICAgaWYgKCFpc1ZhbGlkKHNyYykpIHJldHVybiBSZXN1bHQoU3RhdHVzOjprSW52YWxpZFNyYyk7CiAgICBpZiAoIWlzVmFsaWQoZGVzdCkpIHJldHVybiBSZXN1bHQoU3RhdHVzOjprSW52YWxpZERlc3QpOwogICAgaWYgKCFpc1VuYmxvY2tlZChzcmMpKSByZXR1cm4gUmVzdWx0KFN0YXR1czo6a0Jsb2NrZWRTcmMpOwogICAgaWYgKCFpc1VuYmxvY2tlZChkZXN0KSkgcmV0dXJuIFJlc3VsdChTdGF0dXM6OmtCbG9ja2VkRGVzdCk7CiAgICBpZiAoc3JjID09IGRlc3QpIHJldHVybiBSZXN1bHQoU3RhdHVzOjprQ29pbmNpZGVudHMpOwoKICAgIC8vIE5vdGUgdGhhdCBpbmRleC1iYXNlZCBvcGVyYXRpb25zIG9uIHR3byBmb2xsb3dpbmcgbGlzdHMgcmVxdWlyZSBzdWJzdHJhY3RpbmcgYG1CZWdpbmAgdG8gbWF0Y2ggYG1HcmlkYAogICAgLy8gSW5pdGlhbGl6ZSBjbG9zZWQgbGlzdAogICAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8Ym9vbD4+IGNsb3NlZExpc3QobUVuZC55IC0gbUJlZ2luLnkgKyAxLCBzdGQ6OnZlY3Rvcjxib29sPihtRW5kLnggLSBtQmVnaW4ueCArIDEsIGZhbHNlKSk7ICAgLy8gYGZhbHNlYCBtZWFucyBub3QgdmlzaXRlZCAoYW5kIHZpY2UgdmVyc2EpCgogICAgLy8gSW5pdGlhbGl6ZSBjZWxsIGRhdGEgbGlzdAogICAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8Q2VsbDo6RGF0YT4+IGNlbGxEYXRhTGlzdChtRW5kLnkgLSBtQmVnaW4ueSArIDEsIHN0ZDo6dmVjdG9yPENlbGw6OkRhdGE+KG1FbmQueCAtIG1CZWdpbi54ICsgMSwgQ2VsbDo6RGF0YXt9KSk7CiAgICAKICAgIC8vIEluaXRpYWxpemUgc3RhcnRpbmcgbm9kZSBwYXJhbWV0ZXJzCiAgICBhdXRvJiBzcmNEYXRhID0gY2VsbERhdGFMaXN0W3NyYy55IC0gbUJlZ2luLnldW3NyYy54IC0gbUJlZ2luLnhdOwogICAgc3JjRGF0YS5mID0gMDsKICAgIHNyY0RhdGEucGFyZW50ID0gc3JjOwoKICAgIC8vIEluaXRpYWxpemUgb3BlbiBsaXN0CiAgICBzdGQ6OnN0YWNrPENlbGw+IG9wZW5MaXN0OyAgIC8vIEZvciBvcGVyYXRpb25zIGF0IE8oMSkgdGltZSBjb21wbGV4aXR5CiAgICBvcGVuTGlzdC5wdXNoKHNyYyk7ICAgLy8gUGxhY2UgdGhlIHN0YXJ0aW5nIGNlbGwgb24gdGhlIG9wZW4gbGlzdAoKICAgIGRvdWJsZSBnLCBoLCBmOwoKICAgIHdoaWxlICghb3Blbkxpc3QuZW1wdHkoKSkgewogICAgICAgIGcgPSBoID0gZiA9IDA7CgogICAgICAgIGF1dG8gcGFyZW50ID0gb3Blbkxpc3QudG9wKCk7CiAgICAgICAgb3Blbkxpc3QucG9wKCk7ICAgLy8gUmVtb3ZlIGNlbGwgZnJvbSBvcGVuIGxpc3QKICAgICAgICBjbG9zZWRMaXN0W3BhcmVudC55IC0gbUJlZ2luLnldW3BhcmVudC54IC0gbUJlZ2luLnhdID0gdHJ1ZTsgICAvLyBBZGQgY2VsbCB0byBjbG9zZWQgbGlzdAoKICAgICAgICAvLyBHZW5lcmF0ZSBhbGwgc3VjY2Vzc29ycwogICAgICAgIGZvciAoY29uc3QgYXV0byYgZGlyZWN0aW9uIDogbURpcmVjdGlvbnMpIHsKICAgICAgICAgICAgYXV0byBzdWNjZXNzb3IgPSBwYXJlbnQgKyBkaXJlY3Rpb247CiAgICAgICAgICAgIGlmICghaXNWYWxpZChzdWNjZXNzb3IpKSBjb250aW51ZTsKCiAgICAgICAgICAgIC8vIElmIHN1Y2Nlc3NvciBpcyBkZXN0aW5hdGlvbiwgc2VhcmNoIGlzIGNvbnNpZGVyZWQgc3VjY2Vzc2Z1bAogICAgICAgICAgICBpZiAoc3VjY2Vzc29yID09IGRlc3QpIHsKICAgICAgICAgICAgICAgIGNlbGxEYXRhTGlzdFtzdWNjZXNzb3IueSAtIG1CZWdpbi55XVtzdWNjZXNzb3IueCAtIG1CZWdpbi54XS5wYXJlbnQgPSBwYXJlbnQ7CiAgICAgICAgICAgICAgICByZXR1cm4gUmVzdWx0KFN0YXR1czo6a1N1Y2Nlc3MsIGdldFBhdGgoY2VsbERhdGFMaXN0LCBkZXN0KSk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIC8vIElnbm9yZSBpZiBzdWNjZXNzb3IgaXMgYWxyZWFkeSBvbiB0aGUgY2xvc2VkIGxpc3Qgb3IgaXMgYmxvY2tlZAogICAgICAgICAgICBpZiAoIWNsb3NlZExpc3Rbc3VjY2Vzc29yLnkgLSBtQmVnaW4ueV1bc3VjY2Vzc29yLnggLSBtQmVnaW4ueF0gJiYgaXNVbmJsb2NrZWQoc3VjY2Vzc29yKSkgewogICAgICAgICAgICAgICAgZyA9IGNlbGxEYXRhTGlzdFtwYXJlbnQueSAtIG1CZWdpbi55XVtwYXJlbnQueCAtIG1CZWdpbi54XS5nICsgQ2VsbDo6Z2V0RyhkaXJlY3Rpb24pOwogICAgICAgICAgICAgICAgaCA9IENlbGw6OmdldEg8SD4oc3VjY2Vzc29yLCBkZXN0KTsKICAgICAgICAgICAgICAgIGYgPSBnICsgaDsKCiAgICAgICAgICAgICAgICBhdXRvJiBzdWNjZXNzb3JEYXRhID0gY2VsbERhdGFMaXN0W3N1Y2Nlc3Nvci55IC0gbUJlZ2luLnldW3N1Y2Nlc3Nvci54IC0gbUJlZ2luLnhdOwoKICAgICAgICAgICAgICAgIC8vIEFkZCBzdWNjZXNzb3IgdG8gdGhlIG9wZW4gbGlzdCBpZiBzdWNjZXNzb3IgaXMgbm90IG9uIHRoZSBvcGVuIGxpc3Qgb3IgcHJvdmlkZXMgYSBiZXR0ZXIgcGF0aAogICAgICAgICAgICAgICAgaWYgKHN1Y2Nlc3NvckRhdGEuZiA9PSBzdGQ6Om51bWVyaWNfbGltaXRzPGRvdWJsZT46Om1heCgpIHx8IHN1Y2Nlc3NvckRhdGEuZiA+IGYpIHsKICAgICAgICAgICAgICAgICAgICBvcGVuTGlzdC5wdXNoKHN1Y2Nlc3Nvcik7CgogICAgICAgICAgICAgICAgICAgIC8vIFVwZGF0ZSBzdWNjZXNzb3IgZGF0YQogICAgICAgICAgICAgICAgICAgIHN1Y2Nlc3NvckRhdGEuZiA9IGY7CiAgICAgICAgICAgICAgICAgICAgc3VjY2Vzc29yRGF0YS5nID0gZzsKICAgICAgICAgICAgICAgICAgICBzdWNjZXNzb3JEYXRhLmggPSBoOwogICAgICAgICAgICAgICAgICAgIHN1Y2Nlc3NvckRhdGEucGFyZW50ID0gcGFyZW50OwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIC8vIFNlYXJjaCBpcyBjb25zaWRlcmVkIHVuc3VjY2Vzc2Z1bCBpZiB0aGUgb3BlbiBsaXN0IGlzIGVtcHRpZWQgYmVmb3JlIGRlc3RpbmF0aW9uIGNlbGwgaXMgZm91bmQKICAgIHJldHVybiBSZXN1bHQoU3RhdHVzOjprRmFpbHVyZSk7Cn0KCi8qKgogKiBAbm90ZSBPbmx5IHJldHVybnMgZGlyZWN0aW9uLgoqLwp0ZW1wbGF0ZSA8cGF0aGZpbmRlcnM6OkhldXJpc3RpYyBILCBwYXRoZmluZGVyczo6TW92ZW1lbnRUeXBlIE0+CnBhdGhmaW5kZXJzOjpSZXN1bHQgcGF0aGZpbmRlcnM6OkFTUEY8SCwgTT46OnF1aWNrc2VhcmNoKENlbGwgY29uc3QmIHNyYywgQ2VsbCBjb25zdCYgZGVzdCkgY29uc3QgewogICAgLy8gUHJlLWNoZWNrcyBhcyB1c3VhbAogICAgaWYgKG1HcmlkLmVtcHR5KCkpIHJldHVybiBSZXN1bHQoU3RhdHVzOjprRmFpbHVyZSk7CiAgICAKICAgIGlmICghaXNWYWxpZChzcmMpKSByZXR1cm4gUmVzdWx0KFN0YXR1czo6a0ludmFsaWRTcmMpOwogICAgaWYgKCFpc1ZhbGlkKGRlc3QpKSByZXR1cm4gUmVzdWx0KFN0YXR1czo6a0ludmFsaWREZXN0KTsKICAgIGlmICghaXNVbmJsb2NrZWQoc3JjKSkgcmV0dXJuIFJlc3VsdChTdGF0dXM6OmtCbG9ja2VkU3JjKTsKICAgIGlmICghaXNVbmJsb2NrZWQoZGVzdCkpIHJldHVybiBSZXN1bHQoU3RhdHVzOjprQmxvY2tlZERlc3QpOwogICAgaWYgKHNyYyA9PSBkZXN0KSByZXR1cm4gUmVzdWx0KFN0YXR1czo6a0NvaW5jaWRlbnRzKTsKCiAgICBkb3VibGUgZmMgPSBzdGQ6Om51bWVyaWNfbGltaXRzPGRvdWJsZT46Om1pbigpOwogICAgQ2VsbCBkaXJlY3Rpb25jOwoKICAgIGZvciAoY29uc3QgYXV0byYgZGlyZWN0aW9uIDogbURpcmVjdGlvbnMpIHsKICAgICAgICBhdXRvIHN1Y2Nlc3NvciA9IHNyYyArIGRpcmVjdGlvbjsKICAgICAgICBpZiAoIWlzVmFsaWQoc3VjY2Vzc29yKSB8fCAhaXNVbmJsb2NrZWQoc3VjY2Vzc29yKSkgY29udGludWU7CgogICAgICAgIGlmIChzdWNjZXNzb3IgPT0gZGVzdCkgcmV0dXJuIFJlc3VsdChTdGF0dXM6OmtTdWNjZXNzLCBkaXJlY3Rpb24pOyAgIC8vIElmIHN1Y2Nlc3NvciBpcyBkZXN0aW5hdGlvbiwgc2VhcmNoIGlzIGNvbnNpZGVyZWQgc3VjY2Vzc2Z1bAoKICAgICAgICAvLyBDYWxjdWxhdGUgYGZgIHZhbHVlIG9mIHN1Y2Nlc3NvcgogICAgICAgIGRvdWJsZSBmID0gc3RkOjpzcXJ0KHN0ZDo6cG93KGRpcmVjdGlvbi54LCAyKSArIHN0ZDo6cG93KGRpcmVjdGlvbi55LCAyKSkgKyBDZWxsOjpnZXRIPEg+KHN1Y2Nlc3NvciwgZGVzdCk7CgogICAgICAgIC8vIENhY2hlIHRoZSBzdWNjZXNzb3IgaWYgaXQgcHJvdmlkZXMgYSBiZXR0ZXIgcGF0aAogICAgICAgIGlmIChmID4gZmMpIHsKICAgICAgICAgICAgZmMgPSBmOwogICAgICAgICAgICBkaXJlY3Rpb25jID0gZGlyZWN0aW9uOwogICAgICAgIH0gCiAgICB9CgogICAgLy8gU2VhcmNoIGlzIGNvbnNpZGVyZWQgdW5zdWNjZXNzZnVsIGlmIHRoZSBvcGVuIGxpc3QgaXMgZW1wdGllZCBiZWZvcmUgZGVzdGluYXRpb24gY2VsbCBpcyBmb3VuZAogICAgcmV0dXJuIGZjID09IHN0ZDo6bnVtZXJpY19saW1pdHM8ZG91YmxlPjo6bWluKCkgPyBSZXN1bHQoU3RhdHVzOjprRmFpbHVyZSkgOiBSZXN1bHQoU3RhdHVzOjprU3VjY2VzcywgZGlyZWN0aW9uYyk7Cn0KCgp0ZW1wbGF0ZSBjbGFzcyBwYXRoZmluZGVyczo6QVNQRjxwYXRoZmluZGVyczo6SGV1cmlzdGljOjprTWFuaGF0dGFuLCBwYXRoZmluZGVyczo6TW92ZW1lbnRUeXBlOjprNERpcmVjdGlvbmFsPjsKCgojZGVmaW5lIFJVTihoLCBtLCB0KSBcCmRvIHtcCglkb3VibGUgc3VtID0gMDtcCglcCglhdXRvIG9iaiA9IHBhdGhmaW5kZXJzOjpBU1BGPGgsIG0+KHZlYyk7XAoJb2JqLnNldEJlZ2luKHNyYyAtIHJhbmdlKTtcCglvYmouc2V0RW5kKHNyYyArIHJhbmdlKTtcCglcCglmb3IgKGludCBpID0gMDsgaSA8IHRpbWVzOyArK2kpIHtcCgkJYXV0byBzdGFydCA9IHN0ZDo6Y2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpO1wKCVwKCQlhdXRvIHJlcyA9IG9iai5zZWFyY2goc3JjLCBkZXN0KTtcCgkJYXV0byBkaXIgPSBvYmoucXVpY2tzZWFyY2goc3JjLCBkZXN0KTtcCglcCgkJYXV0byBlbmQgPSBzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTtcCgkJYXV0byBkdXJhdGlvbiA9IHN0ZDo6Y2hyb25vOjpkdXJhdGlvbl9jYXN0PHN0ZDo6Y2hyb25vOjptaWNyb3NlY29uZHM+KGVuZCAtIHN0YXJ0KTtcCgkJc3VtICs9IGR1cmF0aW9uLmNvdW50KCk7XAoJfVwKCVwKCXN0ZDo6Y291dCA8PCBzdGF0aWNfY2FzdDxpbnQ+KGgpIDw8ICItIiA8PCBzdGF0aWNfY2FzdDxpbnQ+KG0pIDw8ICIgOiAiIDw8IHN1bSAvIHRpbWVzIDw8ICIgbXMiIDw8IHN0ZDo6ZW5kbDtcCn0gd2hpbGUgKDApOwoKI2RlZmluZSBSVU5NKGgsIHQpIFwKCVJVTihoLCBwYXRoZmluZGVyczo6TW92ZW1lbnRUeXBlOjprNERpcmVjdGlvbmFsLCB0KTtcCglSVU4oaCwgcGF0aGZpbmRlcnM6Ok1vdmVtZW50VHlwZTo6azhEaXJlY3Rpb25hbCwgdCk7CgojZGVmaW5lIFJVTkhNKHQpIFwKZG8ge1wKCVJVTk0ocGF0aGZpbmRlcnM6OkhldXJpc3RpYzo6a01hbmhhdHRhbiwgdClcCglSVU5NKHBhdGhmaW5kZXJzOjpIZXVyaXN0aWM6OmtDaGVieXNoZXYsIHQpXAoJUlVOTShwYXRoZmluZGVyczo6SGV1cmlzdGljOjprT2N0aWxlLCB0KVwKCVJVTk0ocGF0aGZpbmRlcnM6OkhldXJpc3RpYzo6a0V1Y2xpZGVhbiwgdClcCglSVU5NKHBhdGhmaW5kZXJzOjpIZXVyaXN0aWM6OmtDb25zdGFudFplcm8sIHQpXAoJUlVOTShwYXRoZmluZGVyczo6SGV1cmlzdGljOjprQ29udGFudEluZiwgdClcCn0gd2hpbGUgKDApOwoKCi8qICogKiAqICogKiAqLwppbnQgbWFpbih2b2lkKSB7CiAgICBzdGQ6OnZlY3RvcjxzdGQ6OnZlY3RvcjxpbnQ+PiB2ZWMgPSB7Cnt7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAp7eyAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCB9fSwKe3sgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgfX0sCnt7IDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIDU4ODksIDAsIDAsIDU4ODksIH19LAp7eyA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LAogNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgfX0sCnt7IDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDAsIDAsIDAsIDAsIDAsIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIH19LAp7eyA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCB9fSwKe3sgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgMCwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgfX0sCnt7IDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIH19LAp7eyA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCB9fSwKe3sgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgfX0sCnt7IDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIH19LAp7eyA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCB9fSwKe3sgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgfX0sCnt7IDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIH19LAp7eyA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCB9fSwKe3sgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgNTg4OSwgfX0sCnt7IDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIDU4ODksIH19LAp7eyA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCA1ODg5LCB9fSwKe3sgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgNTg4OSwgMCwgMCwgNTg4OSwgfX0sCnt7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAp7eyAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCB9fSwKe3sgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgfX0sCnt7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAp7eyAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCB9fSwKICAgIH07CgogICAgLy8gaW5wdXQgaXMgbm90IGludmVydGVkCiAgICBjb25zdCBwYXRoZmluZGVyczo6Q2VsbCBzcmMgPSB7IDExMjAgLyAzMiwgMzg0IC8gMzIgfTsKICAgIGNvbnN0IHBhdGhmaW5kZXJzOjpDZWxsIGRlc3QgPSB7IDMyIC8gMzIsIDM4NCAvIDMyIH07CiAgICBjb25zdCBwYXRoZmluZGVyczo6Q2VsbCByYW5nZSA9IHsgc3RkOjpudW1lcmljX2xpbWl0czxzaG9ydD46Om1heCgpLCBzdGQ6Om51bWVyaWNfbGltaXRzPHNob3J0Pjo6bWF4KCkgfTsKCgljb25zdGV4cHIgc3RkOjpzaXplX3QgdGltZXMgPSAxZTI7CglzdGQ6OmNvdXQgPDwgIlJ1bm5pbmcgdGVzdHMgZm9yIHQgPSAiIDw8IHRpbWVzIDw8IHN0ZDo6ZW5kbDsKCVJVTkhNKHQpOwoKCS8vIGZvciAoaW50IGkgPSAwOyBpIDwgdGltZXM7ICsraSkgewoJLy8gCWF1dG8gb2JqID0gcGF0aGZpbmRlcnM6OkFTUEY8aCwgbT4odmVjKTsKCS8vIAlvYmouc2V0QmVnaW4oc3JjIC0gcmFuZ2UpOwoJLy8gCW9iai5zZXRFbmQoc3JjICsgcmFuZ2UpOwoKCS8vIAlhdXRvIHN0YXJ0ID0gc3RkOjpjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CgoJLy8gCWF1dG8gcmVzID0gb2JqLnNlYXJjaChzcmMsIGRlc3QpOwoJLy8gCWF1dG8gZGlyID0gb2JqLnF1aWNrc2VhcmNoKHNyYywgZGVzdCk7CgoJLy8gCWF1dG8gZW5kID0gc3RkOjpjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CgkvLyAJYXV0byBkdXJhdGlvbiA9IHN0ZDo6Y2hyb25vOjpkdXJhdGlvbl9jYXN0PHN0ZDo6Y2hyb25vOjptaWNyb3NlY29uZHM+KGVuZCAtIHN0YXJ0KTsKCS8vIAlzdW0gKz0gZHVyYXRpb24uY291bnQoKTsKCS8vIH0KCgkvLyBzdGQ6OmNvdXQgPDwgc3RhdGljX2Nhc3Q8aW50PihoKSA8PCAiLSIgPDwgc3RhdGljX2Nhc3Q8aW50PihtKSA8PCAiIDogIiA8PCBzdW0gLyB0aW1lcyA8PCAiIG1zIiA8PCBzdGQ6OmVuZGw7CgoJCgogICAgLy8gc3RkOjpjb3V0IDw8ICJFeGVjdXRpb24gdGltZTogIiA8PCBkdXJhdGlvbi5jb3VudCgpIDw8ICIgbXMiIDw8IHN0ZDo6ZW5kbDsKICAgIC8vIHN0ZDo6Y291dCA8PCAiU3RhdHVzOiAiIDw8IHN0YXRpY19jYXN0PGludD4ocmVzLnN0YXR1cykgPDwgc3RkOjplbmRsOwoKICAgIC8vIGF1dG8gcGF0aCA9IHJlcy5wYXRoOwogICAgLy8gd2hpbGUgKHBhdGguc2l6ZSgpID4gMSkgewogICAgLy8gICAgIHN0ZDo6Y291dCA8PCAiKCIgPDwgcGF0aC50b3AoKS54IDw8ICIsICIgPDwgcGF0aC50b3AoKS55IDw8ICIpIC0+ICI7CiAgICAvLyAgICAgcGF0aC5wb3AoKTsKICAgIC8vIH0KICAgIC8vIHN0ZDo6Y291dCA8PCBwYXRoLnRvcCgpIDw8IHN0ZDo6ZW5kbDsKCiAgICAvLyBzdGQ6OmNvdXQgPDwgIlN0YXR1cy1kaXI6ICIgPDwgc3RhdGljX2Nhc3Q8aW50PihkaXIuc3RhdHVzKSA8PCBzdGQ6OmVuZGw7CiAgICAvLyBzdGQ6OmNvdXQgPDwgZGlyLnBhdGgudG9wKCkueCA8PCAiLCAiIDw8IGRpci5wYXRoLnRvcCgpLnkgPDwgc3RkOjplbmRsOwoKICAgIHJldHVybiAwOwp9