// Game Boy Advance library for Logic Machines F'05
// Version 6, November 16th, 2005

#include "gbamath.h"


extern const short cosine_table[];

#define COSINE_PRECISION_SHIFT	4
#define COSINE_PRECISION_SCALE	16	// 2^COSINE_PRECISION_SHIFT


real cosr(real a) {
	return cosine_table[(NormalizeAngle(a)) >> (REAL_SHIFT - COSINE_PRECISION_SHIFT)];
}


real sinr(real a) {
	return cosine_table[NormalizeAngle(a - REAL(64)) >> (REAL_SHIFT - COSINE_PRECISION_SHIFT)];
}


real sqrtr(real x) {

	real tmp, odd, root, last_root, half;
	int loops;

	if (x < REAL(0))
		return REAL(0);

	// first use pell's method to find integer approximation
	if (x < REAL(1))
		root = REAL(1);
	else {
		root = REAL(0);
		odd = REAL(1);
		tmp = x;
		while (tmp >= odd) {
			root += REAL(1);
			tmp -= odd;
			odd += REAL(2);
		}
	}

	// then use babylonian method to find real approximation
	loops = 0;
	half = divr(REAL(1), REAL(2));
	do {
		last_root = root;
		root = mulr(half, root + divr(x, root));
		++loops;
	} while (root != last_root && loops < 5);

	return root;

}


real asinr(real x) {

	int a, step, dir;

	if (x < REAL(-1) || x > REAL(1))
		return 0;

	a = 64 * COSINE_PRECISION_SCALE;		// 90 degrees
	step = 32 * COSINE_PRECISION_SCALE;
	dir = -1;
	while (step > 0) {
	
		real cosa = cosine_table[a];
//		printf("%f %d %d %d (%f)\n", FLOAT(x), a, step, dir, FLOAT(cosa));

		if (x > cosa) {
			if (dir == 1) {
				step >>= 1;
				dir = -1;
			}
		} else if (x < cosa) {
			if (dir == -1) {
				step >>= 1;
				dir = 1;
			}
		} else
			break;

		if (dir == 1)
			a += step;
		else
			a -= step;

	}

	return REAL(64) - (a << (REAL_SHIFT - COSINE_PRECISION_SHIFT));

}


real absr(real x) {

	if (x < REAL(0))
		return -x;
	else
		return x;

}


#if 0
real mulr(real a, real b) {

	long long la = a, lb = b, res;
	
	res = (la * lb) >> REAL_SHIFT;
	return res;

}


real divr(real a, real b) {

	long long la = a, lb = b, res;

	res = (la << REAL_SHIFT) / lb;
	return res;

}
#endif


real GetDistanceBetweenPoints(realpoint *pointOne, realpoint *pointTwo) {

	real deltaXBetweenPoints, deltaYBetweenPoints;

	deltaXBetweenPoints = pointTwo->x - pointOne->x;
	deltaYBetweenPoints = pointTwo->y - pointOne->y;

	return sqrtr(mulr(deltaXBetweenPoints, deltaXBetweenPoints) + mulr(deltaYBetweenPoints, deltaYBetweenPoints));

}


real GetAngleBetweenPoints(realpoint *pointOne, realpoint *pointTwo) {

	real deltaYBetweenPoints;
	real distanceBetweenPoints;
	real answer;
	
	distanceBetweenPoints = GetDistanceBetweenPoints(pointOne, pointTwo);
	if (distanceBetweenPoints == REAL(0))
		return 0;
	
	deltaYBetweenPoints = pointTwo->y - pointOne->y;
	
	answer = asinr(divr(deltaYBetweenPoints, distanceBetweenPoints));

	// Quadrant two
	if ((pointTwo->x < pointOne->x) && (pointTwo->y >= pointOne->y)) {
		answer = REAL(128) - answer;
	// Quadrant three
	} else if ((pointTwo->x <= pointOne->x) && (pointTwo->y < pointOne->y)) {
		answer = REAL(128) - answer;
	// Quadrant four
	} else if ((pointTwo->x > pointOne->x) && (pointTwo->y < pointOne->y)) {
		answer = REAL(256) + answer;
	}

	// Quadrant one
	return answer;

}


// Adjusting a degree heading sometimes results in angles
// greater than 360 or less than 0.  This routine translates those angles
// into their correct 0 to 360 range equivalents.
real NormalizeAngle(real angle) {

	// If the angle is negative, add 360 to it.
	while (angle < REAL(0))
		angle += REAL(256);
	
	// If the angle is over 360, subtract 360 from it.
	while (angle >= REAL(256))
		angle -= REAL(256);
 
 	// If we get here, the angle is between 0 and 360 and therefore
 	// no adjustment is necessary. Just return the angle.
	return angle;

}


// Rotates a source angle towards a target angle by the specified number of degrees,
// always using the shortest path (CW or CCW). Returns the source angle's new angle.
real ChaseAngle(real targetAngle, real sourceAngle, real degreesToRotate) {

	real targetAngleRelativeToZero;
	
	// If the difference between the angles is less than the amount we want to rotate per frame,
	// then just snap the source angle to the target angle.
	if (GetDeltaBetweenAngles(sourceAngle, targetAngle) < degreesToRotate)
		return targetAngle;
	
	// Otherwise, express the target angle relative to 0 degrees due east.
	targetAngleRelativeToZero = NormalizeAngle(targetAngle - sourceAngle);
	
	// If the new target angle is within a 180 clockwise swoop from 0 degrees,
	// we'll want to rotate clockwise,
	if (targetAngleRelativeToZero < REAL(128)) {
		sourceAngle += degreesToRotate;
	// otherwise, counterclockwise.
	} else sourceAngle -= degreesToRotate;
	
	// Finally, normalize and return the new angle.
	return NormalizeAngle(sourceAngle);

}


