#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
long long one_billionth(long long x) {
long long y = (x >> 32) * 2305843009LL;
y >>= 29;
x -= 1000000000LL * y;
x += (x >> 4);
return (y + (((x >> 29) + 1) >> 1));
}
long long crazy_degree_table[] = {
// angle x y angle (dms)
0, 1000000000, 0, // 0: 0: 0
3599269, 999847757, 17448863, // 0:59:59.269
7198351, 999391106, 34891507, // 1:59:58.351
10799869, 998629568, 52335322, // 2:59:59.869
14392361, 997566633, 69719529, // 3:59:52.361
18001484, 996194071, 87162910, // 5: 0: 1.484
21603140, 994520304, 104543603, // 6: 0: 3.14
25198449, 992547068, 121861880, // 6:59:58.449
28800050, 990268035, 139173341, // 8: 0: 0.05
32397717, 987690072, 156423533, // 8:59:57.717
35999728, 984807982, 173646879, // 9:59:59.728
39601035, 981626226, 190813921, // 11: 0:1.035
43199592, 978148012, 207909756, // 11:59:59.592
46800693, 974369309, 224954328, // 13: 0: 0.693
50397751, 970298364, 241911316, // 13:59:57.751
53997701, 965928711, 258808279, // 14:59:57.701
57600865, 961260540, 275641387, // 16: 0: 0.865
61199837, 956304987, 292370949, // 16:59:59.837
64799302, 951057562, 309013776, // 17:59:59.302
68401066, 945516893, 325573041, // 19: 0: 1.066
72001124, 939690757, 342025264, // 20: 0: 1.124
75601453, 933577902, 358374526, // 21: 0: 1.453
79199676, 927184443, 374605137, // 21:59:59.676
82800308, 920504270, 390732503, // 23: 0: 0.308
86400832, 913543817, 406740328, // 24: 0: 0.832
89998876, 906310090, 422613323, // 24:59:58.876
93600202, 898793617, 438372027, // 26: 0: 0.202
97197971, 891010990, 453981735, // 26:59:57.971
100801394, 882944420, 469477530, // 28: 0: 1.394
104401002, 874617352, 484813869, // 29: 0: 1.002
108000141, 866025062, 500000592, // 30: 0: 0.141
111598780, 857170347, 515033005, // 30:59:58.78
115200617, 848046511, 529921801, // 32: 0: 0.617
118802334, 838664405, 544648525, // 33: 0: 2.334
122398991, 829040308, 559188848, // 33:59:58.991
125998685, 819155701, 573571214, // 34:59:58.685
129599798, 809017570, 587784460, // 35:59:59.798
133200048, 798635370, 601815209, // 37: 0: 0.048
136800553, 788009103, 615663588, // 38: 0: 0.553
140401537, 777141272, 629326182, // 39: 0: 1.537
143999915, 766044708, 642787294, // 39:59:59.915
147600516, 754707939, 656060917, // 41: 0: 0.516
151199457, 743146587, 669128650, // 41:59:59.457
154799036, 731356889, 681994942, // 42:59:59.036
158401431, 719334981, 694663361, // 44: 0: 1.431
161995261, 707123027, 707090535 // 44:59:55.261
};
long long crazy_minute_table [] = {
// angle x y angle (dms)
0, 1000000000, 0, // 0: 0: 0
59784, 999999958, 289841, // 0: 0:59.784
119917, 999999831, 581374, // 0: 1:59.917
180056, 999999619, 872936, // 0: 3: 0.056
240017, 999999323, 1163635, // 0: 4: 0.017
300043, 999998942, 1454649, // 0: 5: 0.043
360108, 999998476, 1745852, // 0: 6: 0.108
421304, 999997914, 2042538, // 0: 7: 1.304
479938, 999997293, 2326803, // 0: 7:59.938
539611, 999996578, 2616105, // 0: 8:59.611
600013, 999995769, 2908941, // 0:10: 0.013
659920, 999994882, 3199377, // 0:10:59.92
720569, 999993898, 3493410, // 0:12: 0.569
779998, 999992850, 3781528, // 0:12:59.998
839932, 999991709, 4072094, // 0:13:59.932
900081, 999990479, 4363702, // 0:15: 0.081
959964, 999989170, 4654020, // 0:15:59.964
1020042, 999987772, 4945283, // 0:17: 0.042
1078867, 999986321, 5230471, // 0:17:58.867
1139920, 999984729, 5526460, // 0:18:59.92
1200101, 999983074, 5818221, // 0:20: 0.101
1260042, 999981341, 6108818, // 0:21: 0.042
1320065, 999979521, 6399812, // 0:22: 0.065
1380098, 999977616, 6690854, // 0:23: 0.098
1439844, 999975636, 6980504, // 0:23:59.844
1499876, 999973562, 7271540, // 0:24:59.876
1560081, 999971397, 7563414, // 0:26: 0.081
1619177, 999969189, 7849911, // 0:26:59.177
1679867, 999966836, 8144135, // 0:27:59.867
1740079, 999964416, 8436041, // 0:29: 0.079
1799931, 999961926, 8726201, // 0:29:59.931
1859870, 999959348, 9016782 // 0:30:59.87
};
const long ONE_CRAZY_SECOND = 1000L;
const long ONE_CRAZY_MINUTE = 60L * ONE_CRAZY_SECOND;
const long ONE_CRAZY_DEGREE = 60L * ONE_CRAZY_MINUTE;
const long ONE_CRAZY_OCTANT = 45L * ONE_CRAZY_DEGREE;
const long ONE_CRAZY_TURN = 8L * ONE_CRAZY_OCTANT;
//
// note that 2 * ONE_CRAZY_TURN WILL NOT FIT in a long!!
long crazy_sin (long theta) {
// normalize theta (range: -180 to +180 degrees)
while (theta < (-4 * ONE_CRAZY_OCTANT)) theta += ONE_CRAZY_TURN;
while (theta > (4 * ONE_CRAZY_OCTANT)) theta -= ONE_CRAZY_TURN;
// use an identity to reduce range to: -90 to +90 degrees
if (theta < (-2 * ONE_CRAZY_OCTANT)) {
theta = (-4 * ONE_CRAZY_OCTANT) - theta;
}
if (theta > (2 * ONE_CRAZY_OCTANT)) {
theta = (4 * ONE_CRAZY_OCTANT) - theta;
}
// where do we look in the table?
// this is complicated because C++ modulo function is nuts
int where = theta / ONE_CRAZY_DEGREE;
if ((theta-(where*ONE_CRAZY_DEGREE))>(30*ONE_CRAZY_MINUTE)) where++;
else if ((theta-(where*ONE_CRAZY_DEGREE))<(-30*ONE_CRAZY_MINUTE)) where--;
// now do the table lookup
long long x; long long y;
if (where > 90) return -1111111111L;
else if (where > 45) {
where = 90 - where;
theta -= ((90 * ONE_CRAZY_DEGREE) - crazy_degree_table[where*3]);
y = crazy_degree_table[(where*3)+1];
x = crazy_degree_table[(where*3)+2];
}
else if (where >= 0) {
theta -= crazy_degree_table[where*3];
x = crazy_degree_table[(where*3)+1];
y = crazy_degree_table[(where*3)+2];
}
else if (where >= -45) {
where = -where;
theta += crazy_degree_table[where*3];
x = crazy_degree_table[(where*3)+1];
y = -crazy_degree_table[(where*3)+2];
}
else if (where >= -90) {
where += 90;
theta += ((90 * ONE_CRAZY_DEGREE) - crazy_degree_table[where*3]);
y = -crazy_degree_table[(where*3)+1];
x = crazy_degree_table[(where*3)+2];
}
else return -1111111111L;
// lather, rinse, repeat
where = theta / ONE_CRAZY_MINUTE;
if ((theta-(where*ONE_CRAZY_MINUTE))>(30*ONE_CRAZY_SECOND)) where++;
else if ((theta-(where*ONE_CRAZY_MINUTE))<(-30*ONE_CRAZY_SECOND)) where--;
// okay, now it gets complicated
// let's try to squeeze in a few "guard bits"
x <<= 2;
y <<= 2;
// and we need some new temporary storage
long long x_2;
long long y_2;
long long t;
// so let's take care of the minutes ...
if (where > 31) return -1111111111L;
else if (where >= 0) {
theta -= crazy_minute_table[where*3];
x_2 = crazy_minute_table[(where*3)+1];
y_2 = crazy_minute_table[(where*3)+2];
}
else if (where >= -31) {
where = -where;
theta += crazy_minute_table[where*3];
x_2 = crazy_minute_table[(where*3)+1];
y_2 = -crazy_minute_table[(where*3)+2];
}
else return -1111111111L;
// I told you it would be complicated ...
t = one_billionth((x * x_2) - (y * y_2));
y = one_billionth((x * y_2) + (y * x_2));
x = t;
// next we take care of, that's right, the seconds
// our angle unit is 1/1000 arcsecond,
// which is 4.848136811e-9 of a radian
t = (((635455LL * theta) >> 15)+1)>>1;
x_2 = 2000000000LL - one_billionth((t * t) >> 2); // bug squashed
y_2 = t;
// wiggle it... just a little bit...
// t = one_billionth((x * x_2) - (y * y_2));
y = one_billionth((x * y_2) + (y * x_2));
// x = t;
// x += 4;
y += 4;
// x >>= 3;
y >>= 3;
return y;
}
int main() {
long one_deg = 3600000L;
long one_step = one_deg/200;
double maxerr = 0.0;
for (long i = -360*one_deg; i <= 360*one_deg; i += one_step) {
double th = (i*1.0) / one_deg;
double cs = (crazy_sin(i)*1.0e-9);
double rs = sin(th * 0.0174532925199433);
double err = abs(cs-rs);
if (err > maxerr) maxerr = err;
// cout << th << " " ;
// cout << setprecision(9) << cs << " " << rs << " ";
// cout << err << "\n";
}
cout << maxerr << "\n";
// your code goes here
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGNtYXRoPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbG9uZyBsb25nIG9uZV9iaWxsaW9udGgobG9uZyBsb25nIHgpIHsKCWxvbmcgbG9uZyB5ID0gKHggPj4gMzIpICogMjMwNTg0MzAwOUxMOwoJeSA+Pj0gMjk7Cgl4IC09IDEwMDAwMDAwMDBMTCAqIHk7Cgl4ICs9ICh4ID4+IDQpOwoJcmV0dXJuICh5ICsgKCgoeCA+PiAyOSkgKyAxKSA+PiAxKSk7Cn0KCmxvbmcgbG9uZyBjcmF6eV9kZWdyZWVfdGFibGVbXSA9IHsKICAvLyAgYW5nbGUgICAgICAgIHggICAgICAgICB5ICAgICAgICAgYW5nbGUgKGRtcykKICAgICAgICAgIDAsIDEwMDAwMDAwMDAsICAgICAgICAwLCAvLyAgMDogMDogMAogICAgMzU5OTI2OSwgOTk5ODQ3NzU3LCAgMTc0NDg4NjMsIC8vICAwOjU5OjU5LjI2OQogICAgNzE5ODM1MSwgOTk5MzkxMTA2LCAgMzQ4OTE1MDcsIC8vICAxOjU5OjU4LjM1MQogICAxMDc5OTg2OSwgOTk4NjI5NTY4LCAgNTIzMzUzMjIsIC8vICAyOjU5OjU5Ljg2OQogICAxNDM5MjM2MSwgOTk3NTY2NjMzLCAgNjk3MTk1MjksIC8vICAzOjU5OjUyLjM2MQogICAxODAwMTQ4NCwgOTk2MTk0MDcxLCAgODcxNjI5MTAsIC8vICA1OiAwOiAxLjQ4NAogICAyMTYwMzE0MCwgOTk0NTIwMzA0LCAxMDQ1NDM2MDMsIC8vICA2OiAwOiAzLjE0CiAgIDI1MTk4NDQ5LCA5OTI1NDcwNjgsIDEyMTg2MTg4MCwgLy8gIDY6NTk6NTguNDQ5CiAgIDI4ODAwMDUwLCA5OTAyNjgwMzUsIDEzOTE3MzM0MSwgLy8gIDg6IDA6IDAuMDUKICAgMzIzOTc3MTcsIDk4NzY5MDA3MiwgMTU2NDIzNTMzLCAvLyAgODo1OTo1Ny43MTcKICAgMzU5OTk3MjgsIDk4NDgwNzk4MiwgMTczNjQ2ODc5LCAvLyAgOTo1OTo1OS43MjgKICAgMzk2MDEwMzUsIDk4MTYyNjIyNiwgMTkwODEzOTIxLCAvLyAxMTogMDoxLjAzNQogICA0MzE5OTU5MiwgOTc4MTQ4MDEyLCAyMDc5MDk3NTYsIC8vIDExOjU5OjU5LjU5MgogICA0NjgwMDY5MywgOTc0MzY5MzA5LCAyMjQ5NTQzMjgsIC8vIDEzOiAwOiAwLjY5MwogICA1MDM5Nzc1MSwgOTcwMjk4MzY0LCAyNDE5MTEzMTYsIC8vIDEzOjU5OjU3Ljc1MQogICA1Mzk5NzcwMSwgOTY1OTI4NzExLCAyNTg4MDgyNzksIC8vIDE0OjU5OjU3LjcwMQogICA1NzYwMDg2NSwgOTYxMjYwNTQwLCAyNzU2NDEzODcsIC8vIDE2OiAwOiAwLjg2NQogICA2MTE5OTgzNywgOTU2MzA0OTg3LCAyOTIzNzA5NDksIC8vIDE2OjU5OjU5LjgzNwogICA2NDc5OTMwMiwgOTUxMDU3NTYyLCAzMDkwMTM3NzYsIC8vIDE3OjU5OjU5LjMwMgogICA2ODQwMTA2NiwgOTQ1NTE2ODkzLCAzMjU1NzMwNDEsIC8vIDE5OiAwOiAxLjA2NgogICA3MjAwMTEyNCwgOTM5NjkwNzU3LCAzNDIwMjUyNjQsIC8vIDIwOiAwOiAxLjEyNAogICA3NTYwMTQ1MywgOTMzNTc3OTAyLCAzNTgzNzQ1MjYsIC8vIDIxOiAwOiAxLjQ1MwogICA3OTE5OTY3NiwgOTI3MTg0NDQzLCAzNzQ2MDUxMzcsIC8vIDIxOjU5OjU5LjY3NgogICA4MjgwMDMwOCwgOTIwNTA0MjcwLCAzOTA3MzI1MDMsIC8vIDIzOiAwOiAwLjMwOAogICA4NjQwMDgzMiwgOTEzNTQzODE3LCA0MDY3NDAzMjgsIC8vIDI0OiAwOiAwLjgzMgogICA4OTk5ODg3NiwgOTA2MzEwMDkwLCA0MjI2MTMzMjMsIC8vIDI0OjU5OjU4Ljg3NgogICA5MzYwMDIwMiwgODk4NzkzNjE3LCA0MzgzNzIwMjcsIC8vIDI2OiAwOiAwLjIwMgogICA5NzE5Nzk3MSwgODkxMDEwOTkwLCA0NTM5ODE3MzUsIC8vIDI2OjU5OjU3Ljk3MQogIDEwMDgwMTM5NCwgODgyOTQ0NDIwLCA0Njk0Nzc1MzAsIC8vIDI4OiAwOiAxLjM5NAogIDEwNDQwMTAwMiwgODc0NjE3MzUyLCA0ODQ4MTM4NjksIC8vIDI5OiAwOiAxLjAwMgogIDEwODAwMDE0MSwgODY2MDI1MDYyLCA1MDAwMDA1OTIsIC8vIDMwOiAwOiAwLjE0MQogIDExMTU5ODc4MCwgODU3MTcwMzQ3LCA1MTUwMzMwMDUsIC8vIDMwOjU5OjU4Ljc4CiAgMTE1MjAwNjE3LCA4NDgwNDY1MTEsIDUyOTkyMTgwMSwgLy8gMzI6IDA6IDAuNjE3CiAgMTE4ODAyMzM0LCA4Mzg2NjQ0MDUsIDU0NDY0ODUyNSwgLy8gMzM6IDA6IDIuMzM0CiAgMTIyMzk4OTkxLCA4MjkwNDAzMDgsIDU1OTE4ODg0OCwgLy8gMzM6NTk6NTguOTkxCiAgMTI1OTk4Njg1LCA4MTkxNTU3MDEsIDU3MzU3MTIxNCwgLy8gMzQ6NTk6NTguNjg1CiAgMTI5NTk5Nzk4LCA4MDkwMTc1NzAsIDU4Nzc4NDQ2MCwgLy8gMzU6NTk6NTkuNzk4CiAgMTMzMjAwMDQ4LCA3OTg2MzUzNzAsIDYwMTgxNTIwOSwgLy8gMzc6IDA6IDAuMDQ4CiAgMTM2ODAwNTUzLCA3ODgwMDkxMDMsIDYxNTY2MzU4OCwgLy8gMzg6IDA6IDAuNTUzCiAgMTQwNDAxNTM3LCA3NzcxNDEyNzIsIDYyOTMyNjE4MiwgLy8gMzk6IDA6IDEuNTM3CiAgMTQzOTk5OTE1LCA3NjYwNDQ3MDgsIDY0Mjc4NzI5NCwgLy8gMzk6NTk6NTkuOTE1CiAgMTQ3NjAwNTE2LCA3NTQ3MDc5MzksIDY1NjA2MDkxNywgLy8gNDE6IDA6IDAuNTE2CiAgMTUxMTk5NDU3LCA3NDMxNDY1ODcsIDY2OTEyODY1MCwgLy8gNDE6NTk6NTkuNDU3CiAgMTU0Nzk5MDM2LCA3MzEzNTY4ODksIDY4MTk5NDk0MiwgLy8gNDI6NTk6NTkuMDM2CiAgMTU4NDAxNDMxLCA3MTkzMzQ5ODEsIDY5NDY2MzM2MSwgLy8gNDQ6IDA6IDEuNDMxCiAgMTYxOTk1MjYxLCA3MDcxMjMwMjcsIDcwNzA5MDUzNSAgLy8gNDQ6NTk6NTUuMjYxCn07Cgpsb25nIGxvbmcgY3JhenlfbWludXRlX3RhYmxlIFtdID0gewogIC8vIGFuZ2xlICAgICAgICB4ICAgICAgICAgeSAgICAgYW5nbGUgKGRtcykKICAgICAgICAwLCAxMDAwMDAwMDAwLCAgICAgIDAsIC8vIDA6IDA6IDAKICAgIDU5Nzg0LCA5OTk5OTk5NTgsICAyODk4NDEsIC8vIDA6IDA6NTkuNzg0CiAgIDExOTkxNywgOTk5OTk5ODMxLCAgNTgxMzc0LCAvLyAwOiAxOjU5LjkxNwogICAxODAwNTYsIDk5OTk5OTYxOSwgIDg3MjkzNiwgLy8gMDogMzogMC4wNTYKICAgMjQwMDE3LCA5OTk5OTkzMjMsIDExNjM2MzUsIC8vIDA6IDQ6IDAuMDE3CiAgIDMwMDA0MywgOTk5OTk4OTQyLCAxNDU0NjQ5LCAvLyAwOiA1OiAwLjA0MwogICAzNjAxMDgsIDk5OTk5ODQ3NiwgMTc0NTg1MiwgLy8gMDogNjogMC4xMDgKICAgNDIxMzA0LCA5OTk5OTc5MTQsIDIwNDI1MzgsIC8vIDA6IDc6IDEuMzA0CiAgIDQ3OTkzOCwgOTk5OTk3MjkzLCAyMzI2ODAzLCAvLyAwOiA3OjU5LjkzOAogICA1Mzk2MTEsIDk5OTk5NjU3OCwgMjYxNjEwNSwgLy8gMDogODo1OS42MTEKICAgNjAwMDEzLCA5OTk5OTU3NjksIDI5MDg5NDEsIC8vIDA6MTA6IDAuMDEzCiAgIDY1OTkyMCwgOTk5OTk0ODgyLCAzMTk5Mzc3LCAvLyAwOjEwOjU5LjkyCiAgIDcyMDU2OSwgOTk5OTkzODk4LCAzNDkzNDEwLCAvLyAwOjEyOiAwLjU2OQogICA3Nzk5OTgsIDk5OTk5Mjg1MCwgMzc4MTUyOCwgLy8gMDoxMjo1OS45OTgKICAgODM5OTMyLCA5OTk5OTE3MDksIDQwNzIwOTQsIC8vIDA6MTM6NTkuOTMyCiAgIDkwMDA4MSwgOTk5OTkwNDc5LCA0MzYzNzAyLCAvLyAwOjE1OiAwLjA4MQogICA5NTk5NjQsIDk5OTk4OTE3MCwgNDY1NDAyMCwgLy8gMDoxNTo1OS45NjQKICAxMDIwMDQyLCA5OTk5ODc3NzIsIDQ5NDUyODMsIC8vIDA6MTc6IDAuMDQyCiAgMTA3ODg2NywgOTk5OTg2MzIxLCA1MjMwNDcxLCAvLyAwOjE3OjU4Ljg2NwogIDExMzk5MjAsIDk5OTk4NDcyOSwgNTUyNjQ2MCwgLy8gMDoxODo1OS45MgogIDEyMDAxMDEsIDk5OTk4MzA3NCwgNTgxODIyMSwgLy8gMDoyMDogMC4xMDEKICAxMjYwMDQyLCA5OTk5ODEzNDEsIDYxMDg4MTgsIC8vIDA6MjE6IDAuMDQyCiAgMTMyMDA2NSwgOTk5OTc5NTIxLCA2Mzk5ODEyLCAvLyAwOjIyOiAwLjA2NQogIDEzODAwOTgsIDk5OTk3NzYxNiwgNjY5MDg1NCwgLy8gMDoyMzogMC4wOTgKICAxNDM5ODQ0LCA5OTk5NzU2MzYsIDY5ODA1MDQsIC8vIDA6MjM6NTkuODQ0CiAgMTQ5OTg3NiwgOTk5OTczNTYyLCA3MjcxNTQwLCAvLyAwOjI0OjU5Ljg3NgogIDE1NjAwODEsIDk5OTk3MTM5NywgNzU2MzQxNCwgLy8gMDoyNjogMC4wODEKICAxNjE5MTc3LCA5OTk5NjkxODksIDc4NDk5MTEsIC8vIDA6MjY6NTkuMTc3CiAgMTY3OTg2NywgOTk5OTY2ODM2LCA4MTQ0MTM1LCAvLyAwOjI3OjU5Ljg2NwogIDE3NDAwNzksIDk5OTk2NDQxNiwgODQzNjA0MSwgLy8gMDoyOTogMC4wNzkKICAxNzk5OTMxLCA5OTk5NjE5MjYsIDg3MjYyMDEsIC8vIDA6Mjk6NTkuOTMxCiAgMTg1OTg3MCwgOTk5OTU5MzQ4LCA5MDE2NzgyICAvLyAwOjMwOjU5Ljg3IAp9OwoKY29uc3QgbG9uZyBPTkVfQ1JBWllfU0VDT05EID0gMTAwMEw7CmNvbnN0IGxvbmcgT05FX0NSQVpZX01JTlVURSA9IDYwTCAqIE9ORV9DUkFaWV9TRUNPTkQ7CmNvbnN0IGxvbmcgT05FX0NSQVpZX0RFR1JFRSA9IDYwTCAqIE9ORV9DUkFaWV9NSU5VVEU7CmNvbnN0IGxvbmcgT05FX0NSQVpZX09DVEFOVCA9IDQ1TCAqIE9ORV9DUkFaWV9ERUdSRUU7CmNvbnN0IGxvbmcgT05FX0NSQVpZX1RVUk4gICA9ICA4TCAqIE9ORV9DUkFaWV9PQ1RBTlQ7Ci8vCi8vIG5vdGUgdGhhdCAyICogT05FX0NSQVpZX1RVUk4gV0lMTCBOT1QgRklUIGluIGEgbG9uZyEhCgpsb25nIGNyYXp5X3NpbiAobG9uZyB0aGV0YSkgewogIC8vIG5vcm1hbGl6ZSB0aGV0YSAocmFuZ2U6IC0xODAgIHRvICsxODAgZGVncmVlcykKICB3aGlsZSAodGhldGEgPCAoLTQgKiBPTkVfQ1JBWllfT0NUQU5UKSkgdGhldGEgKz0gT05FX0NSQVpZX1RVUk47CiAgd2hpbGUgKHRoZXRhID4gKDQgKiBPTkVfQ1JBWllfT0NUQU5UKSkgdGhldGEgLT0gT05FX0NSQVpZX1RVUk47CiAgLy8gdXNlIGFuIGlkZW50aXR5IHRvIHJlZHVjZSByYW5nZSB0bzogLTkwIHRvICs5MCBkZWdyZWVzCiAgaWYgKHRoZXRhIDwgKC0yICogT05FX0NSQVpZX09DVEFOVCkpIHsKICAgIHRoZXRhID0gKC00ICogT05FX0NSQVpZX09DVEFOVCkgLSB0aGV0YTsKICB9CiAgaWYgKHRoZXRhID4gKDIgKiBPTkVfQ1JBWllfT0NUQU5UKSkgewogICAgdGhldGEgPSAoNCAqIE9ORV9DUkFaWV9PQ1RBTlQpIC0gdGhldGE7CiAgfQogIC8vIHdoZXJlIGRvIHdlIGxvb2sgaW4gdGhlIHRhYmxlPwogIC8vIHRoaXMgaXMgY29tcGxpY2F0ZWQgYmVjYXVzZSBDKysgbW9kdWxvIGZ1bmN0aW9uIGlzIG51dHMKICBpbnQgd2hlcmUgPSB0aGV0YSAvIE9ORV9DUkFaWV9ERUdSRUU7CiAgaWYgKCh0aGV0YS0od2hlcmUqT05FX0NSQVpZX0RFR1JFRSkpPigzMCpPTkVfQ1JBWllfTUlOVVRFKSkgd2hlcmUrKzsKICBlbHNlIGlmICgodGhldGEtKHdoZXJlKk9ORV9DUkFaWV9ERUdSRUUpKTwoLTMwKk9ORV9DUkFaWV9NSU5VVEUpKSB3aGVyZS0tOwogIC8vIG5vdyBkbyB0aGUgdGFibGUgbG9va3VwCiAgbG9uZyBsb25nIHg7IGxvbmcgbG9uZyB5OwogIGlmICh3aGVyZSA+IDkwKSByZXR1cm4gLTExMTExMTExMTFMOwogIGVsc2UgaWYgKHdoZXJlID4gNDUpIHsKICAgIHdoZXJlID0gOTAgLSB3aGVyZTsKICAgIHRoZXRhIC09ICgoOTAgKiBPTkVfQ1JBWllfREVHUkVFKSAtIGNyYXp5X2RlZ3JlZV90YWJsZVt3aGVyZSozXSk7CiAgICB5ID0gY3JhenlfZGVncmVlX3RhYmxlWyh3aGVyZSozKSsxXTsKICAgIHggPSBjcmF6eV9kZWdyZWVfdGFibGVbKHdoZXJlKjMpKzJdOwogIH0gCiAgZWxzZSBpZiAod2hlcmUgPj0gMCkgewogICAgdGhldGEgLT0gY3JhenlfZGVncmVlX3RhYmxlW3doZXJlKjNdOwogICAgeCA9IGNyYXp5X2RlZ3JlZV90YWJsZVsod2hlcmUqMykrMV07CiAgICB5ID0gY3JhenlfZGVncmVlX3RhYmxlWyh3aGVyZSozKSsyXTsgCiAgfQogIGVsc2UgaWYgKHdoZXJlID49IC00NSkgewogICAgd2hlcmUgPSAtd2hlcmU7CiAgICB0aGV0YSArPSBjcmF6eV9kZWdyZWVfdGFibGVbd2hlcmUqM107CiAgICB4ID0gY3JhenlfZGVncmVlX3RhYmxlWyh3aGVyZSozKSsxXTsKICAgIHkgPSAtY3JhenlfZGVncmVlX3RhYmxlWyh3aGVyZSozKSsyXTsgICAgIAogIH0KICBlbHNlIGlmICh3aGVyZSA+PSAtOTApIHsKICAgIHdoZXJlICs9IDkwOwogICAgdGhldGEgKz0gKCg5MCAqIE9ORV9DUkFaWV9ERUdSRUUpIC0gY3JhenlfZGVncmVlX3RhYmxlW3doZXJlKjNdKTsKICAgIHkgPSAtY3JhenlfZGVncmVlX3RhYmxlWyh3aGVyZSozKSsxXTsKICAgIHggPSBjcmF6eV9kZWdyZWVfdGFibGVbKHdoZXJlKjMpKzJdOyAKICB9CiAgZWxzZSByZXR1cm4gLTExMTExMTExMTFMOwogIC8vIGxhdGhlciwgcmluc2UsIHJlcGVhdAogIHdoZXJlID0gdGhldGEgLyBPTkVfQ1JBWllfTUlOVVRFOwogIGlmICgodGhldGEtKHdoZXJlKk9ORV9DUkFaWV9NSU5VVEUpKT4oMzAqT05FX0NSQVpZX1NFQ09ORCkpIHdoZXJlKys7CiAgZWxzZSBpZiAoKHRoZXRhLSh3aGVyZSpPTkVfQ1JBWllfTUlOVVRFKSk8KC0zMCpPTkVfQ1JBWllfU0VDT05EKSkgd2hlcmUtLTsKICAvLyBva2F5LCBub3cgaXQgZ2V0cyBjb21wbGljYXRlZAogIC8vIGxldCdzIHRyeSB0byBzcXVlZXplIGluIGEgZmV3ICJndWFyZCBiaXRzIgogIHggPDw9IDI7CiAgeSA8PD0gMjsKICAvLyBhbmQgd2UgbmVlZCBzb21lIG5ldyB0ZW1wb3Jhcnkgc3RvcmFnZQogIGxvbmcgbG9uZyB4XzI7CiAgbG9uZyBsb25nIHlfMjsKICBsb25nIGxvbmcgdDsgCiAgLy8gc28gbGV0J3MgdGFrZSBjYXJlIG9mIHRoZSBtaW51dGVzIC4uLgogIGlmICh3aGVyZSA+IDMxKSByZXR1cm4gLTExMTExMTExMTFMOwogIGVsc2UgaWYgKHdoZXJlID49IDApIHsKICAgIHRoZXRhIC09IGNyYXp5X21pbnV0ZV90YWJsZVt3aGVyZSozXTsKICAgIHhfMiA9IGNyYXp5X21pbnV0ZV90YWJsZVsod2hlcmUqMykrMV07CiAgICB5XzIgPSBjcmF6eV9taW51dGVfdGFibGVbKHdoZXJlKjMpKzJdOyAKICB9CiAgZWxzZSBpZiAod2hlcmUgPj0gLTMxKSB7CiAgICB3aGVyZSA9IC13aGVyZTsKICAgIHRoZXRhICs9IGNyYXp5X21pbnV0ZV90YWJsZVt3aGVyZSozXTsKICAgIHhfMiA9IGNyYXp5X21pbnV0ZV90YWJsZVsod2hlcmUqMykrMV07CiAgICB5XzIgPSAtY3JhenlfbWludXRlX3RhYmxlWyh3aGVyZSozKSsyXTsgICAgIAogIH0KICBlbHNlIHJldHVybiAtMTExMTExMTExMUw7CiAgLy8gSSB0b2xkIHlvdSBpdCB3b3VsZCBiZSBjb21wbGljYXRlZCAuLi4KICB0ID0gb25lX2JpbGxpb250aCgoeCAqIHhfMikgLSAoeSAqIHlfMikpOwogIHkgPSBvbmVfYmlsbGlvbnRoKCh4ICogeV8yKSArICh5ICogeF8yKSk7CiAgeCA9IHQ7CiAgLy8gbmV4dCB3ZSB0YWtlIGNhcmUgb2YsIHRoYXQncyByaWdodCwgdGhlIHNlY29uZHMKICAvLyBvdXIgYW5nbGUgdW5pdCBpcyAxLzEwMDAgYXJjc2Vjb25kLAogIC8vIHdoaWNoIGlzIDQuODQ4MTM2ODExZS05IG9mIGEgcmFkaWFuCiAgdCA9ICgoKDYzNTQ1NUxMICogdGhldGEpID4+IDE1KSsxKT4+MTsKICB4XzIgPSAyMDAwMDAwMDAwTEwgLSBvbmVfYmlsbGlvbnRoKCh0ICogdCkgPj4gMik7IC8vIGJ1ZyBzcXVhc2hlZAogIHlfMiA9IHQ7CiAgLy8gd2lnZ2xlIGl0Li4uIGp1c3QgYSBsaXR0bGUgYml0Li4uCiAgLy8gdCA9IG9uZV9iaWxsaW9udGgoKHggKiB4XzIpIC0gKHkgKiB5XzIpKTsKICB5ID0gb25lX2JpbGxpb250aCgoeCAqIHlfMikgKyAoeSAqIHhfMikpOwogIC8vIHggPSB0OwogIC8vIHggKz0gNDsKICB5ICs9IDQ7CiAgLy8geCA+Pj0gMzsKICB5ID4+PSAzOwogIHJldHVybiB5OyAKfQoKaW50IG1haW4oKSB7Cglsb25nIG9uZV9kZWcgPSAzNjAwMDAwTDsKCWxvbmcgb25lX3N0ZXAgPSBvbmVfZGVnLzIwMDsKCWRvdWJsZSBtYXhlcnIgPSAwLjA7Cglmb3IgKGxvbmcgaSA9IC0zNjAqb25lX2RlZzsgaSA8PSAzNjAqb25lX2RlZzsgaSArPSBvbmVfc3RlcCkgewoJICAgIGRvdWJsZSB0aCA9IChpKjEuMCkgLyBvbmVfZGVnOyAKCSAgICBkb3VibGUgY3MgPSAoY3Jhenlfc2luKGkpKjEuMGUtOSk7CgkgICAgZG91YmxlIHJzID0gc2luKHRoICogMC4wMTc0NTMyOTI1MTk5NDMzKTsKCSAgICBkb3VibGUgZXJyID0gYWJzKGNzLXJzKTsKCSAgICBpZiAoZXJyID4gbWF4ZXJyKSBtYXhlcnIgPSBlcnI7CgkgICAgLy8gY291dCA8PCB0aCA8PCAiICAiIDsKCSAgICAvLyBjb3V0IDw8IHNldHByZWNpc2lvbig5KSA8PCBjcyA8PCAiICAiIDw8IHJzIDw8ICIgICI7CgkgICAgLy8gY291dCA8PCBlcnIgPDwgIlxuIjsKCX0KCWNvdXQgPDwgbWF4ZXJyIDw8ICJcbiI7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglyZXR1cm4gMDsKfQ==