#include <bits/stdc++.h>
using namespace std;
const long double PI = acos((long double)-1.0);
const long double EPS = 1e-8;
const long double INF = 1e18 + 10;
struct Vector {
long double x, y;
Vector(long double _x = 0, long double _y = 0) {
x = _x;
y = _y;
}
Vector operator + (Vector v) {
return {x + v.x, y + v.y};
}
Vector operator - (Vector v) {
return {x - v.x, y - v.y};
}
Vector operator * (long double k) {
return {x * k, y * k};
}
Vector operator / (long double k) {
return {x / k, y / k};
}
void setLengthAngle(long double length, long double theta) {
x = length * cos(theta);
y = length * sin(theta);
}
long double getLength() {
return sqrt(x * x + y * y);
}
long double getLengthSquare() {
return x * x + y * y;
}
long double getAngle() {
return atan2(y, x);
}
long double cross(Vector v) {
return x * v.y - y * v.x;
}
long double dot(Vector v) {
return x * v.x + y * v.y;
}
Vector rotate(long double theta) {
return {x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)};
}
long double distance(Vector v) {
return sqrt((v.x - x) * (v.x - x) + (v.y - y) * (v.y - y));
}
long double distanceSquare(Vector v) {
return (v.x - x) * (v.x - x) + (v.y - y) * (v.y - y);
}
};
typedef Vector Point;
typedef pair<Point, Point> Segment;
struct Ball {
Point center;
long double radius;
Vector velocity;
Ball(Point _center, Vector _velocity, long double _radius = 0) {
center = _center;
radius = _radius;
velocity = _velocity;
}
Ball(long double _radius = 0) {
radius = _radius;
}
long double getArea() {
return PI * radius * radius;
}
};
typedef pair<long double, long double> TimeSegment;
typedef pair<TimeSegment, Ball> TimeSegmentBall;
Vector reflect(Vector v, Segment wall) {
Vector n = (wall.second - wall.first).rotate(PI / 2.0);
n = n / n.getLength();
return v - n * (2 * n.dot(v));
}
long double gd(long double x1,long double y1,long double x2,long double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
long double solve_cos(long double a,long double b,long double c)
{
return acos((a*a+b*b-c*c)/(2*a*b));
}
long double cut(long double ang,long double r)
{
long double s1,s2;
s1=ang*r*r/2;
s2=sin(ang)*r*r/2;
return s1-s2;
}
long double solve(long double x1 , long double y1 , long double r1 , long double x2 , long double y2 , long double r2)
{
if (r1<r2)
{
swap(x1,x2);
swap(y1,y2);
swap(r1,r2);
}
long double cd=gd(x1,y1,x2,y2);
if (cd+r2<=r1+EPS)
return r2*r2*PI;
if (cd>=r1+r2-EPS)
return 0;
long double ang1=solve_cos(cd,r1,r2);
long double ang2=solve_cos(cd,r2,r1);
return cut(ang1*2,r1)+cut(ang2*2,r2);
}
long double commonArea(Ball c1, Ball c2) {
return solve(c1.center.x, c1.center.y, c1.radius, c2.center.x, c2.center.y, c2.radius);
}
int sign(long double x) {
if (x < EPS && x > -EPS)
return 0;
if (x > 0)
return 1;
if (x < 0)
return -1;
}
Ball moveBall(Ball ball, long double deltaTime) {
return Ball(ball.center + ball.velocity * deltaTime, ball.velocity, ball.radius);
}
Ball moveBall(Ball ball, TimeSegment timeSegment, long double time) {
if (time >= timeSegment.second)
return Ball(ball.center + (ball.velocity * (timeSegment.second - timeSegment.first)), ball.velocity, ball.radius);
if (time <= timeSegment.first)
return ball;
return Ball(ball.center + (ball.velocity * (time - timeSegment.first)), ball.velocity, ball.radius);
}
long double maximumCommonArea(Ball ball1, Ball ball2, TimeSegment timeSegment1, TimeSegment timeSegment2) {
if (timeSegment1.first > timeSegment1.second) {
swap(timeSegment1.first, timeSegment1.second);
}
if (timeSegment2.first > timeSegment2.second) {
swap(timeSegment2.first, timeSegment2.second);
}
long double lo = max(timeSegment1.first, timeSegment2.first);
long double hi = min(timeSegment1.second, timeSegment2.second);
if (lo > hi)
return 0;
long double ret = 0;
for (int i = 0; i < 2000; i++) {
long double mid1 = (2 * lo + hi) / 3;
long double mid2 = (lo + 2 * hi) / 3;
Ball ball1mid1 = moveBall(ball1, timeSegment1, mid1);
Ball ball2mid1 = moveBall(ball2, timeSegment2, mid1);
Ball ball1mid2 = moveBall(ball1, timeSegment1, mid2);
Ball ball2mid2 = moveBall(ball2, timeSegment2, mid2);
if ((ball1mid1.center - ball2mid1.center).getLength() >= (ball1mid2.center - ball2mid2.center).getLength())
lo = mid1;
else
hi = mid2;
}
Ball newBall1 = moveBall(ball1, timeSegment1, lo);
Ball newBall2 = moveBall(ball2, timeSegment2, lo);
return commonArea(newBall1, newBall2);
}
long double segmentPointDistance(Segment segment, Point point) {
return (segment.first - point).cross(segment.second - point) / (segment.second - segment.first).getLength();
}
vector<TimeSegmentBall> getTimeSegmentBalls(Ball ball, Segment wall) {
int dir1 = sign((wall.first - ball.center).cross(wall.second - ball.center));
int dir2 = sign((wall.first - moveBall(ball, INF).center).cross(wall.second - moveBall(ball, INF).center));
if (dir1 == dir2) {
vector<TimeSegmentBall> ret;
ret.push_back({{0.0, INF}, ball});
return ret;
}
long double lo = 0, hi = INF;
for (int i = 0; i < 2000; i++) {
long double mid = (lo + hi) / 2.0;
Ball ballMid = moveBall(ball, mid);
long double dis = segmentPointDistance(wall, ballMid.center);
if (sign(dis) != dir1 || (sign(dis) == dir1 && fabs(dis) < ball.radius))
hi = mid;
else
lo = mid;
}
vector<TimeSegmentBall> ret;
ret.push_back({{0.0, lo}, ball});
ball = moveBall(ball, lo);
ball.velocity = reflect(ball.velocity, wall);
ret.push_back({{hi, INF}, ball});
return ret;
}
int tc;
vector<TimeSegmentBall> timeSegmentBalls[10];
int main() {
cin >> tc;
cout.precision(12);
while (tc--) {
vector<Ball> balls;
for (int i = 0; i < 2; i++) {
long double x, y;
long double vx, vy;
long double r;
cin >> x >> y;
cin >> vx >> vy;
cin >> r;
balls.push_back(Ball(Point(x, y), Vector(vx, vy), r));
}
long double wallX1, wallY1;
long double wallX2, wallY2;
cin >> wallX1 >> wallY1;
cin >> wallX2 >> wallY2;
Segment wall(Point(wallX1, wallY1), Point(wallX2, wallY2));
long double ans = 0;
for (int i = 0; i < 2; i++) {
timeSegmentBalls[i] = getTimeSegmentBalls(balls[i], wall);
}
for (auto timeSegmentBall0: timeSegmentBalls[0])
for (auto timeSegmentBall1: timeSegmentBalls[1]) {
ans = max(ans, maximumCommonArea(timeSegmentBall0.second, timeSegmentBall1.second, timeSegmentBall0.first, timeSegmentBall1.first));
}
cout << fixed << ans << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgbG9uZyBkb3VibGUgUEkgPSBhY29zKChsb25nIGRvdWJsZSktMS4wKTsKY29uc3QgbG9uZyBkb3VibGUgRVBTID0gMWUtODsKY29uc3QgbG9uZyBkb3VibGUgSU5GID0gMWUxOCArIDEwOwoKc3RydWN0IFZlY3RvciB7CiAgICBsb25nIGRvdWJsZSB4LCB5OwogICAgVmVjdG9yKGxvbmcgZG91YmxlIF94ID0gMCwgbG9uZyBkb3VibGUgX3kgPSAwKSB7CiAgICAgICAgeCA9IF94OwogICAgICAgIHkgPSBfeTsKICAgIH0KICAgIFZlY3RvciBvcGVyYXRvciArIChWZWN0b3IgdikgewogICAgICAgIHJldHVybiB7eCArIHYueCwgeSArIHYueX07CiAgICB9CiAgICBWZWN0b3Igb3BlcmF0b3IgLSAoVmVjdG9yIHYpIHsKICAgICAgICByZXR1cm4ge3ggLSB2LngsIHkgLSB2Lnl9OwogICAgfQogICAgVmVjdG9yIG9wZXJhdG9yICogKGxvbmcgZG91YmxlIGspIHsKICAgICAgICByZXR1cm4ge3ggKiBrLCB5ICoga307CiAgICB9CiAgICBWZWN0b3Igb3BlcmF0b3IgLyAobG9uZyBkb3VibGUgaykgewogICAgICAgIHJldHVybiB7eCAvIGssIHkgLyBrfTsKICAgIH0KICAgIHZvaWQgc2V0TGVuZ3RoQW5nbGUobG9uZyBkb3VibGUgbGVuZ3RoLCBsb25nIGRvdWJsZSB0aGV0YSkgewogICAgICAgIHggPSBsZW5ndGggKiBjb3ModGhldGEpOwogICAgICAgIHkgPSBsZW5ndGggKiBzaW4odGhldGEpOwogICAgfQogICAgbG9uZyBkb3VibGUgZ2V0TGVuZ3RoKCkgewogICAgICAgIHJldHVybiBzcXJ0KHggKiB4ICsgeSAqIHkpOwogICAgfQogICAgbG9uZyBkb3VibGUgZ2V0TGVuZ3RoU3F1YXJlKCkgewogICAgICAgIHJldHVybiB4ICogeCArIHkgKiB5OwogICAgfQogICAgbG9uZyBkb3VibGUgZ2V0QW5nbGUoKSB7CiAgICAgICAgcmV0dXJuIGF0YW4yKHksIHgpOwogICAgfQogICAgbG9uZyBkb3VibGUgY3Jvc3MoVmVjdG9yIHYpIHsKICAgICAgICByZXR1cm4geCAqIHYueSAtIHkgKiB2Lng7CiAgICB9CiAgICBsb25nIGRvdWJsZSBkb3QoVmVjdG9yIHYpIHsKICAgICAgICByZXR1cm4geCAqIHYueCArIHkgKiB2Lnk7CiAgICB9CiAgICBWZWN0b3Igcm90YXRlKGxvbmcgZG91YmxlIHRoZXRhKSB7CiAgICAgICAgcmV0dXJuIHt4ICogY29zKHRoZXRhKSAtIHkgKiBzaW4odGhldGEpLCB4ICogc2luKHRoZXRhKSArIHkgKiBjb3ModGhldGEpfTsKICAgIH0KICAgIGxvbmcgZG91YmxlIGRpc3RhbmNlKFZlY3RvciB2KSB7CiAgICAgICAgcmV0dXJuIHNxcnQoKHYueCAtIHgpICogKHYueCAtIHgpICsgKHYueSAtIHkpICogKHYueSAtIHkpKTsKICAgIH0KICAgIGxvbmcgZG91YmxlIGRpc3RhbmNlU3F1YXJlKFZlY3RvciB2KSB7CiAgICAgICAgcmV0dXJuICh2LnggLSB4KSAqICh2LnggLSB4KSArICh2LnkgLSB5KSAqICh2LnkgLSB5KTsKICAgIH0KfTsKCnR5cGVkZWYgVmVjdG9yIFBvaW50Owp0eXBlZGVmIHBhaXI8UG9pbnQsIFBvaW50PiBTZWdtZW50OwoKc3RydWN0IEJhbGwgewogICAgUG9pbnQgY2VudGVyOwogICAgbG9uZyBkb3VibGUgcmFkaXVzOwogICAgVmVjdG9yIHZlbG9jaXR5OwogICAgQmFsbChQb2ludCBfY2VudGVyLCBWZWN0b3IgX3ZlbG9jaXR5LCBsb25nIGRvdWJsZSBfcmFkaXVzID0gMCkgewogICAgICAgIGNlbnRlciA9IF9jZW50ZXI7CiAgICAgICAgcmFkaXVzID0gX3JhZGl1czsKICAgICAgICB2ZWxvY2l0eSA9IF92ZWxvY2l0eTsKICAgIH0KICAgIEJhbGwobG9uZyBkb3VibGUgX3JhZGl1cyA9IDApIHsKICAgICAgICByYWRpdXMgPSBfcmFkaXVzOwogICAgfQogICAgbG9uZyBkb3VibGUgZ2V0QXJlYSgpIHsKICAgICAgICByZXR1cm4gUEkgKiByYWRpdXMgKiByYWRpdXM7CiAgICB9Cn07Cgp0eXBlZGVmIHBhaXI8bG9uZyBkb3VibGUsIGxvbmcgZG91YmxlPiBUaW1lU2VnbWVudDsKdHlwZWRlZiBwYWlyPFRpbWVTZWdtZW50LCBCYWxsPiBUaW1lU2VnbWVudEJhbGw7CgpWZWN0b3IgcmVmbGVjdChWZWN0b3IgdiwgU2VnbWVudCB3YWxsKSB7CiAgICBWZWN0b3IgbiA9ICh3YWxsLnNlY29uZCAtIHdhbGwuZmlyc3QpLnJvdGF0ZShQSSAvIDIuMCk7CiAgICBuID0gbiAvIG4uZ2V0TGVuZ3RoKCk7CiAgICByZXR1cm4gdiAtIG4gKiAoMiAqIG4uZG90KHYpKTsKfQoKbG9uZyBkb3VibGUgZ2QobG9uZyBkb3VibGUgeDEsbG9uZyBkb3VibGUgeTEsbG9uZyBkb3VibGUgeDIsbG9uZyBkb3VibGUgeTIpCnsKICAgIHJldHVybiBzcXJ0KCh4MS14MikqKHgxLXgyKSsoeTEteTIpKih5MS15MikpOwp9Cgpsb25nIGRvdWJsZSBzb2x2ZV9jb3MobG9uZyBkb3VibGUgYSxsb25nIGRvdWJsZSBiLGxvbmcgZG91YmxlIGMpCnsKICAgIHJldHVybiBhY29zKChhKmErYipiLWMqYykvKDIqYSpiKSk7Cn0KCmxvbmcgZG91YmxlIGN1dChsb25nIGRvdWJsZSBhbmcsbG9uZyBkb3VibGUgcikKewogICAgbG9uZyBkb3VibGUgczEsczI7CiAgICBzMT1hbmcqcipyLzI7CiAgICBzMj1zaW4oYW5nKSpyKnIvMjsKICAgIHJldHVybiBzMS1zMjsKfQoKbG9uZyBkb3VibGUgc29sdmUobG9uZyBkb3VibGUgeDEgLCBsb25nIGRvdWJsZSB5MSAsIGxvbmcgZG91YmxlIHIxICwgbG9uZyBkb3VibGUgeDIgLCBsb25nIGRvdWJsZSB5MiAsIGxvbmcgZG91YmxlIHIyKQp7CiAgICBpZiAocjE8cjIpCiAgICB7CiAgICAgICAgc3dhcCh4MSx4Mik7CiAgICAgICAgc3dhcCh5MSx5Mik7CiAgICAgICAgc3dhcChyMSxyMik7CiAgICB9CiAgICBsb25nIGRvdWJsZSBjZD1nZCh4MSx5MSx4Mix5Mik7CiAgICBpZiAoY2QrcjI8PXIxK0VQUykKICAgICAgICByZXR1cm4gcjIqcjIqUEk7CiAgICBpZiAoY2Q+PXIxK3IyLUVQUykKICAgICAgICByZXR1cm4gMDsKICAgIGxvbmcgZG91YmxlIGFuZzE9c29sdmVfY29zKGNkLHIxLHIyKTsKICAgIGxvbmcgZG91YmxlIGFuZzI9c29sdmVfY29zKGNkLHIyLHIxKTsKICAgIHJldHVybiBjdXQoYW5nMSoyLHIxKStjdXQoYW5nMioyLHIyKTsKfQoKbG9uZyBkb3VibGUgY29tbW9uQXJlYShCYWxsIGMxLCBCYWxsIGMyKSB7CiAgIHJldHVybiBzb2x2ZShjMS5jZW50ZXIueCwgYzEuY2VudGVyLnksIGMxLnJhZGl1cywgYzIuY2VudGVyLngsIGMyLmNlbnRlci55LCBjMi5yYWRpdXMpOwp9CgppbnQgc2lnbihsb25nIGRvdWJsZSB4KSB7CiAgICBpZiAoeCA8IEVQUyAmJiB4ID4gLUVQUykKICAgICAgICByZXR1cm4gMDsKICAgIGlmICh4ID4gMCkKICAgICAgICByZXR1cm4gMTsKICAgIGlmICh4IDwgMCkKICAgICAgICByZXR1cm4gLTE7Cn0KCkJhbGwgbW92ZUJhbGwoQmFsbCBiYWxsLCBsb25nIGRvdWJsZSBkZWx0YVRpbWUpIHsKICAgIHJldHVybiBCYWxsKGJhbGwuY2VudGVyICsgYmFsbC52ZWxvY2l0eSAqIGRlbHRhVGltZSwgYmFsbC52ZWxvY2l0eSwgYmFsbC5yYWRpdXMpOwp9CgpCYWxsIG1vdmVCYWxsKEJhbGwgYmFsbCwgVGltZVNlZ21lbnQgdGltZVNlZ21lbnQsIGxvbmcgZG91YmxlIHRpbWUpIHsKICAgIGlmICh0aW1lID49IHRpbWVTZWdtZW50LnNlY29uZCkKICAgICAgICByZXR1cm4gQmFsbChiYWxsLmNlbnRlciArIChiYWxsLnZlbG9jaXR5ICogKHRpbWVTZWdtZW50LnNlY29uZCAtIHRpbWVTZWdtZW50LmZpcnN0KSksIGJhbGwudmVsb2NpdHksIGJhbGwucmFkaXVzKTsKICAgIGlmICh0aW1lIDw9IHRpbWVTZWdtZW50LmZpcnN0KQogICAgICAgIHJldHVybiBiYWxsOwogICAgcmV0dXJuIEJhbGwoYmFsbC5jZW50ZXIgKyAoYmFsbC52ZWxvY2l0eSAqICh0aW1lIC0gdGltZVNlZ21lbnQuZmlyc3QpKSwgYmFsbC52ZWxvY2l0eSwgYmFsbC5yYWRpdXMpOwp9Cgpsb25nIGRvdWJsZSBtYXhpbXVtQ29tbW9uQXJlYShCYWxsIGJhbGwxLCBCYWxsIGJhbGwyLCBUaW1lU2VnbWVudCB0aW1lU2VnbWVudDEsIFRpbWVTZWdtZW50IHRpbWVTZWdtZW50MikgewogICAgaWYgKHRpbWVTZWdtZW50MS5maXJzdCA+IHRpbWVTZWdtZW50MS5zZWNvbmQpIHsKICAgICAgICBzd2FwKHRpbWVTZWdtZW50MS5maXJzdCwgdGltZVNlZ21lbnQxLnNlY29uZCk7CiAgICB9CiAgICBpZiAodGltZVNlZ21lbnQyLmZpcnN0ID4gdGltZVNlZ21lbnQyLnNlY29uZCkgewogICAgICAgIHN3YXAodGltZVNlZ21lbnQyLmZpcnN0LCB0aW1lU2VnbWVudDIuc2Vjb25kKTsKICAgIH0KICAgIGxvbmcgZG91YmxlIGxvID0gbWF4KHRpbWVTZWdtZW50MS5maXJzdCwgdGltZVNlZ21lbnQyLmZpcnN0KTsKICAgIGxvbmcgZG91YmxlIGhpID0gbWluKHRpbWVTZWdtZW50MS5zZWNvbmQsIHRpbWVTZWdtZW50Mi5zZWNvbmQpOwogICAgaWYgKGxvID4gaGkpCiAgICAgICAgcmV0dXJuIDA7CiAgICBsb25nIGRvdWJsZSByZXQgPSAwOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAyMDAwOyBpKyspIHsKICAgICAgICBsb25nIGRvdWJsZSBtaWQxID0gKDIgKiBsbyArIGhpKSAvIDM7CiAgICAgICAgbG9uZyBkb3VibGUgbWlkMiA9IChsbyArIDIgKiBoaSkgLyAzOwogICAgICAgIEJhbGwgYmFsbDFtaWQxID0gbW92ZUJhbGwoYmFsbDEsIHRpbWVTZWdtZW50MSwgbWlkMSk7CiAgICAgICAgQmFsbCBiYWxsMm1pZDEgPSBtb3ZlQmFsbChiYWxsMiwgdGltZVNlZ21lbnQyLCBtaWQxKTsKICAgICAgICBCYWxsIGJhbGwxbWlkMiA9IG1vdmVCYWxsKGJhbGwxLCB0aW1lU2VnbWVudDEsIG1pZDIpOwogICAgICAgIEJhbGwgYmFsbDJtaWQyID0gbW92ZUJhbGwoYmFsbDIsIHRpbWVTZWdtZW50MiwgbWlkMik7CiAgICAgICAgaWYgKChiYWxsMW1pZDEuY2VudGVyIC0gYmFsbDJtaWQxLmNlbnRlcikuZ2V0TGVuZ3RoKCkgPj0gKGJhbGwxbWlkMi5jZW50ZXIgLSBiYWxsMm1pZDIuY2VudGVyKS5nZXRMZW5ndGgoKSkKICAgICAgICAgICAgbG8gPSBtaWQxOwogICAgICAgIGVsc2UKICAgICAgICAgICAgaGkgPSBtaWQyOwogICAgfQogICAgQmFsbCBuZXdCYWxsMSA9IG1vdmVCYWxsKGJhbGwxLCB0aW1lU2VnbWVudDEsIGxvKTsKICAgIEJhbGwgbmV3QmFsbDIgPSBtb3ZlQmFsbChiYWxsMiwgdGltZVNlZ21lbnQyLCBsbyk7CiAgICByZXR1cm4gY29tbW9uQXJlYShuZXdCYWxsMSwgbmV3QmFsbDIpOwp9Cgpsb25nIGRvdWJsZSBzZWdtZW50UG9pbnREaXN0YW5jZShTZWdtZW50IHNlZ21lbnQsIFBvaW50IHBvaW50KSB7CiAgICByZXR1cm4gKHNlZ21lbnQuZmlyc3QgLSBwb2ludCkuY3Jvc3Moc2VnbWVudC5zZWNvbmQgLSBwb2ludCkgLyAoc2VnbWVudC5zZWNvbmQgLSBzZWdtZW50LmZpcnN0KS5nZXRMZW5ndGgoKTsKfQoKdmVjdG9yPFRpbWVTZWdtZW50QmFsbD4gZ2V0VGltZVNlZ21lbnRCYWxscyhCYWxsIGJhbGwsIFNlZ21lbnQgd2FsbCkgewogICAgaW50IGRpcjEgPSBzaWduKCh3YWxsLmZpcnN0IC0gYmFsbC5jZW50ZXIpLmNyb3NzKHdhbGwuc2Vjb25kIC0gYmFsbC5jZW50ZXIpKTsKICAgIGludCBkaXIyID0gc2lnbigod2FsbC5maXJzdCAtIG1vdmVCYWxsKGJhbGwsIElORikuY2VudGVyKS5jcm9zcyh3YWxsLnNlY29uZCAtIG1vdmVCYWxsKGJhbGwsIElORikuY2VudGVyKSk7CiAgICBpZiAoZGlyMSA9PSBkaXIyKSB7CiAgICAgICAgdmVjdG9yPFRpbWVTZWdtZW50QmFsbD4gcmV0OwogICAgICAgIHJldC5wdXNoX2JhY2soe3swLjAsIElORn0sIGJhbGx9KTsKICAgICAgICByZXR1cm4gcmV0OwogICAgfQogICAgbG9uZyBkb3VibGUgbG8gPSAwLCBoaSA9IElORjsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMjAwMDsgaSsrKSB7CiAgICAgICAgbG9uZyBkb3VibGUgbWlkID0gKGxvICsgaGkpIC8gMi4wOwogICAgICAgIEJhbGwgYmFsbE1pZCA9IG1vdmVCYWxsKGJhbGwsIG1pZCk7CiAgICAgICAgbG9uZyBkb3VibGUgZGlzID0gc2VnbWVudFBvaW50RGlzdGFuY2Uod2FsbCwgYmFsbE1pZC5jZW50ZXIpOwogICAgICAgIGlmIChzaWduKGRpcykgIT0gZGlyMSB8fCAoc2lnbihkaXMpID09IGRpcjEgJiYgZmFicyhkaXMpIDwgYmFsbC5yYWRpdXMpKQogICAgICAgICAgICBoaSA9IG1pZDsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGxvID0gbWlkOwogICAgfQogICAgdmVjdG9yPFRpbWVTZWdtZW50QmFsbD4gcmV0OwogICAgcmV0LnB1c2hfYmFjayh7ezAuMCwgbG99LCBiYWxsfSk7CiAgICBiYWxsID0gbW92ZUJhbGwoYmFsbCwgbG8pOwogICAgYmFsbC52ZWxvY2l0eSA9IHJlZmxlY3QoYmFsbC52ZWxvY2l0eSwgd2FsbCk7CiAgICByZXQucHVzaF9iYWNrKHt7aGksIElORn0sIGJhbGx9KTsKICAgIHJldHVybiByZXQ7Cn0KCmludCB0YzsKdmVjdG9yPFRpbWVTZWdtZW50QmFsbD4gdGltZVNlZ21lbnRCYWxsc1sxMF07CgppbnQgbWFpbigpIHsKICAgIGNpbiA+PiB0YzsKICAgIGNvdXQucHJlY2lzaW9uKDEyKTsKICAgIHdoaWxlICh0Yy0tKSB7CiAgICAgICAgdmVjdG9yPEJhbGw+IGJhbGxzOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMjsgaSsrKSB7CiAgICAgICAgICAgIGxvbmcgZG91YmxlIHgsIHk7CiAgICAgICAgICAgIGxvbmcgZG91YmxlIHZ4LCB2eTsKICAgICAgICAgICAgbG9uZyBkb3VibGUgcjsKICAgICAgICAgICAgY2luID4+IHggPj4geTsKICAgICAgICAgICAgY2luID4+IHZ4ID4+IHZ5OwogICAgICAgICAgICBjaW4gPj4gcjsKICAgICAgICAgICAgYmFsbHMucHVzaF9iYWNrKEJhbGwoUG9pbnQoeCwgeSksIFZlY3Rvcih2eCwgdnkpLCByKSk7CiAgICAgICAgfQogICAgICAgIGxvbmcgZG91YmxlIHdhbGxYMSwgd2FsbFkxOwogICAgICAgIGxvbmcgZG91YmxlIHdhbGxYMiwgd2FsbFkyOwogICAgICAgIGNpbiA+PiB3YWxsWDEgPj4gd2FsbFkxOwogICAgICAgIGNpbiA+PiB3YWxsWDIgPj4gd2FsbFkyOwogICAgICAgIFNlZ21lbnQgd2FsbChQb2ludCh3YWxsWDEsIHdhbGxZMSksIFBvaW50KHdhbGxYMiwgd2FsbFkyKSk7CiAgICAgICAgbG9uZyBkb3VibGUgYW5zID0gMDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDI7IGkrKykgewogICAgICAgICAgICB0aW1lU2VnbWVudEJhbGxzW2ldID0gZ2V0VGltZVNlZ21lbnRCYWxscyhiYWxsc1tpXSwgd2FsbCk7CiAgICAgICAgfQogICAgICAgIGZvciAoYXV0byB0aW1lU2VnbWVudEJhbGwwOiB0aW1lU2VnbWVudEJhbGxzWzBdKQogICAgICAgICAgICBmb3IgKGF1dG8gdGltZVNlZ21lbnRCYWxsMTogdGltZVNlZ21lbnRCYWxsc1sxXSkgewogICAgICAgICAgICAgICAgYW5zID0gbWF4KGFucywgbWF4aW11bUNvbW1vbkFyZWEodGltZVNlZ21lbnRCYWxsMC5zZWNvbmQsIHRpbWVTZWdtZW50QmFsbDEuc2Vjb25kLCB0aW1lU2VnbWVudEJhbGwwLmZpcnN0LCB0aW1lU2VnbWVudEJhbGwxLmZpcnN0KSk7CiAgICAgICAgICAgIH0KICAgICAgICBjb3V0IDw8IGZpeGVkIDw8IGFucyA8PCBlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0=