bpe=0;mask=0;radix=mask+1;digitsStr='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_=!@#$%^&*()[]{}|;:,.<>/?`~ \\\'\"+-';for(bpe=0;(1<<(bpe+1))>(1<<bpe);bpe++);bpe>>=1;mask=(1<<bpe)-1;radix=mask+1;one=int2bigInt(1,1,1);t=new Array(0);ss=t;s0=t;s1=t;s2=t;s3=t;s4=t;s5=t;s6=t;s7=t;T=t;sa=t;mr_x1=t;mr_r=t;mr_a=t;eg_v=t;eg_u=t;eg_A=t;eg_B=t;eg_C=t;eg_D=t;md_q1=t;md_q2=t;md_q3=t;md_r=t;md_r1=t;md_r2=t;md_tt=t;primes=t;pows=t;s_i=t;s_i2=t;s_R=t;s_rm=t;s_q=t;s_n1=t;s_a=t;s_r2=t;s_n=t;s_b=t;s_d=t;s_x1=t;s_x2=t,s_aa=t;function findPrimes(O){var o,I,l,i;I=new Array(O);for(o=0;o<O;o++)I[o]=0;I[0]=2;l=0;for(;I[l]<O;){for(o=I[l]*I[l];o<O;o+=I[l])
I[o]=1;l++;I[l]=I[l-1]+1;for(;I[l]<O&&I[I[l]];)I[l]++}
i=new Array(l);for(o=0;o<l;o++)i[o]=I[o];return i}
function millerRabin(o,c){var O,I,i,l;if(mr_x1.length!=o.length){mr_x1=dup(o);mr_r=dup(o);mr_a=dup(o)}
copyInt_(mr_a,c);copy_(mr_r,o);copy_(mr_x1,o);addInt_(mr_r,-1);addInt_(mr_x1,-1);i=0;for(O=0;O<mr_r.length;O++)for(I=1;I<mask;I<<=1)if(o[O]&I){l=(i<mr_r.length+bpe?i:0);O=mr_r.length;I=mask}else
i++;if(l)rightShift_(mr_r,l);powMod_(mr_a,mr_r,o);if(!equalsInt(mr_a,1)&&!equals(mr_a,mr_x1)){I=1;while(I<=l-1&&!equals(mr_a,mr_x1)){squareMod_(mr_a,o);if(equalsInt(mr_a,1)){return 0}
I++}
if(!equals(mr_a,mr_x1)){return 0}}
return 1}
function bitSize(o){var l,I,i;for(l=o.length-1;(o[l]==0)&&(l>0);l--);for(I=0,i=o[l];i;(i>>=1),I++);I+=bpe*l;return I}
function expand(I,l){var i=int2bigInt(0,(I.length>l?I.length:l)*bpe,0);copy_(i,I);return i}
function randTruePrime(I){var i=int2bigInt(0,I,0);randTruePrime_(i,I);return trim(i,1)}
function mod(I,l){var i=dup(I);mod_(i,l);return trim(i,1)}
function addInt(I,l){var i=expand(I,I.length+1);addInt_(i,l);return trim(i,1)}
function mult(I,l){var i=expand(I,I.length+l.length);mult_(i,l);return trim(i,1)}
function powMod(I,l,o){var i=expand(I,o.length);powMod_(i,trim(l,2),trim(o,2),0);return trim(i,1)}
function sub(I,l){var i=expand(I,(I.length>l.length?I.length+1:l.length+1));sub_(i,l);return trim(i,1)}
function add(I,l){var i=expand(I,(I.length>l.length?I.length+1:l.length+1));add_(i,l);return trim(i,1)}
function inverseMod(l,o){var i=expand(l,o.length),I;I=inverseMod_(i,o);return I?trim(i,1):null}
function multMod(I,l,o){var i=expand(I,o.length);multMod_(i,l,o);return trim(i,1)}
function randTruePrime_(I,Z){var z,V,c,o,v,C,X,i,x,O,l;if(primes.length==0)primes=findPrimes(30000);if(pows.length==0){pows=new Array(512);for(v=0;v<512;v++){pows[v]=Math.pow(2,v/511.-1.)}}
z=0.1;V=20;recLimit=20;if(s_i2.length!=I.length){s_i2=dup(I);s_R=dup(I);s_n1=dup(I);s_r2=dup(I);s_d=dup(I);s_x1=dup(I);s_x2=dup(I);s_b=dup(I);s_n=dup(I);s_i=dup(I);s_rm=dup(I);s_q=dup(I);s_a=dup(I);s_aa=dup(I)}
if(Z<=recLimit){c=(1<<((Z+2)>>1))-1;copyInt_(I,0);for(o=1;o;){o=0;I[0]=1|(1<<(Z-1))|Math.floor(Math.random()*(1<<Z));for(v=1;(v<primes.length)&&((primes[v]&c)==primes[v]);v++){if(0==(I[0]%primes[v])){o=1;break}}}
carry_(I);return}
X=z*Z*Z;if(Z>2*V)
for(C=1;Z-Z*C<=V;)C=pows[Math.floor(Math.random()*512)];else
C=.5;l=Math.floor(C*Z)+1;randTruePrime_(s_q,l);copyInt_(s_i2,0);s_i2[Math.floor((Z-2)/bpe)]|=(1<<((Z-2)%bpe));divide_(s_i2,s_q,s_i,s_rm);x=bitSize(s_i);for(;;){for(;;){randBigInt_(s_R,x,0);if(greater(s_i,s_R))break}
addInt_(s_R,1);add_(s_R,s_i);copy_(s_n,s_q);mult_(s_n,s_R);multInt_(s_n,2);addInt_(s_n,1);copy_(s_r2,s_R);multInt_(s_r2,2);for(i=0,v=0;(v<primes.length)&&(primes[v]<X);v++)if(modInt(s_n,primes[v])==0){i=1;break}
if(!i)
if(!millerRabin(s_n,2))
i=1;if(!i){addInt_(s_n,-3);for(v=s_n.length-1;(s_n[v]==0)&&(v>0);v--);for(O=0,w=s_n[v];w;(w>>=1),O++);O+=bpe*v;for(;;){randBigInt_(s_a,O,0);if(greater(s_n,s_a))break}
addInt_(s_n,3);addInt_(s_a,2);copy_(s_b,s_a);copy_(s_n1,s_n);addInt_(s_n1,-1);powMod_(s_b,s_n1,s_n);addInt_(s_b,-1);if(isZero(s_b)){copy_(s_b,s_a);powMod_(s_b,s_r2,s_n);addInt_(s_b,-1);copy_(s_aa,s_n);copy_(s_d,s_b);GCD_(s_d,s_n);if(equalsInt(s_d,1)){copy_(I,s_aa);return}}}}}
function randBigInt_(i,l,O){var o,I;for(o=0;o<i.length;o++)i[o]=0;I=Math.floor((l-1)/bpe)+1;for(o=0;o<I;o++){i[o]=Math.floor(Math.random()*(1<<(bpe-1)))}
i[I-1]&=(2<<((l-1)%bpe))-1;if(O)i[I-1]|=(1<<((l-1)%bpe))}
function GCD_(V,X){var x,l,I,c,o,O,v,C,i;if(T.length!=V.length)T=dup(V);i=1;while(i){i=0;for(x=1;x<X.length;x++)
if(X[x]){i=1;break}
if(!i)break;for(x=V.length;!V[x]&&x>=0;x--);l=V[x];I=X[x];c=1;o=0;O=0;v=1;while((I+O)&&(I+v)){C=Math.floor((l+c)/(I+O));qp=Math.floor((l+o)/(I+v));if(C!=qp)break;t=c-C*O;c=O;O=t;t=o-C*v;o=v;v=t;t=l-C*I;l=I;I=t}
if(o){copy_(T,V);linComb_(V,X,c,o);linComb_(X,T,v,O)}else{mod_(V,X);copy_(T,V);copy_(V,X);copy_(X,T)}}
if(X[0]==0)return;t=modInt(V,X[0]);copyInt_(V,X[0]);X[0]=t;while(X[0]){V[0]%=X[0];t=V[0];V[0]=X[0];X[0]=t}}
function inverseMod_(I,l){var i=1+2*Math.max(I.length,l.length);if(!(I[0]&1)&&!(l[0]&1)){copyInt_(I,0);return 0}
if(eg_u.length!=i){eg_u=new Array(i);eg_v=new Array(i);eg_A=new Array(i);eg_B=new Array(i);eg_C=new Array(i);eg_D=new Array(i)}
copy_(eg_u,I);copy_(eg_v,l);copyInt_(eg_A,1);copyInt_(eg_B,0);copyInt_(eg_C,0);copyInt_(eg_D,1);for(;;){while(!(eg_u[0]&1)){halve_(eg_u);if(!(eg_A[0]&1)&&!(eg_B[0]&1)){halve_(eg_A);halve_(eg_B)}else{add_(eg_A,l);halve_(eg_A);sub_(eg_B,I);halve_(eg_B)}}
while(!(eg_v[0]&1)){halve_(eg_v);if(!(eg_C[0]&1)&&!(eg_D[0]&1)){halve_(eg_C);halve_(eg_D)}else{add_(eg_C,l);halve_(eg_C);sub_(eg_D,I);halve_(eg_D)}}
if(!greater(eg_v,eg_u)){sub_(eg_u,eg_v);sub_(eg_A,eg_C);sub_(eg_B,eg_D)}else{sub_(eg_v,eg_u);sub_(eg_C,eg_A);sub_(eg_D,eg_B)}
if(equalsInt(eg_u,0)){if(negative(eg_C))
add_(eg_C,l);copy_(I,eg_C);if(!equalsInt(eg_v,1)){copyInt_(I,0);return 0}
return 1}}}
function inverseModInt_(l,O){var o=1,I=0,i;for(;;){if(l==1)return o;if(l==0)return 0;I-=o*Math.floor(O/l);O%=l;if(O==1)return I;if(O==0)return 0;o-=I*Math.floor(l/O);l%=O}}
function eGCD_(i,l,o,O,C){var c=0,I=Math.max(i.length,l.length);if(eg_u.length!=I){eg_u=new Array(I);eg_A=new Array(I);eg_B=new Array(I);eg_C=new Array(I);eg_D=new Array(I)}
while(!(i[0]&1)&&!(l[0]&1)){halve_(i);halve_(l);c++}
copy_(eg_u,i);copy_(o,l);copyInt_(eg_A,1);copyInt_(eg_B,0);copyInt_(eg_C,0);copyInt_(eg_D,1);for(;;){while(!(eg_u[0]&1)){halve_(eg_u);if(!(eg_A[0]&1)&&!(eg_B[0]&1)){halve_(eg_A);halve_(eg_B)}else{add_(eg_A,l);halve_(eg_A);sub_(eg_B,i);halve_(eg_B)}}
while(!(o[0]&1)){halve_(o);if(!(eg_C[0]&1)&&!(eg_D[0]&1)){halve_(eg_C);halve_(eg_D)}else{add_(eg_C,l);halve_(eg_C);sub_(eg_D,i);halve_(eg_D)}}
if(!greater(o,eg_u)){sub_(eg_u,o);sub_(eg_A,eg_C);sub_(eg_B,eg_D)}else{sub_(o,eg_u);sub_(eg_C,eg_A);sub_(eg_D,eg_B)}
if(equalsInt(eg_u,0)){if(negative(eg_C)){add_(eg_C,l);sub_(eg_D,i)}
multInt_(eg_D,-1);copy_(O,eg_C);copy_(C,eg_D);leftShift_(o,c);return}}}
function negative(i){return((i[i.length-1]>>(bpe-1))&1)}
function greaterShift(c,O,I){var o=c.length,l=O.length;k=((o+I)<l)?(o+I):l;for(i=l-1-I;i<o&&i>=0;i++)if(c[i]>0)return 1;for(i=o-1+I;i<l;i++)if(O[i]>0)return 0;for(i=k-1;i>=I;i--)if(c[i-I]>O[i])return 1;else if(c[i-I]<O[i])return 0;return 0}
function greater(i,o){var l,I=(i.length<o.length)?i.length:o.length;for(l=i.length;l<o.length;l++)if(o[l])return 0;for(l=o.length;l<i.length;l++)if(i[l])return 1;for(l=I-1;l>=0;l--)if(i[l]>o[l])return 1;else if(i[l]<o[l])return 0;return 0}
function divide_(V,c,O,Z){var I,i,z,C,l,o,X,x,v;copy_(Z,V);for(i=c.length;c[i-1]==0;i--);for(I=Z.length;Z[I-1]==0&&I>i;I--);v=c[i-1];for(x=0;v;x++)v>>=1;x=bpe-x;leftShift_(c,x);leftShift_(Z,x);copyInt_(O,0);while(!greaterShift(c,Z,I-i)){subShift_(Z,c,I-i);O[I-i]++}
for(z=I-1;z>=i;z--){if(Z[z]==c[i-1])O[z-i]=mask;else
O[z-i]=Math.floor((Z[z]*radix+Z[z-1])/c[i-1]);for(;;){o=(i>1?c[i-2]:0)*O[z-i];X=o>>bpe;o=o&mask;l=X+O[z-i]*c[i-1];X=l>>bpe;l=l&mask;if(X==Z[z]?l==Z[z-1]?o>(z>1?Z[z-2]:0):l>Z[z-1]:X>Z[z])O[z-i]--;else
break}
linCombShift_(Z,c,-O[z-i],z-i);if(negative(Z)){addShift_(Z,c,z-i);O[z-i]--}}
rightShift_(c,x);rightShift_(Z,x)}
function carry_(O){var o,I,i,l;I=O.length;i=0;for(o=0;o<I;o++){i+=O[o];l=0;if(i<0){l=-(i>>bpe);i+=l*radix}
O[o]=i&mask;i=(i>>bpe)-l}}
function modInt(i,o){var l,I=0;for(l=i.length-1;l>=0;l--)I=(I*radix+i[l])%o;return I}
function int2bigInt(o,I,i){var O,l;l=Math.ceil(I/bpe)+1;l=i>l?i:l;buff=new Array(l);copyInt_(buff,o);return buff}
function str2bigInt(C,I,i){var x,O,V,c,o,l,v=C.length;if(I==-1){c=new Array(0);for(;;){o=new Array(c.length+1);for(O=0;O<c.length;O++)o[O+1]=c[O];o[0]=parseInt(C,10);c=o;x=C.indexOf(',',0);if(x<1)break;C=C.substring(x+1);if(C.length==0)break}
if(c.length<i){o=new Array(i);copy_(o,c);return o}
return c}
c=int2bigInt(0,I*v,0);for(O=0;O<v;O++){x=digitsStr.indexOf(C.substring(O,O+1),0);if(I<=36&&x>=36)
x-=26;if(x<I&&x>=0){multInt_(c,I);addInt_(c,x)}}
for(v=c.length;v>0&&!c[v-1];v--);v=i>v+1?i:v+1;o=new Array(v);l=v<c.length?v:c.length;for(O=0;O<l;O++)o[O]=c[O];for(;O<v;O++)o[O]=0;return o}
function equalsInt(I,l){var i;if(I[0]!=l)return 0;for(i=1;i<I.length;i++)if(I[i])return 0;return 1}
function equals(i,o){var l,I=i.length<o.length?i.length:o.length;for(l=0;l<I;l++)if(i[l]!=o[l])return 0;if(i.length>o.length){for(;l<i.length;l++)if(i[l])return 0}else{for(;l<o.length;l++)if(o[l])return 0}
return 1}
function isZero(I){var i;for(i=0;i<I.length;i++)if(I[i])return 0;return 1}
function bigInt2str(l,i){var O,I,o="";if(s6.length!=l.length)s6=dup(l);else
copy_(s6,l);if(i==-1){for(O=l.length-1;O>0;O--)o+=l[O]+',';o+=l[0]}else{while(!isZero(s6)){I=divInt_(s6,i);o=digitsStr.substring(I,I+1)+o}}
if(o.length==0)o="0";return o}
function dup(I){var i;buff=new Array(I.length);copy_(buff,I);return buff}
function copy_(i,o){var l,I=i.length<o.length?i.length:o.length;for(l=0;l<I;l++)i[l]=o[l];for(l=I;l<i.length;l++)i[l]=0}
function copyInt_(i,o){var l,I;for(I=o,l=0;l<i.length;l++){i[l]=I&mask;I>>=bpe}}
function addInt_(o,c){var O,I,i,l;o[0]+=c;I=o.length;i=0;for(O=0;O<I;O++){i+=o[O];l=0;if(i<0){l=-(i>>bpe);i+=l*radix}
o[O]=i&mask;i=(i>>bpe)-l;if(!i)return}}
function rightShift_(i,o){var l,I=Math.floor(o/bpe);if(I){for(l=0;l<i.length-I;l++)
i[l]=i[l+I];for(;l<i.length;l++)i[l]=0;o%=bpe}
for(l=0;l<i.length-1;l++){i[l]=mask&((i[l+1]<<(bpe-o))|(i[l]>>o))}
i[l]>>=o}
function halve_(I){var i;for(i=0;i<I.length-1;i++){I[i]=mask&((I[i+1]<<(bpe-1))|(I[i]>>1))}
I[i]=(I[i]>>1)|(I[i]&(radix>>1))}
function leftShift_(i,o){var l,I=Math.floor(o/bpe);if(I){for(l=i.length;l>=I;l--)
i[l]=i[l-I];for(;l>=0;l--)i[l]=0;o%=bpe}
if(!o)return;for(l=i.length-1;l>0;l--){i[l]=mask&((i[l]<<o)|(i[l-1]>>(bpe-o)))}
i[l]=mask&(i[l]<<o)}
function multInt_(o,c){var O,I,i,l;if(!c)return;I=o.length;i=0;for(O=0;O<I;O++){i+=o[O]*c;l=0;if(i<0){l=-(i>>bpe);i+=l*radix}
o[O]=i&mask;i=(i>>bpe)-l}}
function divInt_(l,O){var o,I=0,i;for(o=l.length-1;o>=0;o--){i=I*radix+l[o];l[o]=Math.floor(i/O);I=i%O}
return I}
function linComb_(o,O,c,v){var C,I,l,i;l=o.length<O.length?o.length:O.length;i=o.length;for(I=0,C=0;C<l;C++){I+=c*o[C]+v*O[C];o[C]=I&mask;I>>=bpe}
for(C=l;C<i;C++){I+=c*o[C];o[C]=I&mask;I>>=bpe}}
function linCombShift_(o,O,c,i){var v,l,C,I;C=o.length<i+O.length?o.length:i+O.length;I=o.length;for(l=0,v=i;v<C;v++){l+=o[v]+c*O[v-i];o[v]=l&mask;l>>=bpe}
for(v=C;l&&v<I;v++){l+=o[v];o[v]=l&mask;l>>=bpe}}
function addShift_(o,O,i){var C,l,c,I;c=o.length<i+O.length?o.length:i+O.length;I=o.length;for(l=0,C=i;C<c;C++){l+=o[C]+O[C-i];o[C]=l&mask;l>>=bpe}
for(C=c;l&&C<I;C++){l+=o[C];o[C]=l&mask;l>>=bpe}}
function subShift_(o,O,i){var C,l,c,I;c=o.length<i+O.length?o.length:i+O.length;I=o.length;for(l=0,C=i;C<c;C++){l+=o[C]-O[C-i];o[C]=l&mask;l>>=bpe}
for(C=c;l&&C<I;C++){l+=o[C];o[C]=l&mask;l>>=bpe}}
function sub_(o,c){var O,I,l,i;l=o.length<c.length?o.length:c.length;for(I=0,O=0;O<l;O++){I+=o[O]-c[O];o[O]=I&mask;I>>=bpe}
for(O=l;I&&O<o.length;O++){I+=o[O];o[O]=I&mask;I>>=bpe}}
function add_(o,c){var O,I,l,i;l=o.length<c.length?o.length:c.length;for(I=0,O=0;O<l;O++){I+=o[O]+c[O];o[O]=I&mask;I>>=bpe}
for(O=l;I&&O<o.length;O++){I+=o[O];o[O]=I&mask;I>>=bpe}}
function mult_(I,l){var i;if(ss.length!=2*I.length)ss=new Array(2*I.length);copyInt_(ss,0);for(i=0;i<l.length;i++)if(l[i])linCombShift_(ss,I,l[i],i);copy_(I,ss)}
function mod_(i,I){if(s4.length!=i.length)s4=dup(i);else
copy_(s4,i);if(s5.length!=i.length)s5=dup(i);divide_(s4,I,s5,i)}
function multMod_(I,i,o){var l;if(s0.length!=2*I.length)s0=new Array(2*I.length);copyInt_(s0,0);for(l=0;l<i.length;l++)if(i[l])linCombShift_(s0,I,i[l],l);mod_(s0,o);copy_(I,s0)}
function squareMod_(C,V){var v,l,O,o,i,I,c;for(i=C.length;i>0&&!C[i-1];i--);c=i>V.length?2*i:2*V.length;if(s0.length!=c)s0=new Array(c);copyInt_(s0,0);for(v=0;v<i;v++){o=s0[2*v]+C[v]*C[v];s0[2*v]=o&mask;o>>=bpe;for(l=v+1;l<i;l++){o=s0[v+l]+2*C[v]*C[l]+o;s0[v+l]=(o&mask);o>>=bpe}
s0[v+i]=o}
mod_(s0,V);copy_(C,s0)}
function trim(i,o){var l,I;for(l=i.length;l>0&&!i[l-1];l--);I=new Array(l+o);copy_(I,i);return I}
function powMod_(c,O,C){var i,I,l,o;if(s7.length!=C.length)s7=dup(C);if((C[0]&1)==0){copy_(s7,c);copyInt_(c,1);while(!equalsInt(O,0)){if(O[0]&1)multMod_(c,s7,C);divInt_(O,2);squareMod_(s7,C)}
return}
copyInt_(s7,0);for(l=C.length;l>0&&!C[l-1];l--);o=radix-inverseModInt_(modInt(C,radix),radix);s7[l]=1;multMod_(c,s7,C);if(s3.length!=c.length)s3=dup(c);else
copy_(s3,c);for(i=O.length-1;i>0&!O[i];i--);if(O[i]==0){copyInt_(c,1);return}
for(I=1<<(bpe-1);I&&!(O[i]&I);I>>=1);for(;;){if(!(I>>=1)){i--;if(i<0){mont_(c,one,C,o);return}
I=1<<(bpe-1)}
mont_(c,c,C,o);if(I&O[i])
mont_(c,s3,C,o)}}
function mont_(v,C,V,l){var X,c,x,I,O,i=V.length,o=C.length;if(sa.length!=i)sa=new Array(i);for(;i>0&&V[i-1]==0;i--);copyInt_(sa,0);for(X=0;X<i;X++){O=sa[0]+v[X]*C[0];I=((O&mask)*l)&mask;x=(O+I*V[0])>>bpe;O=v[X];for(c=1;c<o;c++){x+=sa[c]+O*C[c]+I*V[c];sa[c-1]=x&mask;x>>=bpe}
for(;c<i;c++){x+=sa[c]+I*V[c];sa[c-1]=x&mask;x>>=bpe}
sa[c-1]=x&mask}
if(!greater(V,sa))sub_(sa,V);copy_(v,sa)}