// Returns the smallest sweep between two angles.
real GetDeltaBetweenAngles(real angleOne, real angleTwo) {

	real deltaBetweenAngles;
	
	// Find the difference between the two angles.
	deltaBetweenAngles = absr(angleTwo - angleOne);
	// If the delta is greater than 180 degrees, calculate the 
	// smaller angle by subtracting the delta from 360 degrees.
	if (deltaBetweenAngles > REAL(128))
		deltaBetweenAngles = REAL(256) - deltaBetweenAngles;
	// Finally, return the delta.
	return deltaBetweenAngles;

}


static void updateVector(vector *theVector);


// VECTORS!!  Vectors are used in Zap to move stuff around and to bounce stuff off of each other.
// So, we built routines like MovePointUsingVector, AccelerateVector and CollideVectors.  These
// routines rely upon some slightly lower level routines which break the vector up into its x and y
// components and deal with the ugliness of radians so that we can keep everything in the game in
// happy friendly degrees.  Vectors are cool, but they can be slooow since these lower level routines
// need to make some math toolbox calls like sin, cos, and arcsin.  The trick, then, is to call those
// math functions only when absolutely necessary.  For example, when we want to speed up an alien and move
// it in a certain direction, we call AccelerateVector then MovePointUsingVector.  Both routines need
// to know the vector's X/Y components, which requires sin/cos computations.  But computing them in each
// routine is a waste of time.  And that, kiddies, is why we ended up with a vector struct that's more than
// just the standard magnitude and direction. Our's includes sin and cos too, and uses a lastDirection field to
// know when the vector needs to be updated!  We begin every vector's life then with a single call to InitVector:


void InitVector(vector *theVector) {

	theVector->magnitude = REAL(0);
	theVector->direction = REAL(0);
	theVector->lastDirection = REAL(1);  // force update
	updateVector(theVector);

}


// Then, every time we use that vector, we check lastDirection to see if it's heading in a new direction.
// If so, we call updateVector which sorts out the vector's heading in radians, calculates its sin and cos,
// and finally stores its current direction in lastDirection.

static void updateVector(vector *theVector) {

	real degrees;

	if (theVector->lastDirection == theVector->direction)
		return;

	degrees = theVector->lastDirection = theVector->direction = NormalizeAngle(theVector->direction);
	theVector->cos = cosr(degrees);
	theVector->sin = sinr(degrees);

}


// Now, when we call a basic vector routine like MovePointUsingVector
// which in turn calls GetX/YComponentOfVector, we make use of all the info
// that was precalculated in updateVector (and only recalculating that
// stuff if the angle has changed).

void MovePointUsingVector(realpoint *sourcePoint, vector *theVector) {

	updateVector(theVector);
	
	// Adjust the source point by the vector's x and y components.	
	sourcePoint->x += GetXComponentOfVector(theVector);
	sourcePoint->y += GetYComponentOfVector(theVector);

}


real GetXComponentOfVector(vector *theVector) {

	updateVector(theVector);
	return mulr(theVector->cos, theVector->magnitude);

}


real GetYComponentOfVector(vector *theVector) {

	updateVector(theVector);
	return mulr(theVector->sin, theVector->magnitude);

}


void AccelerateVector(vector *theVector, vector *theAcceleration, real maxMagnitude) {

	AddVectors(theVector, theAcceleration);
	if (theVector->magnitude > maxMagnitude)
		theVector->magnitude = maxMagnitude;

}


real AccelerateQuantity(real theQuantity, real theAcceleration, real maxQuantity) {

	theQuantity += theAcceleration;
	if (theQuantity > maxQuantity)
		theQuantity = maxQuantity;

	return theQuantity;

}


void AddVectors(vector *resultVector, vector *theVector) {

	realpoint resultPoint;
	
	updateVector(resultVector);
	updateVector(theVector);
	
	// Break the two input vectors up into their x and y components,	
	// then add them up to get the x and y components of our new vector.
	resultPoint.x = GetXComponentOfVector(resultVector) + GetXComponentOfVector(theVector);
	resultPoint.y = GetYComponentOfVector(resultVector) + GetYComponentOfVector(theVector);
	
	CreateVectorFromPoint(resultVector, &resultPoint);

}


void CreateVectorFromPoint(vector *resultVector, realpoint *point) {

	realpoint pointZero;
	realpoint pt;

	pointZero.x = REAL(0);
	pointZero.y = REAL(0);
	pt = *point;
	
	// Express the new vector as two points in space,
	// from which we can then extract the vector's magnitude and direction.
	resultVector->magnitude = GetDistanceBetweenPoints(&pointZero, &pt);
	if (resultVector->magnitude < REAL(100)) {
		pt.x = mulr(pt.x, REAL(10));
		pt.y = mulr(pt.y, REAL(10));
	}
	resultVector->direction = GetAngleBetweenPoints(&pointZero, &pt);
	updateVector(resultVector);

}


// Elastically collide two spherical objects of equal mass.
// Uses some fancy math to calculate the parallel and perpendicular
// componenents of the two object's vectors, then swaps the perpendicular
// components.  Tickle me elmo. 

void CreateVectorFromPoint2(real x, real y, vector *vec) {

	realpoint pt;

	pt.x = x;
	pt.y = y;
	CreateVectorFromPoint(vec, &pt);

}


