// fix point
typedef short fixed16;
typedef int fixed32;
#define FIXONE 0x100
#define FIXHALF 0x80
#define FIXCEIL 0xFF
#define f2i(A) ((A)>>8)
#define i2f(A) ((A)<<8)
#define r2i(A) ((A)>>16)
#define i2fdiv2(A) ((A)<<7)
#define f2fl(A) ((A)/256.0)
#define fl2f(A) ((A)*256.0)
#define fixtrunc(A) i2f(f2i(A))
#define fixlerp(A,B,C) ((A)+fixmul((B)-(A),©))
#define fixup(A) f2i((A)+FIXCEIL)
#define fixinv(A) fixdiv(FIXUNIT,(A))
#define intdiv(A,B) ((A)/(B))
#define muldiv(A,B,C) intdiv((A)*(B),©)
#define fixmul(A,B) f2i((A)*(B))
#define fixdiv(A,B) intdiv(i2f(A),(B))
#define fixsin(A) sintable[(A)&2047]
#define fixcos(A) fixsin((A)+512)
const int sintable[2048] = {0,1,2,2,3,4,5,5,6,7,8,9,9,10,11,12,
13,13,14,15,16,16,17,18,19,20,20,21,22,23,24,24,25,26,27,27,28,29,30,31,31,32,
33,34,34,35,36,37,38,38,39,40,41,41,42,43,44,45,45,46,47,48,48,49,50,51,51,52,
53,54,55,55,56,57,58,58,59,60,61,61,62,63,64,64,65,66,67,68,68,69,70,71,71,72,
73,74,74,75,76,77,77,78,79,80,80,81,82,83,83,84,85,86,86,87,88,88,89,90,91,91,
92,93,94,94,95,96,97,97,98,99,99,100,101,102,102,103,104,104,105,106,107,107,
108,109,109,110,111,112,112,113,114,114,115,116,117,117,118,119,119,120,121,121,
122,123,123,124,125,125,126,127,128,128,129,130,130,131,132,132,133,134,134,135,
136,136,137,138,138,139,140,140,141,142,142,143,144,144,145,145,146,147,147,148,
149,149,150,151,151,152,152,153,154,154,155,156,156,157,157,158,159,159,160,161,
161,162,162,163,164,164,165,165,166,167,167,168,168,169,170,170,171,171,172,173,
173,174,174,175,175,176,177,177,178,178,179,179,180,180,181,182,182,183,183,184,
184,185,185,186,186,187,188,188,189,189,190,190,191,191,192,192,193,193,194,194,
195,195,196,196,197,197,198,198,199,199,200,200,201,201,202,202,203,203,204,204,
205,205,206,206,207,207,207,208,208,209,209,210,210,211,211,212,212,212,213,213,
214,214,215,215,215,216,216,217,217,218,218,218,219,219,220,220,220,221,221,222,
222,222,223,223,224,224,224,225,225,225,226,226,227,227,227,228,228,228,229,229,
229,230,230,230,231,231,231,232,232,232,233,233,233,234,234,234,235,235,235,236,
236,236,237,237,237,237,238,238,238,239,239,239,239,240,240,240,241,241,241,241,
242,242,242,242,243,243,243,243,244,244,244,244,245,245,245,245,245,246,246,246,
246,247,247,247,247,247,248,248,248,248,248,249,249,249,249,249,249,250,250,250,
250,250,250,251,251,251,251,251,251,252,252,252,252,252,252,252,252,253,253,253,
253,253,253,253,253,254,254,254,254,254,254,254,254,254,254,255,255,255,255,255,
255,255,255,255,255,255,255,255,255,255,256,256,256,256,256,256,256,256,256,256,
256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,
256,256,256,256,256,256,256,256,256,256,256,255,255,255,255,255,255,255,255,255,
255,255,255,255,255,255,254,254,254,254,254,254,254,254,254,254,253,253,253,253,
253,253,253,253,252,252,252,252,252,252,252,252,251,251,251,251,251,251,250,250,
250,250,250,250,249,249,249,249,249,249,248,248,248,248,248,247,247,247,247,247,
246,246,246,246,245,245,245,245,245,244,244,244,244,243,243,243,243,242,242,242,
242,241,241,241,241,240,240,240,239,239,239,239,238,238,238,237,237,237,237,236,
236,236,235,235,235,234,234,234,233,233,233,232,232,232,231,231,231,230,230,230,
229,229,229,228,228,228,227,227,227,226,226,225,225,225,224,224,224,223,223,222,
222,222,221,221,220,220,220,219,219,218,218,218,217,217,216,216,215,215,215,214,
214,213,213,212,212,212,211,211,210,210,209,209,208,208,207,207,207,206,206,205,
205,204,204,203,203,202,202,201,201,200,200,199,199,198,198,197,197,196,196,195,
195,194,194,193,193,192,192,191,191,190,190,189,189,188,188,187,186,186,185,185,
184,184,183,183,182,182,181,180,180,179,179,178,178,177,177,176,175,175,174,174,
173,173,172,171,171,170,170,169,168,168,167,167,166,165,165,164,164,163,162,162,
161,161,160,159,159,158,157,157,156,156,155,154,154,153,152,152,151,151,150,149,
149,148,147,147,146,145,145,144,144,143,142,142,141,140,140,139,138,138,137,136,
136,135,134,134,133,132,132,131,130,130,129,128,128,127,126,125,125,124,123,123,
122,121,121,120,119,119,118,117,117,116,115,114,114,113,112,112,111,110,109,109,
108,107,107,106,105,104,104,103,102,102,101,100,99,99,98,97,97,96,95,94,94,93,
92,91,91,90,89,88,88,87,86,86,85,84,83,83,82,81,80,80,79,78,77,77,76,75,74,74,
73,72,71,71,70,69,68,68,67,66,65,64,64,63,62,61,61,60,59,58,58,57,56,55,55,54,
53,52,51,51,50,49,48,48,47,46,45,45,44,43,42,41,41,40,39,38,38,37,36,35,34,34,
33,32,31,31,30,29,28,27,27,26,25,24,24,23,22,21,20,20,19,18,17,16,16,15,14,13,
13,12,11,10,9,9,8,7,6,5,5,4,3,2,2,1,0,-1,-2,-2,-3,-4,-5,-5,-6,-7,-8,-9,-9,-10,
-11,-12,-13,-13,-14,-15,-16,-16,-17,-18,-19,-20,-20,-21,-22,-23,-24,-24,-25,-26,
-27,-27,-28,-29,-30,-31,-31,-32,-33,-34,-34,-35,-36,-37,-38,-38,-39,-40,-41,-41,
-42,-43,-44,-45,-45,-46,-47,-48,-48,-49,-50,-51,-51,-52,-53,-54,-55,-55,-56,-57,
-58,-58,-59,-60,-61,-61,-62,-63,-64,-64,-65,-66,-67,-68,-68,-69,-70,-71,-71,-72,
-73,-74,-74,-75,-76,-77,-77,-78,-79,-80,-80,-81,-82,-83,-83,-84,-85,-86,-86,-87,
-88,-88,-89,-90,-91,-91,-92,-93,-94,-94,-95,-96,-97,-97,-98,-99,-99,-100,-101,
-102,-102,-103,-104,-104,-105,-106,-107,-107,-108,-109,-109,-110,-111,-112,-112,
-113,-114,-114,-115,-116,-117,-117,-118,-119,-119,-120,-121,-121,-122,-123,-123,
-124,-125,-125,-126,-127,-128,-128,-129,-130,-130,-131,-132,-132,-133,-134,-134,
-135,-136,-136,-137,-138,-138,-139,-140,-140,-141,-142,-142,-143,-144,-144,-145,
-145,-146,-147,-147,-148,-149,-149,-150,-151,-151,-152,-152,-153,-154,-154,-155,
-156,-156,-157,-157,-158,-159,-159,-160,-161,-161,-162,-162,-163,-164,-164,-165,
-165,-166,-167,-167,-168,-168,-169,-170,-170,-171,-171,-172,-173,-173,-174,-174,
-175,-175,-176,-177,-177,-178,-178,-179,-179,-180,-180,-181,-182,-182,-183,-183,
-184,-184,-185,-185,-186,-186,-187,-188,-188,-189,-189,-190,-190,-191,-191,-192,
-192,-193,-193,-194,-194,-195,-195,-196,-196,-197,-197,-198,-198,-199,-199,-200,
-200,-201,-201,-202,-202,-203,-203,-204,-204,-205,-205,-206,-206,-207,-207,-207,
-208,-208,-209,-209,-210,-210,-211,-211,-212,-212,-212,-213,-213,-214,-214,-215,
-215,-215,-216,-216,-217,-217,-218,-218,-218,-219,-219,-220,-220,-220,-221,-221,
-222,-222,-222,-223,-223,-224,-224,-224,-225,-225,-225,-226,-226,-227,-227,-227,
-228,-228,-228,-229,-229,-229,-230,-230,-230,-231,-231,-231,-232,-232,-232,-233,
-233,-233,-234,-234,-234,-235,-235,-235,-236,-236,-236,-237,-237,-237,-237,-238,
-238,-238,-239,-239,-239,-239,-240,-240,-240,-241,-241,-241,-241,-242,-242,-242,
-242,-243,-243,-243,-243,-244,-244,-244,-244,-245,-245,-245,-245,-245,-246,-246,
-246,-246,-247,-247,-247,-247,-247,-248,-248,-248,-248,-248,-249,-249,-249,-249,
-249,-249,-250,-250,-250,-250,-250,-250,-251,-251,-251,-251,-251,-251,-252,-252,
-252,-252,-252,-252,-252,-252,-253,-253,-253,-253,-253,-253,-253,-253,-254,-254,
-254,-254,-254,-254,-254,-254,-254,-254,-255,-255,-255,-255,-255,-255,-255,-255,
-255,-255,-255,-255,-255,-255,-255,-256,-256,-256,-256,-256,-256,-256,-256,-256,
-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,
-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,-256,
-255,-255,-255,-255,-255,-255,-255,-255,-255,-255,-255,-255,-255,-255,-255,-254,
-254,-254,-254,-254,-254,-254,-254,-254,-254,-253,-253,-253,-253,-253,-253,-253,
-253,-252,-252,-252,-252,-252,-252,-252,-252,-251,-251,-251,-251,-251,-251,-250,
-250,-250,-250,-250,-250,-249,-249,-249,-249,-249,-249,-248,-248,-248,-248,-248,
-247,-247,-247,-247,-247,-246,-246,-246,-246,-245,-245,-245,-245,-245,-244,-244,
-244,-244,-243,-243,-243,-243,-242,-242,-242,-242,-241,-241,-241,-241,-240,-240,
-240,-239,-239,-239,-239,-238,-238,-238,-237,-237,-237,-237,-236,-236,-236,-235,
-235,-235,-234,-234,-234,-233,-233,-233,-232,-232,-232,-231,-231,-231,-230,-230,
-230,-229,-229,-229,-228,-228,-228,-227,-227,-227,-226,-226,-225,-225,-225,-224,
-224,-224,-223,-223,-222,-222,-222,-221,-221,-220,-220,-220,-219,-219,-218,-218,
-218,-217,-217,-216,-216,-215,-215,-215,-214,-214,-213,-213,-212,-212,-212,-211,
-211,-210,-210,-209,-209,-208,-208,-207,-207,-207,-206,-206,-205,-205,-204,-204,
-203,-203,-202,-202,-201,-201,-200,-200,-199,-199,-198,-198,-197,-197,-196,-196,
-195,-195,-194,-194,-193,-193,-192,-192,-191,-191,-190,-190,-189,-189,-188,-188,
-187,-186,-186,-185,-185,-184,-184,-183,-183,-182,-182,-181,-180,-180,-179,-179,
-178,-178,-177,-177,-176,-175,-175,-174,-174,-173,-173,-172,-171,-171,-170,-170,
-169,-168,-168,-167,-167,-166,-165,-165,-164,-164,-163,-162,-162,-161,-161,-160,
-159,-159,-158,-157,-157,-156,-156,-155,-154,-154,-153,-152,-152,-151,-151,-150,
-149,-149,-148,-147,-147,-146,-145,-145,-144,-144,-143,-142,-142,-141,-140,-140,
-139,-138,-138,-137,-136,-136,-135,-134,-134,-133,-132,-132,-131,-130,-130,-129,
-128,-128,-127,-126,-125,-125,-124,-123,-123,-122,-121,-121,-120,-119,-119,-118,
-117,-117,-116,-115,-114,-114,-113,-112,-112,-111,-110,-109,-109,-108,-107,-107,
-106,-105,-104,-104,-103,-102,-102,-101,-100,-99,-99,-98,-97,-97,-96,-95,-94,
-94,-93,-92,-91,-91,-90,-89,-88,-88,-87,-86,-86,-85,-84,-83,-83,-82,-81,-80,-80,
-79,-78,-77,-77,-76,-75,-74,-74,-73,-72,-71,-71,-70,-69,-68,-68,-67,-66,-65,-64,
-64,-63,-62,-61,-61,-60,-59,-58,-58,-57,-56,-55,-55,-54,-53,-52,-51,-51,-50,-49,
-48,-48,-47,-46,-45,-45,-44,-43,-42,-41,-41,-40,-39,-38,-38,-37,-36,-35,-34,-34,
-33,-32,-31,-31,-30,-29,-28,-27,-27,-26,-25,-24,-24,-23,-22,-21,-20,-20,-19,-18,
-17,-16,-16,-15,-14,-13,-13,-12,-11,-10,-9,-9,-8,-7,-6,-5,-5,-4,-3,-2,-2,-1};