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