// A C++ Program to implement A* Search Algorithm
#include <bits/stdc++.h>
using namespace std;
#define ROW 17
#define COL 15
// Creating a shortcut for int, int pair type
typedef pair<int, int> Pair;
// Creating a shortcut for pair<int, pair<int, int>> type
typedef pair<double, pair<int, int> > pPair;
namespace std {
template <>
struct hash<pPair> {
std::size_t operator()(pPair const& instance) const {
return std::hash<double>()(instance.first) ^ std::hash<int>()(instance.second.first) ^ std::hash<int>()(instance.second.second);
}
};
}
// A structure to hold the necessary parameters
struct cell {
// Row and Column index of its parent
// Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
int parent_i, parent_j;
// f = g + h
double f, g, h;
};
// A Utility Function to check whether given cell (row, col)
// is a valid cell or not.
bool isValid(int row, int col)
{
// Returns true if row number and column number
// is in range
return (row >= 0) && (row < ROW) && (col >= 0)
&& (col < COL);
}
// A Utility Function to check whether the given cell is
// blocked or not
bool isUnBlocked(int grid[][COL], int row, int col)
{
// Returns true if the cell is not blocked else false
if (grid[row][col] != 0)
return (true);
else
return (false);
}
// A Utility Function to check whether destination cell has
// been reached or not
bool isDestination(int row, int col, Pair dest)
{
if (row == dest.first && col == dest.second)
return (true);
else
return (false);
}
// A Utility Function to calculate the 'h' heuristics.
double calculateHValue(int row, int col, Pair dest)
{
// Return using the distance formula
return ((double)sqrt(
(row - dest.first) * (row - dest.first)
+ (col - dest.second) * (col - dest.second)));
}
// A Utility Function to trace the path from the source
// to destination
void tracePath(cell cellDetails[][COL], Pair dest)
{
printf("\nThe Path is ");
int row = dest.first;
int col = dest.second;
stack<Pair> Path;
while (!(cellDetails[row][col].parent_i == row
&& cellDetails[row][col].parent_j == col)) {
Path.push(make_pair(row, col));
int temp_row = cellDetails[row][col].parent_i;
int temp_col = cellDetails[row][col].parent_j;
row = temp_row;
col = temp_col;
}
Path.push(make_pair(row, col));
while (!Path.empty()) {
pair<int, int> p = Path.top();
Path.pop();
printf("-> (%d,%d) ", p.first, p.second);
}
return;
}
// A Function to find the shortest path between
// a given source cell to a destination cell according
// to A* Search Algorithm
void aStarSearch(int grid[][COL], Pair src, Pair dest)
{
// If the source is out of range
if (isValid(src.first, src.second) == false) {
printf("Source is invalid\n");
return;
}
// If the destination is out of range
if (isValid(dest.first, dest.second) == false) {
printf("Destination is invalid\n");
return;
}
// Either the source or the destination is blocked
if (isUnBlocked(grid, src.first, src.second) == false
|| isUnBlocked(grid, dest.first, dest.second)
== false) {
printf("Source or the destination is blocked\n");
return;
}
// If the destination cell is the same as source cell
if (isDestination(src.first, src.second, dest)
== true) {
printf("We are already at the destination\n");
return;
}
// Create a closed list and initialise it to false which
// means that no cell has been included yet This closed
// list is implemented as a boolean 2D array
bool closedList[ROW][COL];
memset(closedList, false, sizeof(closedList));
// Declare a 2D array of structure to hold the details
// of that cell
cell cellDetails[ROW][COL];
int i, j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
cellDetails[i][j].f = FLT_MAX;
cellDetails[i][j].g = FLT_MAX;
cellDetails[i][j].h = FLT_MAX;
cellDetails[i][j].parent_i = -1;
cellDetails[i][j].parent_j = -1;
}
}
// Initialising the parameters of the starting node
i = src.first, j = src.second;
cellDetails[i][j].f = 0.0;
cellDetails[i][j].g = 0.0;
cellDetails[i][j].h = 0.0;
cellDetails[i][j].parent_i = i;
cellDetails[i][j].parent_j = j;
/*
Create an open list having information as-
<f, <i, j>>
where f = g + h,
and i, j are the row and column index of that cell
Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
This open list is implemented as a set of pair of
pair.*/
unordered_set<pPair> openList;
// Put the starting cell on the open list and set its
// 'f' as 0
openList.insert(make_pair(0.0, make_pair(i, j)));
// We set this boolean value as false as initially
// the destination is not reached.
bool foundDest = false;
while (!openList.empty()) {
pPair p = *openList.begin();
// Remove this vertex from the open list
openList.erase(openList.begin());
// Add this vertex to the closed list
i = p.second.first;
j = p.second.second;
closedList[i][j] = true;
/*
Generating all the 8 successor of this cell
N.W N N.E
\ | /
\ | /
W----Cell----E
/ | \
/ | \
S.W S S.E
Cell-->Popped Cell (i, j)
N --> North (i-1, j)
S --> South (i+1, j)
E --> East (i, j+1)
W --> West (i, j-1)
N.E--> North-East (i-1, j+1)
N.W--> North-West (i-1, j-1)
S.E--> South-East (i+1, j+1)
S.W--> South-West (i+1, j-1)*/
// To store the 'g', 'h' and 'f' of the 8 successors
double gNew, hNew, fNew;
//----------- 1st Successor (North) ------------
// Only process this cell if this is a valid one
if (isValid(i - 1, j) == true) {
// If the destination cell is the same as the
// current successor
if (isDestination(i - 1, j, dest) == true) {
// Set the Parent of the destination cell
cellDetails[i - 1][j].parent_i = i;
cellDetails[i - 1][j].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i - 1][j] == false
&& isUnBlocked(grid, i - 1, j)
== true) {
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i - 1, j, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is
// better, using 'f' cost as the measure.
if (cellDetails[i - 1][j].f == FLT_MAX
|| cellDetails[i - 1][j].f > fNew) {
openList.insert(make_pair(
fNew, make_pair(i - 1, j)));
// Update the details of this cell
cellDetails[i - 1][j].f = fNew;
cellDetails[i - 1][j].g = gNew;
cellDetails[i - 1][j].h = hNew;
cellDetails[i - 1][j].parent_i = i;
cellDetails[i - 1][j].parent_j = j;
}
}
}
//----------- 2nd Successor (South) ------------
// Only process this cell if this is a valid one
if (isValid(i + 1, j) == true) {
// If the destination cell is the same as the
// current successor
if (isDestination(i + 1, j, dest) == true) {
// Set the Parent of the destination cell
cellDetails[i + 1][j].parent_i = i;
cellDetails[i + 1][j].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i + 1][j] == false
&& isUnBlocked(grid, i + 1, j)
== true) {
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i + 1, j, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is
// better, using 'f' cost as the measure.
if (cellDetails[i + 1][j].f == FLT_MAX
|| cellDetails[i + 1][j].f > fNew) {
openList.insert(make_pair(
fNew, make_pair(i + 1, j)));
// Update the details of this cell
cellDetails[i + 1][j].f = fNew;
cellDetails[i + 1][j].g = gNew;
cellDetails[i + 1][j].h = hNew;
cellDetails[i + 1][j].parent_i = i;
cellDetails[i + 1][j].parent_j = j;
}
}
}
//----------- 3rd Successor (East) ------------
// Only process this cell if this is a valid one
if (isValid(i, j + 1) == true) {
// If the destination cell is the same as the
// current successor
if (isDestination(i, j + 1, dest) == true) {
// Set the Parent of the destination cell
cellDetails[i][j + 1].parent_i = i;
cellDetails[i][j + 1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i][j + 1] == false
&& isUnBlocked(grid, i, j + 1)
== true) {
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i, j + 1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is
// better, using 'f' cost as the measure.
if (cellDetails[i][j + 1].f == FLT_MAX
|| cellDetails[i][j + 1].f > fNew) {
openList.insert(make_pair(
fNew, make_pair(i, j + 1)));
// Update the details of this cell
cellDetails[i][j + 1].f = fNew;
cellDetails[i][j + 1].g = gNew;
cellDetails[i][j + 1].h = hNew;
cellDetails[i][j + 1].parent_i = i;
cellDetails[i][j + 1].parent_j = j;
}
}
}
//----------- 4th Successor (West) ------------
// Only process this cell if this is a valid one
if (isValid(i, j - 1) == true) {
// If the destination cell is the same as the
// current successor
if (isDestination(i, j - 1, dest) == true) {
// Set the Parent of the destination cell
cellDetails[i][j - 1].parent_i = i;
cellDetails[i][j - 1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i][j - 1] == false
&& isUnBlocked(grid, i, j - 1)
== true) {
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i, j - 1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is
// better, using 'f' cost as the measure.
if (cellDetails[i][j - 1].f == FLT_MAX
|| cellDetails[i][j - 1].f > fNew) {
openList.insert(make_pair(
fNew, make_pair(i, j - 1)));
// Update the details of this cell
cellDetails[i][j - 1].f = fNew;
cellDetails[i][j - 1].g = gNew;
cellDetails[i][j - 1].h = hNew;
cellDetails[i][j - 1].parent_i = i;
cellDetails[i][j - 1].parent_j = j;
}
}
}
//----------- 5th Successor (North-East)
//------------
/*
// Only process this cell if this is a valid one
if (isValid(i - 1, j + 1) == true) {
// If the destination cell is the same as the
// current successor
if (isDestination(i - 1, j + 1, dest) == true) {
// Set the Parent of the destination cell
cellDetails[i - 1][j + 1].parent_i = i;
cellDetails[i - 1][j + 1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i - 1][j + 1] == false
&& isUnBlocked(grid, i - 1, j + 1)
== true) {
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i - 1, j + 1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is
// better, using 'f' cost as the measure.
if (cellDetails[i - 1][j + 1].f == FLT_MAX
|| cellDetails[i - 1][j + 1].f > fNew) {
openList.insert(make_pair(
fNew, make_pair(i - 1, j + 1)));
// Update the details of this cell
cellDetails[i - 1][j + 1].f = fNew;
cellDetails[i - 1][j + 1].g = gNew;
cellDetails[i - 1][j + 1].h = hNew;
cellDetails[i - 1][j + 1].parent_i = i;
cellDetails[i - 1][j + 1].parent_j = j;
}
}
}
//----------- 6th Successor (North-West)
//------------
// Only process this cell if this is a valid one
if (isValid(i - 1, j - 1) == true) {
// If the destination cell is the same as the
// current successor
if (isDestination(i - 1, j - 1, dest) == true) {
// Set the Parent of the destination cell
cellDetails[i - 1][j - 1].parent_i = i;
cellDetails[i - 1][j - 1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i - 1][j - 1] == false
&& isUnBlocked(grid, i - 1, j - 1)
== true) {
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i - 1, j - 1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is
// better, using 'f' cost as the measure.
if (cellDetails[i - 1][j - 1].f == FLT_MAX
|| cellDetails[i - 1][j - 1].f > fNew) {
openList.insert(make_pair(
fNew, make_pair(i - 1, j - 1)));
// Update the details of this cell
cellDetails[i - 1][j - 1].f = fNew;
cellDetails[i - 1][j - 1].g = gNew;
cellDetails[i - 1][j - 1].h = hNew;
cellDetails[i - 1][j - 1].parent_i = i;
cellDetails[i - 1][j - 1].parent_j = j;
}
}
}
//----------- 7th Successor (South-East)
//------------
// Only process this cell if this is a valid one
if (isValid(i + 1, j + 1) == true) {
// If the destination cell is the same as the
// current successor
if (isDestination(i + 1, j + 1, dest) == true) {
// Set the Parent of the destination cell
cellDetails[i + 1][j + 1].parent_i = i;
cellDetails[i + 1][j + 1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i + 1][j + 1] == false
&& isUnBlocked(grid, i + 1, j + 1)
== true) {
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i + 1, j + 1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is
// better, using 'f' cost as the measure.
if (cellDetails[i + 1][j + 1].f == FLT_MAX
|| cellDetails[i + 1][j + 1].f > fNew) {
openList.insert(make_pair(
fNew, make_pair(i + 1, j + 1)));
// Update the details of this cell
cellDetails[i + 1][j + 1].f = fNew;
cellDetails[i + 1][j + 1].g = gNew;
cellDetails[i + 1][j + 1].h = hNew;
cellDetails[i + 1][j + 1].parent_i = i;
cellDetails[i + 1][j + 1].parent_j = j;
}
}
}
//----------- 8th Successor (South-West)
//------------
// Only process this cell if this is a valid one
if (isValid(i + 1, j - 1) == true) {
// If the destination cell is the same as the
// current successor
if (isDestination(i + 1, j - 1, dest) == true) {
// Set the Parent of the destination cell
cellDetails[i + 1][j - 1].parent_i = i;
cellDetails[i + 1][j - 1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i + 1][j - 1] == false
&& isUnBlocked(grid, i + 1, j - 1)
== true) {
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i + 1, j - 1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is
// better, using 'f' cost as the measure.
if (cellDetails[i + 1][j - 1].f == FLT_MAX
|| cellDetails[i + 1][j - 1].f > fNew) {
openList.insert(make_pair(
fNew, make_pair(i + 1, j - 1)));
// Update the details of this cell
cellDetails[i + 1][j - 1].f = fNew;
cellDetails[i + 1][j - 1].g = gNew;
cellDetails[i + 1][j - 1].h = hNew;
cellDetails[i + 1][j - 1].parent_i = i;
cellDetails[i + 1][j - 1].parent_j = j;
}
}
}
*/
}
// When the destination cell is not found and the open
// list is empty, then we conclude that we failed to
// reach the destination cell. This may happen when the
// there is no way to destination cell (due to
// blockages)
if (foundDest == false)
printf("Failed to find the Destination Cell\n");
return;
}
// Driver program to test above function
int main()
{
/* Description of the Grid-
1--> The cell is not blocked
0--> The cell is blocked */
int grid[ROW][COL]
= {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, },
};
// Source is the left-most bottom-most corner
Pair src = make_pair(4, 12); // invert
// Destination is the left-most top-most corner
Pair dest = make_pair(15, 5); // invert
aStarSearch(grid, src, dest);
return (0);
}
Ly8gQSBDKysgUHJvZ3JhbSB0byBpbXBsZW1lbnQgQSogU2VhcmNoIEFsZ29yaXRobQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgUk9XIDE3CiNkZWZpbmUgQ09MIDE1CgovLyBDcmVhdGluZyBhIHNob3J0Y3V0IGZvciBpbnQsIGludCBwYWlyIHR5cGUKdHlwZWRlZiBwYWlyPGludCwgaW50PiBQYWlyOwoKLy8gQ3JlYXRpbmcgYSBzaG9ydGN1dCBmb3IgcGFpcjxpbnQsIHBhaXI8aW50LCBpbnQ+PiB0eXBlCnR5cGVkZWYgcGFpcjxkb3VibGUsIHBhaXI8aW50LCBpbnQ+ID4gcFBhaXI7CgpuYW1lc3BhY2Ugc3RkIHsKICAgIHRlbXBsYXRlIDw+CiAgICBzdHJ1Y3QgaGFzaDxwUGFpcj4gewogICAgICAgIHN0ZDo6c2l6ZV90IG9wZXJhdG9yKCkocFBhaXIgY29uc3QmIGluc3RhbmNlKSBjb25zdCB7CiAgICAgICAgICAgIHJldHVybiBzdGQ6Omhhc2g8ZG91YmxlPigpKGluc3RhbmNlLmZpcnN0KSBeIHN0ZDo6aGFzaDxpbnQ+KCkoaW5zdGFuY2Uuc2Vjb25kLmZpcnN0KSBeIHN0ZDo6aGFzaDxpbnQ+KCkoaW5zdGFuY2Uuc2Vjb25kLnNlY29uZCk7CiAgICAgICAgfQogICAgfTsKfQoKLy8gQSBzdHJ1Y3R1cmUgdG8gaG9sZCB0aGUgbmVjZXNzYXJ5IHBhcmFtZXRlcnMKc3RydWN0IGNlbGwgewoJLy8gUm93IGFuZCBDb2x1bW4gaW5kZXggb2YgaXRzIHBhcmVudAoJLy8gTm90ZSB0aGF0IDAgPD0gaSA8PSBST1ctMSAmIDAgPD0gaiA8PSBDT0wtMQoJaW50IHBhcmVudF9pLCBwYXJlbnRfajsKCS8vIGYgPSBnICsgaAoJZG91YmxlIGYsIGcsIGg7Cn07CgovLyBBIFV0aWxpdHkgRnVuY3Rpb24gdG8gY2hlY2sgd2hldGhlciBnaXZlbiBjZWxsIChyb3csIGNvbCkKLy8gaXMgYSB2YWxpZCBjZWxsIG9yIG5vdC4KYm9vbCBpc1ZhbGlkKGludCByb3csIGludCBjb2wpCnsKCS8vIFJldHVybnMgdHJ1ZSBpZiByb3cgbnVtYmVyIGFuZCBjb2x1bW4gbnVtYmVyCgkvLyBpcyBpbiByYW5nZQoJcmV0dXJuIChyb3cgPj0gMCkgJiYgKHJvdyA8IFJPVykgJiYgKGNvbCA+PSAwKQoJCSYmIChjb2wgPCBDT0wpOwp9CgovLyBBIFV0aWxpdHkgRnVuY3Rpb24gdG8gY2hlY2sgd2hldGhlciB0aGUgZ2l2ZW4gY2VsbCBpcwovLyBibG9ja2VkIG9yIG5vdApib29sIGlzVW5CbG9ja2VkKGludCBncmlkW11bQ09MXSwgaW50IHJvdywgaW50IGNvbCkKewoJLy8gUmV0dXJucyB0cnVlIGlmIHRoZSBjZWxsIGlzIG5vdCBibG9ja2VkIGVsc2UgZmFsc2UKCWlmIChncmlkW3Jvd11bY29sXSAhPSAwKQoJCXJldHVybiAodHJ1ZSk7CgllbHNlCgkJcmV0dXJuIChmYWxzZSk7Cn0KCi8vIEEgVXRpbGl0eSBGdW5jdGlvbiB0byBjaGVjayB3aGV0aGVyIGRlc3RpbmF0aW9uIGNlbGwgaGFzCi8vIGJlZW4gcmVhY2hlZCBvciBub3QKYm9vbCBpc0Rlc3RpbmF0aW9uKGludCByb3csIGludCBjb2wsIFBhaXIgZGVzdCkKewoJaWYgKHJvdyA9PSBkZXN0LmZpcnN0ICYmIGNvbCA9PSBkZXN0LnNlY29uZCkKCQlyZXR1cm4gKHRydWUpOwoJZWxzZQoJCXJldHVybiAoZmFsc2UpOwp9CgovLyBBIFV0aWxpdHkgRnVuY3Rpb24gdG8gY2FsY3VsYXRlIHRoZSAnaCcgaGV1cmlzdGljcy4KZG91YmxlIGNhbGN1bGF0ZUhWYWx1ZShpbnQgcm93LCBpbnQgY29sLCBQYWlyIGRlc3QpCnsKCS8vIFJldHVybiB1c2luZyB0aGUgZGlzdGFuY2UgZm9ybXVsYQoJcmV0dXJuICgoZG91YmxlKXNxcnQoCgkJKHJvdyAtIGRlc3QuZmlyc3QpICogKHJvdyAtIGRlc3QuZmlyc3QpCgkJKyAoY29sIC0gZGVzdC5zZWNvbmQpICogKGNvbCAtIGRlc3Quc2Vjb25kKSkpOwp9CgovLyBBIFV0aWxpdHkgRnVuY3Rpb24gdG8gdHJhY2UgdGhlIHBhdGggZnJvbSB0aGUgc291cmNlCi8vIHRvIGRlc3RpbmF0aW9uCnZvaWQgdHJhY2VQYXRoKGNlbGwgY2VsbERldGFpbHNbXVtDT0xdLCBQYWlyIGRlc3QpCnsKCXByaW50ZigiXG5UaGUgUGF0aCBpcyAiKTsKCWludCByb3cgPSBkZXN0LmZpcnN0OwoJaW50IGNvbCA9IGRlc3Quc2Vjb25kOwoKCXN0YWNrPFBhaXI+IFBhdGg7CgoJd2hpbGUgKCEoY2VsbERldGFpbHNbcm93XVtjb2xdLnBhcmVudF9pID09IHJvdwoJCQkmJiBjZWxsRGV0YWlsc1tyb3ddW2NvbF0ucGFyZW50X2ogPT0gY29sKSkgewoJCVBhdGgucHVzaChtYWtlX3BhaXIocm93LCBjb2wpKTsKCQlpbnQgdGVtcF9yb3cgPSBjZWxsRGV0YWlsc1tyb3ddW2NvbF0ucGFyZW50X2k7CgkJaW50IHRlbXBfY29sID0gY2VsbERldGFpbHNbcm93XVtjb2xdLnBhcmVudF9qOwoJCXJvdyA9IHRlbXBfcm93OwoJCWNvbCA9IHRlbXBfY29sOwoJfQoKCVBhdGgucHVzaChtYWtlX3BhaXIocm93LCBjb2wpKTsKCXdoaWxlICghUGF0aC5lbXB0eSgpKSB7CgkJcGFpcjxpbnQsIGludD4gcCA9IFBhdGgudG9wKCk7CgkJUGF0aC5wb3AoKTsKCQlwcmludGYoIi0+ICglZCwlZCkgIiwgcC5maXJzdCwgcC5zZWNvbmQpOwoJfQoKCXJldHVybjsKfQoKLy8gQSBGdW5jdGlvbiB0byBmaW5kIHRoZSBzaG9ydGVzdCBwYXRoIGJldHdlZW4KLy8gYSBnaXZlbiBzb3VyY2UgY2VsbCB0byBhIGRlc3RpbmF0aW9uIGNlbGwgYWNjb3JkaW5nCi8vIHRvIEEqIFNlYXJjaCBBbGdvcml0aG0Kdm9pZCBhU3RhclNlYXJjaChpbnQgZ3JpZFtdW0NPTF0sIFBhaXIgc3JjLCBQYWlyIGRlc3QpCnsKCS8vIElmIHRoZSBzb3VyY2UgaXMgb3V0IG9mIHJhbmdlCglpZiAoaXNWYWxpZChzcmMuZmlyc3QsIHNyYy5zZWNvbmQpID09IGZhbHNlKSB7CgkJcHJpbnRmKCJTb3VyY2UgaXMgaW52YWxpZFxuIik7CgkJcmV0dXJuOwoJfQoKCS8vIElmIHRoZSBkZXN0aW5hdGlvbiBpcyBvdXQgb2YgcmFuZ2UKCWlmIChpc1ZhbGlkKGRlc3QuZmlyc3QsIGRlc3Quc2Vjb25kKSA9PSBmYWxzZSkgewoJCXByaW50ZigiRGVzdGluYXRpb24gaXMgaW52YWxpZFxuIik7CgkJcmV0dXJuOwoJfQoKCS8vIEVpdGhlciB0aGUgc291cmNlIG9yIHRoZSBkZXN0aW5hdGlvbiBpcyBibG9ja2VkCglpZiAoaXNVbkJsb2NrZWQoZ3JpZCwgc3JjLmZpcnN0LCBzcmMuc2Vjb25kKSA9PSBmYWxzZQoJCXx8IGlzVW5CbG9ja2VkKGdyaWQsIGRlc3QuZmlyc3QsIGRlc3Quc2Vjb25kKQoJCQk9PSBmYWxzZSkgewoJCXByaW50ZigiU291cmNlIG9yIHRoZSBkZXN0aW5hdGlvbiBpcyBibG9ja2VkXG4iKTsKCQlyZXR1cm47Cgl9CgoJLy8gSWYgdGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgdGhlIHNhbWUgYXMgc291cmNlIGNlbGwKCWlmIChpc0Rlc3RpbmF0aW9uKHNyYy5maXJzdCwgc3JjLnNlY29uZCwgZGVzdCkKCQk9PSB0cnVlKSB7CgkJcHJpbnRmKCJXZSBhcmUgYWxyZWFkeSBhdCB0aGUgZGVzdGluYXRpb25cbiIpOwoJCXJldHVybjsKCX0KCgkvLyBDcmVhdGUgYSBjbG9zZWQgbGlzdCBhbmQgaW5pdGlhbGlzZSBpdCB0byBmYWxzZSB3aGljaAoJLy8gbWVhbnMgdGhhdCBubyBjZWxsIGhhcyBiZWVuIGluY2x1ZGVkIHlldCBUaGlzIGNsb3NlZAoJLy8gbGlzdCBpcyBpbXBsZW1lbnRlZCBhcyBhIGJvb2xlYW4gMkQgYXJyYXkKCWJvb2wgY2xvc2VkTGlzdFtST1ddW0NPTF07CgltZW1zZXQoY2xvc2VkTGlzdCwgZmFsc2UsIHNpemVvZihjbG9zZWRMaXN0KSk7CgoJLy8gRGVjbGFyZSBhIDJEIGFycmF5IG9mIHN0cnVjdHVyZSB0byBob2xkIHRoZSBkZXRhaWxzCgkvLyBvZiB0aGF0IGNlbGwKCWNlbGwgY2VsbERldGFpbHNbUk9XXVtDT0xdOwoKCWludCBpLCBqOwoKCWZvciAoaSA9IDA7IGkgPCBST1c7IGkrKykgewoJCWZvciAoaiA9IDA7IGogPCBDT0w7IGorKykgewoJCQljZWxsRGV0YWlsc1tpXVtqXS5mID0gRkxUX01BWDsKCQkJY2VsbERldGFpbHNbaV1bal0uZyA9IEZMVF9NQVg7CgkJCWNlbGxEZXRhaWxzW2ldW2pdLmggPSBGTFRfTUFYOwoJCQljZWxsRGV0YWlsc1tpXVtqXS5wYXJlbnRfaSA9IC0xOwoJCQljZWxsRGV0YWlsc1tpXVtqXS5wYXJlbnRfaiA9IC0xOwoJCX0KCX0KCgkvLyBJbml0aWFsaXNpbmcgdGhlIHBhcmFtZXRlcnMgb2YgdGhlIHN0YXJ0aW5nIG5vZGUKCWkgPSBzcmMuZmlyc3QsIGogPSBzcmMuc2Vjb25kOwoJY2VsbERldGFpbHNbaV1bal0uZiA9IDAuMDsKCWNlbGxEZXRhaWxzW2ldW2pdLmcgPSAwLjA7CgljZWxsRGV0YWlsc1tpXVtqXS5oID0gMC4wOwoJY2VsbERldGFpbHNbaV1bal0ucGFyZW50X2kgPSBpOwoJY2VsbERldGFpbHNbaV1bal0ucGFyZW50X2ogPSBqOwoKCS8qCglDcmVhdGUgYW4gb3BlbiBsaXN0IGhhdmluZyBpbmZvcm1hdGlvbiBhcy0KCTxmLCA8aSwgaj4+Cgl3aGVyZSBmID0gZyArIGgsCglhbmQgaSwgaiBhcmUgdGhlIHJvdyBhbmQgY29sdW1uIGluZGV4IG9mIHRoYXQgY2VsbAoJTm90ZSB0aGF0IDAgPD0gaSA8PSBST1ctMSAmIDAgPD0gaiA8PSBDT0wtMQoJVGhpcyBvcGVuIGxpc3QgaXMgaW1wbGVtZW50ZWQgYXMgYSBzZXQgb2YgcGFpciBvZgoJcGFpci4qLwoJdW5vcmRlcmVkX3NldDxwUGFpcj4gb3Blbkxpc3Q7CgoJLy8gUHV0IHRoZSBzdGFydGluZyBjZWxsIG9uIHRoZSBvcGVuIGxpc3QgYW5kIHNldCBpdHMKCS8vICdmJyBhcyAwCglvcGVuTGlzdC5pbnNlcnQobWFrZV9wYWlyKDAuMCwgbWFrZV9wYWlyKGksIGopKSk7CgoJLy8gV2Ugc2V0IHRoaXMgYm9vbGVhbiB2YWx1ZSBhcyBmYWxzZSBhcyBpbml0aWFsbHkKCS8vIHRoZSBkZXN0aW5hdGlvbiBpcyBub3QgcmVhY2hlZC4KCWJvb2wgZm91bmREZXN0ID0gZmFsc2U7CgoJd2hpbGUgKCFvcGVuTGlzdC5lbXB0eSgpKSB7CgkJcFBhaXIgcCA9ICpvcGVuTGlzdC5iZWdpbigpOwoKCQkvLyBSZW1vdmUgdGhpcyB2ZXJ0ZXggZnJvbSB0aGUgb3BlbiBsaXN0CgkJb3Blbkxpc3QuZXJhc2Uob3Blbkxpc3QuYmVnaW4oKSk7CgoJCS8vIEFkZCB0aGlzIHZlcnRleCB0byB0aGUgY2xvc2VkIGxpc3QKCQlpID0gcC5zZWNvbmQuZmlyc3Q7CgkJaiA9IHAuc2Vjb25kLnNlY29uZDsKCQljbG9zZWRMaXN0W2ldW2pdID0gdHJ1ZTsKCgkJLyoKCQlHZW5lcmF0aW5nIGFsbCB0aGUgOCBzdWNjZXNzb3Igb2YgdGhpcyBjZWxsCgoJCQlOLlcgTiBOLkUKCQkJXCB8IC8KCQkJCVwgfCAvCgkJCVctLS0tQ2VsbC0tLS1FCgkJCQkvIHwgXAoJCQkJLyB8IFwKCQkJUy5XIFMgUy5FCgoJCUNlbGwtLT5Qb3BwZWQgQ2VsbCAoaSwgaikKCQlOIC0tPiBOb3J0aAkgKGktMSwgaikKCQlTIC0tPiBTb3V0aAkgKGkrMSwgaikKCQlFIC0tPiBFYXN0CSAoaSwgaisxKQoJCVcgLS0+IFdlc3QJCSAoaSwgai0xKQoJCU4uRS0tPiBOb3J0aC1FYXN0IChpLTEsIGorMSkKCQlOLlctLT4gTm9ydGgtV2VzdCAoaS0xLCBqLTEpCgkJUy5FLS0+IFNvdXRoLUVhc3QgKGkrMSwgaisxKQoJCVMuVy0tPiBTb3V0aC1XZXN0IChpKzEsIGotMSkqLwoKCQkvLyBUbyBzdG9yZSB0aGUgJ2cnLCAnaCcgYW5kICdmJyBvZiB0aGUgOCBzdWNjZXNzb3JzCgkJZG91YmxlIGdOZXcsIGhOZXcsIGZOZXc7CgoJCS8vLS0tLS0tLS0tLS0gMXN0IFN1Y2Nlc3NvciAoTm9ydGgpIC0tLS0tLS0tLS0tLQoKCQkvLyBPbmx5IHByb2Nlc3MgdGhpcyBjZWxsIGlmIHRoaXMgaXMgYSB2YWxpZCBvbmUKCQlpZiAoaXNWYWxpZChpIC0gMSwgaikgPT0gdHJ1ZSkgewoJCQkvLyBJZiB0aGUgZGVzdGluYXRpb24gY2VsbCBpcyB0aGUgc2FtZSBhcyB0aGUKCQkJLy8gY3VycmVudCBzdWNjZXNzb3IKCQkJaWYgKGlzRGVzdGluYXRpb24oaSAtIDEsIGosIGRlc3QpID09IHRydWUpIHsKCQkJCS8vIFNldCB0aGUgUGFyZW50IG9mIHRoZSBkZXN0aW5hdGlvbiBjZWxsCgkJCQljZWxsRGV0YWlsc1tpIC0gMV1bal0ucGFyZW50X2kgPSBpOwoJCQkJY2VsbERldGFpbHNbaSAtIDFdW2pdLnBhcmVudF9qID0gajsKCQkJCXByaW50ZigiVGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgZm91bmRcbiIpOwoJCQkJdHJhY2VQYXRoKGNlbGxEZXRhaWxzLCBkZXN0KTsKCQkJCWZvdW5kRGVzdCA9IHRydWU7CgkJCQlyZXR1cm47CgkJCX0KCQkJLy8gSWYgdGhlIHN1Y2Nlc3NvciBpcyBhbHJlYWR5IG9uIHRoZSBjbG9zZWQKCQkJLy8gbGlzdCBvciBpZiBpdCBpcyBibG9ja2VkLCB0aGVuIGlnbm9yZSBpdC4KCQkJLy8gRWxzZSBkbyB0aGUgZm9sbG93aW5nCgkJCWVsc2UgaWYgKGNsb3NlZExpc3RbaSAtIDFdW2pdID09IGZhbHNlCgkJCQkJJiYgaXNVbkJsb2NrZWQoZ3JpZCwgaSAtIDEsIGopCgkJCQkJCQk9PSB0cnVlKSB7CgkJCQlnTmV3ID0gY2VsbERldGFpbHNbaV1bal0uZyArIDEuMDsKCQkJCWhOZXcgPSBjYWxjdWxhdGVIVmFsdWUoaSAtIDEsIGosIGRlc3QpOwoJCQkJZk5ldyA9IGdOZXcgKyBoTmV3OwoKCQkJCS8vIElmIGl0IGlzbuKAmXQgb24gdGhlIG9wZW4gbGlzdCwgYWRkIGl0IHRvCgkJCQkvLyB0aGUgb3BlbiBsaXN0LiBNYWtlIHRoZSBjdXJyZW50IHNxdWFyZQoJCQkJLy8gdGhlIHBhcmVudCBvZiB0aGlzIHNxdWFyZS4gUmVjb3JkIHRoZQoJCQkJLy8gZiwgZywgYW5kIGggY29zdHMgb2YgdGhlIHNxdWFyZSBjZWxsCgkJCQkvLwkJCSBPUgoJCQkJLy8gSWYgaXQgaXMgb24gdGhlIG9wZW4gbGlzdCBhbHJlYWR5LCBjaGVjawoJCQkJLy8gdG8gc2VlIGlmIHRoaXMgcGF0aCB0byB0aGF0IHNxdWFyZSBpcwoJCQkJLy8gYmV0dGVyLCB1c2luZyAnZicgY29zdCBhcyB0aGUgbWVhc3VyZS4KCQkJCWlmIChjZWxsRGV0YWlsc1tpIC0gMV1bal0uZiA9PSBGTFRfTUFYCgkJCQkJfHwgY2VsbERldGFpbHNbaSAtIDFdW2pdLmYgPiBmTmV3KSB7CgkJCQkJb3Blbkxpc3QuaW5zZXJ0KG1ha2VfcGFpcigKCQkJCQkJZk5ldywgbWFrZV9wYWlyKGkgLSAxLCBqKSkpOwoKCQkJCQkvLyBVcGRhdGUgdGhlIGRldGFpbHMgb2YgdGhpcyBjZWxsCgkJCQkJY2VsbERldGFpbHNbaSAtIDFdW2pdLmYgPSBmTmV3OwoJCQkJCWNlbGxEZXRhaWxzW2kgLSAxXVtqXS5nID0gZ05ldzsKCQkJCQljZWxsRGV0YWlsc1tpIC0gMV1bal0uaCA9IGhOZXc7CgkJCQkJY2VsbERldGFpbHNbaSAtIDFdW2pdLnBhcmVudF9pID0gaTsKCQkJCQljZWxsRGV0YWlsc1tpIC0gMV1bal0ucGFyZW50X2ogPSBqOwoJCQkJfQoJCQl9CgkJfQoKCQkvLy0tLS0tLS0tLS0tIDJuZCBTdWNjZXNzb3IgKFNvdXRoKSAtLS0tLS0tLS0tLS0KCgkJLy8gT25seSBwcm9jZXNzIHRoaXMgY2VsbCBpZiB0aGlzIGlzIGEgdmFsaWQgb25lCgkJaWYgKGlzVmFsaWQoaSArIDEsIGopID09IHRydWUpIHsKCQkJLy8gSWYgdGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgdGhlIHNhbWUgYXMgdGhlCgkJCS8vIGN1cnJlbnQgc3VjY2Vzc29yCgkJCWlmIChpc0Rlc3RpbmF0aW9uKGkgKyAxLCBqLCBkZXN0KSA9PSB0cnVlKSB7CgkJCQkvLyBTZXQgdGhlIFBhcmVudCBvZiB0aGUgZGVzdGluYXRpb24gY2VsbAoJCQkJY2VsbERldGFpbHNbaSArIDFdW2pdLnBhcmVudF9pID0gaTsKCQkJCWNlbGxEZXRhaWxzW2kgKyAxXVtqXS5wYXJlbnRfaiA9IGo7CgkJCQlwcmludGYoIlRoZSBkZXN0aW5hdGlvbiBjZWxsIGlzIGZvdW5kXG4iKTsKCQkJCXRyYWNlUGF0aChjZWxsRGV0YWlscywgZGVzdCk7CgkJCQlmb3VuZERlc3QgPSB0cnVlOwoJCQkJcmV0dXJuOwoJCQl9CgkJCS8vIElmIHRoZSBzdWNjZXNzb3IgaXMgYWxyZWFkeSBvbiB0aGUgY2xvc2VkCgkJCS8vIGxpc3Qgb3IgaWYgaXQgaXMgYmxvY2tlZCwgdGhlbiBpZ25vcmUgaXQuCgkJCS8vIEVsc2UgZG8gdGhlIGZvbGxvd2luZwoJCQllbHNlIGlmIChjbG9zZWRMaXN0W2kgKyAxXVtqXSA9PSBmYWxzZQoJCQkJCSYmIGlzVW5CbG9ja2VkKGdyaWQsIGkgKyAxLCBqKQoJCQkJCQkJPT0gdHJ1ZSkgewoJCQkJZ05ldyA9IGNlbGxEZXRhaWxzW2ldW2pdLmcgKyAxLjA7CgkJCQloTmV3ID0gY2FsY3VsYXRlSFZhbHVlKGkgKyAxLCBqLCBkZXN0KTsKCQkJCWZOZXcgPSBnTmV3ICsgaE5ldzsKCgkJCQkvLyBJZiBpdCBpc27igJl0IG9uIHRoZSBvcGVuIGxpc3QsIGFkZCBpdCB0bwoJCQkJLy8gdGhlIG9wZW4gbGlzdC4gTWFrZSB0aGUgY3VycmVudCBzcXVhcmUKCQkJCS8vIHRoZSBwYXJlbnQgb2YgdGhpcyBzcXVhcmUuIFJlY29yZCB0aGUKCQkJCS8vIGYsIGcsIGFuZCBoIGNvc3RzIG9mIHRoZSBzcXVhcmUgY2VsbAoJCQkJLy8JCQkgT1IKCQkJCS8vIElmIGl0IGlzIG9uIHRoZSBvcGVuIGxpc3QgYWxyZWFkeSwgY2hlY2sKCQkJCS8vIHRvIHNlZSBpZiB0aGlzIHBhdGggdG8gdGhhdCBzcXVhcmUgaXMKCQkJCS8vIGJldHRlciwgdXNpbmcgJ2YnIGNvc3QgYXMgdGhlIG1lYXN1cmUuCgkJCQlpZiAoY2VsbERldGFpbHNbaSArIDFdW2pdLmYgPT0gRkxUX01BWAoJCQkJCXx8IGNlbGxEZXRhaWxzW2kgKyAxXVtqXS5mID4gZk5ldykgewoJCQkJCW9wZW5MaXN0Lmluc2VydChtYWtlX3BhaXIoCgkJCQkJCWZOZXcsIG1ha2VfcGFpcihpICsgMSwgaikpKTsKCQkJCQkvLyBVcGRhdGUgdGhlIGRldGFpbHMgb2YgdGhpcyBjZWxsCgkJCQkJY2VsbERldGFpbHNbaSArIDFdW2pdLmYgPSBmTmV3OwoJCQkJCWNlbGxEZXRhaWxzW2kgKyAxXVtqXS5nID0gZ05ldzsKCQkJCQljZWxsRGV0YWlsc1tpICsgMV1bal0uaCA9IGhOZXc7CgkJCQkJY2VsbERldGFpbHNbaSArIDFdW2pdLnBhcmVudF9pID0gaTsKCQkJCQljZWxsRGV0YWlsc1tpICsgMV1bal0ucGFyZW50X2ogPSBqOwoJCQkJfQoJCQl9CgkJfQoKCQkvLy0tLS0tLS0tLS0tIDNyZCBTdWNjZXNzb3IgKEVhc3QpIC0tLS0tLS0tLS0tLQoKCQkvLyBPbmx5IHByb2Nlc3MgdGhpcyBjZWxsIGlmIHRoaXMgaXMgYSB2YWxpZCBvbmUKCQlpZiAoaXNWYWxpZChpLCBqICsgMSkgPT0gdHJ1ZSkgewoJCQkvLyBJZiB0aGUgZGVzdGluYXRpb24gY2VsbCBpcyB0aGUgc2FtZSBhcyB0aGUKCQkJLy8gY3VycmVudCBzdWNjZXNzb3IKCQkJaWYgKGlzRGVzdGluYXRpb24oaSwgaiArIDEsIGRlc3QpID09IHRydWUpIHsKCQkJCS8vIFNldCB0aGUgUGFyZW50IG9mIHRoZSBkZXN0aW5hdGlvbiBjZWxsCgkJCQljZWxsRGV0YWlsc1tpXVtqICsgMV0ucGFyZW50X2kgPSBpOwoJCQkJY2VsbERldGFpbHNbaV1baiArIDFdLnBhcmVudF9qID0gajsKCQkJCXByaW50ZigiVGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgZm91bmRcbiIpOwoJCQkJdHJhY2VQYXRoKGNlbGxEZXRhaWxzLCBkZXN0KTsKCQkJCWZvdW5kRGVzdCA9IHRydWU7CgkJCQlyZXR1cm47CgkJCX0KCgkJCS8vIElmIHRoZSBzdWNjZXNzb3IgaXMgYWxyZWFkeSBvbiB0aGUgY2xvc2VkCgkJCS8vIGxpc3Qgb3IgaWYgaXQgaXMgYmxvY2tlZCwgdGhlbiBpZ25vcmUgaXQuCgkJCS8vIEVsc2UgZG8gdGhlIGZvbGxvd2luZwoJCQllbHNlIGlmIChjbG9zZWRMaXN0W2ldW2ogKyAxXSA9PSBmYWxzZQoJCQkJCSYmIGlzVW5CbG9ja2VkKGdyaWQsIGksIGogKyAxKQoJCQkJCQkJPT0gdHJ1ZSkgewoJCQkJZ05ldyA9IGNlbGxEZXRhaWxzW2ldW2pdLmcgKyAxLjA7CgkJCQloTmV3ID0gY2FsY3VsYXRlSFZhbHVlKGksIGogKyAxLCBkZXN0KTsKCQkJCWZOZXcgPSBnTmV3ICsgaE5ldzsKCgkJCQkvLyBJZiBpdCBpc27igJl0IG9uIHRoZSBvcGVuIGxpc3QsIGFkZCBpdCB0bwoJCQkJLy8gdGhlIG9wZW4gbGlzdC4gTWFrZSB0aGUgY3VycmVudCBzcXVhcmUKCQkJCS8vIHRoZSBwYXJlbnQgb2YgdGhpcyBzcXVhcmUuIFJlY29yZCB0aGUKCQkJCS8vIGYsIGcsIGFuZCBoIGNvc3RzIG9mIHRoZSBzcXVhcmUgY2VsbAoJCQkJLy8JCQkgT1IKCQkJCS8vIElmIGl0IGlzIG9uIHRoZSBvcGVuIGxpc3QgYWxyZWFkeSwgY2hlY2sKCQkJCS8vIHRvIHNlZSBpZiB0aGlzIHBhdGggdG8gdGhhdCBzcXVhcmUgaXMKCQkJCS8vIGJldHRlciwgdXNpbmcgJ2YnIGNvc3QgYXMgdGhlIG1lYXN1cmUuCgkJCQlpZiAoY2VsbERldGFpbHNbaV1baiArIDFdLmYgPT0gRkxUX01BWAoJCQkJCXx8IGNlbGxEZXRhaWxzW2ldW2ogKyAxXS5mID4gZk5ldykgewoJCQkJCW9wZW5MaXN0Lmluc2VydChtYWtlX3BhaXIoCgkJCQkJCWZOZXcsIG1ha2VfcGFpcihpLCBqICsgMSkpKTsKCgkJCQkJLy8gVXBkYXRlIHRoZSBkZXRhaWxzIG9mIHRoaXMgY2VsbAoJCQkJCWNlbGxEZXRhaWxzW2ldW2ogKyAxXS5mID0gZk5ldzsKCQkJCQljZWxsRGV0YWlsc1tpXVtqICsgMV0uZyA9IGdOZXc7CgkJCQkJY2VsbERldGFpbHNbaV1baiArIDFdLmggPSBoTmV3OwoJCQkJCWNlbGxEZXRhaWxzW2ldW2ogKyAxXS5wYXJlbnRfaSA9IGk7CgkJCQkJY2VsbERldGFpbHNbaV1baiArIDFdLnBhcmVudF9qID0gajsKCQkJCX0KCQkJfQoJCX0KCgkJLy8tLS0tLS0tLS0tLSA0dGggU3VjY2Vzc29yIChXZXN0KSAtLS0tLS0tLS0tLS0KCgkJLy8gT25seSBwcm9jZXNzIHRoaXMgY2VsbCBpZiB0aGlzIGlzIGEgdmFsaWQgb25lCgkJaWYgKGlzVmFsaWQoaSwgaiAtIDEpID09IHRydWUpIHsKCQkJLy8gSWYgdGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgdGhlIHNhbWUgYXMgdGhlCgkJCS8vIGN1cnJlbnQgc3VjY2Vzc29yCgkJCWlmIChpc0Rlc3RpbmF0aW9uKGksIGogLSAxLCBkZXN0KSA9PSB0cnVlKSB7CgkJCQkvLyBTZXQgdGhlIFBhcmVudCBvZiB0aGUgZGVzdGluYXRpb24gY2VsbAoJCQkJY2VsbERldGFpbHNbaV1baiAtIDFdLnBhcmVudF9pID0gaTsKCQkJCWNlbGxEZXRhaWxzW2ldW2ogLSAxXS5wYXJlbnRfaiA9IGo7CgkJCQlwcmludGYoIlRoZSBkZXN0aW5hdGlvbiBjZWxsIGlzIGZvdW5kXG4iKTsKCQkJCXRyYWNlUGF0aChjZWxsRGV0YWlscywgZGVzdCk7CgkJCQlmb3VuZERlc3QgPSB0cnVlOwoJCQkJcmV0dXJuOwoJCQl9CgoJCQkvLyBJZiB0aGUgc3VjY2Vzc29yIGlzIGFscmVhZHkgb24gdGhlIGNsb3NlZAoJCQkvLyBsaXN0IG9yIGlmIGl0IGlzIGJsb2NrZWQsIHRoZW4gaWdub3JlIGl0LgoJCQkvLyBFbHNlIGRvIHRoZSBmb2xsb3dpbmcKCQkJZWxzZSBpZiAoY2xvc2VkTGlzdFtpXVtqIC0gMV0gPT0gZmFsc2UKCQkJCQkmJiBpc1VuQmxvY2tlZChncmlkLCBpLCBqIC0gMSkKCQkJCQkJCT09IHRydWUpIHsKCQkJCWdOZXcgPSBjZWxsRGV0YWlsc1tpXVtqXS5nICsgMS4wOwoJCQkJaE5ldyA9IGNhbGN1bGF0ZUhWYWx1ZShpLCBqIC0gMSwgZGVzdCk7CgkJCQlmTmV3ID0gZ05ldyArIGhOZXc7CgoJCQkJLy8gSWYgaXQgaXNu4oCZdCBvbiB0aGUgb3BlbiBsaXN0LCBhZGQgaXQgdG8KCQkJCS8vIHRoZSBvcGVuIGxpc3QuIE1ha2UgdGhlIGN1cnJlbnQgc3F1YXJlCgkJCQkvLyB0aGUgcGFyZW50IG9mIHRoaXMgc3F1YXJlLiBSZWNvcmQgdGhlCgkJCQkvLyBmLCBnLCBhbmQgaCBjb3N0cyBvZiB0aGUgc3F1YXJlIGNlbGwKCQkJCS8vCQkJIE9SCgkJCQkvLyBJZiBpdCBpcyBvbiB0aGUgb3BlbiBsaXN0IGFscmVhZHksIGNoZWNrCgkJCQkvLyB0byBzZWUgaWYgdGhpcyBwYXRoIHRvIHRoYXQgc3F1YXJlIGlzCgkJCQkvLyBiZXR0ZXIsIHVzaW5nICdmJyBjb3N0IGFzIHRoZSBtZWFzdXJlLgoJCQkJaWYgKGNlbGxEZXRhaWxzW2ldW2ogLSAxXS5mID09IEZMVF9NQVgKCQkJCQl8fCBjZWxsRGV0YWlsc1tpXVtqIC0gMV0uZiA+IGZOZXcpIHsKCQkJCQlvcGVuTGlzdC5pbnNlcnQobWFrZV9wYWlyKAoJCQkJCQlmTmV3LCBtYWtlX3BhaXIoaSwgaiAtIDEpKSk7CgoJCQkJCS8vIFVwZGF0ZSB0aGUgZGV0YWlscyBvZiB0aGlzIGNlbGwKCQkJCQljZWxsRGV0YWlsc1tpXVtqIC0gMV0uZiA9IGZOZXc7CgkJCQkJY2VsbERldGFpbHNbaV1baiAtIDFdLmcgPSBnTmV3OwoJCQkJCWNlbGxEZXRhaWxzW2ldW2ogLSAxXS5oID0gaE5ldzsKCQkJCQljZWxsRGV0YWlsc1tpXVtqIC0gMV0ucGFyZW50X2kgPSBpOwoJCQkJCWNlbGxEZXRhaWxzW2ldW2ogLSAxXS5wYXJlbnRfaiA9IGo7CgkJCQl9CgkJCX0KCQl9CgoJCS8vLS0tLS0tLS0tLS0gNXRoIFN1Y2Nlc3NvciAoTm9ydGgtRWFzdCkKCQkvLy0tLS0tLS0tLS0tLQoKICAgICAgICAvKgoJCS8vIE9ubHkgcHJvY2VzcyB0aGlzIGNlbGwgaWYgdGhpcyBpcyBhIHZhbGlkIG9uZQoJCWlmIChpc1ZhbGlkKGkgLSAxLCBqICsgMSkgPT0gdHJ1ZSkgewoJCQkvLyBJZiB0aGUgZGVzdGluYXRpb24gY2VsbCBpcyB0aGUgc2FtZSBhcyB0aGUKCQkJLy8gY3VycmVudCBzdWNjZXNzb3IKCQkJaWYgKGlzRGVzdGluYXRpb24oaSAtIDEsIGogKyAxLCBkZXN0KSA9PSB0cnVlKSB7CgkJCQkvLyBTZXQgdGhlIFBhcmVudCBvZiB0aGUgZGVzdGluYXRpb24gY2VsbAoJCQkJY2VsbERldGFpbHNbaSAtIDFdW2ogKyAxXS5wYXJlbnRfaSA9IGk7CgkJCQljZWxsRGV0YWlsc1tpIC0gMV1baiArIDFdLnBhcmVudF9qID0gajsKCQkJCXByaW50ZigiVGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgZm91bmRcbiIpOwoJCQkJdHJhY2VQYXRoKGNlbGxEZXRhaWxzLCBkZXN0KTsKCQkJCWZvdW5kRGVzdCA9IHRydWU7CgkJCQlyZXR1cm47CgkJCX0KCgkJCS8vIElmIHRoZSBzdWNjZXNzb3IgaXMgYWxyZWFkeSBvbiB0aGUgY2xvc2VkCgkJCS8vIGxpc3Qgb3IgaWYgaXQgaXMgYmxvY2tlZCwgdGhlbiBpZ25vcmUgaXQuCgkJCS8vIEVsc2UgZG8gdGhlIGZvbGxvd2luZwoJCQllbHNlIGlmIChjbG9zZWRMaXN0W2kgLSAxXVtqICsgMV0gPT0gZmFsc2UKCQkJCQkmJiBpc1VuQmxvY2tlZChncmlkLCBpIC0gMSwgaiArIDEpCgkJCQkJCQk9PSB0cnVlKSB7CgkJCQlnTmV3ID0gY2VsbERldGFpbHNbaV1bal0uZyArIDEuNDE0OwoJCQkJaE5ldyA9IGNhbGN1bGF0ZUhWYWx1ZShpIC0gMSwgaiArIDEsIGRlc3QpOwoJCQkJZk5ldyA9IGdOZXcgKyBoTmV3OwoKCQkJCS8vIElmIGl0IGlzbuKAmXQgb24gdGhlIG9wZW4gbGlzdCwgYWRkIGl0IHRvCgkJCQkvLyB0aGUgb3BlbiBsaXN0LiBNYWtlIHRoZSBjdXJyZW50IHNxdWFyZQoJCQkJLy8gdGhlIHBhcmVudCBvZiB0aGlzIHNxdWFyZS4gUmVjb3JkIHRoZQoJCQkJLy8gZiwgZywgYW5kIGggY29zdHMgb2YgdGhlIHNxdWFyZSBjZWxsCgkJCQkvLwkJCSBPUgoJCQkJLy8gSWYgaXQgaXMgb24gdGhlIG9wZW4gbGlzdCBhbHJlYWR5LCBjaGVjawoJCQkJLy8gdG8gc2VlIGlmIHRoaXMgcGF0aCB0byB0aGF0IHNxdWFyZSBpcwoJCQkJLy8gYmV0dGVyLCB1c2luZyAnZicgY29zdCBhcyB0aGUgbWVhc3VyZS4KCQkJCWlmIChjZWxsRGV0YWlsc1tpIC0gMV1baiArIDFdLmYgPT0gRkxUX01BWAoJCQkJCXx8IGNlbGxEZXRhaWxzW2kgLSAxXVtqICsgMV0uZiA+IGZOZXcpIHsKCQkJCQlvcGVuTGlzdC5pbnNlcnQobWFrZV9wYWlyKAoJCQkJCQlmTmV3LCBtYWtlX3BhaXIoaSAtIDEsIGogKyAxKSkpOwoKCQkJCQkvLyBVcGRhdGUgdGhlIGRldGFpbHMgb2YgdGhpcyBjZWxsCgkJCQkJY2VsbERldGFpbHNbaSAtIDFdW2ogKyAxXS5mID0gZk5ldzsKCQkJCQljZWxsRGV0YWlsc1tpIC0gMV1baiArIDFdLmcgPSBnTmV3OwoJCQkJCWNlbGxEZXRhaWxzW2kgLSAxXVtqICsgMV0uaCA9IGhOZXc7CgkJCQkJY2VsbERldGFpbHNbaSAtIDFdW2ogKyAxXS5wYXJlbnRfaSA9IGk7CgkJCQkJY2VsbERldGFpbHNbaSAtIDFdW2ogKyAxXS5wYXJlbnRfaiA9IGo7CgkJCQl9CgkJCX0KCQl9CgoJCS8vLS0tLS0tLS0tLS0gNnRoIFN1Y2Nlc3NvciAoTm9ydGgtV2VzdCkKCQkvLy0tLS0tLS0tLS0tLQoKCQkvLyBPbmx5IHByb2Nlc3MgdGhpcyBjZWxsIGlmIHRoaXMgaXMgYSB2YWxpZCBvbmUKCQlpZiAoaXNWYWxpZChpIC0gMSwgaiAtIDEpID09IHRydWUpIHsKCQkJLy8gSWYgdGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgdGhlIHNhbWUgYXMgdGhlCgkJCS8vIGN1cnJlbnQgc3VjY2Vzc29yCgkJCWlmIChpc0Rlc3RpbmF0aW9uKGkgLSAxLCBqIC0gMSwgZGVzdCkgPT0gdHJ1ZSkgewoJCQkJLy8gU2V0IHRoZSBQYXJlbnQgb2YgdGhlIGRlc3RpbmF0aW9uIGNlbGwKCQkJCWNlbGxEZXRhaWxzW2kgLSAxXVtqIC0gMV0ucGFyZW50X2kgPSBpOwoJCQkJY2VsbERldGFpbHNbaSAtIDFdW2ogLSAxXS5wYXJlbnRfaiA9IGo7CgkJCQlwcmludGYoIlRoZSBkZXN0aW5hdGlvbiBjZWxsIGlzIGZvdW5kXG4iKTsKCQkJCXRyYWNlUGF0aChjZWxsRGV0YWlscywgZGVzdCk7CgkJCQlmb3VuZERlc3QgPSB0cnVlOwoJCQkJcmV0dXJuOwoJCQl9CgoJCQkvLyBJZiB0aGUgc3VjY2Vzc29yIGlzIGFscmVhZHkgb24gdGhlIGNsb3NlZAoJCQkvLyBsaXN0IG9yIGlmIGl0IGlzIGJsb2NrZWQsIHRoZW4gaWdub3JlIGl0LgoJCQkvLyBFbHNlIGRvIHRoZSBmb2xsb3dpbmcKCQkJZWxzZSBpZiAoY2xvc2VkTGlzdFtpIC0gMV1baiAtIDFdID09IGZhbHNlCgkJCQkJJiYgaXNVbkJsb2NrZWQoZ3JpZCwgaSAtIDEsIGogLSAxKQoJCQkJCQkJPT0gdHJ1ZSkgewoJCQkJZ05ldyA9IGNlbGxEZXRhaWxzW2ldW2pdLmcgKyAxLjQxNDsKCQkJCWhOZXcgPSBjYWxjdWxhdGVIVmFsdWUoaSAtIDEsIGogLSAxLCBkZXN0KTsKCQkJCWZOZXcgPSBnTmV3ICsgaE5ldzsKCgkJCQkvLyBJZiBpdCBpc27igJl0IG9uIHRoZSBvcGVuIGxpc3QsIGFkZCBpdCB0bwoJCQkJLy8gdGhlIG9wZW4gbGlzdC4gTWFrZSB0aGUgY3VycmVudCBzcXVhcmUKCQkJCS8vIHRoZSBwYXJlbnQgb2YgdGhpcyBzcXVhcmUuIFJlY29yZCB0aGUKCQkJCS8vIGYsIGcsIGFuZCBoIGNvc3RzIG9mIHRoZSBzcXVhcmUgY2VsbAoJCQkJLy8JCQkgT1IKCQkJCS8vIElmIGl0IGlzIG9uIHRoZSBvcGVuIGxpc3QgYWxyZWFkeSwgY2hlY2sKCQkJCS8vIHRvIHNlZSBpZiB0aGlzIHBhdGggdG8gdGhhdCBzcXVhcmUgaXMKCQkJCS8vIGJldHRlciwgdXNpbmcgJ2YnIGNvc3QgYXMgdGhlIG1lYXN1cmUuCgkJCQlpZiAoY2VsbERldGFpbHNbaSAtIDFdW2ogLSAxXS5mID09IEZMVF9NQVgKCQkJCQl8fCBjZWxsRGV0YWlsc1tpIC0gMV1baiAtIDFdLmYgPiBmTmV3KSB7CgkJCQkJb3Blbkxpc3QuaW5zZXJ0KG1ha2VfcGFpcigKCQkJCQkJZk5ldywgbWFrZV9wYWlyKGkgLSAxLCBqIC0gMSkpKTsKCQkJCQkvLyBVcGRhdGUgdGhlIGRldGFpbHMgb2YgdGhpcyBjZWxsCgkJCQkJY2VsbERldGFpbHNbaSAtIDFdW2ogLSAxXS5mID0gZk5ldzsKCQkJCQljZWxsRGV0YWlsc1tpIC0gMV1baiAtIDFdLmcgPSBnTmV3OwoJCQkJCWNlbGxEZXRhaWxzW2kgLSAxXVtqIC0gMV0uaCA9IGhOZXc7CgkJCQkJY2VsbERldGFpbHNbaSAtIDFdW2ogLSAxXS5wYXJlbnRfaSA9IGk7CgkJCQkJY2VsbERldGFpbHNbaSAtIDFdW2ogLSAxXS5wYXJlbnRfaiA9IGo7CgkJCQl9CgkJCX0KCQl9CgoJCS8vLS0tLS0tLS0tLS0gN3RoIFN1Y2Nlc3NvciAoU291dGgtRWFzdCkKCQkvLy0tLS0tLS0tLS0tLQoKCQkvLyBPbmx5IHByb2Nlc3MgdGhpcyBjZWxsIGlmIHRoaXMgaXMgYSB2YWxpZCBvbmUKCQlpZiAoaXNWYWxpZChpICsgMSwgaiArIDEpID09IHRydWUpIHsKCQkJLy8gSWYgdGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgdGhlIHNhbWUgYXMgdGhlCgkJCS8vIGN1cnJlbnQgc3VjY2Vzc29yCgkJCWlmIChpc0Rlc3RpbmF0aW9uKGkgKyAxLCBqICsgMSwgZGVzdCkgPT0gdHJ1ZSkgewoJCQkJLy8gU2V0IHRoZSBQYXJlbnQgb2YgdGhlIGRlc3RpbmF0aW9uIGNlbGwKCQkJCWNlbGxEZXRhaWxzW2kgKyAxXVtqICsgMV0ucGFyZW50X2kgPSBpOwoJCQkJY2VsbERldGFpbHNbaSArIDFdW2ogKyAxXS5wYXJlbnRfaiA9IGo7CgkJCQlwcmludGYoIlRoZSBkZXN0aW5hdGlvbiBjZWxsIGlzIGZvdW5kXG4iKTsKCQkJCXRyYWNlUGF0aChjZWxsRGV0YWlscywgZGVzdCk7CgkJCQlmb3VuZERlc3QgPSB0cnVlOwoJCQkJcmV0dXJuOwoJCQl9CgoJCQkvLyBJZiB0aGUgc3VjY2Vzc29yIGlzIGFscmVhZHkgb24gdGhlIGNsb3NlZAoJCQkvLyBsaXN0IG9yIGlmIGl0IGlzIGJsb2NrZWQsIHRoZW4gaWdub3JlIGl0LgoJCQkvLyBFbHNlIGRvIHRoZSBmb2xsb3dpbmcKCQkJZWxzZSBpZiAoY2xvc2VkTGlzdFtpICsgMV1baiArIDFdID09IGZhbHNlCgkJCQkJJiYgaXNVbkJsb2NrZWQoZ3JpZCwgaSArIDEsIGogKyAxKQoJCQkJCQkJPT0gdHJ1ZSkgewoJCQkJZ05ldyA9IGNlbGxEZXRhaWxzW2ldW2pdLmcgKyAxLjQxNDsKCQkJCWhOZXcgPSBjYWxjdWxhdGVIVmFsdWUoaSArIDEsIGogKyAxLCBkZXN0KTsKCQkJCWZOZXcgPSBnTmV3ICsgaE5ldzsKCgkJCQkvLyBJZiBpdCBpc27igJl0IG9uIHRoZSBvcGVuIGxpc3QsIGFkZCBpdCB0bwoJCQkJLy8gdGhlIG9wZW4gbGlzdC4gTWFrZSB0aGUgY3VycmVudCBzcXVhcmUKCQkJCS8vIHRoZSBwYXJlbnQgb2YgdGhpcyBzcXVhcmUuIFJlY29yZCB0aGUKCQkJCS8vIGYsIGcsIGFuZCBoIGNvc3RzIG9mIHRoZSBzcXVhcmUgY2VsbAoJCQkJLy8JCQkgT1IKCQkJCS8vIElmIGl0IGlzIG9uIHRoZSBvcGVuIGxpc3QgYWxyZWFkeSwgY2hlY2sKCQkJCS8vIHRvIHNlZSBpZiB0aGlzIHBhdGggdG8gdGhhdCBzcXVhcmUgaXMKCQkJCS8vIGJldHRlciwgdXNpbmcgJ2YnIGNvc3QgYXMgdGhlIG1lYXN1cmUuCgkJCQlpZiAoY2VsbERldGFpbHNbaSArIDFdW2ogKyAxXS5mID09IEZMVF9NQVgKCQkJCQl8fCBjZWxsRGV0YWlsc1tpICsgMV1baiArIDFdLmYgPiBmTmV3KSB7CgkJCQkJb3Blbkxpc3QuaW5zZXJ0KG1ha2VfcGFpcigKCQkJCQkJZk5ldywgbWFrZV9wYWlyKGkgKyAxLCBqICsgMSkpKTsKCgkJCQkJLy8gVXBkYXRlIHRoZSBkZXRhaWxzIG9mIHRoaXMgY2VsbAoJCQkJCWNlbGxEZXRhaWxzW2kgKyAxXVtqICsgMV0uZiA9IGZOZXc7CgkJCQkJY2VsbERldGFpbHNbaSArIDFdW2ogKyAxXS5nID0gZ05ldzsKCQkJCQljZWxsRGV0YWlsc1tpICsgMV1baiArIDFdLmggPSBoTmV3OwoJCQkJCWNlbGxEZXRhaWxzW2kgKyAxXVtqICsgMV0ucGFyZW50X2kgPSBpOwoJCQkJCWNlbGxEZXRhaWxzW2kgKyAxXVtqICsgMV0ucGFyZW50X2ogPSBqOwoJCQkJfQoJCQl9CgkJfQoKCQkvLy0tLS0tLS0tLS0tIDh0aCBTdWNjZXNzb3IgKFNvdXRoLVdlc3QpCgkJLy8tLS0tLS0tLS0tLS0KCgkJLy8gT25seSBwcm9jZXNzIHRoaXMgY2VsbCBpZiB0aGlzIGlzIGEgdmFsaWQgb25lCgkJaWYgKGlzVmFsaWQoaSArIDEsIGogLSAxKSA9PSB0cnVlKSB7CiAgICAgICAgICAgIAoJCQkvLyBJZiB0aGUgZGVzdGluYXRpb24gY2VsbCBpcyB0aGUgc2FtZSBhcyB0aGUKCQkJLy8gY3VycmVudCBzdWNjZXNzb3IKCQkJaWYgKGlzRGVzdGluYXRpb24oaSArIDEsIGogLSAxLCBkZXN0KSA9PSB0cnVlKSB7CgkJCQkvLyBTZXQgdGhlIFBhcmVudCBvZiB0aGUgZGVzdGluYXRpb24gY2VsbAoJCQkJY2VsbERldGFpbHNbaSArIDFdW2ogLSAxXS5wYXJlbnRfaSA9IGk7CgkJCQljZWxsRGV0YWlsc1tpICsgMV1baiAtIDFdLnBhcmVudF9qID0gajsKCQkJCXByaW50ZigiVGhlIGRlc3RpbmF0aW9uIGNlbGwgaXMgZm91bmRcbiIpOwoJCQkJdHJhY2VQYXRoKGNlbGxEZXRhaWxzLCBkZXN0KTsKCQkJCWZvdW5kRGVzdCA9IHRydWU7CgkJCQlyZXR1cm47CgkJCX0KCgkJCS8vIElmIHRoZSBzdWNjZXNzb3IgaXMgYWxyZWFkeSBvbiB0aGUgY2xvc2VkCgkJCS8vIGxpc3Qgb3IgaWYgaXQgaXMgYmxvY2tlZCwgdGhlbiBpZ25vcmUgaXQuCgkJCS8vIEVsc2UgZG8gdGhlIGZvbGxvd2luZwoJCQllbHNlIGlmIChjbG9zZWRMaXN0W2kgKyAxXVtqIC0gMV0gPT0gZmFsc2UKCQkJCQkmJiBpc1VuQmxvY2tlZChncmlkLCBpICsgMSwgaiAtIDEpCgkJCQkJCQk9PSB0cnVlKSB7CgkJCQlnTmV3ID0gY2VsbERldGFpbHNbaV1bal0uZyArIDEuNDE0OwoJCQkJaE5ldyA9IGNhbGN1bGF0ZUhWYWx1ZShpICsgMSwgaiAtIDEsIGRlc3QpOwoJCQkJZk5ldyA9IGdOZXcgKyBoTmV3OwoKCQkJCS8vIElmIGl0IGlzbuKAmXQgb24gdGhlIG9wZW4gbGlzdCwgYWRkIGl0IHRvCgkJCQkvLyB0aGUgb3BlbiBsaXN0LiBNYWtlIHRoZSBjdXJyZW50IHNxdWFyZQoJCQkJLy8gdGhlIHBhcmVudCBvZiB0aGlzIHNxdWFyZS4gUmVjb3JkIHRoZQoJCQkJLy8gZiwgZywgYW5kIGggY29zdHMgb2YgdGhlIHNxdWFyZSBjZWxsCgkJCQkvLwkJCSBPUgoJCQkJLy8gSWYgaXQgaXMgb24gdGhlIG9wZW4gbGlzdCBhbHJlYWR5LCBjaGVjawoJCQkJLy8gdG8gc2VlIGlmIHRoaXMgcGF0aCB0byB0aGF0IHNxdWFyZSBpcwoJCQkJLy8gYmV0dGVyLCB1c2luZyAnZicgY29zdCBhcyB0aGUgbWVhc3VyZS4KCQkJCWlmIChjZWxsRGV0YWlsc1tpICsgMV1baiAtIDFdLmYgPT0gRkxUX01BWAoJCQkJCXx8IGNlbGxEZXRhaWxzW2kgKyAxXVtqIC0gMV0uZiA+IGZOZXcpIHsKCQkJCQlvcGVuTGlzdC5pbnNlcnQobWFrZV9wYWlyKAoJCQkJCQlmTmV3LCBtYWtlX3BhaXIoaSArIDEsIGogLSAxKSkpOwoKCQkJCQkvLyBVcGRhdGUgdGhlIGRldGFpbHMgb2YgdGhpcyBjZWxsCgkJCQkJY2VsbERldGFpbHNbaSArIDFdW2ogLSAxXS5mID0gZk5ldzsKCQkJCQljZWxsRGV0YWlsc1tpICsgMV1baiAtIDFdLmcgPSBnTmV3OwoJCQkJCWNlbGxEZXRhaWxzW2kgKyAxXVtqIC0gMV0uaCA9IGhOZXc7CgkJCQkJY2VsbERldGFpbHNbaSArIDFdW2ogLSAxXS5wYXJlbnRfaSA9IGk7CgkJCQkJY2VsbERldGFpbHNbaSArIDFdW2ogLSAxXS5wYXJlbnRfaiA9IGo7CgkJCQl9CgkJCX0KCQl9CiAgICAgICAgKi8KICAgIH0KCgkvLyBXaGVuIHRoZSBkZXN0aW5hdGlvbiBjZWxsIGlzIG5vdCBmb3VuZCBhbmQgdGhlIG9wZW4KCS8vIGxpc3QgaXMgZW1wdHksIHRoZW4gd2UgY29uY2x1ZGUgdGhhdCB3ZSBmYWlsZWQgdG8KCS8vIHJlYWNoIHRoZSBkZXN0aW5hdGlvbiBjZWxsLiBUaGlzIG1heSBoYXBwZW4gd2hlbiB0aGUKCS8vIHRoZXJlIGlzIG5vIHdheSB0byBkZXN0aW5hdGlvbiBjZWxsIChkdWUgdG8KCS8vIGJsb2NrYWdlcykKCWlmIChmb3VuZERlc3QgPT0gZmFsc2UpCgkJcHJpbnRmKCJGYWlsZWQgdG8gZmluZCB0aGUgRGVzdGluYXRpb24gQ2VsbFxuIik7CgoJcmV0dXJuOwp9CgovLyBEcml2ZXIgcHJvZ3JhbSB0byB0ZXN0IGFib3ZlIGZ1bmN0aW9uCmludCBtYWluKCkKewoJLyogRGVzY3JpcHRpb24gb2YgdGhlIEdyaWQtCgkxLS0+IFRoZSBjZWxsIGlzIG5vdCBibG9ja2VkCgkwLS0+IFRoZSBjZWxsIGlzIGJsb2NrZWQgKi8KCWludCBncmlkW1JPV11bQ09MXQoJCT0gewogICAgICAgIHsgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgfSwKICAgICAgICB7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH0sCiAgICAgICAgeyAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCB9LAogICAgICAgIHsgMCwgMCwgMCwgMCwgNDE3MSwgNDE3MSwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgfSwKICAgICAgICB7IDAsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIH0sCiAgICAgICAgeyAwLCA0MTcxLCA0MTcxLCA0MTcxLCAwLCAwLCA0MTcxLCA0MTcxLCA0MTcxLCAwLCA0MTcxLCAwLCAwLCAwLCAwLCB9LAogICAgICAgIHsgMCwgNDE3MSwgNDE3MSwgNDE3MSwgMCwgMCwgNDE3MSwgNDE3MSwgNDE3MSwgMCwgNDE3MSwgMCwgMCwgMCwgMCwgfSwKICAgICAgICB7IDAsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIH0sCiAgICAgICAgeyAwLCAwLCAwLCAwLCA0MTcxLCA0MTcxLCAwLCA0MTcxLCA0MTcxLCAwLCA0MTcxLCA0MTcxLCAwLCAwLCAwLCB9LAogICAgICAgIHsgMCwgMCwgMCwgMCwgNDE3MSwgNDE3MSwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgfSwKICAgICAgICB7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH0sCiAgICAgICAgeyAwLCAwLCAwLCAwLCA0MTcxLCA0MTcxLCAwLCA0MTcxLCA0MTcxLCA0MTcxLCA0MTcxLCA0MTcxLCAwLCAwLCAwLCB9LAogICAgICAgIHsgMCwgNDE3MSwgNDE3MSwgNDE3MSwgNDE3MSwgNDE3MSwgNDE3MSwgNDE3MSwgMCwgMCwgMCwgNDE3MSwgNDE3MSwgNDE3MSwgMCwgfSwKICAgICAgICB7IDAsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDAsIDQxNzEsIDAsIDAsIDAsIDQxNzEsIDQxNzEsIDQxNzEsIDAsIH0sCiAgICAgICAgeyAwLCAwLCAwLCAwLCA0MTcxLCA0MTcxLCAwLCA0MTcxLCAwLCAwLCAwLCA0MTcxLCAwLCAwLCAwLCB9LAogICAgICAgIHsgMCwgMCwgMCwgMCwgNDE3MSwgNDE3MSwgMCwgNDE3MSwgNDE3MSwgNDE3MSwgNDE3MSwgNDE3MSwgMCwgMCwgMCwgfSwKICAgICAgICB7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIH0sCiAgICB9OwoKCS8vIFNvdXJjZSBpcyB0aGUgbGVmdC1tb3N0IGJvdHRvbS1tb3N0IGNvcm5lcgoJUGFpciBzcmMgPSBtYWtlX3BhaXIoNCwgMTIpOyAgIC8vIGludmVydAoKCS8vIERlc3RpbmF0aW9uIGlzIHRoZSBsZWZ0LW1vc3QgdG9wLW1vc3QgY29ybmVyCglQYWlyIGRlc3QgPSBtYWtlX3BhaXIoMTUsIDUpOyAgIC8vIGludmVydAoKCWFTdGFyU2VhcmNoKGdyaWQsIHNyYywgZGVzdCk7CgoJcmV0dXJuICgwKTsKfQo=