var biRadixBase=2,biRadixBits=16,bitsPerDigit=biRadixBits,biRadix=65536,biHalfRadix=biRadix>>>1,biRadixSquared=biRadix*biRadix,maxDigitVal=biRadix-1,maxInteger=9999999999999998,maxDigits,ZERO_ARRAY,bigZero,bigOne;function setMaxDigits(a){maxDigits=a;ZERO_ARRAY=new Array(maxDigits);for(a=0;a<ZERO_ARRAY.length;a++)ZERO_ARRAY[a]=0;bigZero=new BigInt;bigOne=new BigInt;bigOne.digits[0]=1}setMaxDigits(20);var dpl10=15,lr10=biFromNumber(1E15);
function BigInt(a){this.digits=typeof a=="boolean"&&a==true?null:ZERO_ARRAY.slice(0);this.isNeg=false}function biFromDecimal(a){for(var c=a.charAt(0)=="-",b=c?1:0,d;b<a.length&&a.charAt(b)=="0";)++b;if(b==a.length)d=new BigInt;else{var e=(a.length-b)%dpl10;if(e==0)e=dpl10;d=biFromNumber(Number(a.substr(b,e)));for(b+=e;b<a.length;){d=biAdd(biMultiply(d,lr10),biFromNumber(Number(a.substr(b,dpl10))));b+=dpl10}d.isNeg=c}return d}
function biCopy(a){var c=new BigInt(true);c.digits=a.digits.slice(0);c.isNeg=a.isNeg;return c}function biFromNumber(a){var c=new BigInt;c.isNeg=a<0;a=Math.abs(a);for(var b=0;a>0;){c.digits[b++]=a&maxDigitVal;a=Math.floor(a/biRadix)}return c}function reverseStr(a){for(var c="",b=a.length-1;b>-1;--b)c+=a.charAt(b);return c}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(a,c){var b=new BigInt;b.digits[0]=c;for(var d=biDivideModulo(a,b),e=hexatrigesimalToChar[d[1].digits[0]];biCompare(d[0],bigZero)==1;){d=biDivideModulo(d[0],b);digit=d[1].digits[0];e+=hexatrigesimalToChar[d[1].digits[0]]}return(a.isNeg?"-":"")+reverseStr(e)}
function biToDecimal(a){var c=new BigInt;c.digits[0]=10;for(var b=biDivideModulo(a,c),d=String(b[1].digits[0]);biCompare(b[0],bigZero)==1;){b=biDivideModulo(b[0],c);d+=String(b[1].digits[0])}return(a.isNeg?"-":"")+reverseStr(d)}var hexToChar=new Array("0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f");function digitToHex(a){var c="";for(i=0;i<4;++i){c+=hexToChar[a&15];a>>>=4}return reverseStr(c)}
function biToHex(a){var c="";biHighIndex(a);for(var b=biHighIndex(a);b>-1;--b)c+=digitToHex(a.digits[b]);return c}function charToHex(a){return a>=48&&a<=57?a-48:a>=65&&a<=90?10+a-65:a>=97&&a<=122?10+a-97:0}function hexToDigit(a){for(var c=0,b=Math.min(a.length,4),d=0;d<b;++d){c<<=4;c|=charToHex(a.charCodeAt(d))}return c}function biFromHex(a){for(var c=new BigInt,b=a.length,d=0;b>0;b-=4,++d)c.digits[d]=hexToDigit(a.substr(Math.max(b-4,0),Math.min(b,4)));return c}
function biFromString(a,c){var b=a.charAt(0)=="-",d=b?1:0,e=new BigInt,g=new BigInt;g.digits[0]=1;for(var f=a.length-1;f>=d;f--){var h=a.charCodeAt(f);h=charToHex(h);h=biMultiplyDigit(g,h);e=biAdd(e,h);g=biMultiplyDigit(g,c)}e.isNeg=b;return e}function biDump(a){return(a.isNeg?"-":"")+a.digits.join(" ")}
function biAdd(a,c){var b;if(a.isNeg!=c.isNeg){c.isNeg=!c.isNeg;b=biSubtract(a,c);c.isNeg=!c.isNeg}else{b=new BigInt;for(var d=0,e=0;e<a.digits.length;++e){d=a.digits[e]+c.digits[e]+d;b.digits[e]=d%biRadix;d=Number(d>=biRadix)}b.isNeg=a.isNeg}return b}
function biSubtract(a,c){var b;if(a.isNeg!=c.isNeg){c.isNeg=!c.isNeg;b=biAdd(a,c);c.isNeg=!c.isNeg}else{b=new BigInt;var d;for(var e=d=0;e<a.digits.length;++e){d=a.digits[e]-c.digits[e]+d;b.digits[e]=d%biRadix;if(b.digits[e]<0)b.digits[e]+=biRadix;d=0-Number(d<0)}if(d==-1){for(e=d=0;e<a.digits.length;++e){d=0-b.digits[e]+d;b.digits[e]=d%biRadix;if(b.digits[e]<0)b.digits[e]+=biRadix;d=0-Number(d<0)}b.isNeg=!a.isNeg}else b.isNeg=a.isNeg}return b}
function biHighIndex(a){for(var c=a.digits.length-1;c>0&&a.digits[c]==0;)--c;return c}function biNumBits(a){var c=biHighIndex(a);a=a.digits[c];c=(c+1)*bitsPerDigit;var b;for(b=c;b>c-bitsPerDigit;--b){if((a&32768)!=0)break;a<<=1}return b}
function biMultiply(a,c){for(var b=new BigInt,d,e=biHighIndex(a),g=biHighIndex(c),f,h=0;h<=g;++h){d=0;f=h;for(j=0;j<=e;++j,++f){d=b.digits[f]+a.digits[j]*c.digits[h]+d;b.digits[f]=d&maxDigitVal;d=d>>>biRadixBits}b.digits[h+e+1]=d}b.isNeg=a.isNeg!=c.isNeg;return b}function biMultiplyDigit(a,c){var b,d;result=new BigInt;b=biHighIndex(a);for(var e=d=0;e<=b;++e){d=result.digits[e]+a.digits[e]*c+d;result.digits[e]=d&maxDigitVal;d=d>>>biRadixBits}result.digits[1+b]=d;return result}
function arrayCopy(a,c,b,d,e){e=Math.min(c+e,a.length);c=c;for(d=d;c<e;++c,++d)b[d]=a[c]}var highBitMasks=new Array(0,32768,49152,57344,61440,63488,64512,65024,65280,65408,65472,65504,65520,65528,65532,65534,65535);
function biShiftLeft(a,c){var b=Math.floor(c/bitsPerDigit),d=new BigInt;arrayCopy(a.digits,0,d.digits,b,d.digits.length-b);b=c%bitsPerDigit;for(var e=bitsPerDigit-b,g=d.digits.length-1,f=g-1;g>0;--g,--f)d.digits[g]=d.digits[g]<<b&maxDigitVal|(d.digits[f]&highBitMasks[b])>>>e;d.digits[0]=d.digits[g]<<b&maxDigitVal;d.isNeg=a.isNeg;return d}var lowBitMasks=new Array(0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535);
function biShiftRight(a,c){var b=Math.floor(c/bitsPerDigit),d=new BigInt;arrayCopy(a.digits,b,d.digits,0,a.digits.length-b);b=c%bitsPerDigit;for(var e=bitsPerDigit-b,g=0,f=g+1;g<d.digits.length-1;++g,++f)d.digits[g]=d.digits[g]>>>b|(d.digits[f]&lowBitMasks[b])<<e;d.digits[d.digits.length-1]>>>=b;d.isNeg=a.isNeg;return d}function biMultiplyByRadixPower(a,c){var b=new BigInt;arrayCopy(a.digits,0,b.digits,c,b.digits.length-c);return b}
function biDivideByRadixPower(a,c){var b=new BigInt;arrayCopy(a.digits,c,b.digits,0,b.digits.length-c);return b}function biModuloByRadixPower(a,c){var b=new BigInt;arrayCopy(a.digits,0,b.digits,0,c);return b}function biCompare(a,c){if(a.isNeg!=c.isNeg)return 1-2*Number(a.isNeg);for(var b=a.digits.length-1;b>=0;--b)if(a.digits[b]!=c.digits[b])return a.isNeg?1-2*Number(a.digits[b]>c.digits[b]):1-2*Number(a.digits[b]<c.digits[b]);return 0}
function biDivideModulo(a,c){var b=biNumBits(a),d=biNumBits(c),e=c.isNeg,g,f;if(b<d){if(a.isNeg){g=biCopy(bigOne);g.isNeg=!c.isNeg;a.isNeg=false;c.isNeg=false;f=biSubtract(c,a);a.isNeg=true;c.isNeg=e}else{g=new BigInt;f=biCopy(a)}return new Array(g,f)}g=new BigInt;f=a;for(var h=Math.ceil(d/bitsPerDigit)-1,k=0;c.digits[h]<biHalfRadix;){c=biShiftLeft(c,1);++k;++d;h=Math.ceil(d/bitsPerDigit)-1}f=biShiftLeft(f,k);b+=k;b=Math.ceil(b/bitsPerDigit)-1;for(d=biMultiplyByRadixPower(c,b-h);biCompare(f,d)!=-1;){++g.digits[b-
h];f=biSubtract(f,d)}for(b=b;b>h;--b){d=b>=f.digits.length?0:f.digits[b];var m=b-1>=f.digits.length?0:f.digits[b-1],n=b-2>=f.digits.length?0:f.digits[b-2],l=h>=c.digits.length?0:c.digits[h],o=h-1>=c.digits.length?0:c.digits[h-1];g.digits[b-h-1]=d==l?maxDigitVal:Math.floor((d*biRadix+m)/l);for(var p=g.digits[b-h-1]*(l*biRadix+o),q=d*biRadixSquared+(m*biRadix+n);p>q;){--g.digits[b-h-1];p=g.digits[b-h-1]*(l*biRadix|o);q=d*biRadix*biRadix+(m*biRadix+n)}d=biMultiplyByRadixPower(c,b-h-1);f=biSubtract(f,
biMultiplyDigit(d,g.digits[b-h-1]));if(f.isNeg){f=biAdd(f,d);--g.digits[b-h-1]}}f=biShiftRight(f,k);g.isNeg=a.isNeg!=e;if(a.isNeg){g=e?biAdd(g,bigOne):biSubtract(g,bigOne);c=biShiftRight(c,k);f=biSubtract(c,f)}if(f.digits[0]==0&&biHighIndex(f)==0)f.isNeg=false;return new Array(g,f)}function biDivide(a,c){return biDivideModulo(a,c)[0]}function biModulo(a,c){return biDivideModulo(a,c)[1]}function biMultiplyMod(a,c,b){return biModulo(biMultiply(a,c),b)}
function biPow(a,c){for(var b=bigOne,d=a;;){if((c&1)!=0)b=biMultiply(b,d);c>>=1;if(c==0)break;d=biMultiply(d,d)}return b}function biPowMod(a,c,b){var d=bigOne;a=a;for(c=c;;){if((c.digits[0]&1)!=0)d=biMultiplyMod(d,a,b);c=biShiftRight(c,1);if(c.digits[0]==0&&biHighIndex(c)==0)break;a=biMultiplyMod(a,a,b)}return d};