1 /** @file mathutil.c Math utilities.
2  *
3  * @authors Copyright © 2003-2017 Jaakko Keränen <jaakko.keranen@iki.fi>
4  * @authors Copyright © 2006-2013 Daniel Swanson <danij@dengine.net>
5  *
6  * @par License
7  * GPL: http://www.gnu.org/licenses/gpl.html
8  *
9  * <small>This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by the
11  * Free Software Foundation; either version 2 of the License, or (at your
12  * option) any later version. This program is distributed in the hope that it
13  * will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
15  * Public License for more details. You should have received a copy of the GNU
16  * General Public License along with this program; if not, see:
17  * http://www.gnu.org/licenses</small>
18  */
19 
20 #include "de/mathutil.h"
21 #include "de/vector1.h"
22 #include <math.h>
23 
24 static int finesine[10240] =
25 {
26     25,75,125,175,226,276,326,376,
27     427,477,527,578,628,678,728,779,
28     829,879,929,980,1030,1080,1130,1181,
29     1231,1281,1331,1382,1432,1482,1532,1583,
30     1633,1683,1733,1784,1834,1884,1934,1985,
31     2035,2085,2135,2186,2236,2286,2336,2387,
32     2437,2487,2537,2587,2638,2688,2738,2788,
33     2839,2889,2939,2989,3039,3090,3140,3190,
34     3240,3291,3341,3391,3441,3491,3541,3592,
35     3642,3692,3742,3792,3843,3893,3943,3993,
36     4043,4093,4144,4194,4244,4294,4344,4394,
37     4445,4495,4545,4595,4645,4695,4745,4796,
38     4846,4896,4946,4996,5046,5096,5146,5197,
39     5247,5297,5347,5397,5447,5497,5547,5597,
40     5647,5697,5748,5798,5848,5898,5948,5998,
41     6048,6098,6148,6198,6248,6298,6348,6398,
42     6448,6498,6548,6598,6648,6698,6748,6798,
43     6848,6898,6948,6998,7048,7098,7148,7198,
44     7248,7298,7348,7398,7448,7498,7548,7598,
45     7648,7697,7747,7797,7847,7897,7947,7997,
46     8047,8097,8147,8196,8246,8296,8346,8396,
47     8446,8496,8545,8595,8645,8695,8745,8794,
48     8844,8894,8944,8994,9043,9093,9143,9193,
49     9243,9292,9342,9392,9442,9491,9541,9591,
50     9640,9690,9740,9790,9839,9889,9939,9988,
51     10038,10088,10137,10187,10237,10286,10336,10386,
52     10435,10485,10534,10584,10634,10683,10733,10782,
53     10832,10882,10931,10981,11030,11080,11129,11179,
54     11228,11278,11327,11377,11426,11476,11525,11575,
55     11624,11674,11723,11773,11822,11872,11921,11970,
56     12020,12069,12119,12168,12218,12267,12316,12366,
57     12415,12464,12514,12563,12612,12662,12711,12760,
58     12810,12859,12908,12957,13007,13056,13105,13154,
59     13204,13253,13302,13351,13401,13450,13499,13548,
60     13597,13647,13696,13745,13794,13843,13892,13941,
61     13990,14040,14089,14138,14187,14236,14285,14334,
62     14383,14432,14481,14530,14579,14628,14677,14726,
63     14775,14824,14873,14922,14971,15020,15069,15118,
64     15167,15215,15264,15313,15362,15411,15460,15509,
65     15557,15606,15655,15704,15753,15802,15850,15899,
66     15948,15997,16045,16094,16143,16191,16240,16289,
67     16338,16386,16435,16484,16532,16581,16629,16678,
68     16727,16775,16824,16872,16921,16970,17018,17067,
69     17115,17164,17212,17261,17309,17358,17406,17455,
70     17503,17551,17600,17648,17697,17745,17793,17842,
71     17890,17939,17987,18035,18084,18132,18180,18228,
72     18277,18325,18373,18421,18470,18518,18566,18614,
73     18663,18711,18759,18807,18855,18903,18951,19000,
74     19048,19096,19144,19192,19240,19288,19336,19384,
75     19432,19480,19528,19576,19624,19672,19720,19768,
76     19816,19864,19912,19959,20007,20055,20103,20151,
77     20199,20246,20294,20342,20390,20438,20485,20533,
78     20581,20629,20676,20724,20772,20819,20867,20915,
79     20962,21010,21057,21105,21153,21200,21248,21295,
80     21343,21390,21438,21485,21533,21580,21628,21675,
81     21723,21770,21817,21865,21912,21960,22007,22054,
82     22102,22149,22196,22243,22291,22338,22385,22433,
83     22480,22527,22574,22621,22668,22716,22763,22810,
84     22857,22904,22951,22998,23045,23092,23139,23186,
85     23233,23280,23327,23374,23421,23468,23515,23562,
86     23609,23656,23703,23750,23796,23843,23890,23937,
87     23984,24030,24077,24124,24171,24217,24264,24311,
88     24357,24404,24451,24497,24544,24591,24637,24684,
89     24730,24777,24823,24870,24916,24963,25009,25056,
90     25102,25149,25195,25241,25288,25334,25381,25427,
91     25473,25520,25566,25612,25658,25705,25751,25797,
92     25843,25889,25936,25982,26028,26074,26120,26166,
93     26212,26258,26304,26350,26396,26442,26488,26534,
94     26580,26626,26672,26718,26764,26810,26856,26902,
95     26947,26993,27039,27085,27131,27176,27222,27268,
96     27313,27359,27405,27450,27496,27542,27587,27633,
97     27678,27724,27770,27815,27861,27906,27952,27997,
98     28042,28088,28133,28179,28224,28269,28315,28360,
99     28405,28451,28496,28541,28586,28632,28677,28722,
100     28767,28812,28858,28903,28948,28993,29038,29083,
101     29128,29173,29218,29263,29308,29353,29398,29443,
102     29488,29533,29577,29622,29667,29712,29757,29801,
103     29846,29891,29936,29980,30025,30070,30114,30159,
104     30204,30248,30293,30337,30382,30426,30471,30515,
105     30560,30604,30649,30693,30738,30782,30826,30871,
106     30915,30959,31004,31048,31092,31136,31181,31225,
107     31269,31313,31357,31402,31446,31490,31534,31578,
108     31622,31666,31710,31754,31798,31842,31886,31930,
109     31974,32017,32061,32105,32149,32193,32236,32280,
110     32324,32368,32411,32455,32499,32542,32586,32630,
111     32673,32717,32760,32804,32847,32891,32934,32978,
112     33021,33065,33108,33151,33195,33238,33281,33325,
113     33368,33411,33454,33498,33541,33584,33627,33670,
114     33713,33756,33799,33843,33886,33929,33972,34015,
115     34057,34100,34143,34186,34229,34272,34315,34358,
116     34400,34443,34486,34529,34571,34614,34657,34699,
117     34742,34785,34827,34870,34912,34955,34997,35040,
118     35082,35125,35167,35210,35252,35294,35337,35379,
119     35421,35464,35506,35548,35590,35633,35675,35717,
120     35759,35801,35843,35885,35927,35969,36011,36053,
121     36095,36137,36179,36221,36263,36305,36347,36388,
122     36430,36472,36514,36555,36597,36639,36681,36722,
123     36764,36805,36847,36889,36930,36972,37013,37055,
124     37096,37137,37179,37220,37262,37303,37344,37386,
125     37427,37468,37509,37551,37592,37633,37674,37715,
126     37756,37797,37838,37879,37920,37961,38002,38043,
127     38084,38125,38166,38207,38248,38288,38329,38370,
128     38411,38451,38492,38533,38573,38614,38655,38695,
129     38736,38776,38817,38857,38898,38938,38979,39019,
130     39059,39100,39140,39180,39221,39261,39301,39341,
131     39382,39422,39462,39502,39542,39582,39622,39662,
132     39702,39742,39782,39822,39862,39902,39942,39982,
133     40021,40061,40101,40141,40180,40220,40260,40300,
134     40339,40379,40418,40458,40497,40537,40576,40616,
135     40655,40695,40734,40773,40813,40852,40891,40931,
136     40970,41009,41048,41087,41127,41166,41205,41244,
137     41283,41322,41361,41400,41439,41478,41517,41556,
138     41595,41633,41672,41711,41750,41788,41827,41866,
139     41904,41943,41982,42020,42059,42097,42136,42174,
140     42213,42251,42290,42328,42366,42405,42443,42481,
141     42520,42558,42596,42634,42672,42711,42749,42787,
142     42825,42863,42901,42939,42977,43015,43053,43091,
143     43128,43166,43204,43242,43280,43317,43355,43393,
144     43430,43468,43506,43543,43581,43618,43656,43693,
145     43731,43768,43806,43843,43880,43918,43955,43992,
146     44029,44067,44104,44141,44178,44215,44252,44289,
147     44326,44363,44400,44437,44474,44511,44548,44585,
148     44622,44659,44695,44732,44769,44806,44842,44879,
149     44915,44952,44989,45025,45062,45098,45135,45171,
150     45207,45244,45280,45316,45353,45389,45425,45462,
151     45498,45534,45570,45606,45642,45678,45714,45750,
152     45786,45822,45858,45894,45930,45966,46002,46037,
153     46073,46109,46145,46180,46216,46252,46287,46323,
154     46358,46394,46429,46465,46500,46536,46571,46606,
155     46642,46677,46712,46747,46783,46818,46853,46888,
156     46923,46958,46993,47028,47063,47098,47133,47168,
157     47203,47238,47273,47308,47342,47377,47412,47446,
158     47481,47516,47550,47585,47619,47654,47688,47723,
159     47757,47792,47826,47860,47895,47929,47963,47998,
160     48032,48066,48100,48134,48168,48202,48237,48271,
161     48305,48338,48372,48406,48440,48474,48508,48542,
162     48575,48609,48643,48676,48710,48744,48777,48811,
163     48844,48878,48911,48945,48978,49012,49045,49078,
164     49112,49145,49178,49211,49244,49278,49311,49344,
165     49377,49410,49443,49476,49509,49542,49575,49608,
166     49640,49673,49706,49739,49771,49804,49837,49869,
167     49902,49935,49967,50000,50032,50065,50097,50129,
168     50162,50194,50226,50259,50291,50323,50355,50387,
169     50420,50452,50484,50516,50548,50580,50612,50644,
170     50675,50707,50739,50771,50803,50834,50866,50898,
171     50929,50961,50993,51024,51056,51087,51119,51150,
172     51182,51213,51244,51276,51307,51338,51369,51401,
173     51432,51463,51494,51525,51556,51587,51618,51649,
174     51680,51711,51742,51773,51803,51834,51865,51896,
175     51926,51957,51988,52018,52049,52079,52110,52140,
176     52171,52201,52231,52262,52292,52322,52353,52383,
177     52413,52443,52473,52503,52534,52564,52594,52624,
178     52653,52683,52713,52743,52773,52803,52832,52862,
179     52892,52922,52951,52981,53010,53040,53069,53099,
180     53128,53158,53187,53216,53246,53275,53304,53334,
181     53363,53392,53421,53450,53479,53508,53537,53566,
182     53595,53624,53653,53682,53711,53739,53768,53797,
183     53826,53854,53883,53911,53940,53969,53997,54026,
184     54054,54082,54111,54139,54167,54196,54224,54252,
185     54280,54308,54337,54365,54393,54421,54449,54477,
186     54505,54533,54560,54588,54616,54644,54672,54699,
187     54727,54755,54782,54810,54837,54865,54892,54920,
188     54947,54974,55002,55029,55056,55084,55111,55138,
189     55165,55192,55219,55246,55274,55300,55327,55354,
190     55381,55408,55435,55462,55489,55515,55542,55569,
191     55595,55622,55648,55675,55701,55728,55754,55781,
192     55807,55833,55860,55886,55912,55938,55965,55991,
193     56017,56043,56069,56095,56121,56147,56173,56199,
194     56225,56250,56276,56302,56328,56353,56379,56404,
195     56430,56456,56481,56507,56532,56557,56583,56608,
196     56633,56659,56684,56709,56734,56760,56785,56810,
197     56835,56860,56885,56910,56935,56959,56984,57009,
198     57034,57059,57083,57108,57133,57157,57182,57206,
199     57231,57255,57280,57304,57329,57353,57377,57402,
200     57426,57450,57474,57498,57522,57546,57570,57594,
201     57618,57642,57666,57690,57714,57738,57762,57785,
202     57809,57833,57856,57880,57903,57927,57950,57974,
203     57997,58021,58044,58067,58091,58114,58137,58160,
204     58183,58207,58230,58253,58276,58299,58322,58345,
205     58367,58390,58413,58436,58459,58481,58504,58527,
206     58549,58572,58594,58617,58639,58662,58684,58706,
207     58729,58751,58773,58795,58818,58840,58862,58884,
208     58906,58928,58950,58972,58994,59016,59038,59059,
209     59081,59103,59125,59146,59168,59190,59211,59233,
210     59254,59276,59297,59318,59340,59361,59382,59404,
211     59425,59446,59467,59488,59509,59530,59551,59572,
212     59593,59614,59635,59656,59677,59697,59718,59739,
213     59759,59780,59801,59821,59842,59862,59883,59903,
214     59923,59944,59964,59984,60004,60025,60045,60065,
215     60085,60105,60125,60145,60165,60185,60205,60225,
216     60244,60264,60284,60304,60323,60343,60363,60382,
217     60402,60421,60441,60460,60479,60499,60518,60537,
218     60556,60576,60595,60614,60633,60652,60671,60690,
219     60709,60728,60747,60766,60785,60803,60822,60841,
220     60859,60878,60897,60915,60934,60952,60971,60989,
221     61007,61026,61044,61062,61081,61099,61117,61135,
222     61153,61171,61189,61207,61225,61243,61261,61279,
223     61297,61314,61332,61350,61367,61385,61403,61420,
224     61438,61455,61473,61490,61507,61525,61542,61559,
225     61577,61594,61611,61628,61645,61662,61679,61696,
226     61713,61730,61747,61764,61780,61797,61814,61831,
227     61847,61864,61880,61897,61913,61930,61946,61963,
228     61979,61995,62012,62028,62044,62060,62076,62092,
229     62108,62125,62141,62156,62172,62188,62204,62220,
230     62236,62251,62267,62283,62298,62314,62329,62345,
231     62360,62376,62391,62407,62422,62437,62453,62468,
232     62483,62498,62513,62528,62543,62558,62573,62588,
233     62603,62618,62633,62648,62662,62677,62692,62706,
234     62721,62735,62750,62764,62779,62793,62808,62822,
235     62836,62850,62865,62879,62893,62907,62921,62935,
236     62949,62963,62977,62991,63005,63019,63032,63046,
237     63060,63074,63087,63101,63114,63128,63141,63155,
238     63168,63182,63195,63208,63221,63235,63248,63261,
239     63274,63287,63300,63313,63326,63339,63352,63365,
240     63378,63390,63403,63416,63429,63441,63454,63466,
241     63479,63491,63504,63516,63528,63541,63553,63565,
242     63578,63590,63602,63614,63626,63638,63650,63662,
243     63674,63686,63698,63709,63721,63733,63745,63756,
244     63768,63779,63791,63803,63814,63825,63837,63848,
245     63859,63871,63882,63893,63904,63915,63927,63938,
246     63949,63960,63971,63981,63992,64003,64014,64025,
247     64035,64046,64057,64067,64078,64088,64099,64109,
248     64120,64130,64140,64151,64161,64171,64181,64192,
249     64202,64212,64222,64232,64242,64252,64261,64271,
250     64281,64291,64301,64310,64320,64330,64339,64349,
251     64358,64368,64377,64387,64396,64405,64414,64424,
252     64433,64442,64451,64460,64469,64478,64487,64496,
253     64505,64514,64523,64532,64540,64549,64558,64566,
254     64575,64584,64592,64601,64609,64617,64626,64634,
255     64642,64651,64659,64667,64675,64683,64691,64699,
256     64707,64715,64723,64731,64739,64747,64754,64762,
257     64770,64777,64785,64793,64800,64808,64815,64822,
258     64830,64837,64844,64852,64859,64866,64873,64880,
259     64887,64895,64902,64908,64915,64922,64929,64936,
260     64943,64949,64956,64963,64969,64976,64982,64989,
261     64995,65002,65008,65015,65021,65027,65033,65040,
262     65046,65052,65058,65064,65070,65076,65082,65088,
263     65094,65099,65105,65111,65117,65122,65128,65133,
264     65139,65144,65150,65155,65161,65166,65171,65177,
265     65182,65187,65192,65197,65202,65207,65212,65217,
266     65222,65227,65232,65237,65242,65246,65251,65256,
267     65260,65265,65270,65274,65279,65283,65287,65292,
268     65296,65300,65305,65309,65313,65317,65321,65325,
269     65329,65333,65337,65341,65345,65349,65352,65356,
270     65360,65363,65367,65371,65374,65378,65381,65385,
271     65388,65391,65395,65398,65401,65404,65408,65411,
272     65414,65417,65420,65423,65426,65429,65431,65434,
273     65437,65440,65442,65445,65448,65450,65453,65455,
274     65458,65460,65463,65465,65467,65470,65472,65474,
275     65476,65478,65480,65482,65484,65486,65488,65490,
276     65492,65494,65496,65497,65499,65501,65502,65504,
277     65505,65507,65508,65510,65511,65513,65514,65515,
278     65516,65518,65519,65520,65521,65522,65523,65524,
279     65525,65526,65527,65527,65528,65529,65530,65530,
280     65531,65531,65532,65532,65533,65533,65534,65534,
281     65534,65535,65535,65535,65535,65535,65535,65535,
282     65535,65535,65535,65535,65535,65535,65535,65534,
283     65534,65534,65533,65533,65532,65532,65531,65531,
284     65530,65530,65529,65528,65527,65527,65526,65525,
285     65524,65523,65522,65521,65520,65519,65518,65516,
286     65515,65514,65513,65511,65510,65508,65507,65505,
287     65504,65502,65501,65499,65497,65496,65494,65492,
288     65490,65488,65486,65484,65482,65480,65478,65476,
289     65474,65472,65470,65467,65465,65463,65460,65458,
290     65455,65453,65450,65448,65445,65442,65440,65437,
291     65434,65431,65429,65426,65423,65420,65417,65414,
292     65411,65408,65404,65401,65398,65395,65391,65388,
293     65385,65381,65378,65374,65371,65367,65363,65360,
294     65356,65352,65349,65345,65341,65337,65333,65329,
295     65325,65321,65317,65313,65309,65305,65300,65296,
296     65292,65287,65283,65279,65274,65270,65265,65260,
297     65256,65251,65246,65242,65237,65232,65227,65222,
298     65217,65212,65207,65202,65197,65192,65187,65182,
299     65177,65171,65166,65161,65155,65150,65144,65139,
300     65133,65128,65122,65117,65111,65105,65099,65094,
301     65088,65082,65076,65070,65064,65058,65052,65046,
302     65040,65033,65027,65021,65015,65008,65002,64995,
303     64989,64982,64976,64969,64963,64956,64949,64943,
304     64936,64929,64922,64915,64908,64902,64895,64887,
305     64880,64873,64866,64859,64852,64844,64837,64830,
306     64822,64815,64808,64800,64793,64785,64777,64770,
307     64762,64754,64747,64739,64731,64723,64715,64707,
308     64699,64691,64683,64675,64667,64659,64651,64642,
309     64634,64626,64617,64609,64600,64592,64584,64575,
310     64566,64558,64549,64540,64532,64523,64514,64505,
311     64496,64487,64478,64469,64460,64451,64442,64433,
312     64424,64414,64405,64396,64387,64377,64368,64358,
313     64349,64339,64330,64320,64310,64301,64291,64281,
314     64271,64261,64252,64242,64232,64222,64212,64202,
315     64192,64181,64171,64161,64151,64140,64130,64120,
316     64109,64099,64088,64078,64067,64057,64046,64035,
317     64025,64014,64003,63992,63981,63971,63960,63949,
318     63938,63927,63915,63904,63893,63882,63871,63859,
319     63848,63837,63825,63814,63803,63791,63779,63768,
320     63756,63745,63733,63721,63709,63698,63686,63674,
321     63662,63650,63638,63626,63614,63602,63590,63578,
322     63565,63553,63541,63528,63516,63504,63491,63479,
323     63466,63454,63441,63429,63416,63403,63390,63378,
324     63365,63352,63339,63326,63313,63300,63287,63274,
325     63261,63248,63235,63221,63208,63195,63182,63168,
326     63155,63141,63128,63114,63101,63087,63074,63060,
327     63046,63032,63019,63005,62991,62977,62963,62949,
328     62935,62921,62907,62893,62879,62865,62850,62836,
329     62822,62808,62793,62779,62764,62750,62735,62721,
330     62706,62692,62677,62662,62648,62633,62618,62603,
331     62588,62573,62558,62543,62528,62513,62498,62483,
332     62468,62453,62437,62422,62407,62391,62376,62360,
333     62345,62329,62314,62298,62283,62267,62251,62236,
334     62220,62204,62188,62172,62156,62141,62125,62108,
335     62092,62076,62060,62044,62028,62012,61995,61979,
336     61963,61946,61930,61913,61897,61880,61864,61847,
337     61831,61814,61797,61780,61764,61747,61730,61713,
338     61696,61679,61662,61645,61628,61611,61594,61577,
339     61559,61542,61525,61507,61490,61473,61455,61438,
340     61420,61403,61385,61367,61350,61332,61314,61297,
341     61279,61261,61243,61225,61207,61189,61171,61153,
342     61135,61117,61099,61081,61062,61044,61026,61007,
343     60989,60971,60952,60934,60915,60897,60878,60859,
344     60841,60822,60803,60785,60766,60747,60728,60709,
345     60690,60671,60652,60633,60614,60595,60576,60556,
346     60537,60518,60499,60479,60460,60441,60421,60402,
347     60382,60363,60343,60323,60304,60284,60264,60244,
348     60225,60205,60185,60165,60145,60125,60105,60085,
349     60065,60045,60025,60004,59984,59964,59944,59923,
350     59903,59883,59862,59842,59821,59801,59780,59759,
351     59739,59718,59697,59677,59656,59635,59614,59593,
352     59572,59551,59530,59509,59488,59467,59446,59425,
353     59404,59382,59361,59340,59318,59297,59276,59254,
354     59233,59211,59190,59168,59146,59125,59103,59081,
355     59059,59038,59016,58994,58972,58950,58928,58906,
356     58884,58862,58840,58818,58795,58773,58751,58729,
357     58706,58684,58662,58639,58617,58594,58572,58549,
358     58527,58504,58481,58459,58436,58413,58390,58367,
359     58345,58322,58299,58276,58253,58230,58207,58183,
360     58160,58137,58114,58091,58067,58044,58021,57997,
361     57974,57950,57927,57903,57880,57856,57833,57809,
362     57785,57762,57738,57714,57690,57666,57642,57618,
363     57594,57570,57546,57522,57498,57474,57450,57426,
364     57402,57377,57353,57329,57304,57280,57255,57231,
365     57206,57182,57157,57133,57108,57083,57059,57034,
366     57009,56984,56959,56935,56910,56885,56860,56835,
367     56810,56785,56760,56734,56709,56684,56659,56633,
368     56608,56583,56557,56532,56507,56481,56456,56430,
369     56404,56379,56353,56328,56302,56276,56250,56225,
370     56199,56173,56147,56121,56095,56069,56043,56017,
371     55991,55965,55938,55912,55886,55860,55833,55807,
372     55781,55754,55728,55701,55675,55648,55622,55595,
373     55569,55542,55515,55489,55462,55435,55408,55381,
374     55354,55327,55300,55274,55246,55219,55192,55165,
375     55138,55111,55084,55056,55029,55002,54974,54947,
376     54920,54892,54865,54837,54810,54782,54755,54727,
377     54699,54672,54644,54616,54588,54560,54533,54505,
378     54477,54449,54421,54393,54365,54337,54308,54280,
379     54252,54224,54196,54167,54139,54111,54082,54054,
380     54026,53997,53969,53940,53911,53883,53854,53826,
381     53797,53768,53739,53711,53682,53653,53624,53595,
382     53566,53537,53508,53479,53450,53421,53392,53363,
383     53334,53304,53275,53246,53216,53187,53158,53128,
384     53099,53069,53040,53010,52981,52951,52922,52892,
385     52862,52832,52803,52773,52743,52713,52683,52653,
386     52624,52594,52564,52534,52503,52473,52443,52413,
387     52383,52353,52322,52292,52262,52231,52201,52171,
388     52140,52110,52079,52049,52018,51988,51957,51926,
389     51896,51865,51834,51803,51773,51742,51711,51680,
390     51649,51618,51587,51556,51525,51494,51463,51432,
391     51401,51369,51338,51307,51276,51244,51213,51182,
392     51150,51119,51087,51056,51024,50993,50961,50929,
393     50898,50866,50834,50803,50771,50739,50707,50675,
394     50644,50612,50580,50548,50516,50484,50452,50420,
395     50387,50355,50323,50291,50259,50226,50194,50162,
396     50129,50097,50065,50032,50000,49967,49935,49902,
397     49869,49837,49804,49771,49739,49706,49673,49640,
398     49608,49575,49542,49509,49476,49443,49410,49377,
399     49344,49311,49278,49244,49211,49178,49145,49112,
400     49078,49045,49012,48978,48945,48911,48878,48844,
401     48811,48777,48744,48710,48676,48643,48609,48575,
402     48542,48508,48474,48440,48406,48372,48338,48304,
403     48271,48237,48202,48168,48134,48100,48066,48032,
404     47998,47963,47929,47895,47860,47826,47792,47757,
405     47723,47688,47654,47619,47585,47550,47516,47481,
406     47446,47412,47377,47342,47308,47273,47238,47203,
407     47168,47133,47098,47063,47028,46993,46958,46923,
408     46888,46853,46818,46783,46747,46712,46677,46642,
409     46606,46571,46536,46500,46465,46429,46394,46358,
410     46323,46287,46252,46216,46180,46145,46109,46073,
411     46037,46002,45966,45930,45894,45858,45822,45786,
412     45750,45714,45678,45642,45606,45570,45534,45498,
413     45462,45425,45389,45353,45316,45280,45244,45207,
414     45171,45135,45098,45062,45025,44989,44952,44915,
415     44879,44842,44806,44769,44732,44695,44659,44622,
416     44585,44548,44511,44474,44437,44400,44363,44326,
417     44289,44252,44215,44178,44141,44104,44067,44029,
418     43992,43955,43918,43880,43843,43806,43768,43731,
419     43693,43656,43618,43581,43543,43506,43468,43430,
420     43393,43355,43317,43280,43242,43204,43166,43128,
421     43091,43053,43015,42977,42939,42901,42863,42825,
422     42787,42749,42711,42672,42634,42596,42558,42520,
423     42481,42443,42405,42366,42328,42290,42251,42213,
424     42174,42136,42097,42059,42020,41982,41943,41904,
425     41866,41827,41788,41750,41711,41672,41633,41595,
426     41556,41517,41478,41439,41400,41361,41322,41283,
427     41244,41205,41166,41127,41088,41048,41009,40970,
428     40931,40891,40852,40813,40773,40734,40695,40655,
429     40616,40576,40537,40497,40458,40418,40379,40339,
430     40300,40260,40220,40180,40141,40101,40061,40021,
431     39982,39942,39902,39862,39822,39782,39742,39702,
432     39662,39622,39582,39542,39502,39462,39422,39382,
433     39341,39301,39261,39221,39180,39140,39100,39059,
434     39019,38979,38938,38898,38857,38817,38776,38736,
435     38695,38655,38614,38573,38533,38492,38451,38411,
436     38370,38329,38288,38248,38207,38166,38125,38084,
437     38043,38002,37961,37920,37879,37838,37797,37756,
438     37715,37674,37633,37592,37551,37509,37468,37427,
439     37386,37344,37303,37262,37220,37179,37137,37096,
440     37055,37013,36972,36930,36889,36847,36805,36764,
441     36722,36681,36639,36597,36556,36514,36472,36430,
442     36388,36347,36305,36263,36221,36179,36137,36095,
443     36053,36011,35969,35927,35885,35843,35801,35759,
444     35717,35675,35633,35590,35548,35506,35464,35421,
445     35379,35337,35294,35252,35210,35167,35125,35082,
446     35040,34997,34955,34912,34870,34827,34785,34742,
447     34699,34657,34614,34571,34529,34486,34443,34400,
448     34358,34315,34272,34229,34186,34143,34100,34057,
449     34015,33972,33929,33886,33843,33799,33756,33713,
450     33670,33627,33584,33541,33498,33454,33411,33368,
451     33325,33281,33238,33195,33151,33108,33065,33021,
452     32978,32934,32891,32847,32804,32760,32717,32673,
453     32630,32586,32542,32499,32455,32411,32368,32324,
454     32280,32236,32193,32149,32105,32061,32017,31974,
455     31930,31886,31842,31798,31754,31710,31666,31622,
456     31578,31534,31490,31446,31402,31357,31313,31269,
457     31225,31181,31136,31092,31048,31004,30959,30915,
458     30871,30826,30782,30738,30693,30649,30604,30560,
459     30515,30471,30426,30382,30337,30293,30248,30204,
460     30159,30114,30070,30025,29980,29936,29891,29846,
461     29801,29757,29712,29667,29622,29577,29533,29488,
462     29443,29398,29353,29308,29263,29218,29173,29128,
463     29083,29038,28993,28948,28903,28858,28812,28767,
464     28722,28677,28632,28586,28541,28496,28451,28405,
465     28360,28315,28269,28224,28179,28133,28088,28042,
466     27997,27952,27906,27861,27815,27770,27724,27678,
467     27633,27587,27542,27496,27450,27405,27359,27313,
468     27268,27222,27176,27131,27085,27039,26993,26947,
469     26902,26856,26810,26764,26718,26672,26626,26580,
470     26534,26488,26442,26396,26350,26304,26258,26212,
471     26166,26120,26074,26028,25982,25936,25889,25843,
472     25797,25751,25705,25658,25612,25566,25520,25473,
473     25427,25381,25334,25288,25241,25195,25149,25102,
474     25056,25009,24963,24916,24870,24823,24777,24730,
475     24684,24637,24591,24544,24497,24451,24404,24357,
476     24311,24264,24217,24171,24124,24077,24030,23984,
477     23937,23890,23843,23796,23750,23703,23656,23609,
478     23562,23515,23468,23421,23374,23327,23280,23233,
479     23186,23139,23092,23045,22998,22951,22904,22857,
480     22810,22763,22716,22668,22621,22574,22527,22480,
481     22433,22385,22338,22291,22243,22196,22149,22102,
482     22054,22007,21960,21912,21865,21817,21770,21723,
483     21675,21628,21580,21533,21485,21438,21390,21343,
484     21295,21248,21200,21153,21105,21057,21010,20962,
485     20915,20867,20819,20772,20724,20676,20629,20581,
486     20533,20485,20438,20390,20342,20294,20246,20199,
487     20151,20103,20055,20007,19959,19912,19864,19816,
488     19768,19720,19672,19624,19576,19528,19480,19432,
489     19384,19336,19288,19240,19192,19144,19096,19048,
490     19000,18951,18903,18855,18807,18759,18711,18663,
491     18614,18566,18518,18470,18421,18373,18325,18277,
492     18228,18180,18132,18084,18035,17987,17939,17890,
493     17842,17793,17745,17697,17648,17600,17551,17503,
494     17455,17406,17358,17309,17261,17212,17164,17115,
495     17067,17018,16970,16921,16872,16824,16775,16727,
496     16678,16629,16581,16532,16484,16435,16386,16338,
497     16289,16240,16191,16143,16094,16045,15997,15948,
498     15899,15850,15802,15753,15704,15655,15606,15557,
499     15509,15460,15411,15362,15313,15264,15215,15167,
500     15118,15069,15020,14971,14922,14873,14824,14775,
501     14726,14677,14628,14579,14530,14481,14432,14383,
502     14334,14285,14236,14187,14138,14089,14040,13990,
503     13941,13892,13843,13794,13745,13696,13646,13597,
504     13548,13499,13450,13401,13351,13302,13253,13204,
505     13154,13105,13056,13007,12957,12908,12859,12810,
506     12760,12711,12662,12612,12563,12514,12464,12415,
507     12366,12316,12267,12218,12168,12119,12069,12020,
508     11970,11921,11872,11822,11773,11723,11674,11624,
509     11575,11525,11476,11426,11377,11327,11278,11228,
510     11179,11129,11080,11030,10981,10931,10882,10832,
511     10782,10733,10683,10634,10584,10534,10485,10435,
512     10386,10336,10286,10237,10187,10137,10088,10038,
513     9988,9939,9889,9839,9790,9740,9690,9640,
514     9591,9541,9491,9442,9392,9342,9292,9243,
515     9193,9143,9093,9043,8994,8944,8894,8844,
516     8794,8745,8695,8645,8595,8545,8496,8446,
517     8396,8346,8296,8246,8196,8147,8097,8047,
518     7997,7947,7897,7847,7797,7747,7697,7648,
519     7598,7548,7498,7448,7398,7348,7298,7248,
520     7198,7148,7098,7048,6998,6948,6898,6848,
521     6798,6748,6698,6648,6598,6548,6498,6448,
522     6398,6348,6298,6248,6198,6148,6098,6048,
523     5998,5948,5898,5848,5798,5748,5697,5647,
524     5597,5547,5497,5447,5397,5347,5297,5247,
525     5197,5146,5096,5046,4996,4946,4896,4846,
526     4796,4745,4695,4645,4595,4545,4495,4445,
527     4394,4344,4294,4244,4194,4144,4093,4043,
528     3993,3943,3893,3843,3792,3742,3692,3642,
529     3592,3541,3491,3441,3391,3341,3291,3240,
530     3190,3140,3090,3039,2989,2939,2889,2839,
531     2788,2738,2688,2638,2587,2537,2487,2437,
532     2387,2336,2286,2236,2186,2135,2085,2035,
533     1985,1934,1884,1834,1784,1733,1683,1633,
534     1583,1532,1482,1432,1382,1331,1281,1231,
535     1181,1130,1080,1030,980,929,879,829,
536     779,728,678,628,578,527,477,427,
537     376,326,276,226,175,125,75,25,
538     -25,-75,-125,-175,-226,-276,-326,-376,
539     -427,-477,-527,-578,-628,-678,-728,-779,
540     -829,-879,-929,-980,-1030,-1080,-1130,-1181,
541     -1231,-1281,-1331,-1382,-1432,-1482,-1532,-1583,
542     -1633,-1683,-1733,-1784,-1834,-1884,-1934,-1985,
543     -2035,-2085,-2135,-2186,-2236,-2286,-2336,-2387,
544     -2437,-2487,-2537,-2588,-2638,-2688,-2738,-2788,
545     -2839,-2889,-2939,-2989,-3039,-3090,-3140,-3190,
546     -3240,-3291,-3341,-3391,-3441,-3491,-3541,-3592,
547     -3642,-3692,-3742,-3792,-3843,-3893,-3943,-3993,
548     -4043,-4093,-4144,-4194,-4244,-4294,-4344,-4394,
549     -4445,-4495,-4545,-4595,-4645,-4695,-4745,-4796,
550     -4846,-4896,-4946,-4996,-5046,-5096,-5146,-5197,
551     -5247,-5297,-5347,-5397,-5447,-5497,-5547,-5597,
552     -5647,-5697,-5748,-5798,-5848,-5898,-5948,-5998,
553     -6048,-6098,-6148,-6198,-6248,-6298,-6348,-6398,
554     -6448,-6498,-6548,-6598,-6648,-6698,-6748,-6798,
555     -6848,-6898,-6948,-6998,-7048,-7098,-7148,-7198,
556     -7248,-7298,-7348,-7398,-7448,-7498,-7548,-7598,
557     -7648,-7697,-7747,-7797,-7847,-7897,-7947,-7997,
558     -8047,-8097,-8147,-8196,-8246,-8296,-8346,-8396,
559     -8446,-8496,-8545,-8595,-8645,-8695,-8745,-8794,
560     -8844,-8894,-8944,-8994,-9043,-9093,-9143,-9193,
561     -9243,-9292,-9342,-9392,-9442,-9491,-9541,-9591,
562     -9640,-9690,-9740,-9790,-9839,-9889,-9939,-9988,
563     -10038,-10088,-10137,-10187,-10237,-10286,-10336,-10386,
564     -10435,-10485,-10534,-10584,-10634,-10683,-10733,-10782,
565     -10832,-10882,-10931,-10981,-11030,-11080,-11129,-11179,
566     -11228,-11278,-11327,-11377,-11426,-11476,-11525,-11575,
567     -11624,-11674,-11723,-11773,-11822,-11872,-11921,-11970,
568     -12020,-12069,-12119,-12168,-12218,-12267,-12316,-12366,
569     -12415,-12464,-12514,-12563,-12612,-12662,-12711,-12760,
570     -12810,-12859,-12908,-12957,-13007,-13056,-13105,-13154,
571     -13204,-13253,-13302,-13351,-13401,-13450,-13499,-13548,
572     -13597,-13647,-13696,-13745,-13794,-13843,-13892,-13941,
573     -13990,-14040,-14089,-14138,-14187,-14236,-14285,-14334,
574     -14383,-14432,-14481,-14530,-14579,-14628,-14677,-14726,
575     -14775,-14824,-14873,-14922,-14971,-15020,-15069,-15118,
576     -15167,-15215,-15264,-15313,-15362,-15411,-15460,-15509,
577     -15557,-15606,-15655,-15704,-15753,-15802,-15850,-15899,
578     -15948,-15997,-16045,-16094,-16143,-16191,-16240,-16289,
579     -16338,-16386,-16435,-16484,-16532,-16581,-16629,-16678,
580     -16727,-16775,-16824,-16872,-16921,-16970,-17018,-17067,
581     -17115,-17164,-17212,-17261,-17309,-17358,-17406,-17455,
582     -17503,-17551,-17600,-17648,-17697,-17745,-17793,-17842,
583     -17890,-17939,-17987,-18035,-18084,-18132,-18180,-18228,
584     -18277,-18325,-18373,-18421,-18470,-18518,-18566,-18614,
585     -18663,-18711,-18759,-18807,-18855,-18903,-18951,-19000,
586     -19048,-19096,-19144,-19192,-19240,-19288,-19336,-19384,
587     -19432,-19480,-19528,-19576,-19624,-19672,-19720,-19768,
588     -19816,-19864,-19912,-19959,-20007,-20055,-20103,-20151,
589     -20199,-20246,-20294,-20342,-20390,-20438,-20485,-20533,
590     -20581,-20629,-20676,-20724,-20772,-20819,-20867,-20915,
591     -20962,-21010,-21057,-21105,-21153,-21200,-21248,-21295,
592     -21343,-21390,-21438,-21485,-21533,-21580,-21628,-21675,
593     -21723,-21770,-21817,-21865,-21912,-21960,-22007,-22054,
594     -22102,-22149,-22196,-22243,-22291,-22338,-22385,-22433,
595     -22480,-22527,-22574,-22621,-22668,-22716,-22763,-22810,
596     -22857,-22904,-22951,-22998,-23045,-23092,-23139,-23186,
597     -23233,-23280,-23327,-23374,-23421,-23468,-23515,-23562,
598     -23609,-23656,-23703,-23750,-23796,-23843,-23890,-23937,
599     -23984,-24030,-24077,-24124,-24171,-24217,-24264,-24311,
600     -24357,-24404,-24451,-24497,-24544,-24591,-24637,-24684,
601     -24730,-24777,-24823,-24870,-24916,-24963,-25009,-25056,
602     -25102,-25149,-25195,-25241,-25288,-25334,-25381,-25427,
603     -25473,-25520,-25566,-25612,-25658,-25705,-25751,-25797,
604     -25843,-25889,-25936,-25982,-26028,-26074,-26120,-26166,
605     -26212,-26258,-26304,-26350,-26396,-26442,-26488,-26534,
606     -26580,-26626,-26672,-26718,-26764,-26810,-26856,-26902,
607     -26947,-26993,-27039,-27085,-27131,-27176,-27222,-27268,
608     -27313,-27359,-27405,-27450,-27496,-27542,-27587,-27633,
609     -27678,-27724,-27770,-27815,-27861,-27906,-27952,-27997,
610     -28042,-28088,-28133,-28179,-28224,-28269,-28315,-28360,
611     -28405,-28451,-28496,-28541,-28586,-28632,-28677,-28722,
612     -28767,-28812,-28858,-28903,-28948,-28993,-29038,-29083,
613     -29128,-29173,-29218,-29263,-29308,-29353,-29398,-29443,
614     -29488,-29533,-29577,-29622,-29667,-29712,-29757,-29801,
615     -29846,-29891,-29936,-29980,-30025,-30070,-30114,-30159,
616     -30204,-30248,-30293,-30337,-30382,-30426,-30471,-30515,
617     -30560,-30604,-30649,-30693,-30738,-30782,-30826,-30871,
618     -30915,-30959,-31004,-31048,-31092,-31136,-31181,-31225,
619     -31269,-31313,-31357,-31402,-31446,-31490,-31534,-31578,
620     -31622,-31666,-31710,-31754,-31798,-31842,-31886,-31930,
621     -31974,-32017,-32061,-32105,-32149,-32193,-32236,-32280,
622     -32324,-32368,-32411,-32455,-32499,-32542,-32586,-32630,
623     -32673,-32717,-32760,-32804,-32847,-32891,-32934,-32978,
624     -33021,-33065,-33108,-33151,-33195,-33238,-33281,-33325,
625     -33368,-33411,-33454,-33498,-33541,-33584,-33627,-33670,
626     -33713,-33756,-33799,-33843,-33886,-33929,-33972,-34015,
627     -34057,-34100,-34143,-34186,-34229,-34272,-34315,-34358,
628     -34400,-34443,-34486,-34529,-34571,-34614,-34657,-34699,
629     -34742,-34785,-34827,-34870,-34912,-34955,-34997,-35040,
630     -35082,-35125,-35167,-35210,-35252,-35294,-35337,-35379,
631     -35421,-35464,-35506,-35548,-35590,-35633,-35675,-35717,
632     -35759,-35801,-35843,-35885,-35927,-35969,-36011,-36053,
633     -36095,-36137,-36179,-36221,-36263,-36305,-36347,-36388,
634     -36430,-36472,-36514,-36555,-36597,-36639,-36681,-36722,
635     -36764,-36805,-36847,-36889,-36930,-36972,-37013,-37055,
636     -37096,-37137,-37179,-37220,-37262,-37303,-37344,-37386,
637     -37427,-37468,-37509,-37551,-37592,-37633,-37674,-37715,
638     -37756,-37797,-37838,-37879,-37920,-37961,-38002,-38043,
639     -38084,-38125,-38166,-38207,-38248,-38288,-38329,-38370,
640     -38411,-38451,-38492,-38533,-38573,-38614,-38655,-38695,
641     -38736,-38776,-38817,-38857,-38898,-38938,-38979,-39019,
642     -39059,-39100,-39140,-39180,-39221,-39261,-39301,-39341,
643     -39382,-39422,-39462,-39502,-39542,-39582,-39622,-39662,
644     -39702,-39742,-39782,-39822,-39862,-39902,-39942,-39982,
645     -40021,-40061,-40101,-40141,-40180,-40220,-40260,-40299,
646     -40339,-40379,-40418,-40458,-40497,-40537,-40576,-40616,
647     -40655,-40695,-40734,-40773,-40813,-40852,-40891,-40931,
648     -40970,-41009,-41048,-41087,-41127,-41166,-41205,-41244,
649     -41283,-41322,-41361,-41400,-41439,-41478,-41517,-41556,
650     -41595,-41633,-41672,-41711,-41750,-41788,-41827,-41866,
651     -41904,-41943,-41982,-42020,-42059,-42097,-42136,-42174,
652     -42213,-42251,-42290,-42328,-42366,-42405,-42443,-42481,
653     -42520,-42558,-42596,-42634,-42672,-42711,-42749,-42787,
654     -42825,-42863,-42901,-42939,-42977,-43015,-43053,-43091,
655     -43128,-43166,-43204,-43242,-43280,-43317,-43355,-43393,
656     -43430,-43468,-43506,-43543,-43581,-43618,-43656,-43693,
657     -43731,-43768,-43806,-43843,-43880,-43918,-43955,-43992,
658     -44029,-44067,-44104,-44141,-44178,-44215,-44252,-44289,
659     -44326,-44363,-44400,-44437,-44474,-44511,-44548,-44585,
660     -44622,-44659,-44695,-44732,-44769,-44806,-44842,-44879,
661     -44915,-44952,-44989,-45025,-45062,-45098,-45135,-45171,
662     -45207,-45244,-45280,-45316,-45353,-45389,-45425,-45462,
663     -45498,-45534,-45570,-45606,-45642,-45678,-45714,-45750,
664     -45786,-45822,-45858,-45894,-45930,-45966,-46002,-46037,
665     -46073,-46109,-46145,-46180,-46216,-46252,-46287,-46323,
666     -46358,-46394,-46429,-46465,-46500,-46536,-46571,-46606,
667     -46642,-46677,-46712,-46747,-46783,-46818,-46853,-46888,
668     -46923,-46958,-46993,-47028,-47063,-47098,-47133,-47168,
669     -47203,-47238,-47273,-47308,-47342,-47377,-47412,-47446,
670     -47481,-47516,-47550,-47585,-47619,-47654,-47688,-47723,
671     -47757,-47792,-47826,-47860,-47895,-47929,-47963,-47998,
672     -48032,-48066,-48100,-48134,-48168,-48202,-48236,-48271,
673     -48304,-48338,-48372,-48406,-48440,-48474,-48508,-48542,
674     -48575,-48609,-48643,-48676,-48710,-48744,-48777,-48811,
675     -48844,-48878,-48911,-48945,-48978,-49012,-49045,-49078,
676     -49112,-49145,-49178,-49211,-49244,-49278,-49311,-49344,
677     -49377,-49410,-49443,-49476,-49509,-49542,-49575,-49608,
678     -49640,-49673,-49706,-49739,-49771,-49804,-49837,-49869,
679     -49902,-49935,-49967,-50000,-50032,-50065,-50097,-50129,
680     -50162,-50194,-50226,-50259,-50291,-50323,-50355,-50387,
681     -50420,-50452,-50484,-50516,-50548,-50580,-50612,-50644,
682     -50675,-50707,-50739,-50771,-50803,-50834,-50866,-50898,
683     -50929,-50961,-50993,-51024,-51056,-51087,-51119,-51150,
684     -51182,-51213,-51244,-51276,-51307,-51338,-51369,-51401,
685     -51432,-51463,-51494,-51525,-51556,-51587,-51618,-51649,
686     -51680,-51711,-51742,-51773,-51803,-51834,-51865,-51896,
687     -51926,-51957,-51988,-52018,-52049,-52079,-52110,-52140,
688     -52171,-52201,-52231,-52262,-52292,-52322,-52353,-52383,
689     -52413,-52443,-52473,-52503,-52534,-52564,-52594,-52624,
690     -52653,-52683,-52713,-52743,-52773,-52803,-52832,-52862,
691     -52892,-52922,-52951,-52981,-53010,-53040,-53069,-53099,
692     -53128,-53158,-53187,-53216,-53246,-53275,-53304,-53334,
693     -53363,-53392,-53421,-53450,-53479,-53508,-53537,-53566,
694     -53595,-53624,-53653,-53682,-53711,-53739,-53768,-53797,
695     -53826,-53854,-53883,-53911,-53940,-53969,-53997,-54026,
696     -54054,-54082,-54111,-54139,-54167,-54196,-54224,-54252,
697     -54280,-54308,-54337,-54365,-54393,-54421,-54449,-54477,
698     -54505,-54533,-54560,-54588,-54616,-54644,-54672,-54699,
699     -54727,-54755,-54782,-54810,-54837,-54865,-54892,-54920,
700     -54947,-54974,-55002,-55029,-55056,-55084,-55111,-55138,
701     -55165,-55192,-55219,-55246,-55274,-55300,-55327,-55354,
702     -55381,-55408,-55435,-55462,-55489,-55515,-55542,-55569,
703     -55595,-55622,-55648,-55675,-55701,-55728,-55754,-55781,
704     -55807,-55833,-55860,-55886,-55912,-55938,-55965,-55991,
705     -56017,-56043,-56069,-56095,-56121,-56147,-56173,-56199,
706     -56225,-56250,-56276,-56302,-56328,-56353,-56379,-56404,
707     -56430,-56456,-56481,-56507,-56532,-56557,-56583,-56608,
708     -56633,-56659,-56684,-56709,-56734,-56760,-56785,-56810,
709     -56835,-56860,-56885,-56910,-56935,-56959,-56984,-57009,
710     -57034,-57059,-57083,-57108,-57133,-57157,-57182,-57206,
711     -57231,-57255,-57280,-57304,-57329,-57353,-57377,-57402,
712     -57426,-57450,-57474,-57498,-57522,-57546,-57570,-57594,
713     -57618,-57642,-57666,-57690,-57714,-57738,-57762,-57785,
714     -57809,-57833,-57856,-57880,-57903,-57927,-57950,-57974,
715     -57997,-58021,-58044,-58067,-58091,-58114,-58137,-58160,
716     -58183,-58207,-58230,-58253,-58276,-58299,-58322,-58345,
717     -58367,-58390,-58413,-58436,-58459,-58481,-58504,-58527,
718     -58549,-58572,-58594,-58617,-58639,-58662,-58684,-58706,
719     -58729,-58751,-58773,-58795,-58818,-58840,-58862,-58884,
720     -58906,-58928,-58950,-58972,-58994,-59016,-59038,-59059,
721     -59081,-59103,-59125,-59146,-59168,-59190,-59211,-59233,
722     -59254,-59276,-59297,-59318,-59340,-59361,-59382,-59404,
723     -59425,-59446,-59467,-59488,-59509,-59530,-59551,-59572,
724     -59593,-59614,-59635,-59656,-59677,-59697,-59718,-59739,
725     -59759,-59780,-59801,-59821,-59842,-59862,-59883,-59903,
726     -59923,-59944,-59964,-59984,-60004,-60025,-60045,-60065,
727     -60085,-60105,-60125,-60145,-60165,-60185,-60205,-60225,
728     -60244,-60264,-60284,-60304,-60323,-60343,-60363,-60382,
729     -60402,-60421,-60441,-60460,-60479,-60499,-60518,-60537,
730     -60556,-60576,-60595,-60614,-60633,-60652,-60671,-60690,
731     -60709,-60728,-60747,-60766,-60785,-60803,-60822,-60841,
732     -60859,-60878,-60897,-60915,-60934,-60952,-60971,-60989,
733     -61007,-61026,-61044,-61062,-61081,-61099,-61117,-61135,
734     -61153,-61171,-61189,-61207,-61225,-61243,-61261,-61279,
735     -61297,-61314,-61332,-61350,-61367,-61385,-61403,-61420,
736     -61438,-61455,-61473,-61490,-61507,-61525,-61542,-61559,
737     -61577,-61594,-61611,-61628,-61645,-61662,-61679,-61696,
738     -61713,-61730,-61747,-61764,-61780,-61797,-61814,-61831,
739     -61847,-61864,-61880,-61897,-61913,-61930,-61946,-61963,
740     -61979,-61995,-62012,-62028,-62044,-62060,-62076,-62092,
741     -62108,-62125,-62141,-62156,-62172,-62188,-62204,-62220,
742     -62236,-62251,-62267,-62283,-62298,-62314,-62329,-62345,
743     -62360,-62376,-62391,-62407,-62422,-62437,-62453,-62468,
744     -62483,-62498,-62513,-62528,-62543,-62558,-62573,-62588,
745     -62603,-62618,-62633,-62648,-62662,-62677,-62692,-62706,
746     -62721,-62735,-62750,-62764,-62779,-62793,-62808,-62822,
747     -62836,-62850,-62865,-62879,-62893,-62907,-62921,-62935,
748     -62949,-62963,-62977,-62991,-63005,-63019,-63032,-63046,
749     -63060,-63074,-63087,-63101,-63114,-63128,-63141,-63155,
750     -63168,-63182,-63195,-63208,-63221,-63235,-63248,-63261,
751     -63274,-63287,-63300,-63313,-63326,-63339,-63352,-63365,
752     -63378,-63390,-63403,-63416,-63429,-63441,-63454,-63466,
753     -63479,-63491,-63504,-63516,-63528,-63541,-63553,-63565,
754     -63578,-63590,-63602,-63614,-63626,-63638,-63650,-63662,
755     -63674,-63686,-63698,-63709,-63721,-63733,-63745,-63756,
756     -63768,-63779,-63791,-63803,-63814,-63825,-63837,-63848,
757     -63859,-63871,-63882,-63893,-63904,-63915,-63927,-63938,
758     -63949,-63960,-63971,-63981,-63992,-64003,-64014,-64025,
759     -64035,-64046,-64057,-64067,-64078,-64088,-64099,-64109,
760     -64120,-64130,-64140,-64151,-64161,-64171,-64181,-64192,
761     -64202,-64212,-64222,-64232,-64242,-64252,-64261,-64271,
762     -64281,-64291,-64301,-64310,-64320,-64330,-64339,-64349,
763     -64358,-64368,-64377,-64387,-64396,-64405,-64414,-64424,
764     -64433,-64442,-64451,-64460,-64469,-64478,-64487,-64496,
765     -64505,-64514,-64523,-64532,-64540,-64549,-64558,-64566,
766     -64575,-64584,-64592,-64601,-64609,-64617,-64626,-64634,
767     -64642,-64651,-64659,-64667,-64675,-64683,-64691,-64699,
768     -64707,-64715,-64723,-64731,-64739,-64747,-64754,-64762,
769     -64770,-64777,-64785,-64793,-64800,-64808,-64815,-64822,
770     -64830,-64837,-64844,-64852,-64859,-64866,-64873,-64880,
771     -64887,-64895,-64902,-64908,-64915,-64922,-64929,-64936,
772     -64943,-64949,-64956,-64963,-64969,-64976,-64982,-64989,
773     -64995,-65002,-65008,-65015,-65021,-65027,-65033,-65040,
774     -65046,-65052,-65058,-65064,-65070,-65076,-65082,-65088,
775     -65094,-65099,-65105,-65111,-65117,-65122,-65128,-65133,
776     -65139,-65144,-65150,-65155,-65161,-65166,-65171,-65177,
777     -65182,-65187,-65192,-65197,-65202,-65207,-65212,-65217,
778     -65222,-65227,-65232,-65237,-65242,-65246,-65251,-65256,
779     -65260,-65265,-65270,-65274,-65279,-65283,-65287,-65292,
780     -65296,-65300,-65305,-65309,-65313,-65317,-65321,-65325,
781     -65329,-65333,-65337,-65341,-65345,-65349,-65352,-65356,
782     -65360,-65363,-65367,-65371,-65374,-65378,-65381,-65385,
783     -65388,-65391,-65395,-65398,-65401,-65404,-65408,-65411,
784     -65414,-65417,-65420,-65423,-65426,-65429,-65431,-65434,
785     -65437,-65440,-65442,-65445,-65448,-65450,-65453,-65455,
786     -65458,-65460,-65463,-65465,-65467,-65470,-65472,-65474,
787     -65476,-65478,-65480,-65482,-65484,-65486,-65488,-65490,
788     -65492,-65494,-65496,-65497,-65499,-65501,-65502,-65504,
789     -65505,-65507,-65508,-65510,-65511,-65513,-65514,-65515,
790     -65516,-65518,-65519,-65520,-65521,-65522,-65523,-65524,
791     -65525,-65526,-65527,-65527,-65528,-65529,-65530,-65530,
792     -65531,-65531,-65532,-65532,-65533,-65533,-65534,-65534,
793     -65534,-65535,-65535,-65535,-65535,-65535,-65535,-65535,
794     -65535,-65535,-65535,-65535,-65535,-65535,-65535,-65534,
795     -65534,-65534,-65533,-65533,-65532,-65532,-65531,-65531,
796     -65530,-65530,-65529,-65528,-65527,-65527,-65526,-65525,
797     -65524,-65523,-65522,-65521,-65520,-65519,-65518,-65516,
798     -65515,-65514,-65513,-65511,-65510,-65508,-65507,-65505,
799     -65504,-65502,-65501,-65499,-65497,-65496,-65494,-65492,
800     -65490,-65488,-65486,-65484,-65482,-65480,-65478,-65476,
801     -65474,-65472,-65470,-65467,-65465,-65463,-65460,-65458,
802     -65455,-65453,-65450,-65448,-65445,-65442,-65440,-65437,
803     -65434,-65431,-65429,-65426,-65423,-65420,-65417,-65414,
804     -65411,-65408,-65404,-65401,-65398,-65395,-65391,-65388,
805     -65385,-65381,-65378,-65374,-65371,-65367,-65363,-65360,
806     -65356,-65352,-65349,-65345,-65341,-65337,-65333,-65329,
807     -65325,-65321,-65317,-65313,-65309,-65305,-65300,-65296,
808     -65292,-65287,-65283,-65279,-65274,-65270,-65265,-65260,
809     -65256,-65251,-65246,-65242,-65237,-65232,-65227,-65222,
810     -65217,-65212,-65207,-65202,-65197,-65192,-65187,-65182,
811     -65177,-65171,-65166,-65161,-65155,-65150,-65144,-65139,
812     -65133,-65128,-65122,-65117,-65111,-65105,-65099,-65094,
813     -65088,-65082,-65076,-65070,-65064,-65058,-65052,-65046,
814     -65040,-65033,-65027,-65021,-65015,-65008,-65002,-64995,
815     -64989,-64982,-64976,-64969,-64963,-64956,-64949,-64943,
816     -64936,-64929,-64922,-64915,-64908,-64902,-64895,-64887,
817     -64880,-64873,-64866,-64859,-64852,-64844,-64837,-64830,
818     -64822,-64815,-64808,-64800,-64793,-64785,-64777,-64770,
819     -64762,-64754,-64747,-64739,-64731,-64723,-64715,-64707,
820     -64699,-64691,-64683,-64675,-64667,-64659,-64651,-64642,
821     -64634,-64626,-64617,-64609,-64601,-64592,-64584,-64575,
822     -64566,-64558,-64549,-64540,-64532,-64523,-64514,-64505,
823     -64496,-64487,-64478,-64469,-64460,-64451,-64442,-64433,
824     -64424,-64414,-64405,-64396,-64387,-64377,-64368,-64358,
825     -64349,-64339,-64330,-64320,-64310,-64301,-64291,-64281,
826     -64271,-64261,-64252,-64242,-64232,-64222,-64212,-64202,
827     -64192,-64181,-64171,-64161,-64151,-64140,-64130,-64120,
828     -64109,-64099,-64088,-64078,-64067,-64057,-64046,-64035,
829     -64025,-64014,-64003,-63992,-63981,-63971,-63960,-63949,
830     -63938,-63927,-63915,-63904,-63893,-63882,-63871,-63859,
831     -63848,-63837,-63825,-63814,-63803,-63791,-63779,-63768,
832     -63756,-63745,-63733,-63721,-63709,-63698,-63686,-63674,
833     -63662,-63650,-63638,-63626,-63614,-63602,-63590,-63578,
834     -63565,-63553,-63541,-63528,-63516,-63504,-63491,-63479,
835     -63466,-63454,-63441,-63429,-63416,-63403,-63390,-63378,
836     -63365,-63352,-63339,-63326,-63313,-63300,-63287,-63274,
837     -63261,-63248,-63235,-63221,-63208,-63195,-63182,-63168,
838     -63155,-63141,-63128,-63114,-63101,-63087,-63074,-63060,
839     -63046,-63032,-63019,-63005,-62991,-62977,-62963,-62949,
840     -62935,-62921,-62907,-62893,-62879,-62865,-62850,-62836,
841     -62822,-62808,-62793,-62779,-62764,-62750,-62735,-62721,
842     -62706,-62692,-62677,-62662,-62648,-62633,-62618,-62603,
843     -62588,-62573,-62558,-62543,-62528,-62513,-62498,-62483,
844     -62468,-62453,-62437,-62422,-62407,-62391,-62376,-62360,
845     -62345,-62329,-62314,-62298,-62283,-62267,-62251,-62236,
846     -62220,-62204,-62188,-62172,-62156,-62141,-62125,-62108,
847     -62092,-62076,-62060,-62044,-62028,-62012,-61995,-61979,
848     -61963,-61946,-61930,-61913,-61897,-61880,-61864,-61847,
849     -61831,-61814,-61797,-61780,-61764,-61747,-61730,-61713,
850     -61696,-61679,-61662,-61645,-61628,-61611,-61594,-61577,
851     -61559,-61542,-61525,-61507,-61490,-61473,-61455,-61438,
852     -61420,-61403,-61385,-61367,-61350,-61332,-61314,-61297,
853     -61279,-61261,-61243,-61225,-61207,-61189,-61171,-61153,
854     -61135,-61117,-61099,-61081,-61062,-61044,-61026,-61007,
855     -60989,-60971,-60952,-60934,-60915,-60897,-60878,-60859,
856     -60841,-60822,-60803,-60785,-60766,-60747,-60728,-60709,
857     -60690,-60671,-60652,-60633,-60614,-60595,-60576,-60556,
858     -60537,-60518,-60499,-60479,-60460,-60441,-60421,-60402,
859     -60382,-60363,-60343,-60323,-60304,-60284,-60264,-60244,
860     -60225,-60205,-60185,-60165,-60145,-60125,-60105,-60085,
861     -60065,-60045,-60025,-60004,-59984,-59964,-59944,-59923,
862     -59903,-59883,-59862,-59842,-59821,-59801,-59780,-59759,
863     -59739,-59718,-59697,-59677,-59656,-59635,-59614,-59593,
864     -59572,-59551,-59530,-59509,-59488,-59467,-59446,-59425,
865     -59404,-59382,-59361,-59340,-59318,-59297,-59276,-59254,
866     -59233,-59211,-59189,-59168,-59146,-59125,-59103,-59081,
867     -59059,-59038,-59016,-58994,-58972,-58950,-58928,-58906,
868     -58884,-58862,-58840,-58818,-58795,-58773,-58751,-58729,
869     -58706,-58684,-58662,-58639,-58617,-58594,-58572,-58549,
870     -58527,-58504,-58481,-58459,-58436,-58413,-58390,-58367,
871     -58345,-58322,-58299,-58276,-58253,-58230,-58207,-58183,
872     -58160,-58137,-58114,-58091,-58067,-58044,-58021,-57997,
873     -57974,-57950,-57927,-57903,-57880,-57856,-57833,-57809,
874     -57785,-57762,-57738,-57714,-57690,-57666,-57642,-57618,
875     -57594,-57570,-57546,-57522,-57498,-57474,-57450,-57426,
876     -57402,-57377,-57353,-57329,-57304,-57280,-57255,-57231,
877     -57206,-57182,-57157,-57133,-57108,-57083,-57059,-57034,
878     -57009,-56984,-56959,-56935,-56910,-56885,-56860,-56835,
879     -56810,-56785,-56760,-56734,-56709,-56684,-56659,-56633,
880     -56608,-56583,-56557,-56532,-56507,-56481,-56456,-56430,
881     -56404,-56379,-56353,-56328,-56302,-56276,-56250,-56225,
882     -56199,-56173,-56147,-56121,-56095,-56069,-56043,-56017,
883     -55991,-55965,-55938,-55912,-55886,-55860,-55833,-55807,
884     -55781,-55754,-55728,-55701,-55675,-55648,-55622,-55595,
885     -55569,-55542,-55515,-55489,-55462,-55435,-55408,-55381,
886     -55354,-55327,-55300,-55274,-55246,-55219,-55192,-55165,
887     -55138,-55111,-55084,-55056,-55029,-55002,-54974,-54947,
888     -54920,-54892,-54865,-54837,-54810,-54782,-54755,-54727,
889     -54699,-54672,-54644,-54616,-54588,-54560,-54533,-54505,
890     -54477,-54449,-54421,-54393,-54365,-54337,-54308,-54280,
891     -54252,-54224,-54196,-54167,-54139,-54111,-54082,-54054,
892     -54026,-53997,-53969,-53940,-53911,-53883,-53854,-53826,
893     -53797,-53768,-53739,-53711,-53682,-53653,-53624,-53595,
894     -53566,-53537,-53508,-53479,-53450,-53421,-53392,-53363,
895     -53334,-53304,-53275,-53246,-53216,-53187,-53158,-53128,
896     -53099,-53069,-53040,-53010,-52981,-52951,-52922,-52892,
897     -52862,-52832,-52803,-52773,-52743,-52713,-52683,-52653,
898     -52624,-52594,-52564,-52534,-52503,-52473,-52443,-52413,
899     -52383,-52353,-52322,-52292,-52262,-52231,-52201,-52171,
900     -52140,-52110,-52079,-52049,-52018,-51988,-51957,-51926,
901     -51896,-51865,-51834,-51803,-51773,-51742,-51711,-51680,
902     -51649,-51618,-51587,-51556,-51525,-51494,-51463,-51432,
903     -51401,-51369,-51338,-51307,-51276,-51244,-51213,-51182,
904     -51150,-51119,-51087,-51056,-51024,-50993,-50961,-50929,
905     -50898,-50866,-50834,-50803,-50771,-50739,-50707,-50675,
906     -50644,-50612,-50580,-50548,-50516,-50484,-50452,-50420,
907     -50387,-50355,-50323,-50291,-50259,-50226,-50194,-50162,
908     -50129,-50097,-50065,-50032,-50000,-49967,-49935,-49902,
909     -49869,-49837,-49804,-49771,-49739,-49706,-49673,-49640,
910     -49608,-49575,-49542,-49509,-49476,-49443,-49410,-49377,
911     -49344,-49311,-49278,-49244,-49211,-49178,-49145,-49112,
912     -49078,-49045,-49012,-48978,-48945,-48911,-48878,-48844,
913     -48811,-48777,-48744,-48710,-48676,-48643,-48609,-48575,
914     -48542,-48508,-48474,-48440,-48406,-48372,-48338,-48305,
915     -48271,-48237,-48202,-48168,-48134,-48100,-48066,-48032,
916     -47998,-47963,-47929,-47895,-47860,-47826,-47792,-47757,
917     -47723,-47688,-47654,-47619,-47585,-47550,-47516,-47481,
918     -47446,-47412,-47377,-47342,-47307,-47273,-47238,-47203,
919     -47168,-47133,-47098,-47063,-47028,-46993,-46958,-46923,
920     -46888,-46853,-46818,-46783,-46747,-46712,-46677,-46642,
921     -46606,-46571,-46536,-46500,-46465,-46429,-46394,-46358,
922     -46323,-46287,-46251,-46216,-46180,-46145,-46109,-46073,
923     -46037,-46002,-45966,-45930,-45894,-45858,-45822,-45786,
924     -45750,-45714,-45678,-45642,-45606,-45570,-45534,-45498,
925     -45462,-45425,-45389,-45353,-45316,-45280,-45244,-45207,
926     -45171,-45135,-45098,-45062,-45025,-44989,-44952,-44915,
927     -44879,-44842,-44806,-44769,-44732,-44695,-44659,-44622,
928     -44585,-44548,-44511,-44474,-44437,-44400,-44363,-44326,
929     -44289,-44252,-44215,-44178,-44141,-44104,-44067,-44029,
930     -43992,-43955,-43918,-43880,-43843,-43806,-43768,-43731,
931     -43693,-43656,-43618,-43581,-43543,-43506,-43468,-43430,
932     -43393,-43355,-43317,-43280,-43242,-43204,-43166,-43128,
933     -43091,-43053,-43015,-42977,-42939,-42901,-42863,-42825,
934     -42787,-42749,-42711,-42672,-42634,-42596,-42558,-42520,
935     -42481,-42443,-42405,-42366,-42328,-42290,-42251,-42213,
936     -42174,-42136,-42097,-42059,-42020,-41982,-41943,-41904,
937     -41866,-41827,-41788,-41750,-41711,-41672,-41633,-41595,
938     -41556,-41517,-41478,-41439,-41400,-41361,-41322,-41283,
939     -41244,-41205,-41166,-41127,-41087,-41048,-41009,-40970,
940     -40931,-40891,-40852,-40813,-40773,-40734,-40695,-40655,
941     -40616,-40576,-40537,-40497,-40458,-40418,-40379,-40339,
942     -40299,-40260,-40220,-40180,-40141,-40101,-40061,-40021,
943     -39982,-39942,-39902,-39862,-39822,-39782,-39742,-39702,
944     -39662,-39622,-39582,-39542,-39502,-39462,-39422,-39382,
945     -39341,-39301,-39261,-39221,-39180,-39140,-39100,-39059,
946     -39019,-38979,-38938,-38898,-38857,-38817,-38776,-38736,
947     -38695,-38655,-38614,-38573,-38533,-38492,-38451,-38411,
948     -38370,-38329,-38288,-38248,-38207,-38166,-38125,-38084,
949     -38043,-38002,-37961,-37920,-37879,-37838,-37797,-37756,
950     -37715,-37674,-37633,-37592,-37550,-37509,-37468,-37427,
951     -37386,-37344,-37303,-37262,-37220,-37179,-37137,-37096,
952     -37055,-37013,-36972,-36930,-36889,-36847,-36805,-36764,
953     -36722,-36681,-36639,-36597,-36556,-36514,-36472,-36430,
954     -36388,-36347,-36305,-36263,-36221,-36179,-36137,-36095,
955     -36053,-36011,-35969,-35927,-35885,-35843,-35801,-35759,
956     -35717,-35675,-35633,-35590,-35548,-35506,-35464,-35421,
957     -35379,-35337,-35294,-35252,-35210,-35167,-35125,-35082,
958     -35040,-34997,-34955,-34912,-34870,-34827,-34785,-34742,
959     -34699,-34657,-34614,-34571,-34529,-34486,-34443,-34400,
960     -34358,-34315,-34272,-34229,-34186,-34143,-34100,-34057,
961     -34015,-33972,-33929,-33886,-33843,-33799,-33756,-33713,
962     -33670,-33627,-33584,-33541,-33498,-33454,-33411,-33368,
963     -33325,-33281,-33238,-33195,-33151,-33108,-33065,-33021,
964     -32978,-32934,-32891,-32847,-32804,-32760,-32717,-32673,
965     -32630,-32586,-32542,-32499,-32455,-32411,-32368,-32324,
966     -32280,-32236,-32193,-32149,-32105,-32061,-32017,-31974,
967     -31930,-31886,-31842,-31798,-31754,-31710,-31666,-31622,
968     -31578,-31534,-31490,-31446,-31402,-31357,-31313,-31269,
969     -31225,-31181,-31136,-31092,-31048,-31004,-30959,-30915,
970     -30871,-30826,-30782,-30738,-30693,-30649,-30604,-30560,
971     -30515,-30471,-30426,-30382,-30337,-30293,-30248,-30204,
972     -30159,-30114,-30070,-30025,-29980,-29936,-29891,-29846,
973     -29801,-29757,-29712,-29667,-29622,-29577,-29533,-29488,
974     -29443,-29398,-29353,-29308,-29263,-29218,-29173,-29128,
975     -29083,-29038,-28993,-28948,-28903,-28858,-28812,-28767,
976     -28722,-28677,-28632,-28586,-28541,-28496,-28451,-28405,
977     -28360,-28315,-28269,-28224,-28179,-28133,-28088,-28042,
978     -27997,-27952,-27906,-27861,-27815,-27770,-27724,-27678,
979     -27633,-27587,-27542,-27496,-27450,-27405,-27359,-27313,
980     -27268,-27222,-27176,-27131,-27085,-27039,-26993,-26947,
981     -26902,-26856,-26810,-26764,-26718,-26672,-26626,-26580,
982     -26534,-26488,-26442,-26396,-26350,-26304,-26258,-26212,
983     -26166,-26120,-26074,-26028,-25982,-25936,-25889,-25843,
984     -25797,-25751,-25705,-25658,-25612,-25566,-25520,-25473,
985     -25427,-25381,-25334,-25288,-25241,-25195,-25149,-25102,
986     -25056,-25009,-24963,-24916,-24870,-24823,-24777,-24730,
987     -24684,-24637,-24591,-24544,-24497,-24451,-24404,-24357,
988     -24311,-24264,-24217,-24171,-24124,-24077,-24030,-23984,
989     -23937,-23890,-23843,-23796,-23750,-23703,-23656,-23609,
990     -23562,-23515,-23468,-23421,-23374,-23327,-23280,-23233,
991     -23186,-23139,-23092,-23045,-22998,-22951,-22904,-22857,
992     -22810,-22763,-22716,-22668,-22621,-22574,-22527,-22480,
993     -22432,-22385,-22338,-22291,-22243,-22196,-22149,-22102,
994     -22054,-22007,-21960,-21912,-21865,-21817,-21770,-21723,
995     -21675,-21628,-21580,-21533,-21485,-21438,-21390,-21343,
996     -21295,-21248,-21200,-21153,-21105,-21057,-21010,-20962,
997     -20915,-20867,-20819,-20772,-20724,-20676,-20629,-20581,
998     -20533,-20485,-20438,-20390,-20342,-20294,-20246,-20199,
999     -20151,-20103,-20055,-20007,-19959,-19912,-19864,-19816,
1000     -19768,-19720,-19672,-19624,-19576,-19528,-19480,-19432,
1001     -19384,-19336,-19288,-19240,-19192,-19144,-19096,-19048,
1002     -19000,-18951,-18903,-18855,-18807,-18759,-18711,-18663,
1003     -18614,-18566,-18518,-18470,-18421,-18373,-18325,-18277,
1004     -18228,-18180,-18132,-18084,-18035,-17987,-17939,-17890,
1005     -17842,-17793,-17745,-17697,-17648,-17600,-17551,-17503,
1006     -17455,-17406,-17358,-17309,-17261,-17212,-17164,-17115,
1007     -17067,-17018,-16970,-16921,-16872,-16824,-16775,-16727,
1008     -16678,-16629,-16581,-16532,-16484,-16435,-16386,-16338,
1009     -16289,-16240,-16191,-16143,-16094,-16045,-15997,-15948,
1010     -15899,-15850,-15802,-15753,-15704,-15655,-15606,-15557,
1011     -15509,-15460,-15411,-15362,-15313,-15264,-15215,-15167,
1012     -15118,-15069,-15020,-14971,-14922,-14873,-14824,-14775,
1013     -14726,-14677,-14628,-14579,-14530,-14481,-14432,-14383,
1014     -14334,-14285,-14236,-14187,-14138,-14089,-14040,-13990,
1015     -13941,-13892,-13843,-13794,-13745,-13696,-13647,-13597,
1016     -13548,-13499,-13450,-13401,-13351,-13302,-13253,-13204,
1017     -13154,-13105,-13056,-13007,-12957,-12908,-12859,-12810,
1018     -12760,-12711,-12662,-12612,-12563,-12514,-12464,-12415,
1019     -12366,-12316,-12267,-12217,-12168,-12119,-12069,-12020,
1020     -11970,-11921,-11872,-11822,-11773,-11723,-11674,-11624,
1021     -11575,-11525,-11476,-11426,-11377,-11327,-11278,-11228,
1022     -11179,-11129,-11080,-11030,-10981,-10931,-10882,-10832,
1023     -10782,-10733,-10683,-10634,-10584,-10534,-10485,-10435,
1024     -10386,-10336,-10286,-10237,-10187,-10137,-10088,-10038,
1025     -9988,-9939,-9889,-9839,-9790,-9740,-9690,-9640,
1026     -9591,-9541,-9491,-9442,-9392,-9342,-9292,-9243,
1027     -9193,-9143,-9093,-9043,-8994,-8944,-8894,-8844,
1028     -8794,-8745,-8695,-8645,-8595,-8545,-8496,-8446,
1029     -8396,-8346,-8296,-8246,-8196,-8147,-8097,-8047,
1030     -7997,-7947,-7897,-7847,-7797,-7747,-7697,-7648,
1031     -7598,-7548,-7498,-7448,-7398,-7348,-7298,-7248,
1032     -7198,-7148,-7098,-7048,-6998,-6948,-6898,-6848,
1033     -6798,-6748,-6698,-6648,-6598,-6548,-6498,-6448,
1034     -6398,-6348,-6298,-6248,-6198,-6148,-6098,-6048,
1035     -5998,-5948,-5898,-5848,-5798,-5747,-5697,-5647,
1036     -5597,-5547,-5497,-5447,-5397,-5347,-5297,-5247,
1037     -5197,-5146,-5096,-5046,-4996,-4946,-4896,-4846,
1038     -4796,-4745,-4695,-4645,-4595,-4545,-4495,-4445,
1039     -4394,-4344,-4294,-4244,-4194,-4144,-4093,-4043,
1040     -3993,-3943,-3893,-3843,-3792,-3742,-3692,-3642,
1041     -3592,-3541,-3491,-3441,-3391,-3341,-3291,-3240,
1042     -3190,-3140,-3090,-3039,-2989,-2939,-2889,-2839,
1043     -2788,-2738,-2688,-2638,-2588,-2537,-2487,-2437,
1044     -2387,-2336,-2286,-2236,-2186,-2135,-2085,-2035,
1045     -1985,-1934,-1884,-1834,-1784,-1733,-1683,-1633,
1046     -1583,-1532,-1482,-1432,-1382,-1331,-1281,-1231,
1047     -1181,-1130,-1080,-1030,-980,-929,-879,-829,
1048     -779,-728,-678,-628,-578,-527,-477,-427,
1049     -376,-326,-276,-226,-175,-125,-75,-25,
1050     25,75,125,175,226,276,326,376,
1051     427,477,527,578,628,678,728,779,
1052     829,879,929,980,1030,1080,1130,1181,
1053     1231,1281,1331,1382,1432,1482,1532,1583,
1054     1633,1683,1733,1784,1834,1884,1934,1985,
1055     2035,2085,2135,2186,2236,2286,2336,2387,
1056     2437,2487,2537,2587,2638,2688,2738,2788,
1057     2839,2889,2939,2989,3039,3090,3140,3190,
1058     3240,3291,3341,3391,3441,3491,3542,3592,
1059     3642,3692,3742,3792,3843,3893,3943,3993,
1060     4043,4093,4144,4194,4244,4294,4344,4394,
1061     4445,4495,4545,4595,4645,4695,4745,4796,
1062     4846,4896,4946,4996,5046,5096,5146,5197,
1063     5247,5297,5347,5397,5447,5497,5547,5597,
1064     5647,5697,5747,5798,5848,5898,5948,5998,
1065     6048,6098,6148,6198,6248,6298,6348,6398,
1066     6448,6498,6548,6598,6648,6698,6748,6798,
1067     6848,6898,6948,6998,7048,7098,7148,7198,
1068     7248,7298,7348,7398,7448,7498,7548,7598,
1069     7648,7697,7747,7797,7847,7897,7947,7997,
1070     8047,8097,8147,8196,8246,8296,8346,8396,
1071     8446,8496,8545,8595,8645,8695,8745,8794,
1072     8844,8894,8944,8994,9043,9093,9143,9193,
1073     9243,9292,9342,9392,9442,9491,9541,9591,
1074     9640,9690,9740,9790,9839,9889,9939,9988,
1075     10038,10088,10137,10187,10237,10286,10336,10386,
1076     10435,10485,10534,10584,10634,10683,10733,10782,
1077     10832,10882,10931,10981,11030,11080,11129,11179,
1078     11228,11278,11327,11377,11426,11476,11525,11575,
1079     11624,11674,11723,11773,11822,11872,11921,11970,
1080     12020,12069,12119,12168,12218,12267,12316,12366,
1081     12415,12464,12514,12563,12612,12662,12711,12760,
1082     12810,12859,12908,12957,13007,13056,13105,13154,
1083     13204,13253,13302,13351,13401,13450,13499,13548,
1084     13597,13647,13696,13745,13794,13843,13892,13941,
1085     13990,14040,14089,14138,14187,14236,14285,14334,
1086     14383,14432,14481,14530,14579,14628,14677,14726,
1087     14775,14824,14873,14922,14971,15020,15069,15118,
1088     15167,15215,15264,15313,15362,15411,15460,15509,
1089     15557,15606,15655,15704,15753,15802,15850,15899,
1090     15948,15997,16045,16094,16143,16191,16240,16289,
1091     16338,16386,16435,16484,16532,16581,16629,16678,
1092     16727,16775,16824,16872,16921,16970,17018,17067,
1093     17115,17164,17212,17261,17309,17358,17406,17455,
1094     17503,17551,17600,17648,17697,17745,17793,17842,
1095     17890,17939,17987,18035,18084,18132,18180,18228,
1096     18277,18325,18373,18421,18470,18518,18566,18614,
1097     18663,18711,18759,18807,18855,18903,18951,19000,
1098     19048,19096,19144,19192,19240,19288,19336,19384,
1099     19432,19480,19528,19576,19624,19672,19720,19768,
1100     19816,19864,19912,19959,20007,20055,20103,20151,
1101     20199,20246,20294,20342,20390,20438,20485,20533,
1102     20581,20629,20676,20724,20772,20819,20867,20915,
1103     20962,21010,21057,21105,21153,21200,21248,21295,
1104     21343,21390,21438,21485,21533,21580,21628,21675,
1105     21723,21770,21817,21865,21912,21960,22007,22054,
1106     22102,22149,22196,22243,22291,22338,22385,22432,
1107     22480,22527,22574,22621,22668,22716,22763,22810,
1108     22857,22904,22951,22998,23045,23092,23139,23186,
1109     23233,23280,23327,23374,23421,23468,23515,23562,
1110     23609,23656,23703,23750,23796,23843,23890,23937,
1111     23984,24030,24077,24124,24171,24217,24264,24311,
1112     24357,24404,24451,24497,24544,24591,24637,24684,
1113     24730,24777,24823,24870,24916,24963,25009,25056,
1114     25102,25149,25195,25241,25288,25334,25381,25427,
1115     25473,25520,25566,25612,25658,25705,25751,25797,
1116     25843,25889,25936,25982,26028,26074,26120,26166,
1117     26212,26258,26304,26350,26396,26442,26488,26534,
1118     26580,26626,26672,26718,26764,26810,26856,26902,
1119     26947,26993,27039,27085,27131,27176,27222,27268,
1120     27313,27359,27405,27450,27496,27542,27587,27633,
1121     27678,27724,27770,27815,27861,27906,27952,27997,
1122     28042,28088,28133,28179,28224,28269,28315,28360,
1123     28405,28451,28496,28541,28586,28632,28677,28722,
1124     28767,28812,28858,28903,28948,28993,29038,29083,
1125     29128,29173,29218,29263,29308,29353,29398,29443,
1126     29488,29533,29577,29622,29667,29712,29757,29801,
1127     29846,29891,29936,29980,30025,30070,30114,30159,
1128     30204,30248,30293,30337,30382,30427,30471,30516,
1129     30560,30604,30649,30693,30738,30782,30826,30871,
1130     30915,30959,31004,31048,31092,31136,31181,31225,
1131     31269,31313,31357,31402,31446,31490,31534,31578,
1132     31622,31666,31710,31754,31798,31842,31886,31930,
1133     31974,32017,32061,32105,32149,32193,32236,32280,
1134     32324,32368,32411,32455,32499,32542,32586,32630,
1135     32673,32717,32760,32804,32847,32891,32934,32978,
1136     33021,33065,33108,33151,33195,33238,33281,33325,
1137     33368,33411,33454,33498,33541,33584,33627,33670,
1138     33713,33756,33799,33843,33886,33929,33972,34015,
1139     34057,34100,34143,34186,34229,34272,34315,34358,
1140     34400,34443,34486,34529,34571,34614,34657,34699,
1141     34742,34785,34827,34870,34912,34955,34997,35040,
1142     35082,35125,35167,35210,35252,35294,35337,35379,
1143     35421,35464,35506,35548,35590,35633,35675,35717,
1144     35759,35801,35843,35885,35927,35969,36011,36053,
1145     36095,36137,36179,36221,36263,36305,36347,36388,
1146     36430,36472,36514,36556,36597,36639,36681,36722,
1147     36764,36805,36847,36889,36930,36972,37013,37055,
1148     37096,37137,37179,37220,37262,37303,37344,37386,
1149     37427,37468,37509,37551,37592,37633,37674,37715,
1150     37756,37797,37838,37879,37920,37961,38002,38043,
1151     38084,38125,38166,38207,38248,38288,38329,38370,
1152     38411,38451,38492,38533,38573,38614,38655,38695,
1153     38736,38776,38817,38857,38898,38938,38979,39019,
1154     39059,39100,39140,39180,39221,39261,39301,39341,
1155     39382,39422,39462,39502,39542,39582,39622,39662,
1156     39702,39742,39782,39822,39862,39902,39942,39982,
1157     40021,40061,40101,40141,40180,40220,40260,40299,
1158     40339,40379,40418,40458,40497,40537,40576,40616,
1159     40655,40695,40734,40773,40813,40852,40891,40931,
1160     40970,41009,41048,41087,41127,41166,41205,41244,
1161     41283,41322,41361,41400,41439,41478,41517,41556,
1162     41595,41633,41672,41711,41750,41788,41827,41866,
1163     41904,41943,41982,42020,42059,42097,42136,42174,
1164     42213,42251,42290,42328,42366,42405,42443,42481,
1165     42520,42558,42596,42634,42672,42711,42749,42787,
1166     42825,42863,42901,42939,42977,43015,43053,43091,
1167     43128,43166,43204,43242,43280,43317,43355,43393,
1168     43430,43468,43506,43543,43581,43618,43656,43693,
1169     43731,43768,43806,43843,43880,43918,43955,43992,
1170     44029,44067,44104,44141,44178,44215,44252,44289,
1171     44326,44363,44400,44437,44474,44511,44548,44585,
1172     44622,44659,44695,44732,44769,44806,44842,44879,
1173     44915,44952,44989,45025,45062,45098,45135,45171,
1174     45207,45244,45280,45316,45353,45389,45425,45462,
1175     45498,45534,45570,45606,45642,45678,45714,45750,
1176     45786,45822,45858,45894,45930,45966,46002,46037,
1177     46073,46109,46145,46180,46216,46252,46287,46323,
1178     46358,46394,46429,46465,46500,46536,46571,46606,
1179     46642,46677,46712,46747,46783,46818,46853,46888,
1180     46923,46958,46993,47028,47063,47098,47133,47168,
1181     47203,47238,47273,47308,47342,47377,47412,47446,
1182     47481,47516,47550,47585,47619,47654,47688,47723,
1183     47757,47792,47826,47861,47895,47929,47963,47998,
1184     48032,48066,48100,48134,48168,48202,48237,48271,
1185     48305,48338,48372,48406,48440,48474,48508,48542,
1186     48575,48609,48643,48676,48710,48744,48777,48811,
1187     48844,48878,48911,48945,48978,49012,49045,49078,
1188     49112,49145,49178,49211,49244,49278,49311,49344,
1189     49377,49410,49443,49476,49509,49542,49575,49608,
1190     49640,49673,49706,49739,49771,49804,49837,49869,
1191     49902,49935,49967,50000,50032,50064,50097,50129,
1192     50162,50194,50226,50259,50291,50323,50355,50387,
1193     50420,50452,50484,50516,50548,50580,50612,50644,
1194     50675,50707,50739,50771,50803,50834,50866,50898,
1195     50929,50961,50993,51024,51056,51087,51119,51150,
1196     51182,51213,51244,51276,51307,51338,51369,51401,
1197     51432,51463,51494,51525,51556,51587,51618,51649,
1198     51680,51711,51742,51773,51803,51834,51865,51896,
1199     51926,51957,51988,52018,52049,52079,52110,52140,
1200     52171,52201,52231,52262,52292,52322,52353,52383,
1201     52413,52443,52473,52503,52534,52564,52594,52624,
1202     52653,52683,52713,52743,52773,52803,52832,52862,
1203     52892,52922,52951,52981,53010,53040,53069,53099,
1204     53128,53158,53187,53216,53246,53275,53304,53334,
1205     53363,53392,53421,53450,53479,53508,53537,53566,
1206     53595,53624,53653,53682,53711,53739,53768,53797,
1207     53826,53854,53883,53912,53940,53969,53997,54026,
1208     54054,54082,54111,54139,54167,54196,54224,54252,
1209     54280,54309,54337,54365,54393,54421,54449,54477,
1210     54505,54533,54560,54588,54616,54644,54672,54699,
1211     54727,54755,54782,54810,54837,54865,54892,54920,
1212     54947,54974,55002,55029,55056,55084,55111,55138,
1213     55165,55192,55219,55246,55274,55300,55327,55354,
1214     55381,55408,55435,55462,55489,55515,55542,55569,
1215     55595,55622,55648,55675,55701,55728,55754,55781,
1216     55807,55833,55860,55886,55912,55938,55965,55991,
1217     56017,56043,56069,56095,56121,56147,56173,56199,
1218     56225,56250,56276,56302,56328,56353,56379,56404,
1219     56430,56456,56481,56507,56532,56557,56583,56608,
1220     56633,56659,56684,56709,56734,56760,56785,56810,
1221     56835,56860,56885,56910,56935,56959,56984,57009,
1222     57034,57059,57083,57108,57133,57157,57182,57206,
1223     57231,57255,57280,57304,57329,57353,57377,57402,
1224     57426,57450,57474,57498,57522,57546,57570,57594,
1225     57618,57642,57666,57690,57714,57738,57762,57785,
1226     57809,57833,57856,57880,57903,57927,57950,57974,
1227     57997,58021,58044,58067,58091,58114,58137,58160,
1228     58183,58207,58230,58253,58276,58299,58322,58345,
1229     58367,58390,58413,58436,58459,58481,58504,58527,
1230     58549,58572,58594,58617,58639,58662,58684,58706,
1231     58729,58751,58773,58795,58818,58840,58862,58884,
1232     58906,58928,58950,58972,58994,59016,59038,59059,
1233     59081,59103,59125,59146,59168,59190,59211,59233,
1234     59254,59276,59297,59318,59340,59361,59382,59404,
1235     59425,59446,59467,59488,59509,59530,59551,59572,
1236     59593,59614,59635,59656,59677,59697,59718,59739,
1237     59759,59780,59801,59821,59842,59862,59883,59903,
1238     59923,59944,59964,59984,60004,60025,60045,60065,
1239     60085,60105,60125,60145,60165,60185,60205,60225,
1240     60244,60264,60284,60304,60323,60343,60363,60382,
1241     60402,60421,60441,60460,60479,60499,60518,60537,
1242     60556,60576,60595,60614,60633,60652,60671,60690,
1243     60709,60728,60747,60766,60785,60803,60822,60841,
1244     60859,60878,60897,60915,60934,60952,60971,60989,
1245     61007,61026,61044,61062,61081,61099,61117,61135,
1246     61153,61171,61189,61207,61225,61243,61261,61279,
1247     61297,61314,61332,61350,61367,61385,61403,61420,
1248     61438,61455,61473,61490,61507,61525,61542,61559,
1249     61577,61594,61611,61628,61645,61662,61679,61696,
1250     61713,61730,61747,61764,61780,61797,61814,61831,
1251     61847,61864,61880,61897,61913,61930,61946,61963,
1252     61979,61995,62012,62028,62044,62060,62076,62092,
1253     62108,62125,62141,62156,62172,62188,62204,62220,
1254     62236,62251,62267,62283,62298,62314,62329,62345,
1255     62360,62376,62391,62407,62422,62437,62453,62468,
1256     62483,62498,62513,62528,62543,62558,62573,62588,
1257     62603,62618,62633,62648,62662,62677,62692,62706,
1258     62721,62735,62750,62764,62779,62793,62808,62822,
1259     62836,62850,62865,62879,62893,62907,62921,62935,
1260     62949,62963,62977,62991,63005,63019,63032,63046,
1261     63060,63074,63087,63101,63114,63128,63141,63155,
1262     63168,63182,63195,63208,63221,63235,63248,63261,
1263     63274,63287,63300,63313,63326,63339,63352,63365,
1264     63378,63390,63403,63416,63429,63441,63454,63466,
1265     63479,63491,63504,63516,63528,63541,63553,63565,
1266     63578,63590,63602,63614,63626,63638,63650,63662,
1267     63674,63686,63698,63709,63721,63733,63745,63756,
1268     63768,63779,63791,63803,63814,63825,63837,63848,
1269     63859,63871,63882,63893,63904,63915,63927,63938,
1270     63949,63960,63971,63981,63992,64003,64014,64025,
1271     64035,64046,64057,64067,64078,64088,64099,64109,
1272     64120,64130,64140,64151,64161,64171,64181,64192,
1273     64202,64212,64222,64232,64242,64252,64261,64271,
1274     64281,64291,64301,64310,64320,64330,64339,64349,
1275     64358,64368,64377,64387,64396,64405,64414,64424,
1276     64433,64442,64451,64460,64469,64478,64487,64496,
1277     64505,64514,64523,64532,64540,64549,64558,64566,
1278     64575,64584,64592,64600,64609,64617,64626,64634,
1279     64642,64651,64659,64667,64675,64683,64691,64699,
1280     64707,64715,64723,64731,64739,64747,64754,64762,
1281     64770,64777,64785,64793,64800,64808,64815,64822,
1282     64830,64837,64844,64852,64859,64866,64873,64880,
1283     64887,64895,64902,64908,64915,64922,64929,64936,
1284     64943,64949,64956,64963,64969,64976,64982,64989,
1285     64995,65002,65008,65015,65021,65027,65033,65040,
1286     65046,65052,65058,65064,65070,65076,65082,65088,
1287     65094,65099,65105,65111,65117,65122,65128,65133,
1288     65139,65144,65150,65155,65161,65166,65171,65177,
1289     65182,65187,65192,65197,65202,65207,65212,65217,
1290     65222,65227,65232,65237,65242,65246,65251,65256,
1291     65260,65265,65270,65274,65279,65283,65287,65292,
1292     65296,65300,65305,65309,65313,65317,65321,65325,
1293     65329,65333,65337,65341,65345,65349,65352,65356,
1294     65360,65363,65367,65371,65374,65378,65381,65385,
1295     65388,65391,65395,65398,65401,65404,65408,65411,
1296     65414,65417,65420,65423,65426,65429,65431,65434,
1297     65437,65440,65442,65445,65448,65450,65453,65455,
1298     65458,65460,65463,65465,65467,65470,65472,65474,
1299     65476,65478,65480,65482,65484,65486,65488,65490,
1300     65492,65494,65496,65497,65499,65501,65502,65504,
1301     65505,65507,65508,65510,65511,65513,65514,65515,
1302     65516,65518,65519,65520,65521,65522,65523,65524,
1303     65525,65526,65527,65527,65528,65529,65530,65530,
1304     65531,65531,65532,65532,65533,65533,65534,65534,
1305     65534,65535,65535,65535,65535,65535,65535,65535
1306 };
1307 
1308 static int tantoangle[2049] =
1309 {
1310     0,333772,667544,1001315,1335086,1668857,2002626,2336395,
1311     2670163,3003929,3337694,3671457,4005219,4338979,4672736,5006492,
1312     5340245,5673995,6007743,6341488,6675230,7008968,7342704,7676435,
1313     8010164,8343888,8677609,9011325,9345037,9678744,10012447,10346145,
1314     10679838,11013526,11347209,11680887,12014558,12348225,12681885,13015539,
1315     13349187,13682829,14016464,14350092,14683714,15017328,15350936,15684536,
1316     16018129,16351714,16685291,17018860,17352422,17685974,18019518,18353054,
1317     18686582,19020100,19353610,19687110,20020600,20354080,20687552,21021014,
1318     21354466,21687906,22021338,22354758,22688168,23021568,23354956,23688332,
1319     24021698,24355052,24688396,25021726,25355046,25688352,26021648,26354930,
1320     26688200,27021456,27354702,27687932,28021150,28354356,28687548,29020724,
1321     29353888,29687038,30020174,30353296,30686404,31019496,31352574,31685636,
1322     32018684,32351718,32684734,33017736,33350722,33683692,34016648,34349584,
1323     34682508,35015412,35348300,35681172,36014028,36346868,36679688,37012492,
1324     37345276,37678044,38010792,38343524,38676240,39008936,39341612,39674272,
1325     40006912,40339532,40672132,41004716,41337276,41669820,42002344,42334848,
1326     42667332,42999796,43332236,43664660,43997060,44329444,44661800,44994140,
1327     45326456,45658752,45991028,46323280,46655512,46987720,47319908,47652072,
1328     47984212,48316332,48648428,48980500,49312548,49644576,49976580,50308556,
1329     50640512,50972444,51304352,51636236,51968096,52299928,52631740,52963524,
1330     53295284,53627020,53958728,54290412,54622068,54953704,55285308,55616888,
1331     55948444,56279972,56611472,56942948,57274396,57605816,57937212,58268576,
1332     58599916,58931228,59262512,59593768,59924992,60256192,60587364,60918508,
1333     61249620,61580704,61911760,62242788,62573788,62904756,63235692,63566604,
1334     63897480,64228332,64559148,64889940,65220696,65551424,65882120,66212788,
1335     66543420,66874024,67204600,67535136,67865648,68196120,68526568,68856984,
1336     69187360,69517712,69848024,70178304,70508560,70838776,71168960,71499112,
1337     71829224,72159312,72489360,72819376,73149360,73479304,73809216,74139096,
1338     74468936,74798744,75128520,75458264,75787968,76117632,76447264,76776864,
1339     77106424,77435952,77765440,78094888,78424304,78753688,79083032,79412336,
1340     79741608,80070840,80400032,80729192,81058312,81387392,81716432,82045440,
1341     82374408,82703336,83032224,83361080,83689896,84018664,84347400,84676096,
1342     85004760,85333376,85661952,85990488,86318984,86647448,86975864,87304240,
1343     87632576,87960872,88289128,88617344,88945520,89273648,89601736,89929792,
1344     90257792,90585760,90913688,91241568,91569408,91897200,92224960,92552672,
1345     92880336,93207968,93535552,93863088,94190584,94518040,94845448,95172816,
1346     95500136,95827416,96154648,96481832,96808976,97136080,97463136,97790144,
1347     98117112,98444032,98770904,99097736,99424520,99751256,100077944,100404592,
1348     100731192,101057744,101384248,101710712,102037128,102363488,102689808,103016080,
1349     103342312,103668488,103994616,104320696,104646736,104972720,105298656,105624552,
1350     105950392,106276184,106601928,106927624,107253272,107578872,107904416,108229920,
1351     108555368,108880768,109206120,109531416,109856664,110181872,110507016,110832120,
1352     111157168,111482168,111807112,112132008,112456856,112781648,113106392,113431080,
1353     113755720,114080312,114404848,114729328,115053760,115378136,115702464,116026744,
1354     116350960,116675128,116999248,117323312,117647320,117971272,118295176,118619024,
1355     118942816,119266560,119590248,119913880,120237456,120560984,120884456,121207864,
1356     121531224,121854528,122177784,122500976,122824112,123147200,123470224,123793200,
1357     124116120,124438976,124761784,125084528,125407224,125729856,126052432,126374960,
1358     126697424,127019832,127342184,127664472,127986712,128308888,128631008,128953072,
1359     129275080,129597024,129918912,130240744,130562520,130884232,131205888,131527480,
1360     131849016,132170496,132491912,132813272,133134576,133455816,133776992,134098120,
1361     134419184,134740176,135061120,135382000,135702816,136023584,136344272,136664912,
1362     136985488,137306016,137626464,137946864,138267184,138587456,138907664,139227808,
1363     139547904,139867920,140187888,140507776,140827616,141147392,141467104,141786752,
1364     142106336,142425856,142745312,143064720,143384048,143703312,144022512,144341664,
1365     144660736,144979744,145298704,145617584,145936400,146255168,146573856,146892480,
1366     147211040,147529536,147847968,148166336,148484640,148802880,149121056,149439152,
1367     149757200,150075168,150393072,150710912,151028688,151346400,151664048,151981616,
1368     152299136,152616576,152933952,153251264,153568496,153885680,154202784,154519824,
1369     154836784,155153696,155470528,155787296,156104000,156420624,156737200,157053696,
1370     157370112,157686480,158002768,158318976,158635136,158951216,159267232,159583168,
1371     159899040,160214848,160530592,160846256,161161840,161477376,161792832,162108208,
1372     162423520,162738768,163053952,163369040,163684080,163999040,164313936,164628752,
1373     164943504,165258176,165572784,165887312,166201776,166516160,166830480,167144736,
1374     167458912,167773008,168087040,168400992,168714880,169028688,169342432,169656096,
1375     169969696,170283216,170596672,170910032,171223344,171536576,171849728,172162800,
1376     172475808,172788736,173101600,173414384,173727104,174039728,174352288,174664784,
1377     174977200,175289536,175601792,175913984,176226096,176538144,176850096,177161984,
1378     177473792,177785536,178097200,178408784,178720288,179031728,179343088,179654368,
1379     179965568,180276704,180587744,180898720,181209616,181520448,181831184,182141856,
1380     182452448,182762960,183073408,183383760,183694048,184004240,184314368,184624416,
1381     184934400,185244288,185554096,185863840,186173504,186483072,186792576,187102000,
1382     187411344,187720608,188029808,188338912,188647936,188956896,189265760,189574560,
1383     189883264,190191904,190500448,190808928,191117312,191425632,191733872,192042016,
1384     192350096,192658096,192966000,193273840,193581584,193889264,194196848,194504352,
1385     194811792,195119136,195426400,195733584,196040688,196347712,196654656,196961520,
1386     197268304,197574992,197881616,198188144,198494592,198800960,199107248,199413456,
1387     199719584,200025616,200331584,200637456,200943248,201248960,201554576,201860128,
1388     202165584,202470960,202776256,203081456,203386592,203691632,203996592,204301472,
1389     204606256,204910976,205215600,205520144,205824592,206128960,206433248,206737456,
1390     207041584,207345616,207649568,207953424,208257216,208560912,208864512,209168048,
1391     209471488,209774832,210078112,210381296,210684384,210987408,211290336,211593184,
1392     211895936,212198608,212501184,212803680,213106096,213408432,213710672,214012816,
1393     214314880,214616864,214918768,215220576,215522288,215823920,216125472,216426928,
1394     216728304,217029584,217330784,217631904,217932928,218233856,218534704,218835472,
1395     219136144,219436720,219737216,220037632,220337952,220638192,220938336,221238384,
1396     221538352,221838240,222138032,222437728,222737344,223036880,223336304,223635664,
1397     223934912,224234096,224533168,224832160,225131072,225429872,225728608,226027232,
1398     226325776,226624240,226922608,227220880,227519056,227817152,228115168,228413088,
1399     228710912,229008640,229306288,229603840,229901312,230198688,230495968,230793152,
1400     231090256,231387280,231684192,231981024,232277760,232574416,232870960,233167440,
1401     233463808,233760096,234056288,234352384,234648384,234944304,235240128,235535872,
1402     235831504,236127056,236422512,236717888,237013152,237308336,237603424,237898416,
1403     238193328,238488144,238782864,239077488,239372016,239666464,239960816,240255072,
1404     240549232,240843312,241137280,241431168,241724960,242018656,242312256,242605776,
1405     242899200,243192512,243485744,243778896,244071936,244364880,244657744,244950496,
1406     245243168,245535744,245828224,246120608,246412912,246705104,246997216,247289216,
1407     247581136,247872960,248164688,248456320,248747856,249039296,249330640,249621904,
1408     249913056,250204128,250495088,250785968,251076736,251367424,251658016,251948512,
1409     252238912,252529200,252819408,253109520,253399536,253689456,253979280,254269008,
1410     254558640,254848176,255137632,255426976,255716224,256005376,256294432,256583392,
1411     256872256,257161024,257449696,257738272,258026752,258315136,258603424,258891600,
1412     259179696,259467696,259755600,260043392,260331104,260618704,260906224,261193632,
1413     261480960,261768176,262055296,262342320,262629248,262916080,263202816,263489456,
1414     263776000,264062432,264348784,264635024,264921168,265207216,265493168,265779024,
1415     266064784,266350448,266636000,266921472,267206832,267492096,267777264,268062336,
1416     268347312,268632192,268916960,269201632,269486208,269770688,270055072,270339360,
1417     270623552,270907616,271191616,271475488,271759296,272042976,272326560,272610048,
1418     272893440,273176736,273459936,273743040,274026048,274308928,274591744,274874432,
1419     275157024,275439520,275721920,276004224,276286432,276568512,276850528,277132416,
1420     277414240,277695936,277977536,278259040,278540448,278821728,279102944,279384032,
1421     279665056,279945952,280226752,280507456,280788064,281068544,281348960,281629248,
1422     281909472,282189568,282469568,282749440,283029248,283308960,283588544,283868032,
1423     284147424,284426720,284705920,284985024,285264000,285542912,285821696,286100384,
1424     286378976,286657440,286935840,287214112,287492320,287770400,288048384,288326240,
1425     288604032,288881696,289159264,289436768,289714112,289991392,290268576,290545632,
1426     290822592,291099456,291376224,291652896,291929440,292205888,292482272,292758528,
1427     293034656,293310720,293586656,293862496,294138240,294413888,294689440,294964864,
1428     295240192,295515424,295790560,296065600,296340512,296615360,296890080,297164704,
1429     297439200,297713632,297987936,298262144,298536256,298810240,299084160,299357952,
1430     299631648,299905248,300178720,300452128,300725408,300998592,301271680,301544640,
1431     301817536,302090304,302362976,302635520,302908000,303180352,303452608,303724768,
1432     303996800,304268768,304540608,304812320,305083968,305355520,305626944,305898272,
1433     306169472,306440608,306711616,306982528,307253344,307524064,307794656,308065152,
1434     308335552,308605856,308876032,309146112,309416096,309685984,309955744,310225408,
1435     310494976,310764448,311033824,311303072,311572224,311841280,312110208,312379040,
1436     312647776,312916416,313184960,313453376,313721696,313989920,314258016,314526016,
1437     314793920,315061728,315329408,315597024,315864512,316131872,316399168,316666336,
1438     316933408,317200384,317467232,317733984,318000640,318267200,318533632,318799968,
1439     319066208,319332352,319598368,319864288,320130112,320395808,320661408,320926912,
1440     321192320,321457632,321722816,321987904,322252864,322517760,322782528,323047200,
1441     323311744,323576192,323840544,324104800,324368928,324632992,324896928,325160736,
1442     325424448,325688096,325951584,326215008,326478304,326741504,327004608,327267584,
1443     327530464,327793248,328055904,328318496,328580960,328843296,329105568,329367712,
1444     329629760,329891680,330153536,330415264,330676864,330938400,331199808,331461120,
1445     331722304,331983392,332244384,332505280,332766048,333026752,333287296,333547776,
1446     333808128,334068384,334328544,334588576,334848512,335108352,335368064,335627712,
1447     335887200,336146624,336405920,336665120,336924224,337183200,337442112,337700864,
1448     337959552,338218112,338476576,338734944,338993184,339251328,339509376,339767296,
1449     340025120,340282848,340540480,340797984,341055392,341312704,341569888,341826976,
1450     342083968,342340832,342597600,342854272,343110848,343367296,343623648,343879904,
1451     344136032,344392064,344648000,344903808,345159520,345415136,345670656,345926048,
1452     346181344,346436512,346691616,346946592,347201440,347456224,347710880,347965440,
1453     348219872,348474208,348728448,348982592,349236608,349490528,349744320,349998048,
1454     350251648,350505152,350758528,351011808,351264992,351518048,351771040,352023872,
1455     352276640,352529280,352781824,353034272,353286592,353538816,353790944,354042944,
1456     354294880,354546656,354798368,355049952,355301440,355552800,355804096,356055264,
1457     356306304,356557280,356808128,357058848,357309504,357560032,357810464,358060768,
1458     358311008,358561088,358811104,359060992,359310784,359560480,359810048,360059520,
1459     360308896,360558144,360807296,361056352,361305312,361554144,361802880,362051488,
1460     362300032,362548448,362796736,363044960,363293056,363541024,363788928,364036704,
1461     364284384,364531936,364779392,365026752,365274016,365521152,365768192,366015136,
1462     366261952,366508672,366755296,367001792,367248192,367494496,367740704,367986784,
1463     368232768,368478656,368724416,368970080,369215648,369461088,369706432,369951680,
1464     370196800,370441824,370686752,370931584,371176288,371420896,371665408,371909792,
1465     372154080,372398272,372642336,372886304,373130176,373373952,373617600,373861152,
1466     374104608,374347936,374591168,374834304,375077312,375320224,375563040,375805760,
1467     376048352,376290848,376533248,376775520,377017696,377259776,377501728,377743584,
1468     377985344,378227008,378468544,378709984,378951328,379192544,379433664,379674688,
1469     379915584,380156416,380397088,380637696,380878176,381118560,381358848,381599040,
1470     381839104,382079072,382318912,382558656,382798304,383037856,383277280,383516640,
1471     383755840,383994976,384233984,384472896,384711712,384950400,385188992,385427488,
1472     385665888,385904160,386142336,386380384,386618368,386856224,387093984,387331616,
1473     387569152,387806592,388043936,388281152,388518272,388755296,388992224,389229024,
1474     389465728,389702336,389938816,390175200,390411488,390647680,390883744,391119712,
1475     391355584,391591328,391826976,392062528,392297984,392533312,392768544,393003680,
1476     393238720,393473632,393708448,393943168,394177760,394412256,394646656,394880960,
1477     395115136,395349216,395583200,395817088,396050848,396284512,396518080,396751520,
1478     396984864,397218112,397451264,397684288,397917248,398150080,398382784,398615424,
1479     398847936,399080320,399312640,399544832,399776928,400008928,400240832,400472608,
1480     400704288,400935872,401167328,401398720,401629984,401861120,402092192,402323136,
1481     402553984,402784736,403015360,403245888,403476320,403706656,403936896,404167008,
1482     404397024,404626944,404856736,405086432,405316032,405545536,405774912,406004224,
1483     406233408,406462464,406691456,406920320,407149088,407377760,407606336,407834784,
1484     408063136,408291392,408519520,408747584,408975520,409203360,409431072,409658720,
1485     409886240,410113664,410340992,410568192,410795296,411022304,411249216,411476032,
1486     411702720,411929312,412155808,412382176,412608480,412834656,413060736,413286720,
1487     413512576,413738336,413964000,414189568,414415040,414640384,414865632,415090784,
1488     415315840,415540800,415765632,415990368,416215008,416439552,416663968,416888288,
1489     417112512,417336640,417560672,417784576,418008384,418232096,418455712,418679200,
1490     418902624,419125920,419349120,419572192,419795200,420018080,420240864,420463552,
1491     420686144,420908608,421130976,421353280,421575424,421797504,422019488,422241344,
1492     422463104,422684768,422906336,423127776,423349120,423570400,423791520,424012576,
1493     424233536,424454368,424675104,424895744,425116288,425336736,425557056,425777280,
1494     425997408,426217440,426437376,426657184,426876928,427096544,427316064,427535488,
1495     427754784,427974016,428193120,428412128,428631040,428849856,429068544,429287168,
1496     429505664,429724064,429942368,430160576,430378656,430596672,430814560,431032352,
1497     431250048,431467616,431685120,431902496,432119808,432336992,432554080,432771040,
1498     432987936,433204736,433421408,433637984,433854464,434070848,434287104,434503296,
1499     434719360,434935360,435151232,435367008,435582656,435798240,436013696,436229088,
1500     436444352,436659520,436874592,437089568,437304416,437519200,437733856,437948416,
1501     438162880,438377248,438591520,438805696,439019744,439233728,439447584,439661344,
1502     439875008,440088576,440302048,440515392,440728672,440941824,441154880,441367872,
1503     441580736,441793472,442006144,442218720,442431168,442643552,442855808,443067968,
1504     443280032,443492000,443703872,443915648,444127296,444338880,444550336,444761696,
1505     444972992,445184160,445395232,445606176,445817056,446027840,446238496,446449088,
1506     446659552,446869920,447080192,447290400,447500448,447710432,447920320,448130112,
1507     448339776,448549376,448758848,448968224,449177536,449386720,449595808,449804800,
1508     450013664,450222464,450431168,450639776,450848256,451056640,451264960,451473152,
1509     451681248,451889248,452097152,452304960,452512672,452720288,452927808,453135232,
1510     453342528,453549760,453756864,453963904,454170816,454377632,454584384,454791008,
1511     454997536,455203968,455410304,455616544,455822688,456028704,456234656,456440512,
1512     456646240,456851904,457057472,457262912,457468256,457673536,457878688,458083744,
1513     458288736,458493600,458698368,458903040,459107616,459312096,459516480,459720768,
1514     459924960,460129056,460333056,460536960,460740736,460944448,461148064,461351584,
1515     461554976,461758304,461961536,462164640,462367680,462570592,462773440,462976160,
1516     463178816,463381344,463583776,463786144,463988384,464190560,464392608,464594560,
1517     464796448,464998208,465199872,465401472,465602944,465804320,466005600,466206816,
1518     466407904,466608896,466809824,467010624,467211328,467411936,467612480,467812896,
1519     468013216,468213440,468413600,468613632,468813568,469013440,469213184,469412832,
1520     469612416,469811872,470011232,470210528,470409696,470608800,470807776,471006688,
1521     471205472,471404192,471602784,471801312,471999712,472198048,472396288,472594400,
1522     472792448,472990400,473188256,473385984,473583648,473781216,473978688,474176064,
1523     474373344,474570528,474767616,474964608,475161504,475358336,475555040,475751648,
1524     475948192,476144608,476340928,476537184,476733312,476929376,477125344,477321184,
1525     477516960,477712640,477908224,478103712,478299104,478494400,478689600,478884704,
1526     479079744,479274656,479469504,479664224,479858880,480053408,480247872,480442240,
1527     480636512,480830656,481024736,481218752,481412640,481606432,481800128,481993760,
1528     482187264,482380704,482574016,482767264,482960416,483153472,483346432,483539296,
1529     483732064,483924768,484117344,484309856,484502240,484694560,484886784,485078912,
1530     485270944,485462880,485654720,485846464,486038144,486229696,486421184,486612576,
1531     486803840,486995040,487186176,487377184,487568096,487758912,487949664,488140320,
1532     488330880,488521312,488711712,488901984,489092160,489282240,489472256,489662176,
1533     489851968,490041696,490231328,490420896,490610336,490799712,490988960,491178144,
1534     491367232,491556224,491745120,491933920,492122656,492311264,492499808,492688256,
1535     492876608,493064864,493253056,493441120,493629120,493817024,494004832,494192544,
1536     494380160,494567712,494755136,494942496,495129760,495316928,495504000,495691008,
1537     495877888,496064704,496251424,496438048,496624608,496811040,496997408,497183680,
1538     497369856,497555936,497741920,497927840,498113632,498299360,498484992,498670560,
1539     498856000,499041376,499226656,499411840,499596928,499781920,499966848,500151680,
1540     500336416,500521056,500705600,500890080,501074464,501258752,501442944,501627040,
1541     501811072,501995008,502178848,502362592,502546240,502729824,502913312,503096704,
1542     503280000,503463232,503646368,503829408,504012352,504195200,504377984,504560672,
1543     504743264,504925760,505108192,505290496,505472736,505654912,505836960,506018944,
1544     506200832,506382624,506564320,506745952,506927488,507108928,507290272,507471552,
1545     507652736,507833824,508014816,508195744,508376576,508557312,508737952,508918528,
1546     509099008,509279392,509459680,509639904,509820032,510000064,510180000,510359872,
1547     510539648,510719328,510898944,511078432,511257856,511437216,511616448,511795616,
1548     511974688,512153664,512332576,512511392,512690112,512868768,513047296,513225792,
1549     513404160,513582432,513760640,513938784,514116800,514294752,514472608,514650368,
1550     514828064,515005664,515183168,515360608,515537952,515715200,515892352,516069440,
1551     516246432,516423328,516600160,516776896,516953536,517130112,517306592,517482976,
1552     517659264,517835488,518011616,518187680,518363648,518539520,518715296,518891008,
1553     519066624,519242144,519417600,519592960,519768256,519943424,520118528,520293568,
1554     520468480,520643328,520818112,520992800,521167392,521341888,521516320,521690656,
1555     521864896,522039072,522213152,522387168,522561056,522734912,522908640,523082304,
1556     523255872,523429376,523602784,523776096,523949312,524122464,524295552,524468512,
1557     524641440,524814240,524986976,525159616,525332192,525504640,525677056,525849344,
1558     526021568,526193728,526365792,526537760,526709632,526881440,527053152,527224800,
1559     527396352,527567840,527739200,527910528,528081728,528252864,528423936,528594880,
1560     528765760,528936576,529107296,529277920,529448480,529618944,529789344,529959648,
1561     530129856,530300000,530470048,530640000,530809888,530979712,531149440,531319072,
1562     531488608,531658080,531827488,531996800,532166016,532335168,532504224,532673184,
1563     532842080,533010912,533179616,533348288,533516832,533685312,533853728,534022048,
1564     534190272,534358432,534526496,534694496,534862400,535030240,535197984,535365632,
1565     535533216,535700704,535868128,536035456,536202720,536369888,536536992,536704000,
1566     536870912
1567 };
1568 
1569 // This is the new flat distribution table
1570 static unsigned char rngTable[256] = {
1571     201, 1, 243, 19, 18, 42, 183, 203, 101, 123, 154, 137, 34, 118, 10, 216,
1572     135, 246, 0, 107, 133, 229, 35, 113, 177, 211, 110, 17, 139, 84, 251, 235,
1573     182, 166, 161, 230, 143, 91, 24, 81, 22, 94, 7, 51, 232, 104, 122, 248,
1574     175, 138, 127, 171, 222, 213, 44, 16, 9, 33, 88, 102, 170, 150, 136, 114,
1575     62, 3, 142, 237, 6, 252, 249, 56, 74, 30, 13, 21, 180, 199, 32, 132,
1576     187, 234, 78, 210, 46, 131, 197, 8, 206, 244, 73, 4, 236, 178, 195, 70,
1577     121, 97, 167, 217, 103, 40, 247, 186, 105, 39, 95, 163, 99, 149, 253, 29,
1578     119, 83, 254, 26, 202, 65, 130, 155, 60, 64, 184, 106, 221, 93, 164, 196,
1579     112, 108, 179, 141, 54, 109, 11, 126, 75, 165, 191, 227, 87, 225, 156, 15,
1580     98, 162, 116, 79, 169, 140, 190, 205, 168, 194, 41, 250, 27, 20, 14, 241,
1581     50, 214, 72, 192, 220, 233, 67, 148, 96, 185, 176, 181, 215, 207, 172, 85,
1582     89, 90, 209, 128, 124, 2, 55, 173, 66, 152, 47, 129, 59, 43, 159, 240,
1583     239, 12, 189, 212, 144, 28, 200, 77, 219, 198, 134, 228, 45, 92, 125, 151,
1584     5, 53, 255, 52, 68, 245, 160, 158, 61, 86, 58, 82, 117, 37, 242, 145,
1585     69, 188, 115, 76, 63, 100, 49, 111, 153, 80, 38, 57, 174, 224, 71, 231,
1586     23, 25, 48, 218, 120, 147, 208, 36, 226, 223, 193, 238, 157, 204, 146, 31
1587 };
1588 static int rngIndex = 0, rngIndex2 = 0;
1589 
RNG_RandByte(void)1590 byte RNG_RandByte(void)
1591 {
1592     if (rngIndex > 255)
1593     {
1594         rngIndex = 0;
1595         rngIndex2++;
1596     }
1597     return rngTable[(++rngIndex) & 0xff] ^ rngTable[rngIndex2 & 0xff];
1598 }
1599 
RNG_RandFloat(void)1600 float RNG_RandFloat(void)
1601 {
1602     return (RNG_RandByte() | (RNG_RandByte() << 8)) / 65535.0f;
1603 }
1604 
RNG_Reset(void)1605 void RNG_Reset(void)
1606 {
1607     rngIndex = 0, rngIndex2 = 0;
1608 }
1609 
M_ClearBox(fixed_t * box)1610 void M_ClearBox(fixed_t *box)
1611 {
1612     box[BOXTOP] = box[BOXRIGHT] = DDMININT;
1613     box[BOXBOTTOM] = box[BOXLEFT] = DDMAXINT;
1614 }
1615 
M_CopyBox(fixed_t dest[4],const fixed_t src[4])1616 void M_CopyBox(fixed_t dest[4], const fixed_t src[4])
1617 {
1618     dest[BOXLEFT]   = src[BOXLEFT];
1619     dest[BOXRIGHT]  = src[BOXRIGHT];
1620     dest[BOXBOTTOM] = src[BOXBOTTOM];
1621     dest[BOXTOP]    = src[BOXTOP];
1622 }
1623 
M_AddToBox(fixed_t * box,fixed_t x,fixed_t y)1624 void M_AddToBox(fixed_t *box, fixed_t x, fixed_t y)
1625 {
1626     if (x < box[BOXLEFT])
1627         box[BOXLEFT] = x;
1628     else if (x > box[BOXRIGHT])
1629         box[BOXRIGHT] = x;
1630     if (y < box[BOXBOTTOM])
1631         box[BOXBOTTOM] = y;
1632     else if (y > box[BOXTOP])
1633         box[BOXTOP] = y;
1634 }
1635 
M_JoinBoxes(float bbox[4],const float other[4])1636 void M_JoinBoxes(float bbox[4], const float other[4])
1637 {
1638     if (other[BOXLEFT] < bbox[BOXLEFT])
1639         bbox[BOXLEFT] = other[BOXLEFT];
1640 
1641     if (other[BOXRIGHT] > bbox[BOXRIGHT])
1642         bbox[BOXRIGHT] = other[BOXRIGHT];
1643 
1644     if (other[BOXTOP] > bbox[BOXTOP])
1645         bbox[BOXTOP] = other[BOXTOP];
1646 
1647     if (other[BOXBOTTOM] < bbox[BOXBOTTOM])
1648         bbox[BOXBOTTOM] = other[BOXBOTTOM];
1649 }
1650 
M_BoundingBoxDiff(const float in[4],const float out[4])1651 float M_BoundingBoxDiff(const float in[4], const float out[4])
1652 {
1653     return in[BOXLEFT]    - out[BOXLEFT] +
1654            in[BOXBOTTOM]  - out[BOXBOTTOM] +
1655            out[BOXRIGHT]  - in[BOXRIGHT] +
1656            out[BOXTOP]    - in[BOXTOP];
1657 }
1658 
M_CRC32(byte const * data,uint length)1659 uint M_CRC32(byte const *data, uint length)
1660 {
1661 /* ====================================================================== */
1662 /*  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or       */
1663 /*  code or tables extracted from it, as desired without restriction.     */
1664 /*                                                                        */
1665 /*  First, the polynomial itself and its table of feedback terms.  The    */
1666 /*  polynomial is                                                         */
1667 /*  X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0   */
1668 /*                                                                        */
1669 /*  Note that we take it "backwards" and put the highest-order term in    */
1670 /*  the lowest-order bit.  The X^32 term is "implied"; the LSB is the     */
1671 /*  X^31 term, etc.  The X^0 term (usually shown as "+1") results in      */
1672 /*  the MSB being 1.                                                      */
1673 /*                                                                        */
1674 /*  Note that the usual hardware shift register implementation, which     */
1675 /*  is what we're using (we're merely optimizing it by doing eight-bit    */
1676 /*  chunks at a time) shifts bits into the lowest-order term.  In our     */
1677 /*  implementation, that means shifting towards the right.  Why do we     */
1678 /*  do it this way?  Because the calculated CRC must be transmitted in    */
1679 /*  order from highest-order term to lowest-order term.  UARTs transmit   */
1680 /*  characters in order from LSB to MSB.  By storing the CRC this way,    */
1681 /*  we hand it to the UART in the order low-byte to high-byte; the UART   */
1682 /*  sends each low-bit to hight-bit; and the result is transmission bit   */
1683 /*  by bit from highest- to lowest-order term without requiring any bit   */
1684 /*  shuffling on our part.  Reception works similarly.                    */
1685 /*                                                                        */
1686 /*  The feedback terms table consists of 256, 32-bit entries.  Notes:     */
1687 /*                                                                        */
1688 /*      The table can be generated at runtime if desired; code to do so   */
1689 /*      is shown later.  It might not be obvious, but the feedback        */
1690 /*      terms simply represent the results of eight shift/xor opera-      */
1691 /*      tions for all combinations of data and CRC register values.       */
1692 /*                                                                        */
1693 /*      The values must be right-shifted by eight bits by the "updcrc"    */
1694 /*      logic; the shift must be unsigned (bring in zeroes).  On some     */
1695 /*      hardware you could probably optimize the shift in assembler by    */
1696 /*      using byte-swap instructions.                                     */
1697 /*      polynomial $edb88320                                              */
1698 /*                                                                        */
1699 /*  --------------------------------------------------------------------  */
1700 
1701     static unsigned long crc32_tab[] = {
1702         0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
1703         0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
1704         0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
1705         0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
1706         0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
1707         0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
1708         0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
1709         0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
1710         0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
1711         0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
1712         0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
1713         0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
1714         0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
1715         0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
1716         0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
1717         0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
1718         0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
1719         0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
1720         0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
1721         0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
1722         0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
1723         0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
1724         0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
1725         0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
1726         0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
1727         0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
1728         0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
1729         0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
1730         0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
1731         0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
1732         0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
1733         0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
1734         0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
1735         0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
1736         0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
1737         0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
1738         0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
1739         0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
1740         0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
1741         0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
1742         0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
1743         0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
1744         0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
1745         0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
1746         0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
1747         0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
1748         0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
1749         0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
1750         0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
1751         0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
1752         0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
1753         0x2d02ef8dL
1754     };
1755 
1756     unsigned int i;
1757     unsigned long crc32 = 0;
1758 
1759     for (i = 0; i < length; ++i)
1760     {
1761         crc32 = crc32_tab[(crc32 ^ data[i]) & 0xff] ^ (crc32 >> 8);
1762     }
1763     return crc32;
1764 }
1765 
M_NumDigits(int value)1766 int M_NumDigits(int value)
1767 {
1768     return (int) (floor(log10(ABS(value))) + 1);
1769 }
1770 
slopeDiv(unsigned num,unsigned den)1771 static int slopeDiv(unsigned num, unsigned den)
1772 {
1773     uint ans;
1774 
1775     if (den < 512)
1776     {
1777         return SLOPERANGE;
1778     }
1779     ans = (num << 3) / (den >> 8);
1780     return ans <= SLOPERANGE ? ans : SLOPERANGE;
1781 }
1782 
M_PointToAngle(double const point[])1783 angle_t M_PointToAngle(double const point[])
1784 {
1785     fixed_t pos[2];
1786 
1787     pos[VX] = FLT2FIX(point[VX]);
1788     pos[VY] = FLT2FIX(point[VY]);
1789 
1790     if (pos[VX] == 0 && pos[VY] == 0)
1791         return 0;
1792 
1793     if (pos[VX] >= 0)
1794     {
1795         // x >=0
1796         if (pos[VY] >= 0)
1797         {
1798             // y>= 0
1799             if (pos[VX] > pos[VY])
1800                 return tantoangle[slopeDiv(pos[VY], pos[VX])]; // octant 0
1801 
1802             return ANG90 - 1 - tantoangle[slopeDiv(pos[VX], pos[VY])]; // octant 1
1803         }
1804 
1805         // y<0
1806         pos[VY] = -pos[VY];
1807         if (pos[VX] > pos[VY])
1808             return -tantoangle[slopeDiv(pos[VY], pos[VX])]; // octant 8
1809 
1810         return ANG270 + tantoangle[slopeDiv(pos[VX], pos[VY])]; // octant 7
1811     }
1812 
1813     // x<0
1814     pos[VX] = -pos[VX];
1815     if (pos[VY] >= 0)
1816     {
1817         // y>= 0
1818         if (pos[VX] > pos[VY])
1819             return ANG180 - 1 - tantoangle[slopeDiv(pos[VY], pos[VX])]; // octant 3
1820 
1821         return ANG90 + tantoangle[slopeDiv(pos[VX], pos[VY])]; // octant 2
1822     }
1823 
1824     // y<0
1825     pos[VY] = -pos[VY];
1826     if (pos[VX] > pos[VY])
1827         return ANG180 + tantoangle[slopeDiv(pos[VY], pos[VX])]; // octant 4
1828 
1829     return ANG270 - 1 - tantoangle[slopeDiv(pos[VX], pos[VY])]; // octant 5
1830 }
1831 
M_PointXYToAngle(double x,double y)1832 angle_t M_PointXYToAngle(double x, double y)
1833 {
1834     double point[2] = { x, y };
1835     return M_PointToAngle(point);
1836 }
1837 
M_PointToAngle2(double const a[],double const b[])1838 angle_t M_PointToAngle2(double const a[], double const b[])
1839 {
1840     double delta[2] = { b[VX] - a[VX], b[VY] - a[VY] };
1841     return M_PointToAngle(delta);
1842 }
1843 
M_PointXYToAngle2(double aX,double aY,double bX,double bY)1844 angle_t M_PointXYToAngle2(double aX, double aY, double bX, double bY)
1845 {
1846     double a[2] = { aX, aY };
1847     double b[2] = { bX, bY };
1848     return M_PointToAngle2(a, b);
1849 }
1850 
M_DirectionToAngleXY(double dx,double dy)1851 double M_DirectionToAngleXY(double dx, double dy)
1852 {
1853     double angle;
1854 
1855     if (dx == 0)
1856         return (dy > 0? 90.0 : 270.0);
1857 
1858     angle = atan2((double) dy, (double) dx) * 180.0 / DD_PI_D;
1859 
1860     if (angle < 0)
1861         angle += 360.0;
1862 
1863     return angle;
1864 }
1865 
M_DirectionToAngle(double const direction[])1866 double M_DirectionToAngle(double const direction[])
1867 {
1868     return M_DirectionToAngleXY(direction[VX], direction[VY]);
1869 }
1870 
M_PointDistance(double const a[],double const b[])1871 double M_PointDistance(double const a[], double const b[])
1872 {
1873     double delta[2];
1874     uint angle;
1875 
1876     delta[VX] = fabs(b[VX] - a[VX]);
1877     delta[VY] = fabs(b[VY] - a[VY]);
1878 
1879     if (delta[VY] > delta[VX])
1880     {
1881         double temp = delta[VX];
1882         delta[VX] = delta[VY];
1883         delta[VY] = temp;
1884     }
1885 
1886     angle = (tantoangle[FLT2FIX(delta[VY] / delta[VX]) >> DBITS] + ANG90) >> ANGLETOFINESHIFT;
1887     return delta[VX] / FIX2FLT(finesine[angle]); // Use as cosine
1888 }
1889 
M_PointXYDistance(double aX,double aY,double bX,double bY)1890 double M_PointXYDistance(double aX, double aY, double bX, double bY)
1891 {
1892     double a[2] = { aX, aY };
1893     double b[2] = { bX, bY };
1894     return M_PointDistance(a, b);
1895 }
1896 
M_ApproxDistance(double dx,double dy)1897 double M_ApproxDistance(double dx, double dy)
1898 {
1899     dx = fabs(dx);
1900     dy = fabs(dy);
1901     if (dx < dy)
1902         return dx + dy - dx / 2;
1903     return dx + dy - dy / 2;
1904 }
1905 
M_ApproxDistancef(float dx,float dy)1906 float M_ApproxDistancef(float dx, float dy)
1907 {
1908     dx = (float) fabs(dx);
1909     dy = (float) fabs(dy);
1910     if (dx < dy)
1911         return dx + dy - dx / 2;
1912     return dx + dy - dy / 2;
1913 }
1914 
M_ApproxDistance3(double dx,double dy,double dz)1915 double M_ApproxDistance3(double dx, double dy, double dz)
1916 {
1917     return M_ApproxDistance(M_ApproxDistance(dx, dy), dz);
1918 }
1919 
M_ApproxDistance3f(float dx,float dy,float dz)1920 float M_ApproxDistance3f(float dx, float dy, float dz)
1921 {
1922     return M_ApproxDistancef(M_ApproxDistancef(dx, dy), dz);
1923 }
1924 
M_TriangleArea(double const v1[],double const v2[],double const v3[])1925 double M_TriangleArea(double const v1[], double const v2[], double const v3[])
1926 {
1927     double a[2], b[2];
1928     double area;
1929 
1930     V2d_Subtract(a, v2, v1);
1931     V2d_Subtract(b, v3, v1);
1932 
1933     area = (a[VX] * b[VY] - b[VX] * a[VY]) / 2;
1934     if (area < 0)
1935         return -area;
1936     return area;
1937 }
1938 
1939 /**
1940  * First yaw, then pitch. Two consecutive 2D rotations.
1941  * Probably could be done a bit more efficiently.
1942  */
M_RotateVector(float vec[3],float degYaw,float degPitch)1943 void M_RotateVector(float vec[3], float degYaw, float degPitch)
1944 {
1945     float radYaw = degYaw / 180 * DD_PI, radPitch = degPitch / 180 * DD_PI;
1946     float Cos, Sin, res[3];
1947 
1948     // Yaw.
1949     if (radYaw != 0)
1950     {
1951         Cos = (float) cos(radYaw);
1952         Sin = (float) sin(radYaw);
1953         res[VX] = vec[VX] * Cos + vec[VY] * Sin;
1954         res[VY] = vec[VX] * -Sin + vec[VY] * Cos;
1955         vec[VX] = res[VX];
1956         vec[VY] = res[VY];
1957     }
1958 
1959     // Pitch.
1960     if (radPitch != 0)
1961     {
1962         Cos = (float) cos(radPitch);
1963         Sin = (float) sin(radPitch);
1964         res[VZ] = vec[VZ] * Cos + vec[VX] * Sin;
1965         res[VX] = vec[VZ] * -Sin + vec[VX] * Cos;
1966         vec[VZ] = res[VZ];
1967         vec[VX] = res[VX];
1968     }
1969 }
1970 
M_CeilPow2(int num)1971 int M_CeilPow2(int num)
1972 {
1973     int         cumul;
1974 
1975     for (cumul = 1; num > cumul; cumul <<= 1);
1976 
1977     return cumul;
1978 }
1979 
M_RoundPow2(int num)1980 int M_RoundPow2(int num)
1981 {
1982     int         cp2 = M_CeilPow2(num), fp2 = M_FloorPow2(num);
1983 
1984     return ((cp2 - num >= num - fp2) ? fp2 : cp2);
1985 }
1986 
M_WeightPow2(int num,float weight)1987 int M_WeightPow2(int num, float weight)
1988 {
1989     int         fp2 = M_FloorPow2(num);
1990     float       frac = (num - fp2) / (float) fp2;
1991 
1992     if (frac <= weight)
1993         return fp2;
1994     else
1995         return (fp2 << 1);
1996 }
1997 
M_CycleIntoRange(float value,float length)1998 float M_CycleIntoRange(float value, float length)
1999 {
2000     if (value < 0)
2001     {
2002         return value - ((int) (value / length) - 1) * length;
2003     }
2004     if (value > length)
2005     {
2006         return value - ((int) (value / length)) * length;
2007     }
2008     return value;
2009 }
2010 
M_RatioReduce(int * numerator,int * denominator)2011 int M_RatioReduce(int* numerator, int* denominator)
2012 {
2013     int n, d, temp;
2014 
2015     if (!numerator || !denominator)
2016     {
2017         return 1;
2018     }
2019 
2020     if (*numerator == *denominator) return 1; // 1:1
2021 
2022     n = ABS(*numerator);
2023     d = ABS(*denominator);
2024     // Ensure numerator is larger.
2025     if (n < d)
2026     {
2027         temp = n;
2028         n = d;
2029         d = temp;
2030     }
2031 
2032     // Reduce to the common divisor.
2033     while (d != 0)
2034     {
2035         temp = n;
2036         n = d;
2037         d = temp % d;
2038     }
2039 
2040     // Apply divisor.
2041     *numerator   /= n;
2042     *denominator /= n;
2043     return n;
2044 }
2045 
M_FloorPow2(int num)2046 int M_FloorPow2(int num)
2047 {
2048     int         fl = M_CeilPow2(num);
2049 
2050     if (fl > num)
2051         fl >>= 1;
2052     return fl;
2053 }
2054 
M_SlopeType(double const direction[])2055 slopetype_t M_SlopeType(double const direction[])
2056 {
2057     return M_SlopeTypeXY(direction[VX], direction[VY]);
2058 }
2059 
M_SlopeTypeXY_FixedPrecision(fixed_t dx,fixed_t dy)2060 slopetype_t M_SlopeTypeXY_FixedPrecision(fixed_t dx, fixed_t dy)
2061 {
2062     if (!dx)
2063     {
2064         return ST_VERTICAL;
2065     }
2066     else if (!dy)
2067     {
2068         return ST_HORIZONTAL;
2069     }
2070     else if (FixedDiv(dy, dx) > 0)
2071     {
2072         return ST_POSITIVE;
2073     }
2074     else
2075     {
2076         return ST_NEGATIVE;
2077     }
2078 }
2079 
M_SlopeTypeXY(double dx,double dy)2080 slopetype_t M_SlopeTypeXY(double dx, double dy)
2081 {
2082     if (IS_ZERO(dx))
2083     {
2084         return ST_VERTICAL;
2085     }
2086     else if (IS_ZERO(dy))
2087     {
2088         return ST_HORIZONTAL;
2089     }
2090     else if (dy / dx > 0)
2091     {
2092         return ST_POSITIVE;
2093     }
2094     else
2095     {
2096         return ST_NEGATIVE;
2097     }
2098 }
2099 
M_InverseAngle(double angle)2100 double M_InverseAngle(double angle)
2101 {
2102     if (angle < 180.0)
2103     {
2104         return (180.0 - -angle);
2105     }
2106     return angle - 180.0;
2107 }
2108 
M_HSVToRGB(float * rgb,float h,float s,float v)2109 void M_HSVToRGB(float* rgb, float h, float s, float v)
2110 {
2111     int                 i;
2112     float               f, p, q, t;
2113 
2114     if (!rgb)
2115         return;
2116 
2117     if (s == 0)
2118     {
2119         // achromatic (grey)
2120         rgb[0] = rgb[1] = rgb[2] = v;
2121         return;
2122     }
2123 
2124     if (h >= 1)
2125         h -= 1;
2126 
2127     h *= 6; // sector 0 to 5
2128     i = (int) floor(h);
2129     f = h - i; // factorial part of h
2130     p = v * (1 - s);
2131     q = v * (1 - s * f);
2132     t = v * (1 - s * (1 - f));
2133 
2134     switch (i)
2135     {
2136     case 0:
2137         rgb[0] = v;
2138         rgb[1] = t;
2139         rgb[2] = p;
2140         break;
2141 
2142     case 1:
2143         rgb[0] = q;
2144         rgb[1] = v;
2145         rgb[2] = p;
2146         break;
2147 
2148     case 2:
2149         rgb[0] = p;
2150         rgb[1] = v;
2151         rgb[2] = t;
2152         break;
2153 
2154     case 3:
2155         rgb[0] = p;
2156         rgb[1] = q;
2157         rgb[2] = v;
2158         break;
2159 
2160     case 4:
2161         rgb[0] = t;
2162         rgb[1] = p;
2163         rgb[2] = v;
2164         break;
2165 
2166     default:
2167         rgb[0] = v;
2168         rgb[1] = p;
2169         rgb[2] = q;
2170         break;
2171     }
2172 }
2173