function BigInteger(n,t,i){n!=null&&("number"==typeof n?this.fromNumber(n,t,i):t==null&&"string"!=typeof n?this.fromString(n,256):this.fromString(n,t))}function nbi(){return new BigInteger(null)}function am1(n,t,i,r,u,f){while(--f>=0){var e=t*this[n++]+i[r]+u;u=Math.floor(e/67108864);i[r++]=e&67108863}return u}function am2(n,t,i,r,u,f){for(var o=t&32767,s=t>>15;--f>=0;){var e=this[n]&32767,h=this[n++]>>15,c=s*e+h*o;e=o*e+((c&32767)<<15)+i[r]+(u&1073741823);u=(e>>>30)+(c>>>15)+s*h+(u>>>30);i[r++]=e&1073741823}return u}function am3(n,t,i,r,u,f){for(var o=t&16383,s=t>>14;--f>=0;){var e=this[n]&16383,h=this[n++]>>14,c=s*e+h*o;e=o*e+((c&16383)<<14)+i[r]+u;u=(e>>28)+(c>>14)+s*h;i[r++]=e&268435455}return u}function int2char(n){return BI_RM.charAt(n)}function intAt(n,t){var i=BI_RC[n.charCodeAt(t)];return i==null?-1:i}function bnpCopyTo(n){for(var t=this.t-1;t>=0;--t)n[t]=this[t];n.t=this.t;n.s=this.s}function bnpFromInt(n){this.t=1;this.s=n<0?-1:0;n>0?this[0]=n:n<-1?this[0]=n+DV:this.t=0}function nbv(n){var t=nbi();return t.fromInt(n),t}function bnpFromString(n,t){var r,u;if(t==16)r=4;else if(t==8)r=3;else if(t==256)r=8;else if(t==2)r=1;else if(t==32)r=5;else if(t==4)r=2;else{this.fromRadix(n,t);return}this.t=0;this.s=0;for(var f=n.length,e=!1,i=0;--f>=0;){if(u=r==8?n[f]&255:intAt(n,f),u<0){n.charAt(f)=="-"&&(e=!0);continue}e=!1;i==0?this[this.t++]=u:i+r>this.DB?(this[this.t-1]|=(u&(1<<this.DB-i)-1)<<i,this[this.t++]=u>>this.DB-i):this[this.t-1]|=u<<i;i+=r;i>=this.DB&&(i-=this.DB)}r==8&&(n[0]&128)!=0&&(this.s=-1,i>0&&(this[this.t-1]|=(1<<this.DB-i)-1<<i));this.clamp();e&&BigInteger.ZERO.subTo(this,this)}function bnpClamp(){for(var n=this.s&this.DM;this.t>0&&this[this.t-1]==n;)--this.t}function bnToString(n){var t;if(this.s<0)return"-"+this.negate().toString(n);if(n==16)t=4;else if(n==8)t=3;else if(n==2)t=1;else if(n==32)t=5;else if(n==64)t=6;else if(n==4)t=2;else return this.toRadix(n);var o=(1<<t)-1,u,f=!1,e="",r=this.t,i=this.DB-r*this.DB%t;if(r-->0)for(i<this.DB&&(u=this[r]>>i)>0&&(f=!0,e=int2char(u));r>=0;)i<t?u=(this[r]&(1<<i)-1)<<t-i|this[--r]>>(i+=this.DB-t):(u=this[r]>>(i-=t)&o,i<=0&&(i+=this.DB,--r)),u>0&&(f=!0),f&&(e+=int2char(u));return f?e:"0"}function bnNegate(){var n=nbi();return BigInteger.ZERO.subTo(this,n),n}function bnAbs(){return this.s<0?this.negate():this}function bnCompareTo(n){var t=this.s-n.s,i;if(t!=0||(i=this.t,t=i-n.t,t!=0))return t;while(--i>=0)if((t=this[i]-n[i])!=0)return t;return 0}function nbits(n){var i=1,t;return(t=n>>>16)!=0&&(n=t,i+=16),(t=n>>8)!=0&&(n=t,i+=8),(t=n>>4)!=0&&(n=t,i+=4),(t=n>>2)!=0&&(n=t,i+=2),(t=n>>1)!=0&&(n=t,i+=1),i}function bnBitLength(){return this.t<=0?0:this.DB*(this.t-1)+nbits(this[this.t-1]^this.s&this.DM)}function bnpDLShiftTo(n,t){for(var i=this.t-1;i>=0;--i)t[i+n]=this[i];for(i=n-1;i>=0;--i)t[i]=0;t.t=this.t+n;t.s=this.s}function bnpDRShiftTo(n,t){for(var i=n;i<this.t;++i)t[i-n]=this[i];t.t=Math.max(this.t-n,0);t.s=this.s}function bnpLShiftTo(n,t){for(var u=n%this.DB,e=this.DB-u,o=(1<<e)-1,r=Math.floor(n/this.DB),f=this.s<<u&this.DM,i=this.t-1;i>=0;--i)t[i+r+1]=this[i]>>e|f,f=(this[i]&o)<<u;for(i=r-1;i>=0;--i)t[i]=0;t[r]=f;t.t=this.t+r+1;t.s=this.s;t.clamp()}function bnpRShiftTo(n,t){var i,r;if(t.s=this.s,i=Math.floor(n/this.DB),i>=this.t){t.t=0;return}var u=n%this.DB,f=this.DB-u,e=(1<<u)-1;for(t[0]=this[i]>>u,r=i+1;r<this.t;++r)t[r-i-1]|=(this[r]&e)<<f,t[r-i]=this[r]>>u;u>0&&(t[this.t-i-1]|=(this.s&e)<<f);t.t=this.t-i;t.clamp()}function bnpSubTo(n,t){for(var r=0,i=0,u=Math.min(n.t,this.t);r<u;)i+=this[r]-n[r],t[r++]=i&this.DM,i>>=this.DB;if(n.t<this.t){for(i-=n.s;r<this.t;)i+=this[r],t[r++]=i&this.DM,i>>=this.DB;i+=this.s}else{for(i+=this.s;r<n.t;)i-=n[r],t[r++]=i&this.DM,i>>=this.DB;i-=n.s}t.s=i<0?-1:0;i<-1?t[r++]=this.DV+i:i>0&&(t[r++]=i);t.t=r;t.clamp()}function bnpMultiplyTo(n,t){var r=this.abs(),u=n.abs(),i=r.t;for(t.t=i+u.t;--i>=0;)t[i]=0;for(i=0;i<u.t;++i)t[i+r.t]=r.am(0,u[i],t,i,0,r.t);t.s=0;t.clamp();this.s!=n.s&&BigInteger.ZERO.subTo(t,t)}function bnpSquareTo(n){for(var i=this.abs(),t=n.t=2*i.t,r;--t>=0;)n[t]=0;for(t=0;t<i.t-1;++t)r=i.am(t,i[t],n,2*t,0,1),(n[t+i.t]+=i.am(t+1,2*i[t],n,2*t+1,r,i.t-t-1))>=i.DV&&(n[t+i.t]-=i.DV,n[t+i.t+1]=1);n.t>0&&(n[n.t-1]+=i.am(t,i[t],n,2*t,0,1));n.s=0;n.clamp()}function bnpDivRemTo(n,t,i){var e=n.abs(),h,u,c,a;if(!(e.t<=0)){if(h=this.abs(),h.t<e.t){t!=null&&t.fromInt(0);i!=null&&this.copyTo(i);return}i==null&&(i=nbi());var r=nbi(),v=this.s,p=n.s,s=this.DB-nbits(e[e.t-1]);if(s>0?(e.lShiftTo(s,r),h.lShiftTo(s,i)):(e.copyTo(r),h.copyTo(i)),u=r.t,c=r[u-1],c!=0){var y=c*(1<<this.F1)+(u>1?r[u-2]>>this.F2:0),w=this.FV/y,b=(1<<this.F1)/y,k=1<<this.F2,o=i.t,l=o-u,f=t==null?nbi():t;for(r.dlShiftTo(l,f),i.compareTo(f)>=0&&(i[i.t++]=1,i.subTo(f,i)),BigInteger.ONE.dlShiftTo(u,f),f.subTo(r,r);r.t<u;)r[r.t++]=0;while(--l>=0)if(a=i[--o]==c?this.DM:Math.floor(i[o]*w+(i[o-1]+k)*b),(i[o]+=r.am(0,a,i,l,0,u))<a)for(r.dlShiftTo(l,f),i.subTo(f,i);i[o]<--a;)i.subTo(f,i);t!=null&&(i.drShiftTo(u,t),v!=p&&BigInteger.ZERO.subTo(t,t));i.t=u;i.clamp();s>0&&i.rShiftTo(s,i);v<0&&BigInteger.ZERO.subTo(i,i)}}}function bnMod(n){var t=nbi();return this.abs().divRemTo(n,null,t),this.s<0&&t.compareTo(BigInteger.ZERO)>0&&n.subTo(t,t),t}function Classic(n){this.m=n}function cConvert(n){return n.s<0||n.compareTo(this.m)>=0?n.mod(this.m):n}function cRevert(n){return n}function cReduce(n){n.divRemTo(this.m,null,n)}function cMulTo(n,t,i){n.multiplyTo(t,i);this.reduce(i)}function cSqrTo(n,t){n.squareTo(t);this.reduce(t)}function bnpInvDigit(){var t,n;return this.t<1?0:(t=this[0],(t&1)==0)?0:(n=t&3,n=n*(2-(t&15)*n)&15,n=n*(2-(t&255)*n)&255,n=n*(2-((t&65535)*n&65535))&65535,n=n*(2-t*n%this.DV)%this.DV,n>0?this.DV-n:-n)}function Montgomery(n){this.m=n;this.mp=n.invDigit();this.mpl=this.mp&32767;this.mph=this.mp>>15;this.um=(1<<n.DB-15)-1;this.mt2=2*n.t}function montConvert(n){var t=nbi();return n.abs().dlShiftTo(this.m.t,t),t.divRemTo(this.m,null,t),n.s<0&&t.compareTo(BigInteger.ZERO)>0&&this.m.subTo(t,t),t}function montRevert(n){var t=nbi();return n.copyTo(t),this.reduce(t),t}function montReduce(n){for(var i,t,r;n.t<=this.mt2;)n[n.t++]=0;for(i=0;i<this.m.t;++i)for(t=n[i]&32767,r=t*this.mpl+((t*this.mph+(n[i]>>15)*this.mpl&this.um)<<15)&n.DM,t=i+this.m.t,n[t]+=this.m.am(0,r,n,i,0,this.m.t);n[t]>=n.DV;)n[t]-=n.DV,n[++t]++;n.clamp();n.drShiftTo(this.m.t,n);n.compareTo(this.m)>=0&&n.subTo(this.m,n)}function montSqrTo(n,t){n.squareTo(t);this.reduce(t)}function montMulTo(n,t,i){n.multiplyTo(t,i);this.reduce(i)}function bnpIsEven(){return(this.t>0?this[0]&1:this.s)==0}function bnpExp(n,t){var e;if(n>4294967295||n<1)return BigInteger.ONE;var i=nbi(),r=nbi(),u=t.convert(this),f=nbits(n)-1;for(u.copyTo(i);--f>=0;)t.sqrTo(i,r),(n&1<<f)>0?t.mulTo(r,u,i):(e=i,i=r,r=e);return t.revert(i)}function bnModPowInt(n,t){var i;return i=n<256||t.isEven()?new Classic(t):new Montgomery(t),this.exp(n,i)}function bnClone(){var n=nbi();return this.copyTo(n),n}function bnIntValue(){if(this.s<0){if(this.t==1)return this[0]-this.DV;if(this.t==0)return-1}else{if(this.t==1)return this[0];if(this.t==0)return 0}return(this[1]&(1<<32-this.DB)-1)<<this.DB|this[0]}function bnByteValue(){return this.t==0?this.s:this[0]<<24>>24}function bnShortValue(){return this.t==0?this.s:this[0]<<16>>16}function bnpChunkSize(n){return Math.floor(Math.LN2*this.DB/Math.log(n))}function bnSigNum(){return this.s<0?-1:this.t<=0||this.t==1&&this[0]<=0?0:1}function bnpToRadix(n){if(n==null&&(n=10),this.signum()==0||n<2||n>36)return"0";var e=this.chunkSize(n),u=Math.pow(n,e),f=nbv(u),t=nbi(),i=nbi(),r="";for(this.divRemTo(f,t,i);t.signum()>0;)r=(u+i.intValue()).toString(n).substr(1)+r,t.divRemTo(f,t,i);return i.intValue().toString(n)+r}function bnpFromRadix(n,t){var r,f;this.fromInt(0);t==null&&(t=10);var e=this.chunkSize(t),s=Math.pow(t,e),o=!1,u=0,i=0;for(r=0;r<n.length;++r){if(f=intAt(n,r),f<0){n.charAt(r)=="-"&&this.signum()==0&&(o=!0);continue}i=t*i+f;++u>=e&&(this.dMultiply(s),this.dAddOffset(i,0),u=0,i=0)}u>0&&(this.dMultiply(Math.pow(t,u)),this.dAddOffset(i,0));o&&BigInteger.ZERO.subTo(this,this)}function bnpFromNumber(n,t,i){if("number"==typeof t)if(n<2)this.fromInt(1);else for(this.fromNumber(n,i),this.testBit(n-1)||this.bitwiseTo(BigInteger.ONE.shiftLeft(n-1),op_or,this),this.isEven()&&this.dAddOffset(1,0);!this.isProbablePrime(t);)this.dAddOffset(2,0),this.bitLength()>n&&this.subTo(BigInteger.ONE.shiftLeft(n-1),this);else{var r=[],u=n&7;r.length=(n>>3)+1;t.nextBytes(r);u>0?r[0]&=(1<<u)-1:r[0]=0;this.fromString(r,256)}}function bnToByteArray(){var i=this.t,u=[],n,t,r;if(u[0]=this.s,n=this.DB-i*this.DB%8,r=0,i-->0)for(n<this.DB&&(t=this[i]>>n)!=(this.s&this.DM)>>n&&(u[r++]=t|this.s<<this.DB-n);i>=0;)n<8?t=(this[i]&(1<<n)-1)<<8-n|this[--i]>>(n+=this.DB-8):(t=this[i]>>(n-=8)&255,n<=0&&(n+=this.DB,--i)),(t&128)!=0&&(t|=-256),r==0&&(this.s&128)!=(t&128)&&++r,(r>0||t!=this.s)&&(u[r++]=t);return u}function bnEquals(n){return this.compareTo(n)==0}function bnMin(n){return this.compareTo(n)<0?this:n}function bnMax(n){return this.compareTo(n)>0?this:n}function bnpBitwiseTo(n,t,i){for(var u,f=Math.min(n.t,this.t),r=0;r<f;++r)i[r]=t(this[r],n[r]);if(n.t<this.t){for(u=n.s&this.DM,r=f;r<this.t;++r)i[r]=t(this[r],u);i.t=this.t}else{for(u=this.s&this.DM,r=f;r<n.t;++r)i[r]=t(u,n[r]);i.t=n.t}i.s=t(this.s,n.s);i.clamp()}function op_and(n,t){return n&t}function bnAnd(n){var t=nbi();return this.bitwiseTo(n,op_and,t),t}function op_or(n,t){return n|t}function bnOr(n){var t=nbi();return this.bitwiseTo(n,op_or,t),t}function op_xor(n,t){return n^t}function bnXor(n){var t=nbi();return this.bitwiseTo(n,op_xor,t),t}function op_andnot(n,t){return n&~t}function bnAndNot(n){var t=nbi();return this.bitwiseTo(n,op_andnot,t),t}function bnNot(){for(var t=nbi(),n=0;n<this.t;++n)t[n]=this.DM&~this[n];return t.t=this.t,t.s=~this.s,t}function bnShiftLeft(n){var t=nbi();return n<0?this.rShiftTo(-n,t):this.lShiftTo(n,t),t}function bnShiftRight(n){var t=nbi();return n<0?this.lShiftTo(-n,t):this.rShiftTo(n,t),t}function lbit(n){if(n==0)return-1;var t=0;return(n&65535)==0&&(n>>=16,t+=16),(n&255)==0&&(n>>=8,t+=8),(n&15)==0&&(n>>=4,t+=4),(n&3)==0&&(n>>=2,t+=2),(n&1)==0&&++t,t}function bnGetLowestSetBit(){for(var n=0;n<this.t;++n)if(this[n]!=0)return n*this.DB+lbit(this[n]);return this.s<0?this.t*this.DB:-1}function cbit(n){for(var t=0;n!=0;)n&=n-1,++t;return t}function bnBitCount(){for(var t=0,i=this.s&this.DM,n=0;n<this.t;++n)t+=cbit(this[n]^i);return t}function bnTestBit(n){var t=Math.floor(n/this.DB);return t>=this.t?this.s!=0:(this[t]&1<<n%this.DB)!=0}function bnpChangeBit(n,t){var i=BigInteger.ONE.shiftLeft(n);return this.bitwiseTo(i,t,i),i}function bnSetBit(n){return this.changeBit(n,op_or)}function bnClearBit(n){return this.changeBit(n,op_andnot)}function bnFlipBit(n){return this.changeBit(n,op_xor)}function bnpAddTo(n,t){for(var r=0,i=0,u=Math.min(n.t,this.t);r<u;)i+=this[r]+n[r],t[r++]=i&this.DM,i>>=this.DB;if(n.t<this.t){for(i+=n.s;r<this.t;)i+=this[r],t[r++]=i&this.DM,i>>=this.DB;i+=this.s}else{for(i+=this.s;r<n.t;)i+=n[r],t[r++]=i&this.DM,i>>=this.DB;i+=n.s}t.s=i<0?-1:0;i>0?t[r++]=i:i<-1&&(t[r++]=this.DV+i);t.t=r;t.clamp()}function bnAdd(n){var t=nbi();return this.addTo(n,t),t}function bnSubtract(n){var t=nbi();return this.subTo(n,t),t}function bnMultiply(n){var t=nbi();return this.multiplyTo(n,t),t}function bnSquare(){var n=nbi();return this.squareTo(n),n}function bnDivide(n){var t=nbi();return this.divRemTo(n,t,null),t}function bnRemainder(n){var t=nbi();return this.divRemTo(n,null,t),t}function bnDivideAndRemainder(n){var t=nbi(),i=nbi();return this.divRemTo(n,t,i),[t,i]}function bnpDMultiply(n){this[this.t]=this.am(0,n-1,this,0,0,this.t);++this.t;this.clamp()}function bnpDAddOffset(n,t){if(n!=0){while(this.t<=t)this[this.t++]=0;for(this[t]+=n;this[t]>=this.DV;)this[t]-=this.DV,++t>=this.t&&(this[this.t++]=0),++this[t]}}function NullExp(){}function nNop(n){return n}function nMulTo(n,t,i){n.multiplyTo(t,i)}function nSqrTo(n,t){n.squareTo(t)}function bnPow(n){return this.exp(n,new NullExp)}function bnpMultiplyLowerTo(n,t,i){var r=Math.min(this.t+n.t,t),u;for(i.s=0,i.t=r;r>0;)i[--r]=0;for(u=i.t-this.t;r<u;++r)i[r+this.t]=this.am(0,n[r],i,r,0,this.t);for(u=Math.min(n.t,t);r<u;++r)this.am(0,n[r],i,r,0,t-r);i.clamp()}function bnpMultiplyUpperTo(n,t,i){--t;var r=i.t=this.t+n.t-t;for(i.s=0;--r>=0;)i[r]=0;for(r=Math.max(t-this.t,0);r<n.t;++r)i[this.t+r-t]=this.am(t-r,n[r],i,0,0,this.t+r-t);i.clamp();i.drShiftTo(1,i)}function Barrett(n){this.r2=nbi();this.q3=nbi();BigInteger.ONE.dlShiftTo(2*n.t,this.r2);this.mu=this.r2.divide(n);this.m=n}function barrettConvert(n){if(n.s<0||n.t>2*this.m.t)return n.mod(this.m);if(n.compareTo(this.m)<0)return n;var t=nbi();return n.copyTo(t),this.reduce(t),t}function barrettRevert(n){return n}function barrettReduce(n){for(n.drShiftTo(this.m.t-1,this.r2),n.t>this.m.t+1&&(n.t=this.m.t+1,n.clamp()),this.mu.multiplyUpperTo(this.r2,this.m.t+1,this.q3),this.m.multiplyLowerTo(this.q3,this.m.t+1,this.r2);n.compareTo(this.r2)<0;)n.dAddOffset(1,this.m.t+1);for(n.subTo(this.r2,n);n.compareTo(this.m)>=0;)n.subTo(this.m,n)}function barrettSqrTo(n,t){n.squareTo(t);this.reduce(t)}function barrettMulTo(n,t,i){n.multiplyTo(t,i);this.reduce(i)}function bnModPow(n,t){var i=n.bitLength(),c,r=nbv(1),f,v;if(i<=0)return r;c=i<18?1:i<48?3:i<144?4:i<768?5:6;f=i<8?new Classic(t):t.isEven()?new Barrett(t):new Montgomery(t);var s=[],u=3,l=c-1,y=(1<<c)-1;if(s[1]=f.convert(this),c>1)for(v=nbi(),f.sqrTo(s[1],v);u<=y;)s[u]=nbi(),f.mulTo(v,s[u-2],s[u]),u+=2;var e=n.t-1,h,p=!0,o=nbi(),a;for(i=nbits(n[e])-1;e>=0;){for(i>=l?h=n[e]>>i-l&y:(h=(n[e]&(1<<i+1)-1)<<l-i,e>0&&(h|=n[e-1]>>this.DB+i-l)),u=c;(h&1)==0;)h>>=1,--u;if((i-=u)<0&&(i+=this.DB,--e),p)s[h].copyTo(r),p=!1;else{while(u>1)f.sqrTo(r,o),f.sqrTo(o,r),u-=2;u>0?f.sqrTo(r,o):(a=r,r=o,o=a);f.mulTo(o,s[h],r)}while(e>=0&&(n[e]&1<<i)==0)f.sqrTo(r,o),a=r,r=o,o=a,--i<0&&(i=this.DB-1,--e)}return f.revert(r)}function bnGCD(n){var i=this.s<0?this.negate():this.clone(),t=n.s<0?n.negate():n.clone(),f,u,r;if(i.compareTo(t)<0&&(f=i,i=t,t=f),u=i.getLowestSetBit(),r=t.getLowestSetBit(),r<0)return i;for(u<r&&(r=u),r>0&&(i.rShiftTo(r,i),t.rShiftTo(r,t));i.signum()>0;)(u=i.getLowestSetBit())>0&&i.rShiftTo(u,i),(u=t.getLowestSetBit())>0&&t.rShiftTo(u,t),i.compareTo(t)>=0?(i.subTo(t,i),i.rShiftTo(1,i)):(t.subTo(i,t),t.rShiftTo(1,t));return r>0&&t.lShiftTo(r,t),t}function bnpModInt(n){var r,t,i;if(n<=0)return 0;if(r=this.DV%n,t=this.s<0?n-1:0,this.t>0)if(r==0)t=this[0]%n;else for(i=this.t-1;i>=0;--i)t=(r*t+this[i])%n;return t}function bnModInverse(n){var o=n.isEven();if(this.isEven()&&o||n.signum()==0)return BigInteger.ZERO;for(var r=n.clone(),u=this.clone(),f=nbv(1),i=nbv(0),e=nbv(0),t=nbv(1);r.signum()!=0;){while(r.isEven())r.rShiftTo(1,r),o?(f.isEven()&&i.isEven()||(f.addTo(this,f),i.subTo(n,i)),f.rShiftTo(1,f)):i.isEven()||i.subTo(n,i),i.rShiftTo(1,i);while(u.isEven())u.rShiftTo(1,u),o?(e.isEven()&&t.isEven()||(e.addTo(this,e),t.subTo(n,t)),e.rShiftTo(1,e)):t.isEven()||t.subTo(n,t),t.rShiftTo(1,t);r.compareTo(u)>=0?(r.subTo(u,r),o&&f.subTo(e,f),i.subTo(t,i)):(u.subTo(r,u),o&&e.subTo(f,e),t.subTo(i,t))}if(u.compareTo(BigInteger.ONE)!=0)return BigInteger.ZERO;if(t.compareTo(n)>=0)return t.subtract(n);if(t.signum()<0)t.addTo(n,t);else return t;return t.signum()<0?t.add(n):t}function bnIsProbablePrime(n){var t,i=this.abs(),r,u;if(i.t==1&&i[0]<=lowprimes[lowprimes.length-1]){for(t=0;t<lowprimes.length;++t)if(i[0]==lowprimes[t])return!0;return!1}if(i.isEven())return!1;for(t=1;t<lowprimes.length;){for(r=lowprimes[t],u=t+1;u<lowprimes.length&&r<lplim;)r*=lowprimes[u++];for(r=i.modInt(r);t<u;)if(r%lowprimes[t++]==0)return!1}return i.millerRabin(n)}function bnpMillerRabin(n){var i=this.subtract(BigInteger.ONE),r=i.getLowestSetBit(),e,u,f,t,o;if(r<=0)return!1;for(e=i.shiftRight(r),n=n+1>>1,n>lowprimes.length&&(n=lowprimes.length),u=nbi(),f=0;f<n;++f)if(u.fromInt(lowprimes[Math.floor(Math.random()*lowprimes.length)]),t=u.modPow(e,this),t.compareTo(BigInteger.ONE)!=0&&t.compareTo(i)!=0){for(o=1;o++<r&&t.compareTo(i)!=0;)if(t=t.modPowInt(2,this),t.compareTo(BigInteger.ONE)==0)return!1;if(t.compareTo(i)!=0)return!1}return!0}var dbits,canary=0xdeadbeefcafe,j_lm=(canary&16777215)==15715070,BI_FP,BI_RM,BI_RC,rr,vv,lowprimes,lplim;for(j_lm&&navigator.appName=="Microsoft Internet Explorer"?(BigInteger.prototype.am=am2,dbits=30):j_lm&&navigator.appName!="Netscape"?(BigInteger.prototype.am=am1,dbits=26):(BigInteger.prototype.am=am3,dbits=28),BigInteger.prototype.DB=dbits,BigInteger.prototype.DM=(1<<dbits)-1,BigInteger.prototype.DV=1<<dbits,BI_FP=52,BigInteger.prototype.FV=Math.pow(2,BI_FP),BigInteger.prototype.F1=BI_FP-dbits,BigInteger.prototype.F2=2*dbits-BI_FP,BI_RM="0123456789abcdefghijklmnopqrstuvwxyz",BI_RC=[],rr="0".charCodeAt(0),vv=0;vv<=9;++vv)BI_RC[rr++]=vv;for(rr="a".charCodeAt(0),vv=10;vv<36;++vv)BI_RC[rr++]=vv;for(rr="A".charCodeAt(0),vv=10;vv<36;++vv)BI_RC[rr++]=vv;Classic.prototype.convert=cConvert;Classic.prototype.revert=cRevert;Classic.prototype.reduce=cReduce;Classic.prototype.mulTo=cMulTo;Classic.prototype.sqrTo=cSqrTo;Montgomery.prototype.convert=montConvert;Montgomery.prototype.revert=montRevert;Montgomery.prototype.reduce=montReduce;Montgomery.prototype.mulTo=montMulTo;Montgomery.prototype.sqrTo=montSqrTo;BigInteger.prototype.copyTo=bnpCopyTo;BigInteger.prototype.fromInt=bnpFromInt;BigInteger.prototype.fromString=bnpFromString;BigInteger.prototype.clamp=bnpClamp;BigInteger.prototype.dlShiftTo=bnpDLShiftTo;BigInteger.prototype.drShiftTo=bnpDRShiftTo;BigInteger.prototype.lShiftTo=bnpLShiftTo;BigInteger.prototype.rShiftTo=bnpRShiftTo;BigInteger.prototype.subTo=bnpSubTo;BigInteger.prototype.multiplyTo=bnpMultiplyTo;BigInteger.prototype.squareTo=bnpSquareTo;BigInteger.prototype.divRemTo=bnpDivRemTo;BigInteger.prototype.invDigit=bnpInvDigit;BigInteger.prototype.isEven=bnpIsEven;BigInteger.prototype.exp=bnpExp;BigInteger.prototype.toString=bnToString;BigInteger.prototype.negate=bnNegate;BigInteger.prototype.abs=bnAbs;BigInteger.prototype.compareTo=bnCompareTo;BigInteger.prototype.bitLength=bnBitLength;BigInteger.prototype.mod=bnMod;BigInteger.prototype.modPowInt=bnModPowInt;BigInteger.ZERO=nbv(0);BigInteger.ONE=nbv(1);NullExp.prototype.convert=nNop;NullExp.prototype.revert=nNop;NullExp.prototype.mulTo=nMulTo;NullExp.prototype.sqrTo=nSqrTo;Barrett.prototype.convert=barrettConvert;Barrett.prototype.revert=barrettRevert;Barrett.prototype.reduce=barrettReduce;Barrett.prototype.mulTo=barrettMulTo;Barrett.prototype.sqrTo=barrettSqrTo;lowprimes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997];lplim=67108864/lowprimes[lowprimes.length-1];BigInteger.prototype.chunkSize=bnpChunkSize;BigInteger.prototype.toRadix=bnpToRadix;BigInteger.prototype.fromRadix=bnpFromRadix;BigInteger.prototype.fromNumber=bnpFromNumber;BigInteger.prototype.bitwiseTo=bnpBitwiseTo;BigInteger.prototype.changeBit=bnpChangeBit;BigInteger.prototype.addTo=bnpAddTo;BigInteger.prototype.dMultiply=bnpDMultiply;BigInteger.prototype.dAddOffset=bnpDAddOffset;BigInteger.prototype.multiplyLowerTo=bnpMultiplyLowerTo;BigInteger.prototype.multiplyUpperTo=bnpMultiplyUpperTo;BigInteger.prototype.modInt=bnpModInt;BigInteger.prototype.millerRabin=bnpMillerRabin;BigInteger.prototype.clone=bnClone;BigInteger.prototype.intValue=bnIntValue;BigInteger.prototype.byteValue=bnByteValue;BigInteger.prototype.shortValue=bnShortValue;BigInteger.prototype.signum=bnSigNum;BigInteger.prototype.toByteArray=bnToByteArray;BigInteger.prototype.equals=bnEquals;BigInteger.prototype.min=bnMin;BigInteger.prototype.max=bnMax;BigInteger.prototype.and=bnAnd;BigInteger.prototype.or=bnOr;BigInteger.prototype.xor=bnXor;BigInteger.prototype.andNot=bnAndNot;BigInteger.prototype.not=bnNot;BigInteger.prototype.shiftLeft=bnShiftLeft;BigInteger.prototype.shiftRight=bnShiftRight;BigInteger.prototype.getLowestSetBit=bnGetLowestSetBit;BigInteger.prototype.bitCount=bnBitCount;BigInteger.prototype.testBit=bnTestBit;BigInteger.prototype.setBit=bnSetBit;BigInteger.prototype.clearBit=bnClearBit;BigInteger.prototype.flipBit=bnFlipBit;BigInteger.prototype.add=bnAdd;BigInteger.prototype.subtract=bnSubtract;BigInteger.prototype.multiply=bnMultiply;BigInteger.prototype.divide=bnDivide;BigInteger.prototype.remainder=bnRemainder;BigInteger.prototype.divideAndRemainder=bnDivideAndRemainder;BigInteger.prototype.modPow=bnModPow;BigInteger.prototype.modInverse=bnModInverse;BigInteger.prototype.pow=bnPow;BigInteger.prototype.gcd=bnGCD;BigInteger.prototype.isProbablePrime=bnIsProbablePrime;BigInteger.prototype.square=bnSquare;var RSAPublicKey=function(n,t){this.modulus=new BigInteger(Hex.encode(n),16);this.encryptionExponent=new BigInteger(Hex.encode(t),16)},UTF8={encode:function(n){var i,r,t;for(n=n.replace(/\r\n/g,"\n"),i="",r=0;r<n.length;r++)t=n.charCodeAt(r),t<128?i+=String.fromCharCode(t):t>127&&t<2048?(i+=String.fromCharCode(t>>6|192),i+=String.fromCharCode(t&63|128)):(i+=String.fromCharCode(t>>12|224),i+=String.fromCharCode(t>>6&63|128),i+=String.fromCharCode(t&63|128));return i},decode:function(n){for(var r="",t=0,i=$c1=$c2=0;t<n.length;)i=n.charCodeAt(t),i<128?(r+=String.fromCharCode(i),t++):i>191&&i<224?($c2=n.charCodeAt(t+1),r+=String.fromCharCode((i&31)<<6|$c2&63),t+=2):($c2=n.charCodeAt(t+1),$c3=n.charCodeAt(t+2),r+=String.fromCharCode((i&15)<<12|($c2&63)<<6|$c3&63),t+=3);return r}},Base64={base64:"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=",encode:function(n){if(!n)return!1;var o="",f,t,i,s,h,e,r,u=0;do f=n.charCodeAt(u++),t=n.charCodeAt(u++),i=n.charCodeAt(u++),s=f>>2,h=(f&3)<<4|t>>4,e=(t&15)<<2|i>>6,r=i&63,isNaN(t)?e=r=64:isNaN(i)&&(r=64),o+=this.base64.charAt(s)+this.base64.charAt(h)+this.base64.charAt(e)+this.base64.charAt(r);while(u<n.length);return o},decode:function(n){if(!n)return!1;n=n.replace(/[^A-Za-z0-9\+\/\=]/g,"");var i="",e,u,r,f,t=0;do e=this.base64.indexOf(n.charAt(t++)),u=this.base64.indexOf(n.charAt(t++)),r=this.base64.indexOf(n.charAt(t++)),f=this.base64.indexOf(n.charAt(t++)),i+=String.fromCharCode(e<<2|u>>4),r!=64&&(i+=String.fromCharCode((u&15)<<4|r>>2)),f!=64&&(i+=String.fromCharCode((r&3)<<6|f));while(t<n.length);return i}},Hex={hex:"0123456789abcdef",encode:function(n){if(!n)return!1;var i="",t,r=0;do t=n.charCodeAt(r++),i+=this.hex.charAt(t>>4&15)+this.hex.charAt(t&15);while(r<n.length);return i},decode:function(n){if(!n)return!1;n=n.replace(/[^0-9abcdef]/g,"");var i="",t=0;do i+=String.fromCharCode(this.hex.indexOf(n.charAt(t++))<<4&240|this.hex.indexOf(n.charAt(t++))&15);while(t<n.length);return i}},ASN1Data=function(n){this.error=!1;this.parse=function(n){var u,i,t,r,f;if(!n)return this.error=!0,null;for(u=[];n.length>0;){if(i=n.charCodeAt(0),n=n.substr(1),t=0,(i&31)==5)n=n.substr(1);else if(n.charCodeAt(0)&128){if(r=n.charCodeAt(0)&127,n=n.substr(1),r>0&&(t=n.charCodeAt(0)),r>1&&(t=t<<8|n.charCodeAt(1)),r>2)return this.error=!0,null;n=n.substr(r)}else t=n.charCodeAt(0),n=n.substr(1);if(f="",t){if(t>n.length)return this.error=!0,null;f=n.substr(0,t);n=n.substr(t)}i&32?u.push(this.parse(f)):u.push(this.value(i&128?4:i&31,f))}return u};this.value=function(n,t){var i,o,r,u,f,s,e,h;if(n==1)return t?!0:!1;if(n==2)return t;if(n==3)return this.parse(t.substr(1));if(n==5)return null;if(n==6){for(i=[],o=t.charCodeAt(0),i.push(Math.floor(o/40)),i.push(o-i[0]*40),r=[],u=0,f=1;f<t.length;f++)if(s=t.charCodeAt(f),r.push(s&127),s&128)u++;else{for(h=0,e=0;e<r.length;e++)h+=r[e]*Math.pow(128,u--);i.push(h);u=0;r=[]}return i.join(".")}return null};this.data=this.parse(n)},RSA={getPublicKey:function(n){return n.length<50?!1:n.substr(0,26)!="-----BEGIN PUBLIC KEY-----"?!1:(n=n.substr(26),n.substr(n.length-24)!="-----END PUBLIC KEY-----")?!1:(n=n.substr(0,n.length-24),n=new ASN1Data(Base64.decode(n)),n.error)?!1:(n=n.data,n[0][0][0]=="1.2.840.113549.1.1.1")?new RSAPublicKey(n[0][1][0][0],n[0][1][0][1]):!1},encrypt:function(n,t){if(!t)return!1;var i=t.modulus.bitLength()+7>>3;if((n=this.pkcs1pad2(n,i),!n)||(n=n.modPowInt(t.encryptionExponent,t.modulus),!n))return!1;for(n=n.toString(16);n.length<i*2;)n="0"+n;return Base64.encode(Hex.decode(n))},pkcs1pad2:function(n,t){if(t<n.length+11)return null;for(var i=[],r=n.length-1;r>=0&&t>0;)i[--t]=n.charCodeAt(r--);for(i[--t]=0;t>2;)i[--t]=Math.floor(Math.random()*254)+1;return i[--t]=2,i[--t]=0,new BigInteger(i)}}