#include <vector>
#include <functional>
#include <stack>
#include <array>
#include <iostream>
#include <limits>
#include <unordered_set>
#include <cmath>
#include <chrono>
/**
* @brief Implementation of A* pathfinding algorithm.
* @see https://w...content-available-to-author-only...s.org/a-search-algorithm/
*/
class ASPFWrapper {
public:
enum class Heuristic : unsigned char {
kManhattan, // Best for 4-directional
kDiagonal, // Best for 8-directional
kEuclidean, // Works for any directions
};
enum class MovementType : bool {
k4Directional,
k8Directional,
};
enum class Status : unsigned char {
kInvalidSrc,
kInvalidDest,
kBlockedSrc,
kBlockedDest,
kCoincidents,
kSuccess,
kFailure,
};
template <typename T = int>
struct Cell {
T 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 }; }
friend inline std::ostream& operator<<(std::ostream& os, Cell const& self) { return os << '(' << self.x << ", " << self.y << ')'; }
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::kDiagonal, 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);
struct Data {
Cell parent;
double g, h, f = std::numeric_limits<double>::max();
};
};
struct Result {
const Status status;
const std::stack<Cell<>> path;
Result(Status status, std::stack<Cell<>> path = {}) : status(status), path(path) {}
};
template <Heuristic H, MovementType M>
class ASPF {
public:
inline ASPF(std::vector<std::vector<int>> const& grid);
~ASPF() = default;
void setBegin(Cell<std::size_t> const& begin);
void setEnd(Cell<std::size_t> const& end);
Result search(Cell<> const& src, Cell<> const& dest);
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<std::size_t> mBegin, mEnd;
static inline constexpr auto mDirections = getDirections();
};
template <Heuristic H = Heuristic::kManhattan, MovementType M = MovementType::k4Directional, typename... Args>
static inline ASPF<H, M> instantiate(Args&&... args) {
return ASPF<H, M>(std::forward<Args>(args)...);
}
};
template <typename T>
template <ASPFWrapper::Heuristic H>
typename std::enable_if_t<H == ASPFWrapper::Heuristic::kManhattan, double>
ASPFWrapper::Cell<T>::getH(Cell const& cell, Cell const& dest) {
return std::abs(cell.x - dest.x) + std::abs(cell.y - dest.y);
}
template <typename T>
template <ASPFWrapper::Heuristic H>
typename std::enable_if_t<H == ASPFWrapper::Heuristic::kDiagonal, double>
ASPFWrapper::Cell<T>::getH(Cell const& cell, Cell const& dest) {
static constexpr double kNodeLength = 1;
static constexpr double kNodeDiagonalDistance = std::sqrt(2);
auto dx = std::abs(cell.x - dest.x);
auto dy = std::abs(cell.y - dest.y);
return kNodeLength * (dx + dy) + (kNodeDiagonalDistance - kNodeLength * 2) * std::min(dx, dy);
}
template <typename T>
template <ASPFWrapper::Heuristic H>
typename std::enable_if_t<H == ASPFWrapper::Heuristic::kEuclidean, double>
ASPFWrapper::Cell<T>::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 <ASPFWrapper::Heuristic H, ASPFWrapper::MovementType M>
ASPFWrapper::ASPF<H, M>::ASPF(std::vector<std::vector<int>> const& grid) : mGrid(grid) {
setBegin({ 0, 0 });
setEnd({ 0, 0 });
}
template <ASPFWrapper::Heuristic H, ASPFWrapper::MovementType M>
bool ASPFWrapper::ASPF<H, M>::isValid(Cell<> const& cell) const {
return static_cast<int>(mBegin.x) <= cell.x <= static_cast<int>(mEnd.x) && static_cast<int>(mBegin.y) <= cell.y <= static_cast<int>(mEnd.y);
}
template <ASPFWrapper::Heuristic H, ASPFWrapper::MovementType M>
bool ASPFWrapper::ASPF<H, M>::isUnblocked(Cell<> const& cell) const {
return mGrid.at(cell.y).at(cell.x) != 0;
}
template <ASPFWrapper::Heuristic H, ASPFWrapper::MovementType M>
bool ASPFWrapper::ASPF<H, M>::isUnblocked(Cell<> const& cell, Cell<> const& successor) const {
return mGrid.at(successor.y).at(successor.x) != 0;
}
template <ASPFWrapper::Heuristic H, ASPFWrapper::MovementType M>
std::stack<ASPFWrapper::Cell<>> ASPFWrapper::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.at(curr.y - mBegin.y).at(curr.x - mBegin.x).parent == curr)) {
path.push(curr);
curr = cellData.at(curr.y - mBegin.y).at(curr.x - mBegin.x).parent;
}
path.push(curr);
return path;
}
template <ASPFWrapper::Heuristic H, ASPFWrapper::MovementType M>
void ASPFWrapper::ASPF<H, M>::setBegin(Cell<std::size_t> const& begin) {
mBegin = {
std::max((std::size_t)(0), begin.x),
std::max((std::size_t)(0), begin.y),
};
}
template <ASPFWrapper::Heuristic H, ASPFWrapper::MovementType M>
void ASPFWrapper::ASPF<H, M>::setEnd(Cell<std::size_t> const& end) {
mEnd = {
std::min(mGrid.front().size() - 1, end.x),
std::min(mGrid.size() - 1, end.y),
};
}
template <ASPFWrapper::Heuristic H, ASPFWrapper::MovementType M>
ASPFWrapper::Result ASPFWrapper::ASPF<H, M>::search(Cell<> const& src, Cell<> const& dest) {
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.at(successor.y - mBegin.y).at(successor.x - mBegin.x) && isUnblocked(successor)) {
g = cellDataList[parent.y - mBegin.y][parent.x - mBegin.x].g + std::sqrt(std::pow(direction.x, 2) + std::pow(direction.y, 2));
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);
}
/* * * * * * */
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, 4171, 4171, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
{{ 0, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 0, 4171, 4171, 4171, 0, 0, }},
{{ 0, 4171, 4171, 4171, 0, 0, 4171, 4171, 4171, 0, 4171, 0, 0, 0, 0, }},
{{ 0, 4171, 4171, 4171, 0, 0, 4171, 4171, 4171, 0, 4171, 0, 0, 0, 0, }},
{{ 0, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 0, 0, 0, }},
{{ 0, 0, 0, 0, 4171, 4171, 0, 4171, 4171, 0, 4171, 4171, 0, 0, 0, }},
{{ 0, 0, 0, 0, 4171, 4171, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
{{ 0, 0, 0, 0, 4171, 4171, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
{{ 0, 0, 0, 0, 4171, 4171, 0, 4171, 4171, 4171, 4171, 4171, 0, 0, 0, }},
{{ 0, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 0, 0, 0, 4171, 4171, 4171, 0, }},
{{ 0, 0, 0, 0, 4171, 4171, 0, 4171, 0, 0, 0, 4171, 4171, 4171, 0, }},
{{ 0, 0, 0, 0, 4171, 4171, 0, 4171, 0, 0, 0, 4171, 0, 0, 0, }},
{{ 0, 0, 0, 0, 4171, 4171, 0, 4171, 4171, 4171, 4171, 4171, 0, 0, 0, }},
{{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }},
};
// input is not inverted
ASPFWrapper::Cell<> src = { 12, 4 };
ASPFWrapper::Cell<> dest = { 5, 15 };
auto obj = ASPFWrapper::instantiate(vec);
obj.setBegin({ 1, 1 });
obj.setEnd({ vec.front().size() - 2, vec.size() - 2 });
auto start = std::chrono::high_resolution_clock::now();
auto res = obj.search(src, dest);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
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;
return 0;
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxzdGFjaz4KI2luY2x1ZGUgPGFycmF5PgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxsaW1pdHM+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8Y21hdGg+CgojaW5jbHVkZSA8Y2hyb25vPgoKCi8qKgogKiBAYnJpZWYgSW1wbGVtZW50YXRpb24gb2YgQSogcGF0aGZpbmRpbmcgYWxnb3JpdGhtLgogKiBAc2VlIGh0dHBzOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5vcmcvYS1zZWFyY2gtYWxnb3JpdGhtLwoqLwpjbGFzcyBBU1BGV3JhcHBlciB7CiAgICBwdWJsaWM6CiAgICAgICAgZW51bSBjbGFzcyBIZXVyaXN0aWMgOiB1bnNpZ25lZCBjaGFyIHsKICAgICAgICAgICAga01hbmhhdHRhbiwgICAvLyBCZXN0IGZvciA0LWRpcmVjdGlvbmFsCiAgICAgICAgICAgIGtEaWFnb25hbCwgICAvLyBCZXN0IGZvciA4LWRpcmVjdGlvbmFsCiAgICAgICAgICAgIGtFdWNsaWRlYW4sICAgLy8gV29ya3MgZm9yIGFueSBkaXJlY3Rpb25zCiAgICAgICAgfTsKCiAgICAgICAgZW51bSBjbGFzcyBNb3ZlbWVudFR5cGUgOiBib29sIHsKICAgICAgICAgICAgazREaXJlY3Rpb25hbCwKICAgICAgICAgICAgazhEaXJlY3Rpb25hbCwKICAgICAgICB9OwoKICAgICAgICBlbnVtIGNsYXNzIFN0YXR1cyA6IHVuc2lnbmVkIGNoYXIgewogICAgICAgICAgICBrSW52YWxpZFNyYywKICAgICAgICAgICAga0ludmFsaWREZXN0LAogICAgICAgICAgICBrQmxvY2tlZFNyYywKICAgICAgICAgICAga0Jsb2NrZWREZXN0LAogICAgICAgICAgICBrQ29pbmNpZGVudHMsCgogICAgICAgICAgICBrU3VjY2VzcywKICAgICAgICAgICAga0ZhaWx1cmUsCiAgICAgICAgfTsKCiAgICAgICAgdGVtcGxhdGUgPHR5cGVuYW1lIFQgPSBpbnQ+CiAgICAgICAgc3RydWN0IENlbGwgewogICAgICAgICAgICBUIHgsIHk7CgogICAgICAgICAgICBpbmxpbmUgYm9vbCBvcGVyYXRvcj09KENlbGwgY29uc3QmIG90aGVyKSBjb25zdCB7IHJldHVybiB4ID09IG90aGVyLnggJiYgeSA9PSBvdGhlci55OyB9CiAgICAgICAgICAgIGlubGluZSBDZWxsIG9wZXJhdG9yKyhDZWxsIGNvbnN0JiBvdGhlcikgY29uc3QgeyByZXR1cm4geyB4ICsgb3RoZXIueCwgeSArIG90aGVyLnkgfTsgfQogICAgICAgICAgICBmcmllbmQgaW5saW5lIHN0ZDo6b3N0cmVhbSYgb3BlcmF0b3I8PChzdGQ6Om9zdHJlYW0mIG9zLCBDZWxsIGNvbnN0JiBzZWxmKSB7IHJldHVybiBvcyA8PCAnKCcgPDwgc2VsZi54IDw8ICIsICIgPDwgc2VsZi55IDw8ICcpJzsgfQoKICAgICAgICAgICAgdGVtcGxhdGUgPEhldXJpc3RpYyBIPgogICAgICAgICAgICB0eXBlbmFtZSBzdGQ6OmVuYWJsZV9pZl90PEggPT0gSGV1cmlzdGljOjprTWFuaGF0dGFuLCBkb3VibGU+CiAgICAgICAgICAgIHN0YXRpYyBnZXRIKENlbGwgY29uc3QmIGxocywgQ2VsbCBjb25zdCYgcmhzKTsKCiAgICAgICAgICAgIHRlbXBsYXRlIDxIZXVyaXN0aWMgSD4KICAgICAgICAgICAgdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IEhldXJpc3RpYzo6a0RpYWdvbmFsLCBkb3VibGU+CiAgICAgICAgICAgIHN0YXRpYyBnZXRIKENlbGwgY29uc3QmIGxocywgQ2VsbCBjb25zdCYgcmhzKTsKCiAgICAgICAgICAgIHRlbXBsYXRlIDxIZXVyaXN0aWMgSD4KICAgICAgICAgICAgdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IEhldXJpc3RpYzo6a0V1Y2xpZGVhbiwgZG91YmxlPgogICAgICAgICAgICBzdGF0aWMgZ2V0SChDZWxsIGNvbnN0JiBsaHMsIENlbGwgY29uc3QmIHJocyk7CgogICAgICAgICAgICBzdHJ1Y3QgRGF0YSB7CiAgICAgICAgICAgICAgICBDZWxsIHBhcmVudDsKICAgICAgICAgICAgICAgIGRvdWJsZSBnLCBoLCBmID0gc3RkOjpudW1lcmljX2xpbWl0czxkb3VibGU+OjptYXgoKTsKICAgICAgICAgICAgfTsKICAgICAgICB9OwoKICAgICAgICBzdHJ1Y3QgUmVzdWx0IHsKICAgICAgICAgICAgY29uc3QgU3RhdHVzIHN0YXR1czsKICAgICAgICAgICAgY29uc3Qgc3RkOjpzdGFjazxDZWxsPD4+IHBhdGg7CgogICAgICAgICAgICBSZXN1bHQoU3RhdHVzIHN0YXR1cywgc3RkOjpzdGFjazxDZWxsPD4+IHBhdGggPSB7fSkgOiBzdGF0dXMoc3RhdHVzKSwgcGF0aChwYXRoKSB7fQogICAgICAgIH07CgogICAgICAgIHRlbXBsYXRlIDxIZXVyaXN0aWMgSCwgTW92ZW1lbnRUeXBlIE0+CiAgICAgICAgY2xhc3MgQVNQRiB7CiAgICAgICAgICAgIHB1YmxpYzoKICAgICAgICAgICAgICAgIGlubGluZSBBU1BGKHN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPGludD4+IGNvbnN0JiBncmlkKTsKICAgICAgICAgICAgICAgIH5BU1BGKCkgPSBkZWZhdWx0OwoKICAgICAgICAgICAgICAgIHZvaWQgc2V0QmVnaW4oQ2VsbDxzdGQ6OnNpemVfdD4gY29uc3QmIGJlZ2luKTsKICAgICAgICAgICAgICAgIHZvaWQgc2V0RW5kKENlbGw8c3RkOjpzaXplX3Q+IGNvbnN0JiBlbmQpOwoKICAgICAgICAgICAgICAgIFJlc3VsdCBzZWFyY2goQ2VsbDw+IGNvbnN0JiBzcmMsIENlbGw8PiBjb25zdCYgZGVzdCk7CgogICAgICAgICAgICBwcml2YXRlOgogICAgICAgICAgICAgICAgYm9vbCBpc1ZhbGlkKENlbGw8PiBjb25zdCYgY2VsbCkgY29uc3Q7CiAgICAgICAgICAgICAgICBib29sIGlzVW5ibG9ja2VkKENlbGw8PiBjb25zdCYgY2VsbCkgY29uc3Q7CiAgICAgICAgICAgICAgICBib29sIGlzVW5ibG9ja2VkKENlbGw8PiBjb25zdCYgcGFyZW50LCBDZWxsPD4gY29uc3QmIHN1Y2Nlc3NvcikgY29uc3Q7CgogICAgICAgICAgICAgICAgc3RkOjpzdGFjazxDZWxsPD4+IGdldFBhdGgoc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8Q2VsbDw+OjpEYXRhPj4gY29uc3QmIGNlbGxEYXRhLCBDZWxsPD4gY29uc3QmIGRlc3QpIGNvbnN0OwoKICAgICAgICAgICAgICAgIHN0YXRpYyBpbmxpbmUgY29uc3RleHByIGF1dG8gZ2V0RGlyZWN0aW9ucygpIHsKICAgICAgICAgICAgICAgICAgICBpZiBjb25zdGV4cHIoTSA9PSBNb3ZlbWVudFR5cGU6Oms0RGlyZWN0aW9uYWwpIHsKICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHN0ZDo6YXJyYXk8Q2VsbDw+LCA0Pnt7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7IDEsIDAgfSwgeyAtMSwgMCB9LCB7IDAsIDEgfSwgeyAwLCAtMSB9LAogICAgICAgICAgICAgICAgICAgICAgICB9fTsKICAgICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gc3RkOjphcnJheTxDZWxsPD4sIDg+e3sKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsgMSwgMCB9LCB7IC0xLCAwIH0sIHsgMCwgMSB9LCB7IDAsIC0xIH0sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7IDEsIDEgfSwgeyAxLCAtMSB9LCB7IC0xLCAxIH0sIHsgLTEsIC0xIH0sCiAgICAgICAgICAgICAgICAgICAgICAgIH19OwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBzdGQ6OnZlY3RvcjxzdGQ6OnZlY3RvcjxpbnQ+PiBjb25zdCYgbUdyaWQ7CiAgICAgICAgICAgICAgICBDZWxsPHN0ZDo6c2l6ZV90PiBtQmVnaW4sIG1FbmQ7CgogICAgICAgICAgICAgICAgc3RhdGljIGlubGluZSBjb25zdGV4cHIgYXV0byBtRGlyZWN0aW9ucyA9IGdldERpcmVjdGlvbnMoKTsKICAgICAgICB9OwoKICAgICAgICB0ZW1wbGF0ZSA8SGV1cmlzdGljIEggPSBIZXVyaXN0aWM6OmtNYW5oYXR0YW4sIE1vdmVtZW50VHlwZSBNID0gTW92ZW1lbnRUeXBlOjprNERpcmVjdGlvbmFsLCB0eXBlbmFtZS4uLiBBcmdzPgogICAgICAgIHN0YXRpYyBpbmxpbmUgQVNQRjxILCBNPiBpbnN0YW50aWF0ZShBcmdzJiYuLi4gYXJncykgewogICAgICAgICAgICByZXR1cm4gQVNQRjxILCBNPihzdGQ6OmZvcndhcmQ8QXJncz4oYXJncykuLi4pOwogICAgICAgIH0KfTsKCgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4KdGVtcGxhdGUgPEFTUEZXcmFwcGVyOjpIZXVyaXN0aWMgSD4KdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IEFTUEZXcmFwcGVyOjpIZXVyaXN0aWM6OmtNYW5oYXR0YW4sIGRvdWJsZT4KQVNQRldyYXBwZXI6OkNlbGw8VD46OmdldEgoQ2VsbCBjb25zdCYgY2VsbCwgQ2VsbCBjb25zdCYgZGVzdCkgewogICAgcmV0dXJuIHN0ZDo6YWJzKGNlbGwueCAtIGRlc3QueCkgKyBzdGQ6OmFicyhjZWxsLnkgLSBkZXN0LnkpOwp9Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4KdGVtcGxhdGUgPEFTUEZXcmFwcGVyOjpIZXVyaXN0aWMgSD4KdHlwZW5hbWUgc3RkOjplbmFibGVfaWZfdDxIID09IEFTUEZXcmFwcGVyOjpIZXVyaXN0aWM6OmtEaWFnb25hbCwgZG91YmxlPgpBU1BGV3JhcHBlcjo6Q2VsbDxUPjo6Z2V0SChDZWxsIGNvbnN0JiBjZWxsLCBDZWxsIGNvbnN0JiBkZXN0KSB7CiAgICBzdGF0aWMgY29uc3RleHByIGRvdWJsZSBrTm9kZUxlbmd0aCA9IDE7CiAgICBzdGF0aWMgY29uc3RleHByIGRvdWJsZSBrTm9kZURpYWdvbmFsRGlzdGFuY2UgPSBzdGQ6OnNxcnQoMik7CgogICAgYXV0byBkeCA9IHN0ZDo6YWJzKGNlbGwueCAtIGRlc3QueCk7CiAgICBhdXRvIGR5ID0gc3RkOjphYnMoY2VsbC55IC0gZGVzdC55KTsKICAgIHJldHVybiBrTm9kZUxlbmd0aCAqIChkeCArIGR5KSArIChrTm9kZURpYWdvbmFsRGlzdGFuY2UgLSBrTm9kZUxlbmd0aCAqIDIpICogc3RkOjptaW4oZHgsIGR5KTsKfQoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+CnRlbXBsYXRlIDxBU1BGV3JhcHBlcjo6SGV1cmlzdGljIEg+CnR5cGVuYW1lIHN0ZDo6ZW5hYmxlX2lmX3Q8SCA9PSBBU1BGV3JhcHBlcjo6SGV1cmlzdGljOjprRXVjbGlkZWFuLCBkb3VibGU+CkFTUEZXcmFwcGVyOjpDZWxsPFQ+OjpnZXRIKENlbGwgY29uc3QmIGNlbGwsIENlbGwgY29uc3QmIGRlc3QpIHsKICAgIHJldHVybiBzdGQ6OnNxcnQoc3RkOjpwb3coY2VsbC54IC0gZGVzdC54LCAyKSArIHN0ZDo6cG93KGNlbGwueSAtIGRlc3QueSwgMikpOwp9Cgp0ZW1wbGF0ZSA8QVNQRldyYXBwZXI6OkhldXJpc3RpYyBILCBBU1BGV3JhcHBlcjo6TW92ZW1lbnRUeXBlIE0+CkFTUEZXcmFwcGVyOjpBU1BGPEgsIE0+OjpBU1BGKHN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPGludD4+IGNvbnN0JiBncmlkKSA6IG1HcmlkKGdyaWQpIHsKICAgIHNldEJlZ2luKHsgMCwgMCB9KTsKICAgIHNldEVuZCh7IDAsIDAgfSk7Cn0KCnRlbXBsYXRlIDxBU1BGV3JhcHBlcjo6SGV1cmlzdGljIEgsIEFTUEZXcmFwcGVyOjpNb3ZlbWVudFR5cGUgTT4KYm9vbCBBU1BGV3JhcHBlcjo6QVNQRjxILCBNPjo6aXNWYWxpZChDZWxsPD4gY29uc3QmIGNlbGwpIGNvbnN0IHsKICAgIHJldHVybiBzdGF0aWNfY2FzdDxpbnQ+KG1CZWdpbi54KSA8PSBjZWxsLnggPD0gc3RhdGljX2Nhc3Q8aW50PihtRW5kLngpICYmIHN0YXRpY19jYXN0PGludD4obUJlZ2luLnkpIDw9IGNlbGwueSA8PSBzdGF0aWNfY2FzdDxpbnQ+KG1FbmQueSk7Cn0KCnRlbXBsYXRlIDxBU1BGV3JhcHBlcjo6SGV1cmlzdGljIEgsIEFTUEZXcmFwcGVyOjpNb3ZlbWVudFR5cGUgTT4KYm9vbCBBU1BGV3JhcHBlcjo6QVNQRjxILCBNPjo6aXNVbmJsb2NrZWQoQ2VsbDw+IGNvbnN0JiBjZWxsKSBjb25zdCB7CiAgICByZXR1cm4gbUdyaWQuYXQoY2VsbC55KS5hdChjZWxsLngpICE9IDA7Cn0KCnRlbXBsYXRlIDxBU1BGV3JhcHBlcjo6SGV1cmlzdGljIEgsIEFTUEZXcmFwcGVyOjpNb3ZlbWVudFR5cGUgTT4KYm9vbCBBU1BGV3JhcHBlcjo6QVNQRjxILCBNPjo6aXNVbmJsb2NrZWQoQ2VsbDw+IGNvbnN0JiBjZWxsLCBDZWxsPD4gY29uc3QmIHN1Y2Nlc3NvcikgY29uc3QgewogICAgcmV0dXJuIG1HcmlkLmF0KHN1Y2Nlc3Nvci55KS5hdChzdWNjZXNzb3IueCkgIT0gMDsKfQoKdGVtcGxhdGUgPEFTUEZXcmFwcGVyOjpIZXVyaXN0aWMgSCwgQVNQRldyYXBwZXI6Ok1vdmVtZW50VHlwZSBNPgpzdGQ6OnN0YWNrPEFTUEZXcmFwcGVyOjpDZWxsPD4+IEFTUEZXcmFwcGVyOjpBU1BGPEgsIE0+OjpnZXRQYXRoKHN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPENlbGw8Pjo6RGF0YT4+IGNvbnN0JiBjZWxsRGF0YSwgQ2VsbDw+IGNvbnN0JiBkZXN0KSBjb25zdCB7CiAgICBzdGQ6OnN0YWNrPENlbGw8Pj4gcGF0aDsKICAgIGF1dG8gY3VyciA9IGRlc3Q7CgogICAgd2hpbGUgKCEoY2VsbERhdGEuYXQoY3Vyci55IC0gbUJlZ2luLnkpLmF0KGN1cnIueCAtIG1CZWdpbi54KS5wYXJlbnQgPT0gY3VycikpIHsKICAgICAgICBwYXRoLnB1c2goY3Vycik7CiAgICAgICAgY3VyciA9IGNlbGxEYXRhLmF0KGN1cnIueSAtIG1CZWdpbi55KS5hdChjdXJyLnggLSBtQmVnaW4ueCkucGFyZW50OwogICAgfQoKICAgIHBhdGgucHVzaChjdXJyKTsKICAgIHJldHVybiBwYXRoOwp9Cgp0ZW1wbGF0ZSA8QVNQRldyYXBwZXI6OkhldXJpc3RpYyBILCBBU1BGV3JhcHBlcjo6TW92ZW1lbnRUeXBlIE0+CnZvaWQgQVNQRldyYXBwZXI6OkFTUEY8SCwgTT46OnNldEJlZ2luKENlbGw8c3RkOjpzaXplX3Q+IGNvbnN0JiBiZWdpbikgewogICAgbUJlZ2luID0gewogICAgICAgIHN0ZDo6bWF4KChzdGQ6OnNpemVfdCkoMCksIGJlZ2luLngpLAogICAgICAgIHN0ZDo6bWF4KChzdGQ6OnNpemVfdCkoMCksIGJlZ2luLnkpLAogICAgfTsKfQoKdGVtcGxhdGUgPEFTUEZXcmFwcGVyOjpIZXVyaXN0aWMgSCwgQVNQRldyYXBwZXI6Ok1vdmVtZW50VHlwZSBNPgp2b2lkIEFTUEZXcmFwcGVyOjpBU1BGPEgsIE0+OjpzZXRFbmQoQ2VsbDxzdGQ6OnNpemVfdD4gY29uc3QmIGVuZCkgewogICAgbUVuZCA9IHsKICAgICAgICBzdGQ6Om1pbihtR3JpZC5mcm9udCgpLnNpemUoKSAtIDEsIGVuZC54KSwKICAgICAgICBzdGQ6Om1pbihtR3JpZC5zaXplKCkgLSAxLCBlbmQueSksCiAgICB9Owp9Cgp0ZW1wbGF0ZSA8QVNQRldyYXBwZXI6OkhldXJpc3RpYyBILCBBU1BGV3JhcHBlcjo6TW92ZW1lbnRUeXBlIE0+CkFTUEZXcmFwcGVyOjpSZXN1bHQgQVNQRldyYXBwZXI6OkFTUEY8SCwgTT46OnNlYXJjaChDZWxsPD4gY29uc3QmIHNyYywgQ2VsbDw+IGNvbnN0JiBkZXN0KSB7CiAgICBpZiAobUdyaWQuZW1wdHkoKSkgcmV0dXJuIFJlc3VsdChTdGF0dXM6OmtGYWlsdXJlKTsKICAgIAogICAgaWYgKCFpc1ZhbGlkKHNyYykpIHJldHVybiBSZXN1bHQoU3RhdHVzOjprSW52YWxpZFNyYyk7CiAgICBpZiAoIWlzVmFsaWQoZGVzdCkpIHJldHVybiBSZXN1bHQoU3RhdHVzOjprSW52YWxpZERlc3QpOwogICAgaWYgKCFpc1VuYmxvY2tlZChzcmMpKSByZXR1cm4gUmVzdWx0KFN0YXR1czo6a0Jsb2NrZWRTcmMpOwogICAgaWYgKCFpc1VuYmxvY2tlZChkZXN0KSkgcmV0dXJuIFJlc3VsdChTdGF0dXM6OmtCbG9ja2VkRGVzdCk7CiAgICBpZiAoc3JjID09IGRlc3QpIHJldHVybiBSZXN1bHQoU3RhdHVzOjprQ29pbmNpZGVudHMpOwoKICAgIC8vIE5vdGUgdGhhdCBpbmRleC1iYXNlZCBvcGVyYXRpb25zIG9uIHR3byBmb2xsb3dpbmcgbGlzdHMgcmVxdWlyZSBzdWJzdHJhY3RpbmcgYG1CZWdpbmAgdG8gbWF0Y2ggYG1HcmlkYAogICAgLy8gSW5pdGlhbGl6ZSBjbG9zZWQgbGlzdAogICAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8Ym9vbD4+IGNsb3NlZExpc3QobUVuZC55IC0gbUJlZ2luLnkgKyAxLCBzdGQ6OnZlY3Rvcjxib29sPihtRW5kLnggLSBtQmVnaW4ueCArIDEsIGZhbHNlKSk7ICAgLy8gYGZhbHNlYCBtZWFucyBub3QgdmlzaXRlZCAoYW5kIHZpY2UgdmVyc2EpCgogICAgLy8gSW5pdGlhbGl6ZSBjZWxsIGRhdGEgbGlzdAogICAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8Q2VsbDw+OjpEYXRhPj4gY2VsbERhdGFMaXN0KG1FbmQueSAtIG1CZWdpbi55ICsgMSwgc3RkOjp2ZWN0b3I8Q2VsbDw+OjpEYXRhPihtRW5kLnggLSBtQmVnaW4ueCArIDEsIENlbGw8Pjo6RGF0YXt9KSk7CiAgICAKICAgIC8vIEluaXRpYWxpemUgc3RhcnRpbmcgbm9kZSBwYXJhbWV0ZXJzCiAgICBhdXRvJiBzcmNEYXRhID0gY2VsbERhdGFMaXN0W3NyYy55IC0gbUJlZ2luLnldW3NyYy54IC0gbUJlZ2luLnhdOwogICAgc3JjRGF0YS5mID0gMDsKICAgIHNyY0RhdGEucGFyZW50ID0gc3JjOwoKICAgIC8vIEluaXRpYWxpemUgb3BlbiBsaXN0CiAgICBzdGQ6OnN0YWNrPENlbGw8Pj4gb3Blbkxpc3Q7ICAgLy8gRm9yIG9wZXJhdGlvbnMgYXQgTygxKSB0aW1lIGNvbXBsZXhpdHkKICAgIG9wZW5MaXN0LnB1c2goc3JjKTsgICAvLyBQbGFjZSB0aGUgc3RhcnRpbmcgY2VsbCBvbiB0aGUgb3BlbiBsaXN0CgogICAgZG91YmxlIGcsIGgsIGY7CgogICAgd2hpbGUgKCFvcGVuTGlzdC5lbXB0eSgpKSB7CiAgICAgICAgZyA9IGggPSBmID0gMDsKCiAgICAgICAgYXV0byBwYXJlbnQgPSBvcGVuTGlzdC50b3AoKTsKICAgICAgICBvcGVuTGlzdC5wb3AoKTsgICAvLyBSZW1vdmUgY2VsbCBmcm9tIG9wZW4gbGlzdAogICAgICAgIGNsb3NlZExpc3RbcGFyZW50LnkgLSBtQmVnaW4ueV1bcGFyZW50LnggLSBtQmVnaW4ueF0gPSB0cnVlOyAgIC8vIEFkZCBjZWxsIHRvIGNsb3NlZCBsaXN0CgogICAgICAgIC8vIEdlbmVyYXRlIGFsbCBzdWNjZXNzb3JzCiAgICAgICAgZm9yIChjb25zdCBhdXRvJiBkaXJlY3Rpb24gOiBtRGlyZWN0aW9ucykgewogICAgICAgICAgICBhdXRvIHN1Y2Nlc3NvciA9IHBhcmVudCArIGRpcmVjdGlvbjsKICAgICAgICAgICAgaWYgKCFpc1ZhbGlkKHN1Y2Nlc3NvcikpIGNvbnRpbnVlOwoKICAgICAgICAgICAgLy8gSWYgc3VjY2Vzc29yIGlzIGRlc3RpbmF0aW9uLCBzZWFyY2ggaXMgY29uc2lkZXJlZCBzdWNjZXNzZnVsCiAgICAgICAgICAgIGlmIChzdWNjZXNzb3IgPT0gZGVzdCkgewogICAgICAgICAgICAgICAgY2VsbERhdGFMaXN0W3N1Y2Nlc3Nvci55IC0gbUJlZ2luLnldW3N1Y2Nlc3Nvci54IC0gbUJlZ2luLnhdLnBhcmVudCA9IHBhcmVudDsKICAgICAgICAgICAgICAgIHJldHVybiBSZXN1bHQoU3RhdHVzOjprU3VjY2VzcywgZ2V0UGF0aChjZWxsRGF0YUxpc3QsIGRlc3QpKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgLy8gSWdub3JlIGlmIHN1Y2Nlc3NvciBpcyBhbHJlYWR5IG9uIHRoZSBjbG9zZWQgbGlzdCBvciBpcyBibG9ja2VkCiAgICAgICAgICAgIGlmICghY2xvc2VkTGlzdC5hdChzdWNjZXNzb3IueSAtIG1CZWdpbi55KS5hdChzdWNjZXNzb3IueCAtIG1CZWdpbi54KSAmJiBpc1VuYmxvY2tlZChzdWNjZXNzb3IpKSB7CiAgICAgICAgICAgICAgICBnID0gY2VsbERhdGFMaXN0W3BhcmVudC55IC0gbUJlZ2luLnldW3BhcmVudC54IC0gbUJlZ2luLnhdLmcgKyBzdGQ6OnNxcnQoc3RkOjpwb3coZGlyZWN0aW9uLngsIDIpICsgc3RkOjpwb3coZGlyZWN0aW9uLnksIDIpKTsKICAgICAgICAgICAgICAgIGggPSBDZWxsPD46OmdldEg8SD4oc3VjY2Vzc29yLCBkZXN0KTsKICAgICAgICAgICAgICAgIGYgPSBnICsgaDsKCiAgICAgICAgICAgICAgICBhdXRvJiBzdWNjZXNzb3JEYXRhID0gY2VsbERhdGFMaXN0W3N1Y2Nlc3Nvci55IC0gbUJlZ2luLnldW3N1Y2Nlc3Nvci54IC0gbUJlZ2luLnhdOwoKICAgICAgICAgICAgICAgIC8vIEFkZCBzdWNjZXNzb3IgdG8gdGhlIG9wZW4gbGlzdCBpZiBzdWNjZXNzb3IgaXMgbm90IG9uIHRoZSBvcGVuIGxpc3Qgb3IgcHJvdmlkZXMgYSBiZXR0ZXIgcGF0aAogICAgICAgICAgICAgICAgaWYgKHN1Y2Nlc3NvckRhdGEuZiA9PSBzdGQ6Om51bWVyaWNfbGltaXRzPGRvdWJsZT46Om1heCgpIHx8IHN1Y2Nlc3NvckRhdGEuZiA+IGYpIHsKICAgICAgICAgICAgICAgICAgICBvcGVuTGlzdC5wdXNoKHN1Y2Nlc3Nvcik7CgogICAgICAgICAgICAgICAgICAgIC8vIFVwZGF0ZSBzdWNjZXNzb3IgZGF0YQogICAgICAgICAgICAgICAgICAgIHN1Y2Nlc3NvckRhdGEuZiA9IGY7CiAgICAgICAgICAgICAgICAgICAgc3VjY2Vzc29yRGF0YS5nID0gZzsKICAgICAgICAgICAgICAgICAgICBzdWNjZXNzb3JEYXRhLmggPSBoOwogICAgICAgICAgICAgICAgICAgIHN1Y2Nlc3NvckRhdGEucGFyZW50ID0gcGFyZW50OwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIC8vIFNlYXJjaCBpcyBjb25zaWRlcmVkIHVuc3VjY2Vzc2Z1bCBpZiB0aGUgb3BlbiBsaXN0IGlzIGVtcHRpZWQgYmVmb3JlIGRlc3RpbmF0aW9uIGNlbGwgaXMgZm91bmQKICAgIHJldHVybiBSZXN1bHQoU3RhdHVzOjprRmFpbHVyZSk7Cn0KCgovKiAqICogKiAqICogKi8KaW50IG1haW4odm9pZCkgewogICAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8aW50Pj4gdmVjID0gewogICAgICAgIHt7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDAsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDAsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDAsIDAsIDAsIDQxNzEsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIH19LAogICAgICAgIHt7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH19LAogICAgfTsKCiAgICAvLyBpbnB1dCBpcyBub3QgaW52ZXJ0ZWQKICAgIEFTUEZXcmFwcGVyOjpDZWxsPD4gc3JjID0geyAxMiwgNCB9OwogICAgQVNQRldyYXBwZXI6OkNlbGw8PiBkZXN0ID0geyA1LCAxNSB9OwoKICAgIGF1dG8gb2JqID0gQVNQRldyYXBwZXI6Omluc3RhbnRpYXRlKHZlYyk7CiAgICBvYmouc2V0QmVnaW4oeyAxLCAxIH0pOwogICAgb2JqLnNldEVuZCh7IHZlYy5mcm9udCgpLnNpemUoKSAtIDIsIHZlYy5zaXplKCkgLSAyIH0pOwoKICAgIGF1dG8gc3RhcnQgPSBzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsKCiAgICBhdXRvIHJlcyA9IG9iai5zZWFyY2goc3JjLCBkZXN0KTsKCiAgICBhdXRvIGVuZCA9IHN0ZDo6Y2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpOwogICAgYXV0byBkdXJhdGlvbiA9IHN0ZDo6Y2hyb25vOjpkdXJhdGlvbl9jYXN0PHN0ZDo6Y2hyb25vOjptaWNyb3NlY29uZHM+KGVuZCAtIHN0YXJ0KTsKCiAgICBzdGQ6OmNvdXQgPDwgIkV4ZWN1dGlvbiB0aW1lOiAiIDw8IGR1cmF0aW9uLmNvdW50KCkgPDwgIiBtcyIgPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8ICJTdGF0dXM6ICIgPDwgc3RhdGljX2Nhc3Q8aW50PihyZXMuc3RhdHVzKSA8PCBzdGQ6OmVuZGw7CgogICAgYXV0byBwYXRoID0gcmVzLnBhdGg7CiAgICB3aGlsZSAocGF0aC5zaXplKCkgPiAxKSB7CiAgICAgICAgc3RkOjpjb3V0IDw8ICIoIiA8PCBwYXRoLnRvcCgpLnggPDwgIiwgIiA8PCBwYXRoLnRvcCgpLnkgPDwgIikgLT4gIjsKICAgICAgICBwYXRoLnBvcCgpOwogICAgfQogICAgc3RkOjpjb3V0IDw8IHBhdGgudG9wKCkgPDwgc3RkOjplbmRsOwoKICAgIHJldHVybiAwOwp9