void CollideVectors(vector *v1, vector *v2) {

	real v1h, v1v, v2h, v2v;
	vector v1par, v1perp, v2par, v2perp;
	real v1parH, v1parV, v1perpH, v1perpV, v2parH, v2parV, v2perpH, v2perpV;
	real v1squaredLength, v2squaredLength, dotProduct;
	real epsilon;
	
	v1h = GetXComponentOfVector(v1);
	v1v = GetYComponentOfVector(v1);
	
	v2h = GetXComponentOfVector(v2);
	v2v = GetYComponentOfVector(v2);
	
	v1squaredLength = mulr(v1h, v1h) + mulr(v1v, v1v);
	v2squaredLength = mulr(v2h, v2h) + mulr(v2v, v2v);
	
	epsilon = REAL(0.1);
	if (v1squaredLength < epsilon) {
		real temp = v1->magnitude;
		*v1 = *v2;
		v2->magnitude = temp;
		return;
	} else if (v2squaredLength < epsilon) {
		real temp = v2->magnitude;
		*v2 = *v1;
		v1->magnitude = temp;
		return;
	}

	dotProduct = mulr(v1h, v2h) + mulr(v1v, v2v);
	
	v1parH = divr(mulr(v2h, dotProduct), v2squaredLength);
	v1parV = divr(mulr(v2v, dotProduct), v2squaredLength);
	CreateVectorFromPoint2(v1parH, v1parV, &v1par);
	v1perpH = v1h - v1parH;
	v1perpV = v1v - v1parV;
	CreateVectorFromPoint2(v1perpH, v1perpV, &v1perp);
	
	v2parH = divr(mulr(v1h, dotProduct), v1squaredLength);
	v2parV = divr(mulr(v1v, dotProduct), v1squaredLength);
	CreateVectorFromPoint2(v2parH, v2parV, &v2par);
	v2perpH = v2h - v2parH;
	v2perpV = v2v - v2parV;
	CreateVectorFromPoint2(v2perpH, v2perpV, &v2perp);
	
	AddVectors(&v1par, &v2perp);
	AddVectors(&v2par, &v1perp);
	*v1 = v1par;
	*v2 = v2par;

}


