#ifndef _GEOMETRY_HPP_
#define _GEOMETRY_HPP_
#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
namespace geo
{
#define MEMBER_TYPE double
const MEMBER_TYPE EPS = 1e-10;
// 度数法から弧度法へ変換する。
template<typename T>
inline T degToRad(T d)
{
return d * M_PI / 180.0;
}
// 弧度法から度数法へ変換する。
template<typename T>
inline T radToDeg(T r)
{
return r * 180.0 / M_PI;
}
template<typename T>
class _Vector2D
{
public:
T x, y;
inline _Vector2D() {}
inline _Vector2D(T x, T y) : x(x), y(y) {}
// ノルムの二乗を返す。
inline T sqnorm()const {
return x*x + y*y;
}
// ノルムを返す。
inline T norm()const {
return std::sqrt(sqnorm());
}
// 偏角を返す。
inline T arg()const {
return std::atan2(y, x);
}
// 同じ方向の単位ベクトルを返す。
inline _Vector2D getNormalized()const {
return *this / norm();
}
// 回転したベクトルを返す。
inline _Vector2D getRotated(T angle)const {
T c = std::cos(angle), s = std::sin(angle);
return _Vector2D(c*x - s*y, s*x + c*y);
}
// 法線ベクトルを返す。
inline _Vector2D getNormal()const {
return _Vector2D(-y, x);
}
// 0ベクトルかどうかを返す。
inline bool isZero()const {
return std::abs(x) < EPS && std::abs(y) < EPS;
}
// unary operators
inline _Vector2D operator+ ()const {
return *this;
}
inline _Vector2D operator- ()const {
return _Vector2D(-x, -y);
}
// binary operators
inline _Vector2D operator+ (const _Vector2D& v)const {
return _Vector2D(x+v.x, y+v.y);
}
inline _Vector2D operator- (const _Vector2D& v)const {
return _Vector2D(x-v.x, y-v.y);
}
inline _Vector2D operator* (T k)const {
return _Vector2D(x*k, y*k);
}
inline _Vector2D operator/ (T k)const {
return _Vector2D(x/k, y/k);
}
inline _Vector2D& operator+=(const _Vector2D& v) {
x += v.x;
y += v.y;
return *this;
}
inline _Vector2D& operator-=(const _Vector2D& v) {
x -= v.x;
y -= v.y;
return *this;
}
inline _Vector2D& operator*=(T k) {
x *= k;
y *= k;
return *this;
}
inline _Vector2D& operator/=(T k) {
x /= k;
y /= k;
return *this;
}
inline bool operator==(const _Vector2D& v)const {
return (*this-v).sqnorm() < EPS;
}
// 直交座標からベクトルを定義する。
inline static _Vector2D fromCoordinates(T x, T y)
{
return _Vector2D(x, y);
}
// 長さr, 偏角θのベクトルを定義する。
inline static _Vector2D fromPolarForm(T r, T theta)
{
return _Vector2D(r*std::cos(theta), r*std::sin(theta));
}
};
// 内積を返す。
template<typename T>
inline T dot(const _Vector2D<T>& a, const _Vector2D<T>& b)
{
return a.x*b.x + a.y*b.y;
}
// 外積を返す。2次元ベクトルの場合はスカラ。
template<typename T>
inline T cross(const _Vector2D<T>& a, const _Vector2D<T>& b)
{
return a.x*b.y - a.y*b.x;
}
// 二つのベクトルが成す角(a->b)のsinを返す。
template<typename T>
inline T sin(const _Vector2D<T>& a, const _Vector2D<T>& b)
{
return cross(a, b) / sqrt(a.sqnorm() * b.sqnorm());
}
// 二つのベクトルが成す角(a->b)のcosを返す。
template<typename T>
inline T cos(const _Vector2D<T>& a, const _Vector2D<T>& b)
{
return dot(a, b) / sqrt(a.sqnorm() * b.sqnorm());
}
// 二つのベクトルが成す角(a->b)のtanを返す。
template<typename T>
inline T tan(const _Vector2D<T>& a, const _Vector2D<T>& b)
{
return cross(a, b) / dot(a, b);
}
// 二つのベクトルが成す角(a->b)を(-π, π]の範囲で返す。
template<typename T>
inline T arg(const _Vector2D<T>& a, const _Vector2D<T>& b)
{
return std::acos(cos(a, b)) * (cross(a, b) < 0.0 ? -1.0 : 1.0);
}
// scalar * vector
template<typename T>
inline _Vector2D<T> operator* (MEMBER_TYPE k, const _Vector2D<T>& v)
{
return _Vector2D<T>(k*v.x, k*v.y);
}
// output
template<typename T>
inline std::ostream& operator<<(std::ostream& out, const _Vector2D<T>& v)
{
return out << '(' << v.x << ", " << v.y << ')';
}
template<typename T>
class _Line2D
{
public:
_Vector2D<T> p; // p : 直線上の一点の位置ベクトル
_Vector2D<T> d; // d : 直線の方向ベクトル
inline _Line2D() {}
inline _Line2D(const _Vector2D<T>& p, const _Vector2D<T>& d) : p(p), d(d) {}
// 指定されたy座標に対応する直線上のx座標を返す。
inline T getX(T y)const {
return p.x + (y - p.y)*d.x / d.y;
}
// 指定されたx座標に対応する直線上のy座標を返す。
inline T getY(T x)const {
return p.y + (x - p.x)*d.y / d.x;
}
// 直線がx軸と成す角を(-π/2, π/2]の範囲で返す。
inline T getAngle()const {
T angle = d.arg();
return angle + (angle > M_PI_2 ? -M_PI : (angle > -M_PI_2 ? 0.0 : M_PI));
}
// 直線の傾きを返す。
inline T getSlope()const {
return d.y / d.x;
}
// 直線の方程式 ax+by+c=0 の係数a, b, cをそれぞれ引数に代入する。
inline void getLineEquation(T& a, T& b, T& c)const {
a = d.y;
b = -d.x;
c = cross(d, p);
}
inline bool operator==(const _Line2D L)const {
return std::abs(cross(d, L.d)) < EPS && std::abs(cross(p-L.p, d)) < EPS;
}
// 点pを通り、dに平行な直線を定義する。
inline static _Line2D fromPointAndDirection(const _Vector2D<T>& p, const _Vector2D<T>& d)
{
return _Line2D(p, d);
}
// 2点pとqを通る直線を定義する。
inline static _Line2D fromTwoPoints(const _Vector2D<T>& p, const _Vector2D<T>& q)
{
return _Line2D(p, q-p);
}
// pを通り、x軸と成す角度がθの直線を定義する。
inline static _Line2D fromPointAndAngle(const _Vector2D<T>& p, T theta)
{
return _Line2D(p, _Vector2D<T>::fromPolarForm(1.0, theta));
}
// pを通り、傾きがaの直線を定義する。
inline static _Line2D fromPointAndSlope(const _Vector2D<T>& p, T a)
{
return _Line2D(p, _Vector2D<T>(1.0, a));
}
// 直線 y=ax+b を定義する。
inline static _Line2D fromSlopeAndIntercept(T a, T b)
{
return fromPointAndSlope(_Vector2D<T>(0.0, b), a);
}
// 直線 ax+by+c=0 を定義する。
inline static _Line2D fromLineEquation(T a, T b, T c)
{
if(std::abs(a) > std::abs(b))
return _Line2D(_Vector2D<T>(-c/a, 0.0), _Vector2D<T>(-b, a));
else
return _Line2D(_Vector2D<T>(0.0, -c/b), _Vector2D<T>(b, -a));
}
};
template<typename T>
class _Ellipse2D
{
public:
_Vector2D<T> center; // 中心座標
T A, B; // A : 軸A方向の半長, B : 軸B方向の半長
T angle; // 軸Aとx軸の成す角
inline _Ellipse2D() {}
inline _Ellipse2D(const _Vector2D<T>& center, T A, T B, T angle) : center(center), A(A), B(B), angle(angle) {}
// 長軸の半長を返す。
inline T getHalfMajorLength()const {
return std::max(A, B);
}
// 長軸の全長を返す。
inline T getMajorLength()const {
return getHalfMajorLength() * 2.0;
}
// 短軸の半長を返す。
inline T getHalfMinorLength()const {
return std::min(A, B);
}
// 短軸の全長を返す。
inline T getMinorLength()const {
return getHalfMinorLength() * 2.0;
}
// 長軸の両端の座標を返す。
inline std::pair<_Vector2D<T>, _Vector2D<T> > getMajorEnds()const {
_Vector2D<T> tmp;
if(A < B)
tmp = B * _Vector2D<T>(-std::sin(angle), std::cos(angle));
else
tmp = A * _Vector2D<T>(std::cos(angle), std::sin(angle));
return std::make_pair(center + tmp, center - tmp);
}
// 短軸の両端の座標を返す。
inline std::pair<_Vector2D<T>, _Vector2D<T> > getMinorEnds()const {
_Vector2D<T> tmp;
if(A < B)
tmp = A * _Vector2D<T>(std::cos(angle), std::sin(angle));
else
tmp = B * _Vector2D<T>(-std::sin(angle), std::cos(angle));
return std::make_pair(center + tmp, center - tmp);
}
// 長軸とx軸が成す角を返す。
inline T getMajorArgument()const {
if(A < B)
return angle + (angle < 0.0 ? M_PI_2 : -M_PI_2);
else
return angle;
}
// 短軸とx軸が成す角を返す。
inline T getMinorArgument()const {
if(A < B)
return angle;
else
return angle + (angle < 0.0 ? M_PI_2 : -M_PI_2);
}
// 長軸の直線を返す。
inline _Line2D<T> getMajorLine()const {
T arg = getMajorArgument();
return _Line2D<T>(center, _Vector2D<T>(std::cos(arg), std::sin(arg)));
}
// 短軸の直線を返す。
inline _Line2D<T> getMinorLine()const {
T arg = getMinorArgument();
return _Line2D<T>(center, _Vector2D<T>(std::cos(arg), std::sin(arg)));
}
// 楕円が円かどうかを返す。
inline bool isCircle()const {
return abs(A-B) < EPS;
}
// 面積を返す。
inline T getArea()const {
return M_PI * A * B;
}
// 楕円弧上で最もx座標が小さい点を返す。
inline _Vector2D<T> getLeft()const {
T cos = std::cos(angle);
T sin = std::sin(angle);
T x = -_Vector2D<T>(A*cos, B*sin).norm();
return _Vector2D<T>(x+center.x, (A*A-B*B)*sin*cos/x + center.y);
}
// 楕円弧上で最もx座標が大きい点を返す。
inline _Vector2D<T> getRight()const {
T cos = std::cos(angle);
T sin = std::sin(angle);
T x = _Vector2D<T>(A*cos, B*sin).norm();
return _Vector2D<T>(x+center.x, (A*A-B*B)*sin*cos/x + center.y);
}
// 楕円弧上で最もy座標が小さい点を返す。
inline _Vector2D<T> getTop()const {
T cos = std::cos(angle);
T sin = std::sin(angle);
T y = -_Vector2D<T>(A*sin, B*cos).norm();
return _Vector2D<T>((A*A-B*B)*sin*cos/y + center.x, y+center.y);
}
// 楕円弧上で最もy座標が大きい点を返す。
inline _Vector2D<T> getBottom()const {
T cos = std::cos(angle);
T sin = std::sin(angle);
T y = _Vector2D<T>(A*sin, B*cos).norm();
return _Vector2D<T>((A*A-B*B)*sin*cos/y + center.x, y+center.y);
}
// 指定されたy座標に対応する直線上のx座標を引数にそれぞれ代入する(x1≦x2)。
// 戻り値は対応点の個数(0~2)。
inline int getX(T y, T& x1, T& x2)const {
T a, b, c, d, e, f;
getEquation(a, b, c, d, e, f);
b = b*y + d;
c = c*y*y + e*y + f;
T D = b*b - 4.0*a*c;
if(std::abs(D) < EPS){
x1 = x2 = -b / (2.0*a);
return 1;
}
else if(D > 0.0){
D = std::sqrt(D);
x1 = (-b-D)/(2.0*a);
x2 = (-b+D)/(2.0*a);
return 2;
}
else
return 0;
}
// 楕円の方程式 ax^2+bxy+cy^2+dx+ey+f=0 の各係数をそれぞれ引数に代入する。
inline void getEquation(T& a, T& b, T& c, T& d, T& e, T& f)const {
T cos = std::cos(angle);
T sin = std::sin(angle);
T a2 = 1.0 / (A * A);
T b2 = 1.0 / (B * B);
a = cos*cos*a2 + sin*sin*b2;
b = 2.0*(a2-b2)*sin*cos;
c = sin*sin*a2 + cos*cos*b2;
d = -2.0*center.x*a - center.y*b;
e = -2.0*center.y*c - center.x*b;
T tmp1 = center.x*cos + center.y*sin;
T tmp2 = -center.x*sin + center.y*cos;
f = tmp1*tmp1*a2 + tmp2*tmp2*b2 - 1.0;
}
inline bool operator==(const _Ellipse2D& ell)const {
return center == ell.center
&& std::abs(getMajorLength() - ell.getMajorLength()) < EPS
&& std::abs(getMinorLength() - ell.getMinorLength()) < EPS
&& (std::abs(A-B) < EPS || std::abs(getMajorArgument() - ell.getMajorArgument()));
}
// 楕円の中心と軸の半長と角度から楕円を定義する。
inline static _Ellipse2D fromCenterAndLengthesAndAngle(const _Vector2D<T>& center, T A, T B, T angle)
{
return _Ellipse2D(center, A, B, angle);
}
// (v.x, v.y), (v.x+w, v.y), (v.x, v.y+h), (v.x+w, v.y+h)を頂点とする長方形に内接する楕円を定義する。
inline static _Ellipse2D fromRectangle(const _Vector2D<T>& v, T w, T h)
{
w *= 0.5;
h *= 0.5;
return _Ellipse2D(_Vector2D<T>(v.x + w, v.y + h), w, h, 0.0);
}
// 二次曲線 ax^2+bxy+cy^2+dx+ey+f=0 が楕円の方程式かどうかを判別する。
inline static bool isEllipseEquation(T a, T b, T c, T d, T e, T f)
{
T D = 4.0*a*c - b*b;
return D > 0.0 && a*((d*(b*e-2.0*c*d)+e*(b*d-2.0*a*e))/D + 2.0*f) < 0.0;
}
// 楕円の方程式 ax^2+bxy+cy^2+dx+ey+f=0 から楕円を定義する。
inline static _Ellipse2D fromEquation(T a, T b, T c, T d, T e, T f)
{
_Ellipse2D ell;
ell.center = _Vector2D<T>(b*e-2.0*c*d, b*d-2.0*a*e) / (4.0*a*c - b*b);
T sum = a + c;
T diff = a - c;
T sq = std::sqrt(diff*diff + b*b);
T beta = -d*ell.center.x - e*ell.center.y - 2.0*f;
ell.A = std::sqrt(beta/(sum+sq));
ell.B = std::sqrt(beta/(sum-sq));
ell.angle = a>c ? std::atan2(b, diff+sq) : std::atan2(-diff+sq, b);
return ell;
}
};
template<typename T>
class _Circle2D
{
public:
_Vector2D<T> center; // 中心座標
T radius; // 半径
inline _Circle2D() {}
inline _Circle2D(const _Vector2D<T>& center, T radius) : center(center), radius(radius) {}
// 円の方程式 x^2+ax+y^2+by+c=0 の各係数a, b, cをそれぞれ引数に代入する。
inline void getCircleEquation(T& a, T& b, T& c)const {
a = -2.0 * center.x;
b = -2.0 * center.y;
c = center.sqnorm() - radius*radius;
}
// 面積を返す。
inline T getArea()const {
return M_PI * radius * radius;
}
inline bool operator==(const _Circle2D& C)const {
return center == C.center && std::abs(radius - C.radius) < EPS;
}
// 楕円への変換
inline operator _Ellipse2D<T>() const{
return _Ellipse2D<T>::fromCenterAndLengthesAndAngle(center, radius, radius, 0.0);
}
// 中心座標と半径から円を定義する。
inline static _Circle2D fromCenterAndRadius(const _Vector2D<T>& c, T r)
{
return _Circle2D(c, r);
}
// 中心座標と円周上の一点から円を定義する。
inline static _Circle2D fromCenterAndPoint(const _Vector2D<T>& c, const _Vector2D<T>& p)
{
return _Circle2D(c, (c-p).norm());
}
// 指定された二点を直径の両端とする円を定義する。
inline static _Circle2D fromDiaEnds(const _Vector2D<T>& a, const _Vector2D<T>& b)
{
return _Circle2D((a+b)*0.5, (a-b).norm()*0.5);
}
// 円周上の三点から円を定義する。
inline static _Circle2D fromThreePoints(const _Vector2D<T>& a, const _Vector2D<T>& b, const _Vector2D<T>& c)
{
_Vector2D<T> A(2.0*(b.x-a.x), 2.0*(c.x-a.x));
_Vector2D<T> B(2.0*(b.y-a.y), 2.0*(c.y-a.y));
T asq = a.sqnorm();
_Vector2D<T> C(asq-b.sqnorm(), asq-c.sqnorm());
_Vector2D<T> center = Vector2D(cross(B, C), cross(C, A)) / cross(A, B);
return _Circle2D(center, (center-a).norm());
}
// (v.x, v.y), (v.x+a, v.y), (v.x, v.y+a), (v.x+a, v.y+a)を頂点とする正方形に内接する円を定義する。
inline static _Circle2D fromSquare(const _Vector2D<T>& v, T a)
{
a *= 0.5;
return _Circle2D(_Vector2D<T>(v.x+a, v.y+a), std::abs(a));
}
// 円 x^2+ax+y^2+by+c=0 を定義する。
inline static _Circle2D fromCircleEquation(T a, T b, T c)
{
_Vector2D<T> center(-a*0.5, -b*0.5);
return _Circle2D(center, sqrt(center.sqnorm() - c));
}
};
// 点Pと直線Lの距離を返す。
template<typename T>
inline T getDistance(const _Vector2D<T>& P, const _Line2D<T>& L)
{
T a, b, c;
L.getLinearEquation(a, b, c);
return std::abs(a*P.x + b*P.y + c)/std::sqrt(a*a + b*b);
}
// 直線Lと直線Mの交点をinterに代入する。
// 戻り値は交点の個数(0~1)。aとbが重なっている時は-1。
template<typename T>
int getIntersection(const _Line2D<T>& L, const _Line2D<T>& M, _Vector2D<T>& inter)
{
T denominator = cross(L.d, M.d);
T numerator = cross(M.p-L.p, M.d);
if(std::abs(denominator) < EPS){
return std::abs(numerator) < EPS ? -1 : 0;
}
else{
inter = L.p + numerator/denominator * L.d;
return 1;
}
}
// 直線Lと円Cの交点をinter1, inter2に代入する。
// 戻り値は交点の個数(0~2)。
template<typename T>
int getIntersection(const _Line2D<T>& L, const _Circle2D<T>& C, _Vector2D<T>& inter1, _Vector2D<T>& inter2)
{
_Vector2D<T> diff = L.p - C.center;
T a = L.d.sqnorm();
T b = dot(L.d, diff);
T c = diff.sqnorm() - C.radius * C.radius;
T D = b*b - a*c;
if(std::abs(D) < EPS){
inter1 = inter2 = L.p - b/a * L.d;
return 1;
}
else if(D > 0.0){
D = std::sqrt(D);
inter1 = L.p + (-b+D)/a * L.d;
inter2 = L.p - (b+D)/a * L.d;
return 2;
}
else{
return 0;
}
}
typedef _Vector2D<MEMBER_TYPE> Vector2D;
typedef _Line2D<MEMBER_TYPE> Line2D;
typedef _Circle2D<MEMBER_TYPE> Circle2D;
typedef _Ellipse2D<MEMBER_TYPE> Ellipse2D;
#ifdef __OPENCV_CORE_C_H__
namespace opencv
{
template<typename T>
inline CvPoint vecToCP(T x, T y) {
return cvPoint(static_cast<int>(x + 0.5), static_cast<int>(y + 0.5));
}
template<typename T>
inline CvPoint vecToCP(const _Vector2D<T>& v) {
return vecToCP(v.x, v.y);
}
// 点を描く。
template<typename T>
inline void drawPoint(CvArr* img, const _Vector2D<T>& point, CvScalar color, int radius=3, int thickness=-1, int lineType=CV_AA, int shift=0)
{
cvCircle(img, vecToCP(point), radius, color, thickness, lineType, shift);
}
// 直線を描く。
template<typename T>
void drawLine(IplImage* img, const _Line2D<T>& line, CvScalar color, int thickness=1, int line_type=8, int shift=0)
{
double h = img->height + 1.0, w = img->width + 1.0;
CvPoint p1, p2;
if(std::abs(line.d.x) < std::abs(line.d.y)){
p1 = vecToCP(line.getX(-1.0), -1.0);
p2 = vecToCP(line.getX(h), h);
}
else{
p1 = vecToCP(-1.0, line.getY(-1.0));
p2 = vecToCP(w, line.getY(w));
}
cvLine(img, p1, p2, color, thickness, line_type, shift);
}
// 円を描く。
template<typename T>
inline void drawCircle(CvArr* img, const _Circle2D<T>& circle, CvScalar color, int thickness=1, int lineType=8, int shift=0)
{
cvCircle(img, vecToCP(circle.center), static_cast<int>(circle.radius + 0.5), color, thickness, lineType, shift);
}
// 楕円を描く。
template<typename T>
inline void drawEllipse(CvArr* img, const _Ellipse2D<T>& ellipse, CvScalar color, int thickness=1, int lineType=8, int shift=0)
{
cvEllipse(
img,
vecToCP(ellipse.center),
cvSize(static_cast<int>(ellipse.A + 0.5), static_cast<int>(ellipse.B + 0.5)),
radToDeg(ellipse.angle), 0.0, 360.0,
color, thickness, lineType, shift
);
}
}
#endif
}
#endif
I2lmbmRlZiBfR0VPTUVUUllfSFBQXwojZGVmaW5lIF9HRU9NRVRSWV9IUFBfCgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHV0aWxpdHk+CgpuYW1lc3BhY2UgZ2VvCnsKCSNkZWZpbmUgTUVNQkVSX1RZUEUgZG91YmxlCgljb25zdCBNRU1CRVJfVFlQRSBFUFMgPSAxZS0xMDsKCgkvLyDluqbmlbDms5XjgYvjgonlvKfluqbms5XjgbjlpInmj5vjgZnjgovjgIIKCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CglpbmxpbmUgVCBkZWdUb1JhZChUIGQpCgl7CgkJcmV0dXJuIGQgKiBNX1BJIC8gMTgwLjA7Cgl9CgoJLy8g5byn5bqm5rOV44GL44KJ5bqm5pWw5rOV44G45aSJ5o+b44GZ44KL44CCCgl0ZW1wbGF0ZTx0eXBlbmFtZSBUPgoJaW5saW5lIFQgcmFkVG9EZWcoVCByKQoJewoJCXJldHVybiByICogMTgwLjAgLyBNX1BJOwoJfQoKCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CgljbGFzcyBfVmVjdG9yMkQKCXsKCXB1YmxpYzoKCQlUIHgsIHk7CgoJCWlubGluZSBfVmVjdG9yMkQoKSB7fQoJCWlubGluZSBfVmVjdG9yMkQoVCB4LCBUIHkpIDogeCh4KSwgeSh5KSB7fQoJCgkJLy8g44OO44Or44Og44Gu5LqM5LmX44KS6L+U44GZ44CCCgkJaW5saW5lIFQgc3Fub3JtKCljb25zdCB7CgkJCXJldHVybiB4KnggKyB5Knk7CgkJfQoJCS8vIOODjuODq+ODoOOCkui/lOOBmeOAggoJCWlubGluZSBUIG5vcm0oKWNvbnN0IHsKCQkJcmV0dXJuIHN0ZDo6c3FydChzcW5vcm0oKSk7CgkJfQoJCS8vIOWBj+inkuOCkui/lOOBmeOAggoJCWlubGluZSBUIGFyZygpY29uc3QgewoJCQlyZXR1cm4gc3RkOjphdGFuMih5LCB4KTsKCQl9CgkJLy8g5ZCM44GY5pa55ZCR44Gu5Y2Y5L2N44OZ44Kv44OI44Or44KS6L+U44GZ44CCCgkJaW5saW5lIF9WZWN0b3IyRCBnZXROb3JtYWxpemVkKCljb25zdCB7CgkJCXJldHVybiAqdGhpcyAvIG5vcm0oKTsKCQl9CgkJLy8g5Zue6Lui44GX44Gf44OZ44Kv44OI44Or44KS6L+U44GZ44CCCgkJaW5saW5lIF9WZWN0b3IyRCBnZXRSb3RhdGVkKFQgYW5nbGUpY29uc3QgewoJCQlUIGMgPSBzdGQ6OmNvcyhhbmdsZSksIHMgPSBzdGQ6OnNpbihhbmdsZSk7CgkJCXJldHVybiBfVmVjdG9yMkQoYyp4IC0gcyp5LCBzKnggKyBjKnkpOwoJCX0KCQkvLyDms5Xnt5rjg5njgq/jg4jjg6vjgpLov5TjgZnjgIIKCQlpbmxpbmUgX1ZlY3RvcjJEIGdldE5vcm1hbCgpY29uc3QgewoJCQlyZXR1cm4gX1ZlY3RvcjJEKC15LCB4KTsKCQl9CgkJLy8gMOODmeOCr+ODiOODq+OBi+OBqeOBhuOBi+OCkui/lOOBmeOAggoJCWlubGluZSBib29sIGlzWmVybygpY29uc3QgewoJCQlyZXR1cm4gc3RkOjphYnMoeCkgPCBFUFMgJiYgc3RkOjphYnMoeSkgPCBFUFM7CgkJfQoKCQkvLyB1bmFyeSBvcGVyYXRvcnMKCQlpbmxpbmUgX1ZlY3RvcjJEIG9wZXJhdG9yKyAoKWNvbnN0IHsKCQkJcmV0dXJuICp0aGlzOwoJCX0KCQlpbmxpbmUgX1ZlY3RvcjJEIG9wZXJhdG9yLSAoKWNvbnN0IHsKCQkJcmV0dXJuIF9WZWN0b3IyRCgteCwgLXkpOwoJCX0KCgkJLy8gYmluYXJ5IG9wZXJhdG9ycwoJCWlubGluZSBfVmVjdG9yMkQgb3BlcmF0b3IrIChjb25zdCBfVmVjdG9yMkQmIHYpY29uc3QgewoJCQlyZXR1cm4gX1ZlY3RvcjJEKHgrdi54LCB5K3YueSk7CgkJfQoJCWlubGluZSBfVmVjdG9yMkQgb3BlcmF0b3ItIChjb25zdCBfVmVjdG9yMkQmIHYpY29uc3QgewoJCQlyZXR1cm4gX1ZlY3RvcjJEKHgtdi54LCB5LXYueSk7CgkJfQoJCWlubGluZSBfVmVjdG9yMkQgb3BlcmF0b3IqIChUIGspY29uc3QgewoJCQlyZXR1cm4gX1ZlY3RvcjJEKHgqaywgeSprKTsKCQl9CgkJaW5saW5lIF9WZWN0b3IyRCBvcGVyYXRvci8gKFQgayljb25zdCB7CgkJCXJldHVybiBfVmVjdG9yMkQoeC9rLCB5L2spOwoJCX0KCQlpbmxpbmUgX1ZlY3RvcjJEJiBvcGVyYXRvcis9KGNvbnN0IF9WZWN0b3IyRCYgdikgewoJCQl4ICs9IHYueDsKCQkJeSArPSB2Lnk7CgkJCXJldHVybiAqdGhpczsKCQl9CgkJaW5saW5lIF9WZWN0b3IyRCYgb3BlcmF0b3ItPShjb25zdCBfVmVjdG9yMkQmIHYpIHsKCQkJeCAtPSB2Lng7CgkJCXkgLT0gdi55OwoJCQlyZXR1cm4gKnRoaXM7CgkJfQoJCWlubGluZSBfVmVjdG9yMkQmIG9wZXJhdG9yKj0oVCBrKSB7CgkJCXggKj0gazsKCQkJeSAqPSBrOwoJCQlyZXR1cm4gKnRoaXM7CgkJfQoJCWlubGluZSBfVmVjdG9yMkQmIG9wZXJhdG9yLz0oVCBrKSB7CgkJCXggLz0gazsKCQkJeSAvPSBrOwoJCQlyZXR1cm4gKnRoaXM7CgkJfQoJCWlubGluZSBib29sIG9wZXJhdG9yPT0oY29uc3QgX1ZlY3RvcjJEJiB2KWNvbnN0IHsKCQkJcmV0dXJuICgqdGhpcy12KS5zcW5vcm0oKSA8IEVQUzsKCQl9CgoJCS8vIOebtOS6pOW6p+aomeOBi+OCieODmeOCr+ODiOODq+OCkuWumue+qeOBmeOCi+OAggoJCWlubGluZSBzdGF0aWMgX1ZlY3RvcjJEIGZyb21Db29yZGluYXRlcyhUIHgsIFQgeSkKCQl7CgkJCXJldHVybiBfVmVjdG9yMkQoeCwgeSk7CgkJfQoKCQkvLyDplbfjgZVyLCDlgY/op5LOuOOBruODmeOCr+ODiOODq+OCkuWumue+qeOBmeOCi+OAggoJCWlubGluZSBzdGF0aWMgX1ZlY3RvcjJEIGZyb21Qb2xhckZvcm0oVCByLCBUIHRoZXRhKQoJCXsKCQkJcmV0dXJuIF9WZWN0b3IyRChyKnN0ZDo6Y29zKHRoZXRhKSwgcipzdGQ6OnNpbih0aGV0YSkpOwoJCX0KCX07CgoJLy8g5YaF56mN44KS6L+U44GZ44CCCgl0ZW1wbGF0ZTx0eXBlbmFtZSBUPgoJaW5saW5lIFQgZG90KGNvbnN0IF9WZWN0b3IyRDxUPiYgYSwgY29uc3QgX1ZlY3RvcjJEPFQ+JiBiKQoJewoJCXJldHVybiBhLngqYi54ICsgYS55KmIueTsKCX0KCgkvLyDlpJbnqY3jgpLov5TjgZnjgIIy5qyh5YWD44OZ44Kv44OI44Or44Gu5aC05ZCI44Gv44K544Kr44Op44CCCgl0ZW1wbGF0ZTx0eXBlbmFtZSBUPgoJaW5saW5lIFQgY3Jvc3MoY29uc3QgX1ZlY3RvcjJEPFQ+JiBhLCBjb25zdCBfVmVjdG9yMkQ8VD4mIGIpCgl7CgkJcmV0dXJuIGEueCpiLnkgLSBhLnkqYi54OwoJfQoKCS8vIOS6jOOBpOOBruODmeOCr+ODiOODq+OBjOaIkOOBmeinkihhLT5iKeOBrnNpbuOCkui/lOOBmeOAggoJdGVtcGxhdGU8dHlwZW5hbWUgVD4KCWlubGluZSBUIHNpbihjb25zdCBfVmVjdG9yMkQ8VD4mIGEsIGNvbnN0IF9WZWN0b3IyRDxUPiYgYikKCXsKCQlyZXR1cm4gY3Jvc3MoYSwgYikgLyBzcXJ0KGEuc3Fub3JtKCkgKiBiLnNxbm9ybSgpKTsKCX0KCgkvLyDkuozjgaTjga7jg5njgq/jg4jjg6vjgYzmiJDjgZnop5IoYS0+Yinjga5jb3PjgpLov5TjgZnjgIIKCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CglpbmxpbmUgVCBjb3MoY29uc3QgX1ZlY3RvcjJEPFQ+JiBhLCBjb25zdCBfVmVjdG9yMkQ8VD4mIGIpCgl7CgkJcmV0dXJuIGRvdChhLCBiKSAvIHNxcnQoYS5zcW5vcm0oKSAqIGIuc3Fub3JtKCkpOwoJfQoKCS8vIOS6jOOBpOOBruODmeOCr+ODiOODq+OBjOaIkOOBmeinkihhLT5iKeOBrnRhbuOCkui/lOOBmeOAggoJdGVtcGxhdGU8dHlwZW5hbWUgVD4KCWlubGluZSBUIHRhbihjb25zdCBfVmVjdG9yMkQ8VD4mIGEsIGNvbnN0IF9WZWN0b3IyRDxUPiYgYikKCXsKCQlyZXR1cm4gY3Jvc3MoYSwgYikgLyBkb3QoYSwgYik7Cgl9CgoJLy8g5LqM44Gk44Gu44OZ44Kv44OI44Or44GM5oiQ44GZ6KeSKGEtPmIp44KSKC3PgCwgz4Bd44Gu56+E5Zuy44Gn6L+U44GZ44CCCgl0ZW1wbGF0ZTx0eXBlbmFtZSBUPgoJaW5saW5lIFQgYXJnKGNvbnN0IF9WZWN0b3IyRDxUPiYgYSwgY29uc3QgX1ZlY3RvcjJEPFQ+JiBiKQoJewoJCXJldHVybiBzdGQ6OmFjb3MoY29zKGEsIGIpKSAqIChjcm9zcyhhLCBiKSA8IDAuMCA/IC0xLjAgOiAxLjApOwoJfQoKCS8vIHNjYWxhciAqIHZlY3RvcgoJdGVtcGxhdGU8dHlwZW5hbWUgVD4KCWlubGluZSBfVmVjdG9yMkQ8VD4gb3BlcmF0b3IqIChNRU1CRVJfVFlQRSBrLCBjb25zdCBfVmVjdG9yMkQ8VD4mIHYpCgl7CgkJcmV0dXJuIF9WZWN0b3IyRDxUPihrKnYueCwgayp2LnkpOwoJfQoKCS8vIG91dHB1dAoJdGVtcGxhdGU8dHlwZW5hbWUgVD4KCWlubGluZSBzdGQ6Om9zdHJlYW0mIG9wZXJhdG9yPDwoc3RkOjpvc3RyZWFtJiBvdXQsIGNvbnN0IF9WZWN0b3IyRDxUPiYgdikKCXsKCQlyZXR1cm4gb3V0IDw8ICcoJyA8PCB2LnggPDwgIiwgIiA8PCB2LnkgPDwgJyknOwoJfQoKCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CgljbGFzcyBfTGluZTJECgl7CglwdWJsaWM6CgkJX1ZlY3RvcjJEPFQ+IHA7IC8vIHAgOiDnm7Tnt5rkuIrjga7kuIDngrnjga7kvY3nva7jg5njgq/jg4jjg6sKCQlfVmVjdG9yMkQ8VD4gZDsgLy8gZCA6IOebtOe3muOBruaWueWQkeODmeOCr+ODiOODqwoJCQoJCWlubGluZSBfTGluZTJEKCkge30KCQlpbmxpbmUgX0xpbmUyRChjb25zdCBfVmVjdG9yMkQ8VD4mIHAsIGNvbnN0IF9WZWN0b3IyRDxUPiYgZCkgOiBwKHApLCBkKGQpIHt9CgoJCS8vIOaMh+WumuOBleOCjOOBn3nluqfmqJnjgavlr77lv5zjgZnjgovnm7Tnt5rkuIrjga545bqn5qiZ44KS6L+U44GZ44CCCgkJaW5saW5lIFQgZ2V0WChUIHkpY29uc3QgewoJCQlyZXR1cm4gcC54ICsgKHkgLSBwLnkpKmQueCAvIGQueTsKCQl9CgkJCgkJLy8g5oyH5a6a44GV44KM44GfeOW6p+aomeOBq+WvvuW/nOOBmeOCi+ebtOe3muS4iuOBrnnluqfmqJnjgpLov5TjgZnjgIIKCQlpbmxpbmUgVCBnZXRZKFQgeCljb25zdCB7CgkJCXJldHVybiBwLnkgKyAoeCAtIHAueCkqZC55IC8gZC54OwoJCX0KCgkJLy8g55u057ea44GMeOi7uOOBqOaIkOOBmeinkuOCkigtz4AvMiwgz4AvMl3jga7nr4Tlm7Ljgafov5TjgZnjgIIKCQlpbmxpbmUgVCBnZXRBbmdsZSgpY29uc3QgewoJCQlUIGFuZ2xlID0gZC5hcmcoKTsKCQkJcmV0dXJuIGFuZ2xlICsgKGFuZ2xlID4gTV9QSV8yID8gLU1fUEkgOiAoYW5nbGUgPiAtTV9QSV8yID8gMC4wIDogTV9QSSkpOwoJCX0KCgkJLy8g55u057ea44Gu5YK+44GN44KS6L+U44GZ44CCCgkJaW5saW5lIFQgZ2V0U2xvcGUoKWNvbnN0IHsKCQkJcmV0dXJuIGQueSAvIGQueDsKCQl9CgoJCS8vIOebtOe3muOBruaWueeoi+W8jyBheCtieStjPTAg44Gu5L+C5pWwYSwgYiwgY+OCkuOBneOCjOOBnuOCjOW8leaVsOOBq+S7o+WFpeOBmeOCi+OAggoJCWlubGluZSB2b2lkIGdldExpbmVFcXVhdGlvbihUJiBhLCBUJiBiLCBUJiBjKWNvbnN0IHsKCQkJYSA9IGQueTsKCQkJYiA9IC1kLng7CgkJCWMgPSBjcm9zcyhkLCBwKTsKCQl9CgoJCWlubGluZSBib29sIG9wZXJhdG9yPT0oY29uc3QgX0xpbmUyRCBMKWNvbnN0IHsKCQkJcmV0dXJuIHN0ZDo6YWJzKGNyb3NzKGQsIEwuZCkpIDwgRVBTICYmIHN0ZDo6YWJzKGNyb3NzKHAtTC5wLCBkKSkgPCBFUFM7CgkJfQoKCQkvLyDngrlw44KS6YCa44KK44CBZOOBq+W5s+ihjOOBquebtOe3muOCkuWumue+qeOBmeOCi+OAggoJCWlubGluZSBzdGF0aWMgX0xpbmUyRCBmcm9tUG9pbnRBbmREaXJlY3Rpb24oY29uc3QgX1ZlY3RvcjJEPFQ+JiBwLCBjb25zdCBfVmVjdG9yMkQ8VD4mIGQpCgkJewoJCQlyZXR1cm4gX0xpbmUyRChwLCBkKTsKCQl9CgoJCS8vIDLngrlw44GoceOCkumAmuOCi+ebtOe3muOCkuWumue+qeOBmeOCi+OAggoJCWlubGluZSBzdGF0aWMgX0xpbmUyRCBmcm9tVHdvUG9pbnRzKGNvbnN0IF9WZWN0b3IyRDxUPiYgcCwgY29uc3QgX1ZlY3RvcjJEPFQ+JiBxKQoJCXsKCQkJcmV0dXJuIF9MaW5lMkQocCwgcS1wKTsKCQl9CgoJCS8vIHDjgpLpgJrjgorjgIF46Lu444Go5oiQ44GZ6KeS5bqm44GMzrjjga7nm7Tnt5rjgpLlrprnvqnjgZnjgovjgIIKCQlpbmxpbmUgc3RhdGljIF9MaW5lMkQgZnJvbVBvaW50QW5kQW5nbGUoY29uc3QgX1ZlY3RvcjJEPFQ+JiBwLCBUIHRoZXRhKQoJCXsKCQkJcmV0dXJuIF9MaW5lMkQocCwgX1ZlY3RvcjJEPFQ+Ojpmcm9tUG9sYXJGb3JtKDEuMCwgdGhldGEpKTsKCQl9CgoJCS8vIHDjgpLpgJrjgorjgIHlgr7jgY3jgYxh44Gu55u057ea44KS5a6a576p44GZ44KL44CCCgkJaW5saW5lIHN0YXRpYyBfTGluZTJEIGZyb21Qb2ludEFuZFNsb3BlKGNvbnN0IF9WZWN0b3IyRDxUPiYgcCwgVCBhKQoJCXsKCQkJcmV0dXJuIF9MaW5lMkQocCwgX1ZlY3RvcjJEPFQ+KDEuMCwgYSkpOwoJCX0KCgkJLy8g55u057eaIHk9YXgrYiDjgpLlrprnvqnjgZnjgovjgIIKCQlpbmxpbmUgc3RhdGljIF9MaW5lMkQgZnJvbVNsb3BlQW5kSW50ZXJjZXB0KFQgYSwgVCBiKQoJCXsKCQkJcmV0dXJuIGZyb21Qb2ludEFuZFNsb3BlKF9WZWN0b3IyRDxUPigwLjAsIGIpLCBhKTsKCQl9CgoJCS8vIOebtOe3miBheCtieStjPTAg44KS5a6a576p44GZ44KL44CCCgkJaW5saW5lIHN0YXRpYyBfTGluZTJEIGZyb21MaW5lRXF1YXRpb24oVCBhLCBUIGIsIFQgYykKCQl7CgkJCWlmKHN0ZDo6YWJzKGEpID4gc3RkOjphYnMoYikpCgkJCQlyZXR1cm4gX0xpbmUyRChfVmVjdG9yMkQ8VD4oLWMvYSwgMC4wKSwgX1ZlY3RvcjJEPFQ+KC1iLCBhKSk7CgkJCWVsc2UKCQkJCXJldHVybiBfTGluZTJEKF9WZWN0b3IyRDxUPigwLjAsIC1jL2IpLCBfVmVjdG9yMkQ8VD4oYiwgLWEpKTsKCQl9Cgl9OwoKCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CgljbGFzcyBfRWxsaXBzZTJECgl7CglwdWJsaWM6CgkJX1ZlY3RvcjJEPFQ+IGNlbnRlcjsgLy8g5Lit5b+D5bqn5qiZCgkJVCBBLCBCOyAgICAgICAgICAgICAgLy8gQSA6IOi7uEHmlrnlkJHjga7ljYrplbcsIEIgOiDou7hC5pa55ZCR44Gu5Y2K6ZW3CgkJVCBhbmdsZTsgICAgICAgICAgICAgLy8g6Lu4QeOBqHjou7jjga7miJDjgZnop5IKCgkJaW5saW5lIF9FbGxpcHNlMkQoKSB7fQoJCWlubGluZSBfRWxsaXBzZTJEKGNvbnN0IF9WZWN0b3IyRDxUPiYgY2VudGVyLCBUIEEsIFQgQiwgVCBhbmdsZSkgOiBjZW50ZXIoY2VudGVyKSwgQShBKSwgQihCKSwgYW5nbGUoYW5nbGUpIHt9CgoJCS8vIOmVt+i7uOOBruWNiumVt+OCkui/lOOBmeOAggoJCWlubGluZSBUIGdldEhhbGZNYWpvckxlbmd0aCgpY29uc3QgewoJCQlyZXR1cm4gc3RkOjptYXgoQSwgQik7CgkJfQoKCQkvLyDplbfou7jjga7lhajplbfjgpLov5TjgZnjgIIKCQlpbmxpbmUgVCBnZXRNYWpvckxlbmd0aCgpY29uc3QgewoJCQlyZXR1cm4gZ2V0SGFsZk1ham9yTGVuZ3RoKCkgKiAyLjA7CgkJfQoKCQkvLyDnn63ou7jjga7ljYrplbfjgpLov5TjgZnjgIIKCQlpbmxpbmUgVCBnZXRIYWxmTWlub3JMZW5ndGgoKWNvbnN0IHsKCQkJcmV0dXJuIHN0ZDo6bWluKEEsIEIpOwoJCX0KCgkJLy8g55+t6Lu444Gu5YWo6ZW344KS6L+U44GZ44CCCgkJaW5saW5lIFQgZ2V0TWlub3JMZW5ndGgoKWNvbnN0IHsKCQkJcmV0dXJuIGdldEhhbGZNaW5vckxlbmd0aCgpICogMi4wOwoJCX0KCgkJLy8g6ZW36Lu444Gu5Lih56uv44Gu5bqn5qiZ44KS6L+U44GZ44CCCgkJaW5saW5lIHN0ZDo6cGFpcjxfVmVjdG9yMkQ8VD4sIF9WZWN0b3IyRDxUPiA+IGdldE1ham9yRW5kcygpY29uc3QgewoJCQlfVmVjdG9yMkQ8VD4gdG1wOwoJCQlpZihBIDwgQikKCQkJCXRtcCA9IEIgKiBfVmVjdG9yMkQ8VD4oLXN0ZDo6c2luKGFuZ2xlKSwgc3RkOjpjb3MoYW5nbGUpKTsKCQkJZWxzZQoJCQkJdG1wID0gQSAqIF9WZWN0b3IyRDxUPihzdGQ6OmNvcyhhbmdsZSksIHN0ZDo6c2luKGFuZ2xlKSk7CgkJCXJldHVybiBzdGQ6Om1ha2VfcGFpcihjZW50ZXIgKyB0bXAsIGNlbnRlciAtIHRtcCk7CgkJfQoKCQkvLyDnn63ou7jjga7kuKHnq6/jga7luqfmqJnjgpLov5TjgZnjgIIKCQlpbmxpbmUgc3RkOjpwYWlyPF9WZWN0b3IyRDxUPiwgX1ZlY3RvcjJEPFQ+ID4gZ2V0TWlub3JFbmRzKCljb25zdCB7CgkJCV9WZWN0b3IyRDxUPiB0bXA7CgkJCWlmKEEgPCBCKQoJCQkJdG1wID0gQSAqIF9WZWN0b3IyRDxUPihzdGQ6OmNvcyhhbmdsZSksIHN0ZDo6c2luKGFuZ2xlKSk7CgkJCWVsc2UKCQkJCXRtcCA9IEIgKiBfVmVjdG9yMkQ8VD4oLXN0ZDo6c2luKGFuZ2xlKSwgc3RkOjpjb3MoYW5nbGUpKTsKCQkJcmV0dXJuIHN0ZDo6bWFrZV9wYWlyKGNlbnRlciArIHRtcCwgY2VudGVyIC0gdG1wKTsKCQl9CgoJCS8vIOmVt+i7uOOBqHjou7jjgYzmiJDjgZnop5LjgpLov5TjgZnjgIIKCQlpbmxpbmUgVCBnZXRNYWpvckFyZ3VtZW50KCljb25zdCB7CgkJCWlmKEEgPCBCKQoJCQkJcmV0dXJuIGFuZ2xlICsgKGFuZ2xlIDwgMC4wID8gTV9QSV8yIDogLU1fUElfMik7CgkJCWVsc2UKCQkJCXJldHVybiBhbmdsZTsKCQl9CgoJCS8vIOefrei7uOOBqHjou7jjgYzmiJDjgZnop5LjgpLov5TjgZnjgIIKCQlpbmxpbmUgVCBnZXRNaW5vckFyZ3VtZW50KCljb25zdCB7CgkJCWlmKEEgPCBCKQoJCQkJcmV0dXJuIGFuZ2xlOwoJCQllbHNlCgkJCQlyZXR1cm4gYW5nbGUgKyAoYW5nbGUgPCAwLjAgPyBNX1BJXzIgOiAtTV9QSV8yKTsKCQl9CgoJCS8vIOmVt+i7uOOBruebtOe3muOCkui/lOOBmeOAggoJCWlubGluZSBfTGluZTJEPFQ+IGdldE1ham9yTGluZSgpY29uc3QgewoJCQlUIGFyZyA9IGdldE1ham9yQXJndW1lbnQoKTsKCQkJcmV0dXJuIF9MaW5lMkQ8VD4oY2VudGVyLCBfVmVjdG9yMkQ8VD4oc3RkOjpjb3MoYXJnKSwgc3RkOjpzaW4oYXJnKSkpOwoJCX0KCQkKCQkvLyDnn63ou7jjga7nm7Tnt5rjgpLov5TjgZnjgIIKCQlpbmxpbmUgX0xpbmUyRDxUPiBnZXRNaW5vckxpbmUoKWNvbnN0IHsKCQkJVCBhcmcgPSBnZXRNaW5vckFyZ3VtZW50KCk7CgkJCXJldHVybiBfTGluZTJEPFQ+KGNlbnRlciwgX1ZlY3RvcjJEPFQ+KHN0ZDo6Y29zKGFyZyksIHN0ZDo6c2luKGFyZykpKTsKCQl9CgoJCS8vIOalleWGhuOBjOWGhuOBi+OBqeOBhuOBi+OCkui/lOOBmeOAggoJCWlubGluZSBib29sIGlzQ2lyY2xlKCljb25zdCB7CgkJCXJldHVybiBhYnMoQS1CKSA8IEVQUzsKCQl9CgoJCS8vIOmdouepjeOCkui/lOOBmeOAggoJCWlubGluZSBUIGdldEFyZWEoKWNvbnN0IHsKCQkJcmV0dXJuIE1fUEkgKiBBICogQjsKCQl9CgoJCS8vIOalleWGhuW8p+S4iuOBp+acgOOCgnjluqfmqJnjgYzlsI/jgZXjgYTngrnjgpLov5TjgZnjgIIKCQlpbmxpbmUgX1ZlY3RvcjJEPFQ+IGdldExlZnQoKWNvbnN0IHsKCQkJVCBjb3MgPSBzdGQ6OmNvcyhhbmdsZSk7CgkJCVQgc2luID0gc3RkOjpzaW4oYW5nbGUpOwoJCQlUIHggPSAtX1ZlY3RvcjJEPFQ+KEEqY29zLCBCKnNpbikubm9ybSgpOwoJCQlyZXR1cm4gX1ZlY3RvcjJEPFQ+KHgrY2VudGVyLngsIChBKkEtQipCKSpzaW4qY29zL3ggKyBjZW50ZXIueSk7CgkJfQoKCQkvLyDmpZXlhoblvKfkuIrjgafmnIDjgoJ45bqn5qiZ44GM5aSn44GN44GE54K544KS6L+U44GZ44CCCgkJaW5saW5lIF9WZWN0b3IyRDxUPiBnZXRSaWdodCgpY29uc3QgewoJCQlUIGNvcyA9IHN0ZDo6Y29zKGFuZ2xlKTsKCQkJVCBzaW4gPSBzdGQ6OnNpbihhbmdsZSk7CgkJCVQgeCA9IF9WZWN0b3IyRDxUPihBKmNvcywgQipzaW4pLm5vcm0oKTsKCQkJcmV0dXJuIF9WZWN0b3IyRDxUPih4K2NlbnRlci54LCAoQSpBLUIqQikqc2luKmNvcy94ICsgY2VudGVyLnkpOwoJCX0KCgkJLy8g5qWV5YaG5byn5LiK44Gn5pyA44KCeeW6p+aomeOBjOWwj+OBleOBhOeCueOCkui/lOOBmeOAggoJCWlubGluZSBfVmVjdG9yMkQ8VD4gZ2V0VG9wKCljb25zdCB7CgkJCVQgY29zID0gc3RkOjpjb3MoYW5nbGUpOwoJCQlUIHNpbiA9IHN0ZDo6c2luKGFuZ2xlKTsKCQkJVCB5ID0gLV9WZWN0b3IyRDxUPihBKnNpbiwgQipjb3MpLm5vcm0oKTsKCQkJcmV0dXJuIF9WZWN0b3IyRDxUPigoQSpBLUIqQikqc2luKmNvcy95ICsgY2VudGVyLngsIHkrY2VudGVyLnkpOwoJCX0KCgkJLy8g5qWV5YaG5byn5LiK44Gn5pyA44KCeeW6p+aomeOBjOWkp+OBjeOBhOeCueOCkui/lOOBmeOAggoJCWlubGluZSBfVmVjdG9yMkQ8VD4gZ2V0Qm90dG9tKCljb25zdCB7CgkJCVQgY29zID0gc3RkOjpjb3MoYW5nbGUpOwoJCQlUIHNpbiA9IHN0ZDo6c2luKGFuZ2xlKTsKCQkJVCB5ID0gX1ZlY3RvcjJEPFQ+KEEqc2luLCBCKmNvcykubm9ybSgpOwoJCQlyZXR1cm4gX1ZlY3RvcjJEPFQ+KChBKkEtQipCKSpzaW4qY29zL3kgKyBjZW50ZXIueCwgeStjZW50ZXIueSk7CgkJfQoJCQoJCS8vIOaMh+WumuOBleOCjOOBn3nluqfmqJnjgavlr77lv5zjgZnjgovnm7Tnt5rkuIrjga545bqn5qiZ44KS5byV5pWw44Gr44Gd44KM44Ge44KM5Luj5YWl44GZ44KLKHgx4ommeDIp44CCCgkJLy8g5oi744KK5YCk44Gv5a++5b+c54K544Gu5YCL5pWwKDDvvZ4yKeOAggoJCWlubGluZSBpbnQgZ2V0WChUIHksIFQmIHgxLCBUJiB4Miljb25zdCB7CgkJCVQgYSwgYiwgYywgZCwgZSwgZjsKCQkJZ2V0RXF1YXRpb24oYSwgYiwgYywgZCwgZSwgZik7CgkJCWIgPSBiKnkgKyBkOwoJCQljID0gYyp5KnkgKyBlKnkgKyBmOwoKCQkJVCBEID0gYipiIC0gNC4wKmEqYzsKCQkJaWYoc3RkOjphYnMoRCkgPCBFUFMpewoJCQkJeDEgPSB4MiA9IC1iIC8gKDIuMCphKTsKCQkJCXJldHVybiAxOwoJCQl9CgkJCWVsc2UgaWYoRCA+IDAuMCl7CgkJCQlEID0gc3RkOjpzcXJ0KEQpOwoJCQkJeDEgPSAoLWItRCkvKDIuMCphKTsKCQkJCXgyID0gKC1iK0QpLygyLjAqYSk7CgkJCQlyZXR1cm4gMjsKCQkJfQoJCQllbHNlCgkJCQlyZXR1cm4gMDsKCQl9CgoJCS8vIOalleWGhuOBruaWueeoi+W8jyBheF4yK2J4eStjeV4yK2R4K2V5K2Y9MCDjga7lkITkv4LmlbDjgpLjgZ3jgozjgZ7jgozlvJXmlbDjgavku6PlhaXjgZnjgovjgIIKCQlpbmxpbmUgdm9pZCBnZXRFcXVhdGlvbihUJiBhLCBUJiBiLCBUJiBjLCBUJiBkLCBUJiBlLCBUJiBmKWNvbnN0IHsKCQkJVCBjb3MgPSBzdGQ6OmNvcyhhbmdsZSk7CgkJCVQgc2luID0gc3RkOjpzaW4oYW5nbGUpOwoJCQlUIGEyID0gMS4wIC8gKEEgKiBBKTsKCQkJVCBiMiA9IDEuMCAvIChCICogQik7CgoJCQlhID0gY29zKmNvcyphMiArIHNpbipzaW4qYjI7CgkJCWIgPSAyLjAqKGEyLWIyKSpzaW4qY29zOwoJCQljID0gc2luKnNpbiphMiArIGNvcypjb3MqYjI7CgkJCWQgPSAtMi4wKmNlbnRlci54KmEgLSBjZW50ZXIueSpiOwoJCQllID0gLTIuMCpjZW50ZXIueSpjIC0gY2VudGVyLngqYjsKCQkJVCB0bXAxID0gIGNlbnRlci54KmNvcyArIGNlbnRlci55KnNpbjsKCQkJVCB0bXAyID0gLWNlbnRlci54KnNpbiArIGNlbnRlci55KmNvczsKCQkJZiA9IHRtcDEqdG1wMSphMiArIHRtcDIqdG1wMipiMiAtIDEuMDsKCQl9CgoJCWlubGluZSBib29sIG9wZXJhdG9yPT0oY29uc3QgX0VsbGlwc2UyRCYgZWxsKWNvbnN0IHsKCQkJcmV0dXJuIGNlbnRlciA9PSBlbGwuY2VudGVyCgkJCQkmJiBzdGQ6OmFicyhnZXRNYWpvckxlbmd0aCgpIC0gZWxsLmdldE1ham9yTGVuZ3RoKCkpIDwgRVBTCgkJCQkmJiBzdGQ6OmFicyhnZXRNaW5vckxlbmd0aCgpIC0gZWxsLmdldE1pbm9yTGVuZ3RoKCkpIDwgRVBTCgkJCQkmJiAoc3RkOjphYnMoQS1CKSA8IEVQUyB8fCBzdGQ6OmFicyhnZXRNYWpvckFyZ3VtZW50KCkgLSBlbGwuZ2V0TWFqb3JBcmd1bWVudCgpKSk7CgkJfQoKCQkvLyDmpZXlhobjga7kuK3lv4Pjgajou7jjga7ljYrplbfjgajop5LluqbjgYvjgonmpZXlhobjgpLlrprnvqnjgZnjgovjgIIKCQlpbmxpbmUgc3RhdGljIF9FbGxpcHNlMkQgZnJvbUNlbnRlckFuZExlbmd0aGVzQW5kQW5nbGUoY29uc3QgX1ZlY3RvcjJEPFQ+JiBjZW50ZXIsIFQgQSwgVCBCLCBUIGFuZ2xlKQoJCXsKCQkJcmV0dXJuIF9FbGxpcHNlMkQoY2VudGVyLCBBLCBCLCBhbmdsZSk7CgkJfQoKCQkvLyAodi54LCB2LnkpLCAodi54K3csIHYueSksICh2LngsIHYueStoKSwgKHYueCt3LCB2LnkraCnjgpLpoILngrnjgajjgZnjgovplbfmlrnlvaLjgavlhoXmjqXjgZnjgovmpZXlhobjgpLlrprnvqnjgZnjgovjgIIKCQlpbmxpbmUgc3RhdGljIF9FbGxpcHNlMkQgZnJvbVJlY3RhbmdsZShjb25zdCBfVmVjdG9yMkQ8VD4mIHYsIFQgdywgVCBoKQoJCXsKCQkJdyAqPSAwLjU7CgkJCWggKj0gMC41OwoJCQlyZXR1cm4gX0VsbGlwc2UyRChfVmVjdG9yMkQ8VD4odi54ICsgdywgdi55ICsgaCksIHcsIGgsIDAuMCk7CgkJfQoKCQkvLyDkuozmrKHmm7Lnt5ogYXheMitieHkrY3leMitkeCtleStmPTAg44GM5qWV5YaG44Gu5pa556iL5byP44GL44Gp44GG44GL44KS5Yik5Yil44GZ44KL44CCCgkJaW5saW5lIHN0YXRpYyBib29sIGlzRWxsaXBzZUVxdWF0aW9uKFQgYSwgVCBiLCBUIGMsIFQgZCwgVCBlLCBUIGYpCgkJewoJCQlUIEQgPSA0LjAqYSpjIC0gYipiOwoJCQlyZXR1cm4gRCA+IDAuMCAmJiBhKigoZCooYiplLTIuMCpjKmQpK2UqKGIqZC0yLjAqYSplKSkvRCArIDIuMCpmKSA8IDAuMDsKCQl9CgoJCS8vIOalleWGhuOBruaWueeoi+W8jyBheF4yK2J4eStjeV4yK2R4K2V5K2Y9MCDjgYvjgonmpZXlhobjgpLlrprnvqnjgZnjgovjgIIKCQlpbmxpbmUgc3RhdGljIF9FbGxpcHNlMkQgZnJvbUVxdWF0aW9uKFQgYSwgVCBiLCBUIGMsIFQgZCwgVCBlLCBUIGYpCgkJewoJCQlfRWxsaXBzZTJEIGVsbDsKCQkJZWxsLmNlbnRlciA9IF9WZWN0b3IyRDxUPihiKmUtMi4wKmMqZCwgYipkLTIuMCphKmUpIC8gKDQuMCphKmMgLSBiKmIpOwoJCQlUIHN1bSA9IGEgKyBjOwoJCQlUIGRpZmYgPSBhIC0gYzsKCQkJVCBzcSA9IHN0ZDo6c3FydChkaWZmKmRpZmYgKyBiKmIpOwoJCQlUIGJldGEgPSAtZCplbGwuY2VudGVyLnggLSBlKmVsbC5jZW50ZXIueSAtIDIuMCpmOwoJCQllbGwuQSA9IHN0ZDo6c3FydChiZXRhLyhzdW0rc3EpKTsKCQkJZWxsLkIgPSBzdGQ6OnNxcnQoYmV0YS8oc3VtLXNxKSk7CgkJCWVsbC5hbmdsZSA9IGE+YyA/IHN0ZDo6YXRhbjIoYiwgZGlmZitzcSkgOiBzdGQ6OmF0YW4yKC1kaWZmK3NxLCBiKTsKCQkJcmV0dXJuIGVsbDsKCQl9Cgl9OwoKCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CgljbGFzcyBfQ2lyY2xlMkQKCXsKCXB1YmxpYzoKCQlfVmVjdG9yMkQ8VD4gY2VudGVyOyAvLyDkuK3lv4PluqfmqJkKCQlUIHJhZGl1czsgICAgICAgICAgICAvLyDljYrlvoQKCgkJaW5saW5lIF9DaXJjbGUyRCgpIHt9CgkJaW5saW5lIF9DaXJjbGUyRChjb25zdCBfVmVjdG9yMkQ8VD4mIGNlbnRlciwgVCByYWRpdXMpIDogY2VudGVyKGNlbnRlciksIHJhZGl1cyhyYWRpdXMpIHt9CgoJCS8vIOWGhuOBruaWueeoi+W8jyB4XjIrYXgreV4yK2J5K2M9MCDjga7lkITkv4LmlbBhLCBiLCBj44KS44Gd44KM44Ge44KM5byV5pWw44Gr5Luj5YWl44GZ44KL44CCCgkJaW5saW5lIHZvaWQgZ2V0Q2lyY2xlRXF1YXRpb24oVCYgYSwgVCYgYiwgVCYgYyljb25zdCB7CgkJCWEgPSAtMi4wICogY2VudGVyLng7CgkJCWIgPSAtMi4wICogY2VudGVyLnk7CgkJCWMgPSBjZW50ZXIuc3Fub3JtKCkgLSByYWRpdXMqcmFkaXVzOwoJCX0KCgkJLy8g6Z2i56mN44KS6L+U44GZ44CCCgkJaW5saW5lIFQgZ2V0QXJlYSgpY29uc3QgewoJCQlyZXR1cm4gTV9QSSAqIHJhZGl1cyAqIHJhZGl1czsKCQl9CgoJCWlubGluZSBib29sIG9wZXJhdG9yPT0oY29uc3QgX0NpcmNsZTJEJiBDKWNvbnN0IHsKCQkJcmV0dXJuIGNlbnRlciA9PSBDLmNlbnRlciAmJiBzdGQ6OmFicyhyYWRpdXMgLSBDLnJhZGl1cykgPCBFUFM7CgkJfQoKCQkvLyDmpZXlhobjgbjjga7lpInmj5sKCQlpbmxpbmUgb3BlcmF0b3IgX0VsbGlwc2UyRDxUPigpIGNvbnN0ewoJCQlyZXR1cm4gX0VsbGlwc2UyRDxUPjo6ZnJvbUNlbnRlckFuZExlbmd0aGVzQW5kQW5nbGUoY2VudGVyLCByYWRpdXMsIHJhZGl1cywgMC4wKTsKCQl9CgoJCS8vIOS4reW/g+W6p+aomeOBqOWNiuW+hOOBi+OCieWGhuOCkuWumue+qeOBmeOCi+OAggoJCWlubGluZSBzdGF0aWMgX0NpcmNsZTJEIGZyb21DZW50ZXJBbmRSYWRpdXMoY29uc3QgX1ZlY3RvcjJEPFQ+JiBjLCBUIHIpCgkJewoJCQlyZXR1cm4gX0NpcmNsZTJEKGMsIHIpOwoJCX0KCgkJLy8g5Lit5b+D5bqn5qiZ44Go5YaG5ZGo5LiK44Gu5LiA54K544GL44KJ5YaG44KS5a6a576p44GZ44KL44CCCgkJaW5saW5lIHN0YXRpYyBfQ2lyY2xlMkQgZnJvbUNlbnRlckFuZFBvaW50KGNvbnN0IF9WZWN0b3IyRDxUPiYgYywgY29uc3QgX1ZlY3RvcjJEPFQ+JiBwKQoJCXsKCQkJcmV0dXJuIF9DaXJjbGUyRChjLCAoYy1wKS5ub3JtKCkpOwoJCX0KCgkJLy8g5oyH5a6a44GV44KM44Gf5LqM54K544KS55u05b6E44Gu5Lih56uv44Go44GZ44KL5YaG44KS5a6a576p44GZ44KL44CCCgkJaW5saW5lIHN0YXRpYyBfQ2lyY2xlMkQgZnJvbURpYUVuZHMoY29uc3QgX1ZlY3RvcjJEPFQ+JiBhLCBjb25zdCBfVmVjdG9yMkQ8VD4mIGIpCgkJewoJCQlyZXR1cm4gX0NpcmNsZTJEKChhK2IpKjAuNSwgKGEtYikubm9ybSgpKjAuNSk7CgkJfQoKCQkvLyDlhoblkajkuIrjga7kuInngrnjgYvjgonlhobjgpLlrprnvqnjgZnjgovjgIIKCQlpbmxpbmUgc3RhdGljIF9DaXJjbGUyRCBmcm9tVGhyZWVQb2ludHMoY29uc3QgX1ZlY3RvcjJEPFQ+JiBhLCBjb25zdCBfVmVjdG9yMkQ8VD4mIGIsIGNvbnN0IF9WZWN0b3IyRDxUPiYgYykKCQl7CgkJCV9WZWN0b3IyRDxUPiBBKDIuMCooYi54LWEueCksIDIuMCooYy54LWEueCkpOwoJCQlfVmVjdG9yMkQ8VD4gQigyLjAqKGIueS1hLnkpLCAyLjAqKGMueS1hLnkpKTsKCQkJVCBhc3EgPSBhLnNxbm9ybSgpOwoJCQlfVmVjdG9yMkQ8VD4gQyhhc3EtYi5zcW5vcm0oKSwgYXNxLWMuc3Fub3JtKCkpOwoJCQlfVmVjdG9yMkQ8VD4gY2VudGVyID0gVmVjdG9yMkQoY3Jvc3MoQiwgQyksIGNyb3NzKEMsIEEpKSAvIGNyb3NzKEEsIEIpOwoJCQlyZXR1cm4gX0NpcmNsZTJEKGNlbnRlciwgKGNlbnRlci1hKS5ub3JtKCkpOwoJCX0KCgkJLy8gKHYueCwgdi55KSwgKHYueCthLCB2LnkpLCAodi54LCB2LnkrYSksICh2LngrYSwgdi55K2Ep44KS6aCC54K544Go44GZ44KL5q2j5pa55b2i44Gr5YaF5o6l44GZ44KL5YaG44KS5a6a576p44GZ44KL44CCCgkJaW5saW5lIHN0YXRpYyBfQ2lyY2xlMkQgZnJvbVNxdWFyZShjb25zdCBfVmVjdG9yMkQ8VD4mIHYsIFQgYSkKCQl7CgkJCWEgKj0gMC41OwoJCQlyZXR1cm4gX0NpcmNsZTJEKF9WZWN0b3IyRDxUPih2LngrYSwgdi55K2EpLCBzdGQ6OmFicyhhKSk7CgkJfQoKCQkvLyDlhoYgeF4yK2F4K3leMitieStjPTAg44KS5a6a576p44GZ44KL44CCCgkJaW5saW5lIHN0YXRpYyBfQ2lyY2xlMkQgZnJvbUNpcmNsZUVxdWF0aW9uKFQgYSwgVCBiLCBUIGMpCgkJewoJCQlfVmVjdG9yMkQ8VD4gY2VudGVyKC1hKjAuNSwgLWIqMC41KTsKCQkJcmV0dXJuIF9DaXJjbGUyRChjZW50ZXIsIHNxcnQoY2VudGVyLnNxbm9ybSgpIC0gYykpOwoJCX0KCX07CgoJLy8g54K5UOOBqOebtOe3mkzjga7ot53pm6LjgpLov5TjgZnjgIIKCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CglpbmxpbmUgVCBnZXREaXN0YW5jZShjb25zdCBfVmVjdG9yMkQ8VD4mIFAsIGNvbnN0IF9MaW5lMkQ8VD4mIEwpCgl7CgkJVCBhLCBiLCBjOwoJCUwuZ2V0TGluZWFyRXF1YXRpb24oYSwgYiwgYyk7CgkJcmV0dXJuIHN0ZDo6YWJzKGEqUC54ICsgYipQLnkgKyBjKS9zdGQ6OnNxcnQoYSphICsgYipiKTsKCX0KCgkvLyDnm7Tnt5pM44Go55u057eaTeOBruS6pOeCueOCkmludGVy44Gr5Luj5YWl44GZ44KL44CCCgkvLyDmiLvjgorlgKTjga/kuqTngrnjga7lgIvmlbAoMO+9njEp44CCYeOBqGLjgYzph43jgarjgaPjgabjgYTjgovmmYLjga8tMeOAggoJdGVtcGxhdGU8dHlwZW5hbWUgVD4KCWludCBnZXRJbnRlcnNlY3Rpb24oY29uc3QgX0xpbmUyRDxUPiYgTCwgY29uc3QgX0xpbmUyRDxUPiYgTSwgX1ZlY3RvcjJEPFQ+JiBpbnRlcikKCXsKCQlUIGRlbm9taW5hdG9yID0gY3Jvc3MoTC5kLCBNLmQpOwoJCVQgbnVtZXJhdG9yID0gY3Jvc3MoTS5wLUwucCwgTS5kKTsKCQlpZihzdGQ6OmFicyhkZW5vbWluYXRvcikgPCBFUFMpewoJCQlyZXR1cm4gc3RkOjphYnMobnVtZXJhdG9yKSA8IEVQUyA/IC0xIDogMDsKCQl9CgkJZWxzZXsKCQkJaW50ZXIgPSBMLnAgKyBudW1lcmF0b3IvZGVub21pbmF0b3IgKiBMLmQ7CgkJCXJldHVybiAxOwoJCX0KCX0KCgkvLyDnm7Tnt5pM44Go5YaGQ+OBruS6pOeCueOCkmludGVyMSwgaW50ZXIy44Gr5Luj5YWl44GZ44KL44CCCgkvLyDmiLvjgorlgKTjga/kuqTngrnjga7lgIvmlbAoMO+9njIp44CCCgl0ZW1wbGF0ZTx0eXBlbmFtZSBUPgoJaW50IGdldEludGVyc2VjdGlvbihjb25zdCBfTGluZTJEPFQ+JiBMLCBjb25zdCBfQ2lyY2xlMkQ8VD4mIEMsIF9WZWN0b3IyRDxUPiYgaW50ZXIxLCBfVmVjdG9yMkQ8VD4mIGludGVyMikKCXsKCQlfVmVjdG9yMkQ8VD4gZGlmZiA9IEwucCAtIEMuY2VudGVyOwoJCVQgYSA9IEwuZC5zcW5vcm0oKTsKCQlUIGIgPSBkb3QoTC5kLCBkaWZmKTsKCQlUIGMgPSBkaWZmLnNxbm9ybSgpIC0gQy5yYWRpdXMgKiBDLnJhZGl1czsKCQlUIEQgPSBiKmIgLSBhKmM7CgkJaWYoc3RkOjphYnMoRCkgPCBFUFMpewoJCQlpbnRlcjEgPSBpbnRlcjIgPSBMLnAgLSBiL2EgKiBMLmQ7CgkJCXJldHVybiAxOwoJCX0KCQllbHNlIGlmKEQgPiAwLjApewoJCQlEID0gc3RkOjpzcXJ0KEQpOwoJCQlpbnRlcjEgPSBMLnAgKyAoLWIrRCkvYSAqIEwuZDsKCQkJaW50ZXIyID0gTC5wIC0gKGIrRCkvYSAqIEwuZDsKCQkJcmV0dXJuIDI7CgkJfQoJCWVsc2V7CgkJCXJldHVybiAwOwoJCX0KCX0KCQoJdHlwZWRlZiBfVmVjdG9yMkQ8TUVNQkVSX1RZUEU+IFZlY3RvcjJEOwoJdHlwZWRlZiBfTGluZTJEPE1FTUJFUl9UWVBFPiBMaW5lMkQ7Cgl0eXBlZGVmIF9DaXJjbGUyRDxNRU1CRVJfVFlQRT4gQ2lyY2xlMkQ7Cgl0eXBlZGVmIF9FbGxpcHNlMkQ8TUVNQkVSX1RZUEU+IEVsbGlwc2UyRDsKCQojaWZkZWYgX19PUEVOQ1ZfQ09SRV9DX0hfXwoJbmFtZXNwYWNlIG9wZW5jdgoJewoJCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CgkJaW5saW5lIEN2UG9pbnQgdmVjVG9DUChUIHgsIFQgeSkgewoJCQlyZXR1cm4gY3ZQb2ludChzdGF0aWNfY2FzdDxpbnQ+KHggKyAwLjUpLCBzdGF0aWNfY2FzdDxpbnQ+KHkgKyAwLjUpKTsKCQl9CgoJCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CgkJaW5saW5lIEN2UG9pbnQgdmVjVG9DUChjb25zdCBfVmVjdG9yMkQ8VD4mIHYpIHsKCQkJcmV0dXJuIHZlY1RvQ1Aodi54LCB2LnkpOwoJCX0KCgkJLy8g54K544KS5o+P44GP44CCCgkJdGVtcGxhdGU8dHlwZW5hbWUgVD4KCQlpbmxpbmUgdm9pZCBkcmF3UG9pbnQoQ3ZBcnIqIGltZywgY29uc3QgX1ZlY3RvcjJEPFQ+JiBwb2ludCwgQ3ZTY2FsYXIgY29sb3IsIGludCByYWRpdXM9MywgaW50IHRoaWNrbmVzcz0tMSwgaW50IGxpbmVUeXBlPUNWX0FBLCBpbnQgc2hpZnQ9MCkKCQl7CgkJCWN2Q2lyY2xlKGltZywgdmVjVG9DUChwb2ludCksIHJhZGl1cywgY29sb3IsIHRoaWNrbmVzcywgbGluZVR5cGUsIHNoaWZ0KTsKCQl9CgoJCS8vIOebtOe3muOCkuaPj+OBj+OAggoJCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CgkJdm9pZCBkcmF3TGluZShJcGxJbWFnZSogaW1nLCBjb25zdCBfTGluZTJEPFQ+JiBsaW5lLCBDdlNjYWxhciBjb2xvciwgaW50IHRoaWNrbmVzcz0xLCBpbnQgbGluZV90eXBlPTgsIGludCBzaGlmdD0wKQoJCXsKCQkJZG91YmxlIGggPSBpbWctPmhlaWdodCArIDEuMCwgdyA9IGltZy0+d2lkdGggKyAxLjA7CgkJCQoJCQlDdlBvaW50IHAxLCBwMjsKCQkJaWYoc3RkOjphYnMobGluZS5kLngpIDwgc3RkOjphYnMobGluZS5kLnkpKXsKCQkJCXAxID0gdmVjVG9DUChsaW5lLmdldFgoLTEuMCksIC0xLjApOwoJCQkJcDIgPSB2ZWNUb0NQKGxpbmUuZ2V0WChoKSwgaCk7CgkJCX0KCQkJZWxzZXsKCQkJCXAxID0gdmVjVG9DUCgtMS4wLCBsaW5lLmdldFkoLTEuMCkpOwoJCQkJcDIgPSB2ZWNUb0NQKHcsIGxpbmUuZ2V0WSh3KSk7CgkJCX0KCQkJY3ZMaW5lKGltZywgcDEsIHAyLCBjb2xvciwgdGhpY2tuZXNzLCBsaW5lX3R5cGUsIHNoaWZ0KTsKCQl9CgoJCS8vIOWGhuOCkuaPj+OBj+OAggoJCXRlbXBsYXRlPHR5cGVuYW1lIFQ+CgkJaW5saW5lIHZvaWQgZHJhd0NpcmNsZShDdkFyciogaW1nLCBjb25zdCBfQ2lyY2xlMkQ8VD4mIGNpcmNsZSwgQ3ZTY2FsYXIgY29sb3IsIGludCB0aGlja25lc3M9MSwgaW50IGxpbmVUeXBlPTgsIGludCBzaGlmdD0wKQoJCXsKCQkJY3ZDaXJjbGUoaW1nLCB2ZWNUb0NQKGNpcmNsZS5jZW50ZXIpLCBzdGF0aWNfY2FzdDxpbnQ+KGNpcmNsZS5yYWRpdXMgKyAwLjUpLCBjb2xvciwgdGhpY2tuZXNzLCBsaW5lVHlwZSwgc2hpZnQpOwoJCX0KCgkJLy8g5qWV5YaG44KS5o+P44GP44CCCgkJdGVtcGxhdGU8dHlwZW5hbWUgVD4KCQlpbmxpbmUgdm9pZCBkcmF3RWxsaXBzZShDdkFyciogaW1nLCBjb25zdCBfRWxsaXBzZTJEPFQ+JiBlbGxpcHNlLCBDdlNjYWxhciBjb2xvciwgaW50IHRoaWNrbmVzcz0xLCBpbnQgbGluZVR5cGU9OCwgaW50IHNoaWZ0PTApCgkJewoJCQljdkVsbGlwc2UoCgkJCQlpbWcsCgkJCQl2ZWNUb0NQKGVsbGlwc2UuY2VudGVyKSwKCQkJCWN2U2l6ZShzdGF0aWNfY2FzdDxpbnQ+KGVsbGlwc2UuQSArIDAuNSksIHN0YXRpY19jYXN0PGludD4oZWxsaXBzZS5CICsgMC41KSksCgkJCQlyYWRUb0RlZyhlbGxpcHNlLmFuZ2xlKSwgMC4wLCAzNjAuMCwKCQkJCWNvbG9yLCB0aGlja25lc3MsIGxpbmVUeXBlLCBzaGlmdAoJCQkJKTsKCQl9Cgl9CiNlbmRpZgp9CgojZW5kaWYK