【C++】C++写的用于大数计算的C++类

0xAA55

类名：InfiniteInt
作用：完成不限位数的超大数的运算。
重载了各种运算符，使用方便。支持以下功能：
转换成各种基本类型
输出字符串
从各种基本类型转换
从字符串转换
转换为IEEE浮点数
从IEEE浮点数转换
无符号加减、递增递减、比较
有符号加减乘除、递增递减、比较
二进制位的设置与清除
请看头文件：

1. /* 文件：InfiniteInt.h
   
2. * 描述：提供类InfiniteInt的声明。
   
3. *
   
4. * 类名：InfiniteInt
   
5. * 描述：用于进行无限位数的运算。
   
6. *
   
7. * 用到了vector
   
8. * 为了支持从IEEE浮点数转换、以及转换为IEEE浮点数，使用了float、double变量类型，但是并没有进行浮点数的运算。
   
9. * 为了支持从字符串转换，用到了tchar.h
   
10. */
    
11. #ifndef _INFINITE_INT_
    
12. #define _INFINITE_INT_
    
13. 
    
14. #include<vector>//用vector存储运算单元
    
15. #include<tchar.h>//输出字符兼容UNICODE
    
16. 
    
17. #ifdef  __GNUC__
    
18. typedef long long           __int64;            //给GNU的C\C艹编译器定义64位整数
    
19. #endif
    
20. 
    
21. #define INFINT_UNIT         unsigned            //运算单元
    
22. #define INFINT_INT          int                 //有符号的运算单元
    
23. 
    
24. #define INFINT_SIZE         4                   //单个运算单元的大小。编译的时候请务必确认INFINT_SIZE的值==sizeof(INFINT_UNIT)。请勿直接使用sizeof(INFINT_UNIT)
    
25. #define INFINT_BITS         (INFINT_SIZE*8)     //单个运算单元的位数
    
26. #define INFINT_MAX          ((INFINT_UNIT)-1)   //单个运算单元的最大值
    
27. #define INFINT_HIGHBIT      (1<<(INFINT_BITS-1))//运算单位的最高位
    
28. #define INFINT_LOWBIT       1                   //运算单位的最低位
    
29. 
    
30. #define INFINT_GREATERTHAN  1
    
31. #define INFINT_EQUALTO      0
    
32. #define INFINT_LESSTHAN     -1
    
33. 
    
34. typedef float               INFINT_FLOAT32;
    
35. typedef double              INFINT_FLOAT64;
    
36. typedef signed char         INFINT_INT8;
    
37. typedef signed short        INFINT_INT16;
    
38. typedef signed long         INFINT_INT32;
    
39. typedef signed __int64      INFINT_INT64;
    
40. typedef unsigned char       INFINT_UINT8;
    
41. typedef unsigned short      INFINT_UINT16;
    
42. typedef unsigned long       INFINT_UINT32;
    
43. typedef unsigned __int64    INFINT_UINT64;
    
44. 
    
45. class InfiniteInt
    
