var biRadixBase=2;
var biRadixBits=16;
var bitsPerDigit=biRadixBits;
var biRadix=1<<16;
var biHalfRadix=biRadix>>>1;
var biRadixSquared=biRadix*biRadix;
var maxDigitVal=biRadix-1;
var maxInteger=9999999999999998;
var maxDigits;
var ZERO_ARRAY;
var bigZero,bigOne;
function setMaxDigits(_1){
maxDigits=_1;
ZERO_ARRAY=new Array(maxDigits);
for(var _2=0;_2<ZERO_ARRAY.length;_2++){
ZERO_ARRAY[_2]=0;
}
bigZero=new BigInt();
bigOne=new BigInt();
bigOne.digits[0]=1;
}
setMaxDigits(20);
var dpl10=15;
var lr10=biFromNumber(1000000000000000);
function BigInt(_3){
if(typeof _3=="boolean"&&_3==true){
this.digits=null;
}else{
this.digits=ZERO_ARRAY.slice(0);
}
this.isNeg=false;
}
function biFromDecimal(s){
var _5=s.charAt(0)=="-";
var i=_5?1:0;
var _7;
while(i<s.length&&s.charAt(i)=="0"){
++i;
}
if(i==s.length){
_7=new BigInt();
}else{
var _8=s.length-i;
var _9=_8%dpl10;
if(_9==0){
_9=dpl10;
}
_7=biFromNumber(Number(s.substr(i,_9)));
i+=_9;
while(i<s.length){
_7=biAdd(biMultiply(_7,lr10),biFromNumber(Number(s.substr(i,dpl10))));
i+=dpl10;
}
_7.isNeg=_5;
}
return _7;
}
function biCopy(bi){
var _b=new BigInt(true);
_b.digits=bi.digits.slice(0);
_b.isNeg=bi.isNeg;
return _b;
}
function biFromNumber(i){
var _d=new BigInt();
_d.isNeg=i<0;
i=Math.abs(i);
var j=0;
while(i>0){
_d.digits[j++]=i&maxDigitVal;
i=Math.floor(i/biRadix);
}
return _d;
}
function reverseStr(s){
var _10="";
for(var i=s.length-1;i>-1;--i){
_10+=s.charAt(i);
}
return _10;
}
var hexatrigesimalToChar=new Array("0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z");
function biToString(x,_13){
var b=new BigInt();
b.digits[0]=_13;
var qr=biDivideModulo(x,b);
var _16=hexatrigesimalToChar[qr[1].digits[0]];
while(biCompare(qr[0],bigZero)==1){
qr=biDivideModulo(qr[0],b);
digit=qr[1].digits[0];
_16+=hexatrigesimalToChar[qr[1].digits[0]];
}
return (x.isNeg?"-":"")+reverseStr(_16);
}
function biToDecimal(x){
var b=new BigInt();
b.digits[0]=10;
var qr=biDivideModulo(x,b);
var _1a=String(qr[1].digits[0]);
while(biCompare(qr[0],bigZero)==1){
qr=biDivideModulo(qr[0],b);
_1a+=String(qr[1].digits[0]);
}
return (x.isNeg?"-":"")+reverseStr(_1a);
}
var hexToChar=new Array("0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f");
function digitToHex(n){
var _1c=15;
var _1d="";
for(i=0;i<4;++i){
_1d+=hexToChar[n&_1c];
n>>>=4;
}
return reverseStr(_1d);
}
function biToHex(x){
var _1f="";
var n=biHighIndex(x);
for(var i=biHighIndex(x);i>-1;--i){
_1f+=digitToHex(x.digits[i]);
}
return _1f;
}
function charToHex(c){
var _23=48;
var _24=_23+9;
var _25=97;
var _26=_25+25;
var _27=65;
var _28=65+25;
var _29;
if(c>=_23&&c<=_24){
_29=c-_23;
}else{
if(c>=_27&&c<=_28){
_29=10+c-_27;
}else{
if(c>=_25&&c<=_26){
_29=10+c-_25;
}else{
_29=0;
}
}
}
return _29;
}
function hexToDigit(s){
var _2b=0;
var sl=Math.min(s.length,4);
for(var i=0;i<sl;++i){
_2b<<=4;
_2b|=charToHex(s.charCodeAt(i));
}
return _2b;
}
function biFromHex(s){
var _2f=new BigInt();
var sl=s.length;
for(var i=sl,j=0;i>0;i-=4,++j){
_2f.digits[j]=hexToDigit(s.substr(Math.max(i-4,0),Math.min(i,4)));
}
return _2f;
}
function biFromString(s,_33){
var _34=s.charAt(0)=="-";
var _35=_34?1:0;
var _36=new BigInt();
var _37=new BigInt();
_37.digits[0]=1;
for(var i=s.length-1;i>=_35;i--){
var c=s.charCodeAt(i);
var _3a=charToHex(c);
var _3b=biMultiplyDigit(_37,_3a);
_36=biAdd(_36,_3b);
_37=biMultiplyDigit(_37,_33);
}
_36.isNeg=_34;
return _36;
}
function biDump(b){
return (b.isNeg?"-":"")+b.digits.join(" ");
}
function biAdd(x,y){
var _3f;
if(x.isNeg!=y.isNeg){
y.isNeg=!y.isNeg;
_3f=biSubtract(x,y);
y.isNeg=!y.isNeg;
}else{
_3f=new BigInt();
var c=0;
var n;
for(var i=0;i<x.digits.length;++i){
n=x.digits[i]+y.digits[i]+c;
_3f.digits[i]=n%biRadix;
c=Number(n>=biRadix);
}
_3f.isNeg=x.isNeg;
}
return _3f;
}
function biSubtract(x,y){
var _45;
if(x.isNeg!=y.isNeg){
y.isNeg=!y.isNeg;
_45=biAdd(x,y);
y.isNeg=!y.isNeg;
}else{
_45=new BigInt();
var n,c;
c=0;
for(var i=0;i<x.digits.length;++i){
n=x.digits[i]-y.digits[i]+c;
_45.digits[i]=n%biRadix;
if(_45.digits[i]<0){
_45.digits[i]+=biRadix;
}
c=0-Number(n<0);
}
if(c==-1){
c=0;
for(var i=0;i<x.digits.length;++i){
n=0-_45.digits[i]+c;
_45.digits[i]=n%biRadix;
if(_45.digits[i]<0){
_45.digits[i]+=biRadix;
}
c=0-Number(n<0);
}
_45.isNeg=!x.isNeg;
}else{
_45.isNeg=x.isNeg;
}
}
return _45;
}
function biHighIndex(x){
var _49=x.digits.length-1;
while(_49>0&&x.digits[_49]==0){
--_49;
}
return _49;
}
function biNumBits(x){
var n=biHighIndex(x);
var d=x.digits[n];
var m=(n+1)*bitsPerDigit;
var _4e;
for(_4e=m;_4e>m-bitsPerDigit;--_4e){
if((d&32768)!=0){
break;
}
d<<=1;
}
return _4e;
}
function biMultiply(x,y){
var _51=new BigInt();
var c;
var n=biHighIndex(x);
var t=biHighIndex(y);
var u,uv,k;
for(var i=0;i<=t;++i){
c=0;
k=i;
for(j=0;j<=n;++j,++k){
uv=_51.digits[k]+x.digits[j]*y.digits[i]+c;
_51.digits[k]=uv&maxDigitVal;
c=uv>>>biRadixBits;
}
_51.digits[i+n+1]=c;
}
_51.isNeg=x.isNeg!=y.isNeg;
return _51;
}
function biMultiplyDigit(x,y){
var n,c,uv;
result=new BigInt();
n=biHighIndex(x);
c=0;
for(var j=0;j<=n;++j){
uv=result.digits[j]+x.digits[j]*y+c;
result.digits[j]=uv&maxDigitVal;
c=uv>>>biRadixBits;
}
result.digits[1+n]=c;
return result;
}
function arrayCopy(src,_5c,_5d,_5e,n){
var m=Math.min(_5c+n,src.length);
for(var i=_5c,j=_5e;i<m;++i,++j){
_5d[j]=src[i];
}
}
var highBitMasks=new Array(0,32768,49152,57344,61440,63488,64512,65024,65280,65408,65472,65504,65520,65528,65532,65534,65535);
function biShiftLeft(x,n){
var _64=Math.floor(n/bitsPerDigit);
var _65=new BigInt();
arrayCopy(x.digits,0,_65.digits,_64,_65.digits.length-_64);
var _66=n%bitsPerDigit;
var _67=bitsPerDigit-_66;
for(var i=_65.digits.length-1,i1=i-1;i>0;--i,--i1){
_65.digits[i]=((_65.digits[i]<<_66)&maxDigitVal)|((_65.digits[i1]&highBitMasks[_66])>>>(_67));
}
_65.digits[0]=((_65.digits[i]<<_66)&maxDigitVal);
_65.isNeg=x.isNeg;
return _65;
}
var lowBitMasks=new Array(0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535);
function biShiftRight(x,n){
var _6b=Math.floor(n/bitsPerDigit);
var _6c=new BigInt();
arrayCopy(x.digits,_6b,_6c.digits,0,x.digits.length-_6b);
var _6d=n%bitsPerDigit;
var _6e=bitsPerDigit-_6d;
for(var i=0,i1=i+1;i<_6c.digits.length-1;++i,++i1){
_6c.digits[i]=(_6c.digits[i]>>>_6d)|((_6c.digits[i1]&lowBitMasks[_6d])<<_6e);
}
_6c.digits[_6c.digits.length-1]>>>=_6d;
_6c.isNeg=x.isNeg;
return _6c;
}
function biMultiplyByRadixPower(x,n){
var _72=new BigInt();
arrayCopy(x.digits,0,_72.digits,n,_72.digits.length-n);
return _72;
}
function biDivideByRadixPower(x,n){
var _75=new BigInt();
arrayCopy(x.digits,n,_75.digits,0,_75.digits.length-n);
return _75;
}
function biModuloByRadixPower(x,n){
var _78=new BigInt();
arrayCopy(x.digits,0,_78.digits,0,n);
return _78;
}
function biCompare(x,y){
if(x.isNeg!=y.isNeg){
return 1-2*Number(x.isNeg);
}
for(var i=x.digits.length-1;i>=0;--i){
if(x.digits[i]!=y.digits[i]){
if(x.isNeg){
return 1-2*Number(x.digits[i]>y.digits[i]);
}else{
return 1-2*Number(x.digits[i]<y.digits[i]);
}
}
}
return 0;
}
function biDivideModulo(x,y){
var nb=biNumBits(x);
var tb=biNumBits(y);
var _80=y.isNeg;
var q,r;
if(nb<tb){
if(x.isNeg){
q=biCopy(bigOne);
q.isNeg=!y.isNeg;
x.isNeg=false;
y.isNeg=false;
r=biSubtract(y,x);
x.isNeg=true;
y.isNeg=_80;
}else{
q=new BigInt();
r=biCopy(x);
}
return new Array(q,r);
}
q=new BigInt();
r=x;
var t=Math.ceil(tb/bitsPerDigit)-1;
var _83=0;
while(y.digits[t]<biHalfRadix){
y=biShiftLeft(y,1);
++_83;
++tb;
t=Math.ceil(tb/bitsPerDigit)-1;
}
r=biShiftLeft(r,_83);
nb+=_83;
var n=Math.ceil(nb/bitsPerDigit)-1;
var b=biMultiplyByRadixPower(y,n-t);
while(biCompare(r,b)!=-1){
++q.digits[n-t];
r=biSubtract(r,b);
}
for(var i=n;i>t;--i){
var ri=(i>=r.digits.length)?0:r.digits[i];
var ri1=(i-1>=r.digits.length)?0:r.digits[i-1];
var ri2=(i-2>=r.digits.length)?0:r.digits[i-2];
var yt=(t>=y.digits.length)?0:y.digits[t];
var yt1=(t-1>=y.digits.length)?0:y.digits[t-1];
if(ri==yt){
q.digits[i-t-1]=maxDigitVal;
}else{
q.digits[i-t-1]=Math.floor((ri*biRadix+ri1)/yt);
}
var c1=q.digits[i-t-1]*((yt*biRadix)+yt1);
var c2=(ri*biRadixSquared)+((ri1*biRadix)+ri2);
while(c1>c2){
--q.digits[i-t-1];
c1=q.digits[i-t-1]*((yt*biRadix)|yt1);
c2=(ri*biRadix*biRadix)+((ri1*biRadix)+ri2);
}
b=biMultiplyByRadixPower(y,i-t-1);
r=biSubtract(r,biMultiplyDigit(b,q.digits[i-t-1]));
if(r.isNeg){
r=biAdd(r,b);
--q.digits[i-t-1];
}
}
r=biShiftRight(r,_83);
q.isNeg=x.isNeg!=_80;
if(x.isNeg){
if(_80){
q=biAdd(q,bigOne);
}else{
q=biSubtract(q,bigOne);
}
y=biShiftRight(y,_83);
r=biSubtract(y,r);
}
if(r.digits[0]==0&&biHighIndex(r)==0){
r.isNeg=false;
}
return new Array(q,r);
}
function biDivide(x,y){
return biDivideModulo(x,y)[0];
}
function biModulo(x,y){
return biDivideModulo(x,y)[1];
}
function biMultiplyMod(x,y,m){
return biModulo(biMultiply(x,y),m);
}
function biPow(x,y){
var _97=bigOne;
var a=x;
while(true){
if((y&1)!=0){
_97=biMultiply(_97,a);
}
y>>=1;
if(y==0){
break;
}
a=biMultiply(a,a);
}
return _97;
}
function biPowMod(x,y,m){
var _9c=bigOne;
var a=x;
var k=y;
while(true){
if((k.digits[0]&1)!=0){
_9c=biMultiplyMod(_9c,a,m);
}
k=biShiftRight(k,1);
if(k.digits[0]==0&&biHighIndex(k)==0){
break;
}
a=biMultiplyMod(a,a,m);
}
return _9c;
}