const static short cosine_table[] = {
	1024, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023,
	1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1022, 1022, 1022,
	1022, 1022, 1022, 1022, 1022, 1022, 1022, 1022, 1022, 1021, 1021, 1021, 1021, 1021, 1021, 1021,
	1021, 1021, 1020, 1020, 1020, 1020, 1020, 1020, 1020, 1020, 1019, 1019, 1019, 1019, 1019, 1019,
	1019, 1018, 1018, 1018, 1018, 1018, 1018, 1017, 1017, 1017, 1017, 1017, 1017, 1016, 1016, 1016,
	1016, 1016, 1015, 1015, 1015, 1015, 1015, 1014, 1014, 1014, 1014, 1014, 1013, 1013, 1013, 1013,
	1012, 1012, 1012, 1012, 1011, 1011, 1011, 1011, 1010, 1010, 1010, 1010, 1009, 1009, 1009, 1009,
	1008, 1008, 1008, 1008, 1007, 1007, 1007, 1006, 1006, 1006, 1006, 1005, 1005, 1005, 1004, 1004,
	1004, 1004, 1003, 1003, 1003, 1002, 1002, 1002, 1001, 1001, 1001, 1000, 1000, 1000, 999, 999,
	999, 998, 998, 998, 997, 997, 997, 996, 996, 995, 995, 995, 994, 994, 994, 993,
	993, 992, 992, 992, 991, 991, 990, 990, 990, 989, 989, 988, 988, 988, 987, 987,
	986, 986, 986, 985, 985, 984, 984, 983, 983, 983, 982, 982, 981, 981, 980, 980,
	979, 979, 978, 978, 978, 977, 977, 976, 976, 975, 975, 974, 974, 973, 973, 972,
	972, 971, 971, 970, 970, 969, 969, 968, 968, 967, 967, 966, 966, 965, 965, 964,
	964, 963, 963, 962, 962, 961, 960, 960, 959, 959, 958, 958, 957, 957, 956, 955,
	955, 954, 954, 953, 953, 952, 951, 951, 950, 950, 949, 949, 948, 947, 947, 946,
	946, 945, 944, 944, 943, 943, 942, 941, 941, 940, 939, 939, 938, 938, 937, 936,
	936, 935, 934, 934, 933, 932, 932, 931, 930, 930, 929, 929, 928, 927, 927, 926,
	925, 925, 924, 923, 922, 922, 921, 920, 920, 919, 918, 918, 917, 916, 916, 915,
	914, 913, 913, 912, 911, 911, 910, 909, 908, 908, 907, 906, 906, 905, 904, 903,
	903, 902, 901, 900, 900, 899, 898, 897, 897, 896, 895, 894, 894, 893, 892, 891,
	890, 890, 889, 888, 887, 887, 886, 885, 884, 883, 883, 882, 881, 880, 879, 879,
	878, 877, 876, 875, 875, 874, 873, 872, 871, 870, 870, 869, 868, 867, 866, 865,
	865, 864, 863, 862, 861, 860, 860, 859, 858, 857, 856, 855, 854, 854, 853, 852,
	851, 850, 849, 848, 847, 847, 846, 845, 844, 843, 842, 841, 840, 839, 839, 838,
	837, 836, 835, 834, 833, 832, 831, 830, 829, 828, 828, 827, 826, 825, 824, 823,
	822, 821, 820, 819, 818, 817, 816, 815, 814, 813, 813, 812, 811, 810, 809, 808,
	807, 806, 805, 804, 803, 802, 801, 800, 799, 798, 797, 796, 795, 794, 793, 792,
	791, 790, 789, 788, 787, 786, 785, 784, 783, 782, 781, 780, 779, 778, 777, 776,
	775, 774, 773, 772, 771, 770, 769, 768, 767, 766, 765, 763, 762, 761, 760, 759,
	758, 757, 756, 755, 754, 753, 752, 751, 750, 749, 748, 747, 745, 744, 743, 742,
	741, 740, 739, 738, 737, 736, 735, 734, 732, 731, 730, 729, 728, 727, 726, 725,
	724, 722, 721, 720, 719, 718, 717, 716, 715, 714, 712, 711, 710, 709, 708, 707,
	706, 704, 703, 702, 701, 700, 699, 698, 696, 695, 694, 693, 692, 691, 690, 688,
	687, 686, 685, 684, 683, 681, 680, 679, 678, 677, 675, 674, 673, 672, 671, 670,
	668, 667, 666, 665, 664, 662, 661, 660, 659, 658, 656, 655, 654, 653, 652, 650,
	649, 648, 647, 645, 644, 643, 642, 641, 639, 638, 637, 636, 634, 633, 632, 631,
	629, 628, 627, 626, 625, 623, 622, 621, 620, 618, 617, 616, 615, 613, 612, 611,
	609, 608, 607, 606, 604, 603, 602, 601, 599, 598, 597, 596, 594, 593, 592, 590,
	589, 588, 587, 585, 584, 583, 581, 580, 579, 578, 576, 575, 574, 572, 571, 570,
	568, 567, 566, 564, 563, 562, 561, 559, 558, 557, 555, 554, 553, 551, 550, 549,
	547, 546, 545, 543, 542, 541, 539, 538, 537, 535, 534, 533, 531, 530, 529, 527,
	526, 525, 523, 522, 521, 519, 518, 516, 515, 514, 512, 511, 510, 508, 507, 506,
	504, 503, 501, 500, 499, 497, 496, 495, 493, 492, 491, 489, 488, 486, 485, 484,
	482, 481, 479, 478, 477, 475, 474, 472, 471, 470, 468, 467, 466, 464, 463, 461,
	460, 458, 457, 456, 454, 453, 451, 450, 449, 447, 446, 444, 443, 442, 440, 439,
	437, 436, 434, 433, 432, 430, 429, 427, 426, 424, 423, 422, 420, 419, 417, 416,
	414, 413, 412, 410, 409, 407, 406, 404, 403, 402, 400, 399, 397, 396, 394, 393,
	391, 390, 388, 387, 386, 384, 383, 381, 380, 378, 377, 375, 374, 372, 371, 369,
	368, 367, 365, 364, 362, 361, 359, 358, 356, 355, 353, 352, 350, 349, 347, 346,
	344, 343, 342, 340, 339, 337, 336, 334, 333, 331, 330, 328, 327, 325, 324, 322,
	321, 319, 318, 316, 315, 313, 312, 310, 309, 307, 306, 304, 303, 301, 300, 298,
	297, 295, 294, 292, 291, 289, 288, 286, 285, 283, 282, 280, 279, 277, 276, 274,
	273, 271, 270, 268, 267, 265, 264, 262, 260, 259, 257, 256, 254, 253, 251, 250,
	248, 247, 245, 244, 242, 241, 239, 238, 236, 235, 233, 232, 230, 228, 227, 225,
	224, 222, 221, 219, 218, 216, 215, 213, 212, 210, 209, 207, 205, 204, 202, 201,
	199, 198, 196, 195, 193, 192, 190, 188, 187, 185, 184, 182, 181, 179, 178, 176,
	175, 173, 171, 170, 168, 167, 165, 164, 162, 161, 159, 158, 156, 154, 153, 151,
	150, 148, 147, 145, 144, 142, 140, 139, 137, 136, 134, 133, 131, 130, 128, 126,
	125, 123, 122, 120, 119, 117, 115, 114, 112, 111, 109, 108, 106, 105, 103, 101,
	100, 98, 97, 95, 94, 92, 90, 89, 87, 86, 84, 83, 81, 80, 78, 76,
	75, 73, 72, 70, 69, 67, 65, 64, 62, 61, 59, 58, 56, 54, 53, 51,
	50, 48, 47, 45, 43, 42, 40, 39, 37, 36, 34, 32, 31, 29, 28, 26,
	25, 23, 21, 20, 18, 17, 15, 14, 12, 10, 9, 7, 6, 4, 3, 1,
	0, -1, -3, -4, -6, -7, -9, -10, -12, -14, -15, -17, -18, -20, -21, -23,
	-25, -26, -28, -29, -31, -32, -34, -36, -37, -39, -40, -42, -43, -45, -47, -48,
	-50, -51, -53, -54, -56, -58, -59, -61, -62, -64, -65, -67, -69, -70, -72, -73,
	-75, -76, -78, -80, -81, -83, -84, -86, -87, -89, -90, -92, -94, -95, -97, -98,
	-100, -101, -103, -105, -106, -108, -109, -111, -112, -114, -115, -117, -119, -120, -122, -123,
	-125, -126, -128, -130, -131, -133, -134, -136, -137, -139, -140, -142, -144, -145, -147, -148,
	-150, -151, -153, -154, -156, -158, -159, -161, -162, -164, -165, -167, -168, -170, -171, -173,
	-175, -176, -178, -179, -181, -182, -184, -185, -187, -188, -190, -192, -193, -195, -196, -198,
	-199, -201, -202, -204, -205, -207, -209, -210, -212, -213, -215, -216, -218, -219, -221, -222,
	-224, -225, -227, -228, -230, -232, -233, -235, -236, -238, -239, -241, -242, -244, -245, -247,
	-248, -250, -251, -253, -254, -256, -257, -259, -260, -262, -264, -265, -267, -268, -270, -271,
	-273, -274, -276, -277, -279, -280, -282, -283, -285, -286, -288, -289, -291, -292, -294, -295,
	-297, -298, -300, -301, -303, -304, -306, -307, -309, -310, -312, -313, -315, -316, -318, -319,
	-321, -322, -324, -325, -327, -328, -330, -331, -333, -334, -336, -337, -339, -340, -342, -343,
	-344, -346, -347, -349, -350, -352, -353, -355, -356, -358, -359, -361, -362, -364, -365, -367,
	-368, -369, -371, -372, -374, -375, -377, -378, -380, -381, -383, -384, -386, -387, -388, -390,
	-391, -393, -394, -396, -397, -399, -400, -402, -403, -404, -406, -407, -409, -410, -412, -413,
	-414, -416, -417, -419, -420, -422, -423, -424, -426, -427, -429, -430, -432, -433, -434, -436,
	-437, -439, -440, -442, -443, -444, -446, -447, -449, -450, -451, -453, -454, -456, -457, -458,
	-460, -461, -463, -464, -466, -467, -468, -470, -471, -472, -474, -475, -477, -478, -479, -481,
	-482, -484, -485, -486, -488, -489, -491, -492, -493, -495, -496, -497, -499, -500, -501, -503,
	-504, -506, -507, -508, -510, -511, -512, -514, -515, -516, -518, -519, -521, -522, -523, -525,
	-526, -527, -529, -530, -531, -533, -534, -535, -537, -538, -539, -541, -542, -543, -545, -546,
	-547, -549, -550, -551, -553, -554, -555, -557, -558, -559, -561, -562, -563, -564, -566, -567,
	-568, -570, -571, -572, -574, -575, -576, -578, -579, -580, -581, -583, -584, -585, -587, -588,
	-589, -590, -592, -593, -594, -596, -597, -598, -599, -601, -602, -603, -604, -606, -607, -608,
	-609, -611, -612, -613, -615, -616, -617, -618, -620, -621, -622, -623, -625, -626, -627, -628,
	-629, -631, -632, -633, -634, -636, -637, -638, -639, -641, -642, -643, -644, -645, -647, -648,
	-649, -650, -652, -653, -654, -655, -656, -658, -659, -660, -661, -662, -664, -665, -666, -667,
	-668, -670, -671, -672, -673, -674, -675, -677, -678, -679, -680, -681, -683, -684, -685, -686,
	-687, -688, -690, -691, -692, -693, -694, -695, -696, -698, -699, -700, -701, -702, -703, -704,
	-706, -707, -708, -709, -710, -711, -712, -714, -715, -716, -717, -718, -719, -720, -721, -722,
	-724, -725, -726, -727, -728, -729, -730, -731, -732, -734, -735, -736, -737, -738, -739, -740,
	-741, -742, -743, -744, -745, -747, -748, -749, -750, -751, -752, -753, -754, -755, -756, -757,
	-758, -759, -760, -761, -762, -763, -765, -766, -767, -768, -769, -770, -771, -772, -773, -774,
	-775, -776, -777, -778, -779, -780, -781, -782, -783, -784, -785, -786, -787, -788, -789, -790,
	-791, -792, -793, -794, -795, -796, -797, -798, -799, -800, -801, -802, -803, -804, -805, -806,
	-807, -808, -809, -810, -811, -812, -813, -813, -814, -815, -816, -817, -818, -819, -820, -821,
	-822, -823, -824, -825, -826, -827, -828, -828, -829, -830, -831, -832, -833, -834, -835, -836,
	-837, -838, -839, -839, -840, -841, -842, -843, -844, -845, -846, -847, -847, -848, -849, -850,
	-851, -852, -853, -854, -854, -855, -856, -857, -858, -859, -860, -860, -861, -862, -863, -864,
	-865, -865, -866, -867, -868, -869, -870, -870, -871, -872, -873, -874, -875, -875, -876, -877,
	-878, -879, -879, -880, -881, -882, -883, -883, -884, -885, -886, -887, -887, -888, -889, -890,
	-890, -891, -892, -893, -894, -894, -895, -896, -897, -897, -898, -899, -900, -900, -901, -902,
	-903, -903, -904, -905, -906, -906, -907, -908, -908, -909, -910, -911, -911, -912, -913, -913,
	-914, -915, -916, -916, -917, -918, -918, -919, -920, -920, -921, -922, -922, -923, -924, -925,
	-925, -926, -927, -927, -928, -929, -929, -930, -930, -931, -932, -932, -933, -934, -934, -935,
	-936, -936, -937, -938, -938, -939, -939, -940, -941, -941, -942, -943, -943, -944, -944, -945,
	-946, -946, -947, -947, -948, -949, -949, -950, -950, -951, -951, -952, -953, -953, -954, -954,
	-955, -955, -956, -957, -957, -958, -958, -959, -959, -960, -960, -961, -962, -962, -963, -963,
	-964, -964, -965, -965, -966, -966, -967, -967, -968, -968, -969, -969, -970, -970, -971, -971,
	-972, -972, -973, -973, -974, -974, -975, -975, -976, -976, -977, -977, -978, -978, -978, -979,
	-979, -980, -980, -981, -981, -982, -982, -983, -983, -983, -984, -984, -985, -985, -986, -986,
	-986, -987, -987, -988, -988, -988, -989, -989, -990, -990, -990, -991, -991, -992, -992, -992,
	-993, -993, -994, -994, -994, -995, -995, -995, -996, -996, -997, -997, -997, -998, -998, -998,
	-999, -999, -999, -1000, -1000, -1000, -1001, -1001, -1001, -1002, -1002, -1002, -1003, -1003, -1003, -1004,
	-1004, -1004, -1004, -1005, -1005, -1005, -1006, -1006, -1006, -1006, -1007, -1007, -1007, -1008, -1008, -1008,
	-1008, -1009, -1009, -1009, -1009, -1010, -1010, -1010, -1010, -1011, -1011, -1011, -1011, -1012, -1012, -1012,
	-1012, -1013, -1013, -1013, -1013, -1014, -1014, -1014, -1014, -1014, -1015, -1015, -1015, -1015, -1015, -1016,
	-1016, -1016, -1016, -1016, -1017, -1017, -1017, -1017, -1017, -1017, -1018, -1018, -1018, -1018, -1018, -1018,
	-1019, -1019, -1019, -1019, -1019, -1019, -1019, -1020, -1020, -1020, -1020, -1020, -1020, -1020, -1020, -1021,
	-1021, -1021, -1021, -1021, -1021, -1021, -1021, -1021, -1022, -1022, -1022, -1022, -1022, -1022, -1022, -1022,
	-1022, -1022, -1022, -1022, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023,
	-1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023,
	-1024, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023,
	-1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1023, -1022, -1022, -1022,
	-1022, -1022, -1022, -1022, -1022, -1022, -1022, -1022, -1022, -1021, -1021, -1021, -1021, -1021, -1021, -1021,
	-1021, -1021, -1020, -1020, -1020, -1020, -1020, -1020, -1020, -1020, -1019, -1019, -1019, -1019, -1019, -1019,
	-1019, -1018, -1018, -1018, -1018, -1018, -1018, -1017, -1017, -1017, -1017, -1017, -1017, -1016, -1016, -1016,
	-1016, -1016, -1015, -1015, -1015, -1015, -1015, -1014, -1014, -1014, -1014, -1014, -1013, -1013, -1013, -1013,
	-1012, -1012, -1012, -1012, -1011, -1011, -1011, -1011, -1010, -1010, -1010, -1010, -1009, -1009, -1009, -1009,
	-1008, -1008, -1008, -1008, -1007, -1007, -1007, -1006, -1006, -1006, -1006, -1005, -1005, -1005, -1004, -1004,
	-1004, -1004, -1003, -1003, -1003, -1002, -1002, -1002, -1001, -1001, -1001, -1000, -1000, -1000, -999, -999,
	-999, -998, -998, -998, -997, -997, -997, -996, -996, -995, -995, -995, -994, -994, -994, -993,
	-993, -992, -992, -992, -991, -991, -990, -990, -990, -989, -989, -988, -988, -988, -987, -987,
	-986, -986, -986, -985, -985, -984, -984, -983, -983, -983, -982, -982, -981, -981, -980, -980,
	-979, -979, -978, -978, -978, -977, -977, -976, -976, -975, -975, -974, -974, -973, -973, -972,
	-972, -971, -971, -970, -970, -969, -969, -968, -968, -967, -967, -966, -966, -965, -965, -964,
	-964, -963, -963, -962, -962, -961, -960, -960, -959, -959, -958, -958, -957, -957, -956, -955,
	-955, -954, -954, -953, -953, -952, -951, -951, -950, -950, -949, -949, -948, -947, -947, -946,
	-946, -945, -944, -944, -943, -943, -942, -941, -941, -940, -939, -939, -938, -938, -937, -936,
	-936, -935, -934, -934, -933, -932, -932, -931, -930, -930, -929, -929, -928, -927, -927, -926,
	-925, -925, -924, -923, -922, -922, -921, -920, -920, -919, -918, -918, -917, -916, -916, -915,
	-914, -913, -913, -912, -911, -911, -910, -909, -908, -908, -907, -906, -906, -905, -904, -903,
	-903, -902, -901, -900, -900, -899, -898, -897, -897, -896, -895, -894, -894, -893, -892, -891,
	-890, -890, -889, -888, -887, -887, -886, -885, -884, -883, -883, -882, -881, -880, -879, -879,
	-878, -877, -876, -875, -875, -874, -873, -872, -871, -870, -870, -869, -868, -867, -866, -865,
	-865, -864, -863, -862, -861, -860, -860, -859, -858, -857, -856, -855, -854, -854, -853, -852,
	-851, -850, -849, -848, -847, -847, -846, -845, -844, -843, -842, -841, -840, -839, -839, -838,
	-837, -836, -835, -834, -833, -832, -831, -830, -829, -828, -828, -827, -826, -825, -824, -823,
	-822, -821, -820, -819, -818, -817, -816, -815, -814, -813, -813, -812, -811, -810, -809, -808,
	-807, -806, -805, -804, -803, -802, -801, -800, -799, -798, -797, -796, -795, -794, -793, -792,
	-791, -790, -789, -788, -787, -786, -785, -784, -783, -782, -781, -780, -779, -778, -777, -776,
	-775, -774, -773, -772, -771, -770, -769, -768, -767, -766, -765, -763, -762, -761, -760, -759,
	-758, -757, -756, -755, -754, -753, -752, -751, -750, -749, -748, -747, -745, -744, -743, -742,
	-741, -740, -739, -738, -737, -736, -735, -734, -732, -731, -730, -729, -728, -727, -726, -725,
	-724, -722, -721, -720, -719, -718, -717, -716, -715, -714, -712, -711, -710, -709, -708, -707,
	-706, -704, -703, -702, -701, -700, -699, -698, -696, -695, -694, -693, -692, -691, -690, -688,
	-687, -686, -685, -684, -683, -681, -680, -679, -678, -677, -675, -674, -673, -672, -671, -670,
	-668, -667, -666, -665, -664, -662, -661, -660, -659, -658, -656, -655, -654, -653, -652, -650,
	-649, -648, -647, -645, -644, -643, -642, -641, -639, -638, -637, -636, -634, -633, -632, -631,
	-629, -628, -627, -626, -625, -623, -622, -621, -620, -618, -617, -616, -615, -613, -612, -611,
	-609, -608, -607, -606, -604, -603, -602, -601, -599, -598, -597, -596, -594, -593, -592, -590,
	-589, -588, -587, -585, -584, -583, -581, -580, -579, -578, -576, -575, -574, -572, -571, -570,
	-568, -567, -566, -564, -563, -562, -561, -559, -558, -557, -555, -554, -553, -551, -550, -549,
	-547, -546, -545, -543, -542, -541, -539, -538, -537, -535, -534, -533, -531, -530, -529, -527,
	-526, -525, -523, -522, -521, -519, -518, -516, -515, -514, -512, -511, -510, -508, -507, -506,
	-504, -503, -501, -500, -499, -497, -496, -495, -493, -492, -491, -489, -488, -486, -485, -484,
	-482, -481, -479, -478, -477, -475, -474, -472, -471, -470, -468, -467, -466, -464, -463, -461,
	-460, -458, -457, -456, -454, -453, -451, -450, -449, -447, -446, -444, -443, -442, -440, -439,
	-437, -436, -434, -433, -432, -430, -429, -427, -426, -424, -423, -422, -420, -419, -417, -416,
	-414, -413, -412, -410, -409, -407, -406, -404, -403, -402, -400, -399, -397, -396, -394, -393,
	-391, -390, -388, -387, -386, -384, -383, -381, -380, -378, -377, -375, -374, -372, -371, -369,
	-368, -367, -365, -364, -362, -361, -359, -358, -356, -355, -353, -352, -350, -349, -347, -346,
	-344, -343, -342, -340, -339, -337, -336, -334, -333, -331, -330, -328, -327, -325, -324, -322,
	-321, -319, -318, -316, -315, -313, -312, -310, -309, -307, -306, -304, -303, -301, -300, -298,
	-297, -295, -294, -292, -291, -289, -288, -286, -285, -283, -282, -280, -279, -277, -276, -274,
	-273, -271, -270, -268, -267, -265, -264, -262, -260, -259, -257, -256, -254, -253, -251, -250,
	-248, -247, -245, -244, -242, -241, -239, -238, -236, -235, -233, -232, -230, -228, -227, -225,
	-224, -222, -221, -219, -218, -216, -215, -213, -212, -210, -209, -207, -205, -204, -202, -201,
	-199, -198, -196, -195, -193, -192, -190, -188, -187, -185, -184, -182, -181, -179, -178, -176,
	-175, -173, -171, -170, -168, -167, -165, -164, -162, -161, -159, -158, -156, -154, -153, -151,
	-150, -148, -147, -145, -144, -142, -140, -139, -137, -136, -134, -133, -131, -130, -128, -126,
	-125, -123, -122, -120, -119, -117, -115, -114, -112, -111, -109, -108, -106, -105, -103, -101,
	-100, -98, -97, -95, -94, -92, -90, -89, -87, -86, -84, -83, -81, -80, -78, -76,
	-75, -73, -72, -70, -69, -67, -65, -64, -62, -61, -59, -58, -56, -54, -53, -51,
	-50, -48, -47, -45, -43, -42, -40, -39, -37, -36, -34, -32, -31, -29, -28, -26,
	-25, -23, -21, -20, -18, -17, -15, -14, -12, -10, -9, -7, -6, -4, -3, -1,
	0, 1, 3, 4, 6, 7, 9, 10, 12, 14, 15, 17, 18, 20, 21, 23,
	25, 26, 28, 29, 31, 32, 34, 36, 37, 39, 40, 42, 43, 45, 47, 48,
	50, 51, 53, 54, 56, 58, 59, 61, 62, 64, 65, 67, 69, 70, 72, 73,
	75, 76, 78, 80, 81, 83, 84, 86, 87, 89, 90, 92, 94, 95, 97, 98,
	100, 101, 103, 105, 106, 108, 109, 111, 112, 114, 115, 117, 119, 120, 122, 123,
	125, 126, 128, 130, 131, 133, 134, 136, 137, 139, 140, 142, 144, 145, 147, 148,
	150, 151, 153, 154, 156, 158, 159, 161, 162, 164, 165, 167, 168, 170, 171, 173,
	175, 176, 178, 179, 181, 182, 184, 185, 187, 188, 190, 192, 193, 195, 196, 198,
	199, 201, 202, 204, 205, 207, 209, 210, 212, 213, 215, 216, 218, 219, 221, 222,
	224, 225, 227, 228, 230, 232, 233, 235, 236, 238, 239, 241, 242, 244, 245, 247,
	248, 250, 251, 253, 254, 256, 257, 259, 260, 262, 264, 265, 267, 268, 270, 271,
	273, 274, 276, 277, 279, 280, 282, 283, 285, 286, 288, 289, 291, 292, 294, 295,
	297, 298, 300, 301, 303, 304, 306, 307, 309, 310, 312, 313, 315, 316, 318, 319,
	321, 322, 324, 325, 327, 328, 330, 331, 333, 334, 336, 337, 339, 340, 342, 343,
	344, 346, 347, 349, 350, 352, 353, 355, 356, 358, 359, 361, 362, 364, 365, 367,
	368, 369, 371, 372, 374, 375, 377, 378, 380, 381, 383, 384, 386, 387, 388, 390,
	391, 393, 394, 396, 397, 399, 400, 402, 403, 404, 406, 407, 409, 410, 412, 413,
	414, 416, 417, 419, 420, 422, 423, 424, 426, 427, 429, 430, 432, 433, 434, 436,
	437, 439, 440, 442, 443, 444, 446, 447, 449, 450, 451, 453, 454, 456, 457, 458,
	460, 461, 463, 464, 466, 467, 468, 470, 471, 472, 474, 475, 477, 478, 479, 481,
	482, 484, 485, 486, 488, 489, 491, 492, 493, 495, 496, 497, 499, 500, 501, 503,
	504, 506, 507, 508, 510, 511, 512, 514, 515, 516, 518, 519, 521, 522, 523, 525,
	526, 527, 529, 530, 531, 533, 534, 535, 537, 538, 539, 541, 542, 543, 545, 546,
	547, 549, 550, 551, 553, 554, 555, 557, 558, 559, 561, 562, 563, 564, 566, 567,
	568, 570, 571, 572, 574, 575, 576, 578, 579, 580, 581, 583, 584, 585, 587, 588,
	589, 590, 592, 593, 594, 596, 597, 598, 599, 601, 602, 603, 604, 606, 607, 608,
	609, 611, 612, 613, 615, 616, 617, 618, 620, 621, 622, 623, 625, 626, 627, 628,
	629, 631, 632, 633, 634, 636, 637, 638, 639, 641, 642, 643, 644, 645, 647, 648,
	649, 650, 652, 653, 654, 655, 656, 658, 659, 660, 661, 662, 664, 665, 666, 667,
	668, 670, 671, 672, 673, 674, 675, 677, 678, 679, 680, 681, 683, 684, 685, 686,
	687, 688, 690, 691, 692, 693, 694, 695, 696, 698, 699, 700, 701, 702, 703, 704,
	706, 707, 708, 709, 710, 711, 712, 714, 715, 716, 717, 718, 719, 720, 721, 722,
	724, 725, 726, 727, 728, 729, 730, 731, 732, 734, 735, 736, 737, 738, 739, 740,
	741, 742, 743, 744, 745, 747, 748, 749, 750, 751, 752, 753, 754, 755, 756, 757,
	758, 759, 760, 761, 762, 763, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774,
	775, 776, 777, 778, 779, 780, 781, 782, 783, 784, 785, 786, 787, 788, 789, 790,
	791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 804, 805, 806,
	807, 808, 809, 810, 811, 812, 813, 813, 814, 815, 816, 817, 818, 819, 820, 821,
	822, 823, 824, 825, 826, 827, 828, 828, 829, 830, 831, 832, 833, 834, 835, 836,
	837, 838, 839, 839, 840, 841, 842, 843, 844, 845, 846, 847, 847, 848, 849, 850,
	851, 852, 853, 854, 854, 855, 856, 857, 858, 859, 860, 860, 861, 862, 863, 864,
	865, 865, 866, 867, 868, 869, 870, 870, 871, 872, 873, 874, 875, 875, 876, 877,
	878, 879, 879, 880, 881, 882, 883, 883, 884, 885, 886, 887, 887, 888, 889, 890,
	890, 891, 892, 893, 894, 894, 895, 896, 897, 897, 898, 899, 900, 900, 901, 902,
	903, 903, 904, 905, 906, 906, 907, 908, 908, 909, 910, 911, 911, 912, 913, 913,
	914, 915, 916, 916, 917, 918, 918, 919, 920, 920, 921, 922, 922, 923, 924, 925,
	925, 926, 927, 927, 928, 929, 929, 930, 930, 931, 932, 932, 933, 934, 934, 935,
	936, 936, 937, 938, 938, 939, 939, 940, 941, 941, 942, 943, 943, 944, 944, 945,
	946, 946, 947, 947, 948, 949, 949, 950, 950, 951, 951, 952, 953, 953, 954, 954,
	955, 955, 956, 957, 957, 958, 958, 959, 959, 960, 960, 961, 962, 962, 963, 963,
	964, 964, 965, 965, 966, 966, 967, 967, 968, 968, 969, 969, 970, 970, 971, 971,
	972, 972, 973, 973, 974, 974, 975, 975, 976, 976, 977, 977, 978, 978, 978, 979,
	979, 980, 980, 981, 981, 982, 982, 983, 983, 983, 984, 984, 985, 985, 986, 986,
	986, 987, 987, 988, 988, 988, 989, 989, 990, 990, 990, 991, 991, 992, 992, 992,
	993, 993, 994, 994, 994, 995, 995, 995, 996, 996, 997, 997, 997, 998, 998, 998,
	999, 999, 999, 1000, 1000, 1000, 1001, 1001, 1001, 1002, 1002, 1002, 1003, 1003, 1003, 1004,
	1004, 1004, 1004, 1005, 1005, 1005, 1006, 1006, 1006, 1006, 1007, 1007, 1007, 1008, 1008, 1008,
	1008, 1009, 1009, 1009, 1009, 1010, 1010, 1010, 1010, 1011, 1011, 1011, 1011, 1012, 1012, 1012,
	1012, 1013, 1013, 1013, 1013, 1014, 1014, 1014, 1014, 1014, 1015, 1015, 1015, 1015, 1015, 1016,
	1016, 1016, 1016, 1016, 1017, 1017, 1017, 1017, 1017, 1017, 1018, 1018, 1018, 1018, 1018, 1018,
	1019, 1019, 1019, 1019, 1019, 1019, 1019, 1020, 1020, 1020, 1020, 1020, 1020, 1020, 1020, 1021,
	1021, 1021, 1021, 1021, 1021, 1021, 1021, 1021, 1022, 1022, 1022, 1022, 1022, 1022, 1022, 1022,
	1022, 1022, 1022, 1022, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023,
	1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023, 1023,
};