46. {
    
47. public:
    
48.     bool                                m_bSigned;
    
49.     std::vector<INFINT_UNIT>            m_vUnits;
    
50. public:
    
51.     InfiniteInt()                       {m_bSigned=false;}
    
52.     InfiniteInt(InfiniteInt&r)          {*this=r;}
    
53. 
    
54.     //从别的类型转换
    
55.     InfiniteInt(INFINT_INT s)           {if(s>=0){m_bSigned=false;m_vUnits.push_back(s);}else{m_bSigned=true;m_vUnits.push_back(-s);}}
    
56.     InfiniteInt(INFINT_UNIT u)          {m_bSigned=false;m_vUnits.push_back(u);}
    
57.     InfiniteInt(INFINT_INT8);           //从8位整数转换
    
58.     InfiniteInt(INFINT_INT16);          //从16位整数转换
    
59.     InfiniteInt(INFINT_INT32);          //从32位整数转换
    
60.     InfiniteInt(INFINT_INT64);          //从64位整数转换
    
61.     InfiniteInt(INFINT_UINT8);          //从无符号8位整数转换
    
62.     InfiniteInt(INFINT_UINT16);         //从无符号16位整数转换
    
63.     InfiniteInt(INFINT_UINT32);         //从无符号32位整数转换
    
64.     InfiniteInt(INFINT_UINT64);         //从无符号64位整数转换
    
65.     InfiniteInt(INFINT_FLOAT32);        //从单精度转换
    
66.     InfiniteInt(INFINT_FLOAT64);        //从双精度转换
    
67. 
    
68.     //转换为别的类型
    
69.     operator INFINT_INT()               {if(!m_vUnits.size())return 0;if(m_bSigned)return -m_vUnits[0];return m_vUnits[0];}
    
70.     operator INFINT_UNIT()              {if(!m_vUnits.size())return 0;return m_vUnits[0];}
    
71.     operator INFINT_INT8();             //转换为8位整数
    
72.     operator INFINT_INT16();            //转换为16位整数
    
73.     operator INFINT_INT32();            //转换为32位整数
    
74.     operator INFINT_INT64();            //转换为64位整数
    
75.     operator INFINT_UINT8();            //转换为无符号8位整数
    
76.     operator INFINT_UINT16();           //转换为无符号16位整数
    
77.     operator INFINT_UINT32();           //转换为无符号32位整数
    
78.     operator INFINT_UINT64();           //转换为无符号64位整数
    
79.     operator INFINT_FLOAT32();          //转换为32位浮点数
    
80.     operator INFINT_FLOAT64();          //转换为64位浮点数
    
81. 
    
82.     //基本的数学运算
    
83.     void UnsignedIncrease();            //无符号加1
    
84.     void UnsignedDecrease();            //无符号减1，计算结果不小于0
    
85.     void UnsignedAdd(InfiniteInt&);     //无符号加法
    
86.     void UnsignedSub(InfiniteInt&);     //无符号减法，计算结果不小于0
    
87.     void UnsignedRSub(InfiniteInt&r)    //无符号反过来的减法，计算结果不小于0
    
88.     {InfiniteInt iToSub(r);iToSub.UnsignedSub(*this);*this=iToSub;}
    
89.     int UnsignedCompare(InfiniteInt&);  //无符号判断
    
90.     int SignedCompare(InfiniteInt&);    //有符号判断
    
91.     InfiniteInt Div(InfiniteInt&);      //除法，返回商，自身为余数
    
92. 
    
93.     //辅助函数
    
94.     size_t GetBitCount();               //取得位数
    
95.     bool TestBit(size_t);               //检测某个为是否为1
    
96.     void SetBit(size_t);                //设置位
    
97.     void ClearBit(size_t);              //清除位
    
98.     void PushBit(bool);                 //压入位
    
99.     bool PopBit(void);                  //弹出位
    
100.     void PushUnit(INFINT_UNIT);         //压入运算单元
     
101.     INFINT_UNIT PopUnit(void);          //弹出运算单元
     
102. 
     
103.     //其它函数
     
104.     void Optimize();                    //优化（删除多余的0）
     
105.     void Align(InfiniteInt&r)/*通过补充0来使两个类占用同样的字节数*/{while(m_vUnits.size()<r.m_vUnits.size())m_vUnits.push_back(0);while(m_vUnits.size()>r.m_vUnits.size())r.m_vUnits.push_back(0);}
     
106.     void ToZero()                       {m_bSigned=false;m_vUnits.clear();}
     
107.     void Swap(InfiniteInt&);            //交换
     
108.     size_t ToHex(TCHAR*,size_t);        //提取十六进制格式的字符串
     
109.     size_t ToDec(TCHAR*,size_t);        //提取十进制格式的字符串
     
110.     size_t ToBin(TCHAR*,size_t);        //提取二进制格式的字符串
     
111.     void FromHex(TCHAR*,size_t);        //从十六进制格式的字符串转换
     
112.     void FromDec(TCHAR*,size_t);        //从十进制格式的字符串转换
     
113.     void FromBin(TCHAR*,size_t);        //从二进制格式的字符串转换
     
114. 
     
115.     //运算符
     
116.     InfiniteInt&    operator=(InfiniteInt&);
     
117.     InfiniteInt&    operator+(){return *this;}
     
118.     InfiniteInt&    operator-(){if(m_vUnits.size())m_bSigned=!m_bSigned;return *this;}
     
119.     bool            operator!(){Optimize();return !m_vUnits.size();}//判断是否为0
     
120.     operator        bool(){Optimize();return m_vUnits.size()?true:false;}//判断是否非零
     
121.     InfiniteInt     operator++(int){InfiniteInt Ret(*this);Optimize();if(m_bSigned)UnsignedDecrease();else UnsignedIncrease();return Ret;}
     
122.     InfiniteInt     operator--(int){InfiniteInt Ret(*this);Optimize();if(m_bSigned)UnsignedIncrease();else UnsignedDecrease();return Ret;}
     
123.     InfiniteInt&    operator++(){Optimize();if(m_bSigned)UnsignedDecrease();else UnsignedIncrease();return*this;}
     
124.     InfiniteInt&    operator--(){Optimize();if(m_bSigned)UnsignedIncrease();else UnsignedDecrease();return*this;}
     
125. 
     
126.     //判断
     
127.     bool            operator==(InfiniteInt&r)/*判断是否等于*/   {return SignedCompare(r)==INFINT_EQUALTO;}
     
128.     bool            operator!=(InfiniteInt&r)/*判断是否不等于*/ {return SignedCompare(r)!=INFINT_EQUALTO;}
     
129.     bool            operator> (InfiniteInt&r)/*判断是否大于*/   {return SignedCompare(r)==INFINT_GREATERTHAN;}
     
130.     bool            operator< (InfiniteInt&r)/*判断是否小于*/   {return SignedCompare(r)==INFINT_LESSTHAN;}
     
131.     bool            operator>=(InfiniteInt&r)/*判断是否不小于*/ {return SignedCompare(r)!=INFINT_LESSTHAN;}
     
132.     bool            operator<=(InfiniteInt&r)/*判断是否不大于*/ {return SignedCompare(r)!=INFINT_GREATERTHAN;}
     
133.     bool            operator&&(InfiniteInt&r)/*判断是否都非零*/ {return (bool)*this&&(bool)r;}
     
134.     bool            operator||(InfiniteInt&r)/*判断是否有非零*/ {return (bool)*this||(bool)r;}
     
135. 
     
136.     //累积性
     
137.     InfiniteInt&    operator<<=(INFINT_INT);//左移
     
138.     InfiniteInt&    operator>>=(INFINT_INT);//右移
     
139. 
     
140.     InfiniteInt&    operator+=(InfiniteInt&);//加法
     
141.     InfiniteInt&    operator-=(InfiniteInt&);//减法
     
142.     InfiniteInt&    operator*=(InfiniteInt&);//乘法
     
143.     InfiniteInt&    operator/=(InfiniteInt&);//求商
     
144.     InfiniteInt&    operator%=(InfiniteInt&);//求余
     
145.     InfiniteInt&    operator&=(InfiniteInt&);//与
     
146.     InfiniteInt&    operator|=(InfiniteInt&);//或
     
147.     InfiniteInt&    operator^=(InfiniteInt&);//Xor
     
148. 
     
149.     //非累积性
     
150.     InfiniteInt     operator<<(INFINT_INT shifts)/*左移*/       {InfiniteInt iRet(*this);iRet<<=shifts;return iRet;}
     
151.     InfiniteInt     operator>>(INFINT_INT shifts)/*右移*/       {InfiniteInt iRet(*this);iRet>>=shifts;return iRet;}
     
152.     InfiniteInt     operator+(InfiniteInt&r)/*加法*/            {InfiniteInt iRet(*this);iRet+=r;return iRet;}
     
153.     InfiniteInt     operator-(InfiniteInt&r)/*减法*/            {InfiniteInt iRet(*this);iRet-=r;return iRet;}
     
154.     InfiniteInt     operator*(InfiniteInt&r)/*乘法*/            {InfiniteInt iRet(*this);iRet*=r;return iRet;}
     
155.     InfiniteInt     operator/(InfiniteInt&r)/*求商*/            {InfiniteInt iRet(*this);iRet/=r;return iRet;}
     
156.     InfiniteInt     operator%(InfiniteInt&r)/*求余*/            {InfiniteInt iRet(*this);iRet%=r;return iRet;}
     
157.     InfiniteInt     operator&(InfiniteInt&r)/*与*/              {InfiniteInt iRet(*this);iRet&=r;return iRet;}
     
158.     InfiniteInt     operator|(InfiniteInt&r)/*或*/              {InfiniteInt iRet(*this);iRet|=r;return iRet;}
     
159.     InfiniteInt     operator^(InfiniteInt&r)/*Xor*/             {InfiniteInt iRet(*this);iRet^=r;return iRet;}
     
160. 
     
161.     //针对INFINT_INT
     
162.     //判断
     
163.     bool            operator==(INFINT_INT i)/*判断是否等于*/    {return SignedCompare(InfiniteInt(i))==INFINT_EQUALTO;}
     
164.     bool            operator!=(INFINT_INT i)/*判断是否不等于*/  {return SignedCompare(InfiniteInt(i))!=INFINT_EQUALTO;}
     
165.     bool            operator> (INFINT_INT i)/*判断是否大于*/    {return SignedCompare(InfiniteInt(i))==INFINT_GREATERTHAN;}
     
166.     bool            operator< (INFINT_INT i)/*判断是否小于*/    {return SignedCompare(InfiniteInt(i))==INFINT_LESSTHAN;}
     
167.     bool            operator>=(INFINT_INT i)/*判断是否不小于*/  {return SignedCompare(InfiniteInt(i))!=INFINT_LESSTHAN;}
     
168.     bool            operator<=(INFINT_INT i)/*判断是否不大于*/  {return SignedCompare(InfiniteInt(i))!=INFINT_GREATERTHAN;}
     
169.     bool            operator&&(INFINT_INT i)/*判断是否都非零*/  {return (bool)*this&&(bool)InfiniteInt(i);}
     
170.     bool            operator||(INFINT_INT i)/*判断是否有非零*/  {return (bool)*this||(bool)InfiniteInt(i);}
     
171.    
     
172.     //累积性
     
173.     InfiniteInt&    operator+=(INFINT_INT i)/*加法*/            {return *this+=InfiniteInt(i);}
     
174.     InfiniteInt&    operator-=(INFINT_INT i)/*减法*/            {return *this-=InfiniteInt(i);}
     
175.     InfiniteInt&    operator*=(INFINT_INT i)/*乘法*/            {return *this*=InfiniteInt(i);}
     
176.     InfiniteInt&    operator/=(INFINT_INT i)/*求商*/            {return *this/=InfiniteInt(i);}
     
177.     InfiniteInt&    operator%=(INFINT_INT i)/*求余*/            {return *this%=InfiniteInt(i);}
     
178.     InfiniteInt&    operator&=(INFINT_INT i)/*与*/              {return *this&=InfiniteInt(i);}
     
179.     InfiniteInt&    operator|=(INFINT_INT i)/*或*/              {return *this|=InfiniteInt(i);}
     
180.     InfiniteInt&    operator^=(INFINT_INT i)/*Xor*/             {return *this^=InfiniteInt(i);}
     
181. 
     
182.     //非累积性
     
183.     InfiniteInt     operator+(INFINT_INT i)/*加法*/             {InfiniteInt iRet(*this);iRet+=InfiniteInt(i);return iRet;}
     
184.     InfiniteInt     operator-(INFINT_INT i)/*减法*/             {InfiniteInt iRet(*this);iRet-=InfiniteInt(i);return iRet;}
     
185.     InfiniteInt     operator*(INFINT_INT i)/*乘法*/             {InfiniteInt iRet(*this);iRet*=InfiniteInt(i);return iRet;}
     
186.     InfiniteInt     operator/(INFINT_INT i)/*求商*/             {InfiniteInt iRet(*this);iRet/=InfiniteInt(i);return iRet;}
     
187.     InfiniteInt     operator%(INFINT_INT i)/*求余*/             {InfiniteInt iRet(*this);iRet%=InfiniteInt(i);return iRet;}
     
188.     InfiniteInt     operator&(INFINT_INT i)/*与*/               {InfiniteInt iRet(*this);iRet&=InfiniteInt(i);return iRet;}
     
189.     InfiniteInt     operator|(INFINT_INT i)/*或*/               {InfiniteInt iRet(*this);iRet|=InfiniteInt(i);return iRet;}
     
190.     InfiniteInt     operator^(INFINT_INT i)/*Xor*/              {InfiniteInt iRet(*this);iRet^=InfiniteInt(i);return iRet;}
     
191. };
     
192. 
     
193. #endif

复制代码

经过测试证明这货能正常运行。只是运行速度不太理想。我拿它做10000!（一万的阶乘）算了整整一下午都没算出来。
源码的下载地址：
InfiniteInt.7z (39.57 KB, 下载次数: 5, 售价: 10 个宅币)

2014-4-10 02:27 上传

点击文件名下载附件

13*0217

{:soso_e179:} 可以试一试 1000！ 100！...

0xAA55

100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

0xAA55

500!=1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

0xAA55

1000!=402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

watermelon

支持！！
我用py简单算了一下10000的阶乘，计算速度还是很快的。


10000！= 28462596809170545189064132121198688901480514017027992307941799942744113400037644437729907867577847758158840621423175288300423399401535187390524211613827161748198241998275924182892597878981242531205946599625986706560161572036032397926328736717055741975962099479720346153698119897092611277500484198845410475544642442136573303076703628825803548967461117097369578603670191071512730587281041158640561281165385325968425825995584688146430425589836649317059251717204276597407446133400054194052462303436869154059404066227828248371512038322178644627183822923899638992827221879702459387693803094627332292570555459690027875282242544348021127559019169425429028916907219097083690539873747452483372899521802363282741217040268086769210451555840567172555372015852132829034279989818449313610640381489304499621599999359670892980190336998484404665419236258424947163178961192041233108268651071354516845540936033009607210346944377982349430780626069422302681885227592057029230843126188497606560742586279448827155956831533440534425446648416894580425709461673613187605234982286326452921529423479870603344290737158688499178932580691483168854251956006172372636323974420786924642956012306288720122652952964091508301336630982733806353972901506581822574295475894399765113865541208125788683704239208764484761569001264889271590706306409661628038784044485191643790807186112370622133415415065991843875961023926713276546986163657706626438638029848051952769536195259240930908614471907390768585755934786981720734372093104825475628567777694081564074962275254993384112809289637516990219870492405617531786346939798024619737079041868329931016554150742308393176878366923694849025999607729684293977427536263119825416681531891763234839190821000147178932184227805135181734921901146246875769835373441456013122615221391178759688367364087207937002992038279198038702372078039140312368997608152840306051116709484722224870389199993442071395836983063962232079115624044250808919914319837120445598344047556759489212101498152454543594285414390843564419984224855478532163624030098442855331829253154206551237079705816393460296247697010388742206441536626733715428700789122749340684336442889847100840641600093623935261248037975293343928764398316390312776450722479267851700826669598389526150759007349215197592659192708873202594066382118801988854748266048342256457705743973122259700671936061763513579529821794290797705327283267501488024443528681645026165662837546519006171873442260438919298506071515390031106684727360135816706437861756757439184376479658136100599638689552334648781746143243573224864326798481981458432703035895508420534788493364582482592033288089025782388233265770205248970937047210214248413342465268206806732314214483854074182139621846870108359582946965235632764870475718351616879235068366271743711915723361143070121120767608697851559721846485985918643641716850899625516820910793570231118518174775010804622585521314764897490660752877082897667514951009682329689732000622392888056658036140311285465929084078033974900664953205873164948093883816198658850827382468034897864757116679890423568018303504133875731972630897909435710687797301633918087868474943633533893373586906405848417828065196275826434429258058422212947649402948622670761832988229004072390403733168207417413251656688443079339447019208905620788387585342512820957359307018197708340163817638278562539516825426644614941044711579533262372815468794080423718587423026200264221822694188626212107297776657401018376182280136857586442185863011539843712299107010094061929413223202773193959467006713695377097897778118288242442920864816134179562017471831609687661043140497958198236445807368209404022211181530051433387076607063149616107771117448059552764348333385744040212757031851527298377435921878558552795591028664457917362007221858143309977294778923720717942857756271300923982397921957581197264742642878266682353915687857271620146192244266266708400765665625807109474398740110772811669918806268726626565583345665007890309050656074633078027158530817691223772813510584527326591626219647620571434880215630815259005343721141000303039242866457207328473481712034168186328968865048287367933398443971236735084527340196309427697652684170174990756947982757825835229994315633322107439131550124459005324702680312912392297979030417587823398622373535054642646913502503951009239286585108682088070662734733200354995720397086488066040929854607006339409885836349865466136727880748764700702458790118046518296111277090609016152022111461543158317669957060974618085359390400067892878548827850938637353703904049412684618991272871562655001270833039950257879931705431882752659225814948950746639976007316927310831735883056612614782997663188070063044632429112260691931278881566221591523270457695867512821990938942686601963904489718918597472925310322480210543841044325828472830584297804162405108110326914001900568784396341502696521048920272140232160234898588827371428695339681755106287470907473718188014223487248498558198439094651708364368994306189650243288353279667190184527620551085707626204244509623323204744707831190434499351442625501701771017379551124746159471731862701565571266295855125077711738338208419705893367323724453280456537178514960308802580284067847809414641838659226652806867978843250660537943046250287105104929347267471267499892634627358167146935060495110340755404658170393481046758485625967767959768299409334026387269378365320912287718077451152622642548771835461108886360843272806227776643097283879056728618036048633464893371439415250259459652501520959536157977135595794965729775650902694428088479761276664847003619648906043761934694270444070215317943583831051404915462608728486678750541674146731648999356381312866931427616863537305634586626957894568275065810235950814888778955073939365341937365700848318504475682215444067599203138077073539978036339267334549549296668759922530893898086430606532961793164029612492673080638031873912596151131890359351266480818568366770286537742390746582390910955517179770580797789289752490230737801753142680363914244720257728891784950078117889336629750436804214668197824272980697579391742229456683185815676816288797870624531246651727622758295493421483658868919299587402095696000243560305289829866386892076992834030549710266514322306125231915131843876903823706205399206933943716880466429711476743564486375026847698148853105354063328845062012173302630676481322931561043551941761050712449024873277273112091945865137493190965162497691657553812198566432207978666300398938660238607357858114394715872800893374165033792965832618436073133327526023605115524227228447251463863269369763762510196714380125691227784428426999440829152215904694437282498658085205186576292992775508833128672638418713277780874446643875352644733562441139447628780974650683952982108174967958836452273344694873793471790710064978236466016680572034297929207446822322848665839522211446859572858403863377278030227591530497865873919513650246274195899088374387331594287372029770620207120213038572175933211162413330422773742416353553587977065309647685886077301432778290328894795818404378858567772932094476778669357537460048142376741194182671636870481056911156215614357516290527351224350080604653668917458196549482608612260750293062761478813268955280736149022525819682815051033318132129659664958159030421238775645990973296728066683849166257949747922905361845563741034791430771561168650484292490281102992529678735298767829269040788778480262479222750735948405817439086251877946890045942060168605142772244486272469911146200149880662723538837809380628544384763053235070132028029488392008132135446450056134987017834271106158177289819290656498688081045562233703067254251277277330283498433595772575956224703707793387146593033088629699440318332665797514676502717346298883777397848218700718026741265997158728035440478432478674907127921672898523588486943546692255101337606377915164597254257116968477339951158998349081888281263984400505546210066988792614558214565319696909827253934515760408613476258778165867294410775358824162315779082538054746933540582469717674324523451498483027170396543887737637358191736582454273347490424262946011299881916563713847111849156915054768140411749801454265712394204425441028075806001388198650613759288539038922644322947990286482840099598675963580999112695367601527173086852756572147583507122298296529564917835071750835741362282545055620270969417476799259229774888627411314587676147531456895328093117052696486410187407673296986649236437382565475022816471926815559883196629848307776666840622314315884384910519058281816740764463033300119710293036455866594651869074475250837841987622990415911793682799760654186088721626654886492344391030923256910633775969739051781122764668486791736049404393703339351900609387268397299246478483727274770977466693599784857120156789000241947269220974984127323147401549980920381459821416481176357147801554231599667838534854486406936410556913531335231184053581348940938191821898694825383960989942822027599339635206217705343572073396250574216769465101608495601439303244304271576099527308684609204422226103154229984444802110098161333824827375218998738205315164927134498105950159974800571591912202154487748750103473246190633941303030892399411985006225902184164409988173214324422108554248620896250260604398180189026317781146617454999771440665232863846363847001655618153861098188111181734191305505024860345856755585637511729774299329074944236579668332700918367338977347901759248885660379952771540569083017311723894140326159612292912225191095948743805673381278538616491842786938417556898047100859868372033615175158097022566275200160956192229925401759878522038545913771783976389811198485803291048751666921195104514896677761598249468727420663437593207852618922687285527671324883267794152912839165407968344190239094803676688707838011367042753971396201424784935196735301444404037823526674437556740883025225745273806209980451233188102729012042997989005423126217968135237758041162511459175993279134176507292826762236897291960528289675223521425234217247841869317397460411877634604625637135309801590617736758715336803958559054827361876112151384673432884325090045645358186681905108731791346215730339540580987172013844377099279532797675531099381365840403556795731894141976511436325526270639743146526348120032720096755667701926242585057770617893798231096986788448546659527327061670308918277206432551919393673591346037757083193180845929565158875244597601729455720505595085929175506510115665075521635142318153548176884196032085050871496270494017684183980582594038182593986461260275954247433376226256287153916069025098985070798660621732200163593938611475394561406635675718526617031471453516753007499213865207768523824884600623735896608054951652406480547295869918694358811197833680141488078321213457152360124065922208508912956907835370576734671667863780908811283450395784812212101117250718383359083886187574661201317298217131072944737656265172310694884425498369514147383892477742320940207831200807235326288053906266018186050424938788677872495503255424284226596271050692646071767467502337805671893450110737377034119346113374033865364675136733661394731550211457104671161445253324850197901083431641989998414045044901130163759520675715567509485243580269104077637210998671624254795385312852889930956570729218673523216666097874989635362610529821472569482799996220825775840988458484250391189447608729685184983976367918242266571167166580157914500811657192200233759765317495922397884982814705506190689275625210462185661305800255607974609726715033327032310025274640428755556546883765838802543227403507431684278620637697054791726484378174446361520570933228587284315690756255569305558818822603590006739339952504379887470935079276181116276309771257983975996526612120317495882059435754883862282508401408885720583992400971219212548074097752974278775912566026443482713647231849125180866278708626116699989634812405803684794587364820124653663228889011636572270887757736152003450102268890189101673572058661410011723664762657835396364297819011647056170279631922332294228739309233330748258937626198997596530084135383241125899639629445129082802023225498936627506499530838925632246794695960669046906686292645006219740121782899872979704859021775060092893328957272392019589994471945147360850770400725717439318148461909406269545285030526341000565022226152309364882887122046454267700577148994335147162504252365173710266068647253458120186683273953682547456536553597546685788700056988360286686450740256993087483441094086086303707908295240576731684941855810482475304758923392801571302824106234999945932390521409856559565661346003396150515164758852742214732517999548977992849522746029855666700811871200856155016457400484170210303038996339253337466556817824410737409336919294104632307731994759826307383499600770372410446285414648704116273895649834555162165685114551383822047005483996671706246467566101291382048909121117229386244253158913066987462045587244806052829378148302622164542280421757760762365459828223070815503469404938317755053305094698999476119419231280721807216964378433313606760676965187138394338772485493689061845700572043696666465080734495814495966306246698679832872586300064215220210171813917325275173672262621454945468506006334692713838311715849753092643252486960220059099802663765386225463265168414963306369548086551101256757717890616694758344043486218485369591602172030456183497524162039926441331651884768606830642004858557924473340290142588876403712518642229016333691585063273727199596362912783344786218887871009533753551054688980236378263714926913289564339440899470121452134572117715657591451734895195016800621353927175419843876163543479806920886666227099512371706241924914282576453125769939735341673046864585181979668232015693792684926999983992413571941496882273704022820805171808003400480615261792013978945186295290558440703738300533552421153903385185829366779190610116306233673144419202893857201855569596330833615450290424822309297087124788002017383072060482680156675397593789931793515799958929562156307338416294599900276730832827716595064217966523190439250543226753731811755315476780739470338931185107297724318378972674957455778183345495942317353558291046967315391275975687281861691161083156337232639968881490543943261197182274996791176628553401860198315809629981791107208804992292016062059067271273599461871634945774995805337947187105456452579396024210259136415528398395201773012712514892051061708228008339985665786646920737114269682301770416324829479409558694699089379165191006305185352102345189798127619143061864362703081977124992751056732909481202057747100687703379708934229207183903744167503493818836342229284946790660285674293251642569044363473087656797056595677285291081242733154406580199802711579126254172797452862574865921933293805915239524735518887119860391319654287576290190503964083560246277534314409155642181729459941596061979622633242715863425977947348682074802021538734729707999753332987785531053820162169791880380753006334350766147737135939362651905222242528141084747045295688647757913502160922040348449149950778743107189655725492651282693489515795075486172341394610365176616750329948642244039659511882264981315925080185126386635308622223491094629059317829408195640484702456538305432056506924422671863255307640761872086780391711356363501269525091291020496042823232628996502758951052844368177415730941874894428065427561430975828127698124936993313028946670560414084308942231140912722238148470364341019630413630736771060038159590829746410114421358321042574358350220737173219745089035573187350445827238770728271406162997919629357224104477155051652535867544109395079218369015261138440382680054150924346511711436477899444553993653667727589565713987505542990824585609510036934663100673714708029927656933435500927189854050109917474979991554392031908961967615444686048175400695689471463928245383807010444181045506171305160584355817521032338465829201071030061124283407458607006060194830551364867021020364708470807422704371893706965688795617928713045224516842027402021966415605280335061293558739079393524404092584248380607177444609964035221891022961909032569042381374492494906892314330884224399631396391545854065286326468807581148748371408284176455226386313520264894016262494802388568231599102952620337126449279901938211134518446387544516391239377974190576649911764237637722282802318465738050121277809680315691477264910257503508758792248110223544524410872448565700755187132146592093548504552829170749596775404450779494836371756062326925757412813110241910373338080434325310884694831555729402265394972913817581338619457057799561808755951413644907613109617155928376585840036489374076822257523935988731081689667688287403837192827690431514106997678303819085690713091931340846019511147482766350724676534922040058626677632935516631939622498979912708004465982264899125226813124300528104995058595676527123591494442612554437618645029202881358582871789577224116380815161831603129728796987480139828621645629196153096358337313619724773332353025466571196902611237380629030242904275794549030022660847446513161741691916851746464945459696005330885252792083472495235473110674109099223541055506299687642153951249355986311346661725116890785633328935569150449485189113488301876365100638502565916433021928565596263914382895068324838727165616560111531517055222955765944972454788815532316417453267167978861141165355597588331979638070962998880767303616940317736448140427867784251232449974693421348217179595190698204602997172001174857303889719205597414742453011135869766256607770970225633261701108463784795555258504578058879440756064974127974530918418405207558526462208821483646754652237609210787539190454684852349759986044943322828073120679922402477507514105890774627334319091255451352225329275913842047384603056163154236552935312278389759446515787337343463172280001031380425481404022090580405056003860937403435068863081434683848900708938565050027569059678069404698435184535134141031615133683043714786642925389717165978629010728400758939700388317742648163725113277369926827709465342583596111881955092462062153978121197244762623771534452048069819082524943963962251113831177428978535825590832490480497516047104257569753442551515779815600370847230603484753977513688390404316017486248871339311818523029425425676202485688393970836748788453789172574145155917919035398535077200900594979352939459631213445503368260690059828717723533375221941915547303742062343262892968397015058892191112049249864792053410872349115430987182160055762209075732304626106597744947658346313025598636315029959672352476943975462530206788193304372284800209305354155640664838569378144603138697563459200233462606995955513484754147891180830329816421587452922952678937925647752029052675349356673744293182673374571642465407748267901046778759085408130531447176455869894169668940436489952465247443988349583871206296485413357553813419500498743813369062703973874586604296871595820715766599826607317005624465541763024501349159567288942619746144496908671655859782729228702723774835097362901019130417812735773037781804081589136005207315806941034305003184349342360269244733060013861119781774472669608928321052543116496033420102032603863672532889648333405862204843616575362001468405476649666473566979572953394809138263703324220930839366954980688240491622063147911494642042500022450413425558561937442905257252436320054487441524307305215070491020434076572476865095751174125413729531644521765577235348601821566833352520532830000108344008762266843817023235605645158256954177359197813649975559601912567744942717986360045847405209290089397315276024304951653864431388147876977541478757432610159879709758855625806766197973098472460769484821127948427976536607055051639104415022554420329721292033009353356687294595912327965886376486894188433640548494009574965791657687213927330153555097865114767947399690623184878377515462613823651665956337209345708208301840482797005728071432925727577436229587047361641609731817241594204270366066404089740245521530725227388637241859646455223673260411164598464020010216920823315155388821071527191267876531795071908204525100447821291318544054814494151867114207103693891129125012750853466337717749376016543454696390042711129829255096830420665725364279472200020835313883708781649957189717629338794854271276882652003766325924561614868744897471519366219275665852462114457407010675380427564184440834805203838265052601698584060084788422421887856927897751810442805474427229455167420335686460609977973124950433321425205053675790499520783597650415379001132579536040655172654879022173595444151139429231648950663177813039057462082449171921311864129633704661406456900178942356738775523130952785912774533241855442484484493664210731348819180640189222317302156645813473186449997905781662091469870718039388885781280740226363602294114354869871402143572055947730892808653678920201935102605361567924483276749476117858316071865710310842200560259545115191391309119544447844361032741876102338843391687589233423790859841968266525610628751237572318491474951945985728897934981791761822652480408237128109790772638864286067917082288575852703470839714561619926247844794692794996845945632382702297364173503430783194115698247820013290851202878474805860188960045901745974055630732714487679085288867978809970695240681006625611440014983413580889737246844064948857074167687916413224205373654067330186392497910915474785959163865597507090581175924899502214799250945635582514315814464060134283490422798357939659258985200763845646681640732681928346007767285876284900068874564639274964415904034033672337814491597032941787294155061054129515400159393851663929325677429557549480046658273579653990940233543644649376827272541873627547532976808190325336141086433084237771738995221536763095302045902438694632702895293994483013577589081214884558493819874505920914067209522469096263076941753340983698859363700314973728977996360018626500174929290087931189997822963712306642297996163582572600112288983647651418045975770042120833949364659647336464289044499325396227091907373705772051322815957863227591912786054297862953188615559804728160710864132803585400160055575686855791785977899197902656592621283007225351401525973569300729015392211116868504740402172174442051738000251361000494534119324331668344243125963098812396962202358858395587831685194833126653577353244379935683215269177042249034574534858913812582681366908929476809052635560638119661306063936938411817713545929884317232912236262458868394202889981693561169865429884776513118227662526739978808816010470651542335015671353744817086234314662531190291040152262927104099285072418843329007277794754111637552176563589316326636049381218401837512818884771168975479483767664084842753623074019542183217985496260666590347925816342392670947839907062923166535037285019751324813803837070894638925470887039085723581006130628646664710006104352115778926613432214655311411882596942926284522109026688414975763341554921135581254616558078273470115814006008345762133130389987843270653719956709570847385786092649188858378739239165554263577301292243641604062551736892335636568854365851646207821875741724364525814143487632761341752707376754922276287782264765154315341585713773522730335403376364204258034257264749686217823666951353410677378421131371131987373222891805275062812277716412494412401207125954319991746574745892582613712825555535080404143944557295994554635608487251339462936358940832098964801619583130429720964794128539388996265368928263807677168759588502216464582430940165009688797366157733560316836710386895228270941509545222744002735499253670214715994056544813842186380128799900820933576320736369405991424263718294000613741900579513096298545330748197802568301089672873802234820488862973130369689882640657904781562389778485365025691064231795736025330908763271784911189748432246868086340383964176127605788646574472284824932687443062551220506955168464669477183681911432873544815836350548146411099960143390595799766290646881295025039150923633011076070632863317393378149693380247580035052789782755750928604039420506342939327064636161031822879248152679306862749237275631852225654266008556849497720285909150930495425967473648331437236349555448901598668408362176913559656039519670425368863482369587129462524759031776813184977588276576740482558136502103649585505703259219957675334264223783723586058509403583977103476670644788640831109650302565215607464019652716999732373465237173456595514559493098166644006211599349133180135150528651842178828026343325934755850761168697709125580056185683710540856081249519403148064618719402577663285267019698387567561524696759028106864896869293315954352097687527137201616160931174250199709289684940034696242325688410665113304377412256176258658941236728171145526423894512631717834790276921171452887352955019336759218908006048633737786728180610254782570436788449503518925787499836694785908612975543084122677060954347612133717433156783790162012337237023338316414706428592185977610158232721997915062871868186750981665537745013020880333904353639770263363809098526494532628146558065546504823486429495390613257400496912888340518222933644476683855037967975809619983575807027759535968788226194659612223044549275600274955168583542582295336042834426318478068825395450746691877897765406038432512843812811316856204608617289408229658626174420766920297427930088129519854678713548623236610413216581279267151545961594352593456757445992307889205519540082316409719591250025455237503106735639748835542480449681383030671851931491335789202123605308199952020584503423499932150962634977812456658304680581824563524814625849331926195406884818446445248429486063016169476663242625231476322371109695369483824482316410396224507675405614287468267835723704895606990652792688455844512046654853378534026646645042339638488257719874953611300494215593735545211926186721478265416885604094928290056616883807637656690510740892510549165222968878676968631652514917701499900066637344546120262780701925698706225540928945194718778004306130021828287425867048748480826948573444778244078734102710824870269523830804910960482013901294024631244800159336670212658317677879752965963472576894326540435889267293950687860830626266263287392087327302547910099932113388977807814336728791448768373686467748528777737403547472871644217767820712964506270880978637928144071192505141148004907055608097229299792441471062852247029870699869227676341773513258602908903875707454368077876422385333700692089616351009233587303986543906071880952557553380364725895007306772122528078179471056481171378557451057691044322925429024149433588396093679321361696954251299731031032804436954501929843820842383121265825740594509426942777307124802176915781835720087170538773256017987133005505911377823841791640280841409623820847637393013930778428554545222367559824666250608754284876104145661362227642405914304455580856318180935230407793891614902116292400515074914068443203230365609954878620999194306564455332547135557365318516011700321550690787716752062881527885897149410320986984083048966524351030502444679931779147659103428949129054120361601695671222140806369405940304552186212879933092856231022418446365289097444640151986623183881962444822590783585914043686193019041458962693878907034982169868696934448086213990534591792826654304798207219634134755646525483143771156678459077797196510772468000293581546267646310224279007313631352522067062951125935874473134186492497282784796644585448962932905262058065248588707020879389134476083344653170939242408249328008915731319541348311820927752486880548733943315867562666122179355051190609992911379445634995627391898459029021713155706096267881673302940198464237390445098028030948975981259252055850973537436556825780313681902007151675693827281818824587541710721180806556448039122504537089422695358382192535075692834095639859265599740391316709290043996275976830375217503360879028295673068862263077729733533853682668734519035709709687322323738300494090123239274318759046526327095178406267264828893646896593219169521106361729757074376148061601331104911692271318609404145014842866423634716982892418180484365230538864559809839273836490685480823014267803143937440431807822678779494006206489151248952516543005634448375046751754207043313372486870633237561645232360481932024377596890914783372179553676992603235715185513391098402739063753280702313301755754269396202629423910945323537910125948964941812563672992967084250667599803456273455598559628512281414582556024841783305645240508450065988755987518601335860624932784487772006842296591945516539562982960591610046578907214842054861830418175604559815168088031783080261445994444677918012432146400983610678683412974872596729258786806223080115822026289014364459002301645823666709265571264559925790622304745235625575111770791512002789380975775468546121017307522799241407026308137792971909461413145802081087738121624539858769697371425881836152605069380926917712087321915005831977113322793572385071940612761291872572099404930250277748156614021327434743881966413330052634229082906400927944924808556131183440161804801357032507836323938921567643159620442612809700944107776130638909071294456394056601559246025454204771186140420155233371270501377121034570009578009389265329385720478576508777149663403003562380595757191609382171312222810465858388943507176431939973012661591423837170284400120399485880996231859472474858776584355077006934099220340378772192728370301380838144394114984971730766162961342059105014814283949700695951676939041557902856356911055547312684571497449635320554677940775184056667637222969090346128706829887104278761090090999160443821794511763620835379716161833124364431267855435550800507986124664397724135502128238026726719914989727248512981287283697489276420792868666970177259794407858155909332508554131299946581118527691652464790819119384233275897699573012098103009171001695718791616942270079528915191912521053891838538959315167400505723817401030621004380243011187977704252328073236575129609372456053680037516596164236147709330391224409752871732067976128120428026739256557305675931512645750047875756531854825821411574030473147492511910835615765732002546109686701890307648531373832912682481741181359032826625082549313211431478953352317043989053928534946642886074268371824902498092479487226633686823799580875637040808655649321905489637785549531167397935270799470452399153297534358690514105864096534514182896474439367182852711843560799285895978176543950113088848419163516673213692860830956744502801800373716458009168082972708715609185038654053436660045504985624687376022557041595800250174095361839287643458003670864954057941720085136357127163768323493134230703821274484501440529541695374381945459456533165140990993722722801019654652726227831512103467686166826131471843610025517863247950150022953695466317739589344131481485834694374523981159954666071205997794363440185078360899108948073419633939259318973940943110042116729120199722626609871927014024105805515315100109804996044147291039451030312664114726736839973315035036742741546992633165270432940675237449075056739508929674779115800864399992564817208847429250821546279856079127768611946086210349405535850134472190244543824521089284409498132717010673966471114931896789977661595488186193176900175027901783824624387873831483279500879026433992577026588005849778984624295660321276945810824348129690840972550671054732471317254997191901039553305847040728081693158626093886019147689944137673621432083607375131574376316754666479186753896571555100850626810005119827486807780592667765654100834778571024250133253391587384761024129794736751001163498977803745930025457609870671092153597115178252014281216647543034075128600240297038428615984289816602143429849088917359682192284469123035904329877231843309914187264674607558318725713138832356015809009594182530207799397648462597901883341793830920965841463574411985878296475850943053008148341821747826603773762252997703468752903517310792083220038080809212164346586817989810504274375385786789186350517717501606531826406928883250135919517178537687865881752366421534010961295763074762648070312757365787762352859057153932484576503944390496668087711899192498933896524852395536795827530614167131757915756386606004839994179548705868209201195154952031294562451315422506574858629161606523796643010172693950282294667489681746821163996794950294284013099235901278250437428192557634533217576162292751110598368271567229778620053722932314082887058749444060116236521627717558503013451471452765841864277071769968435499620257547431811994883385806759692359580622165832464092095350648357935817742903018315351290014321495518177456908388719320697769695657771754499149911431368950836160692539606469893374870942933219185601299108564470256257163505508620689240297589684714283678684735455533583477652536156578189996983068654671736445996343136468195427420490472433064675001442697508322369013083895492637066778406531328664886080129513771720847581157719491012345141774941482773580041432667332379617716965698582785832300505265883502247868050648201444570593197343382923860072601696510903258980909912837652275381493529845099414966933862815568031306981064525192703818515872648691762563239441425216118427769145067718411735714396681005615483952443154944864238384298900399826113322468963346522104692545137969276009719645338955332105584245640187448611050959111766828942711640054010503770420346052521318228045892998637903572350665108782350043349942391285236308896510989246641056331584171142885304143772286629832318970869030400301325951476774237516158840915838059151673504519131178193943428482922272304061422582078027829148070426761629302539228321084917759984200595105312164731818409493139800444072847325902609169730998153853939031280878823902948001579008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000