// polyclip-ts v0.16.8 Copyright (c) 2022 Luiz Felipe Machado Barboza
!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e((t="undefined"!=typeof globalThis?globalThis:t||self).polyclip=t.polyclip||{})}(this,(function(t){"use strict";var e=t=>()=>t,n=t=>{const n=t?(e,n)=>n.minus(e).abs().isLessThanOrEqualTo(t):e(!1);return(t,e)=>n(t,e)?0:t.comparedTo(e)};function i(t){const n=t?(e,n,i,r,s)=>e.exponentiatedBy(2).isLessThanOrEqualTo(r.minus(n).exponentiatedBy(2).plus(s.minus(i).exponentiatedBy(2)).times(t)):e(!1);return(t,e,i)=>{const r=t.x,s=t.y,o=i.x,l=i.y,u=s.minus(l).times(e.x.minus(o)).minus(r.minus(o).times(e.y.minus(l)));return n(u,r,s,o,l)?0:u.comparedTo(0)}}var r=/^-?(?:\d+(?:\.\d*)?|\.\d+)(?:e[+-]?\d+)?$/i,s=Math.ceil,o=Math.floor,l="[BigNumber Error] ",u=l+"Number primitive has more than 15 significant digits: ",h=1e14,f=14,a=9007199254740991,c=[1,10,100,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13],p=1e7,g=1e9;function y(t){var e=0|t;return t>0||t===e?e:e-1}function d(t){for(var e,n,i=1,r=t.length,s=t[0]+"";i<r;){for(e=t[i++]+"",n=f-e.length;n--;e="0"+e);s+=e}for(r=s.length;48===s.charCodeAt(--r););return s.slice(0,r+1||1)}function m(t,e){var n,i,r=t.c,s=e.c,o=t.s,l=e.s,u=t.e,h=e.e;if(!o||!l)return null;if(n=r&&!r[0],i=s&&!s[0],n||i)return n?i?0:-l:o;if(o!=l)return o;if(n=o<0,i=u==h,!r||!s)return i?0:!r^n?1:-1;if(!i)return u>h^n?1:-1;for(l=(u=r.length)<(h=s.length)?u:h,o=0;o<l;o++)if(r[o]!=s[o])return r[o]>s[o]^n?1:-1;return u==h?0:u>h^n?1:-1}function x(t,e,n,i){if(t<e||t>n||t!==o(t))throw Error(l+(i||"Argument")+("number"==typeof t?t<e||t>n?" out of range: ":" not an integer: ":" not a primitive number: ")+String(t))}function b(t){var e=t.c.length-1;return y(t.e/f)==e&&t.c[e]%2!=0}function w(t,e){return(t.length>1?t.charAt(0)+"."+t.slice(1):t)+(e<0?"e":"e+")+e}function E(t,e,n){var i,r;if(e<0){for(r=n+".";++e;r+=n);t=r+t}else if(++e>(i=t.length)){for(r=n,e-=i;--e;r+=n);t+=r}else e<i&&(t=t.slice(0,e)+"."+t.slice(e));return t}var v=function t(e){var n,i,v,S,T,R,N,O,_,L,I=$.prototype={constructor:$,toString:null,valueOf:null},P=new $(1),A=20,k=4,C=-7,B=21,G=-1e7,M=1e7,q=!1,D=1,z=0,U={prefix:"",groupSize:3,secondaryGroupSize:0,groupSeparator:",",decimalSeparator:".",fractionGroupSize:0,fractionGroupSeparator:" ",suffix:""},F="0123456789abcdefghijklmnopqrstuvwxyz",j=!0;function $(t,e){var n,s,l,h,c,p,g,y,d=this;if(!(d instanceof $))return new $(t,e);if(null==e){if(t&&!0===t._isBigNumber)return d.s=t.s,void(!t.c||t.e>M?d.c=d.e=null:t.e<G?d.c=[d.e=0]:(d.e=t.e,d.c=t.c.slice()));if((p="number"==typeof t)&&0*t==0){if(d.s=1/t<0?(t=-t,-1):1,t===~~t){for(h=0,c=t;c>=10;c/=10,h++);return void(h>M?d.c=d.e=null:(d.e=h,d.c=[t]))}y=String(t)}else{if(!r.test(y=String(t)))return v(d,y,p);d.s=45==y.charCodeAt(0)?(y=y.slice(1),-1):1}(h=y.indexOf("."))>-1&&(y=y.replace(".","")),(c=y.search(/e/i))>0?(h<0&&(h=c),h+=+y.slice(c+1),y=y.substring(0,c)):h<0&&(h=y.length)}else{if(x(e,2,F.length,"Base"),10==e&&j)return H(d=new $(t),A+d.e+1,k);if(y=String(t),p="number"==typeof t){if(0*t!=0)return v(d,y,p,e);if(d.s=1/t<0?(y=y.slice(1),-1):1,$.DEBUG&&y.replace(/^0\.0*|\./,"").length>15)throw Error(u+t)}else d.s=45===y.charCodeAt(0)?(y=y.slice(1),-1):1;for(n=F.slice(0,e),h=c=0,g=y.length;c<g;c++)if(n.indexOf(s=y.charAt(c))<0){if("."==s){if(c>h){h=g;continue}}else if(!l&&(y==y.toUpperCase()&&(y=y.toLowerCase())||y==y.toLowerCase()&&(y=y.toUpperCase()))){l=!0,c=-1,h=0;continue}return v(d,String(t),p,e)}p=!1,(h=(y=i(y,e,10,d.s)).indexOf("."))>-1?y=y.replace(".",""):h=y.length}for(c=0;48===y.charCodeAt(c);c++);for(g=y.length;48===y.charCodeAt(--g););if(y=y.slice(c,++g)){if(g-=c,p&&$.DEBUG&&g>15&&(t>a||t!==o(t)))throw Error(u+d.s*t);if((h=h-c-1)>M)d.c=d.e=null;else if(h<G)d.c=[d.e=0];else{if(d.e=h,d.c=[],c=(h+1)%f,h<0&&(c+=f),c<g){for(c&&d.c.push(+y.slice(0,c)),g-=f;c<g;)d.c.push(+y.slice(c,c+=f));c=f-(y=y.slice(c)).length}else c-=g;for(;c--;y+="0");d.c.push(+y)}}else d.c=[d.e=0]}function V(t,e,n,i){var r,s,o,l,u;if(null==n?n=k:x(n,0,8),!t.c)return t.toString();if(r=t.c[0],o=t.e,null==e)u=d(t.c),u=1==i||2==i&&(o<=C||o>=B)?w(u,o):E(u,o,"0");else if(s=(t=H(new $(t),e,n)).e,l=(u=d(t.c)).length,1==i||2==i&&(e<=s||s<=C)){for(;l<e;u+="0",l++);u=w(u,s)}else if(e-=o,u=E(u,s,"0"),s+1>l){if(--e>0)for(u+=".";e--;u+="0");}else if((e+=s-l)>0)for(s+1==l&&(u+=".");e--;u+="0");return t.s<0&&r?"-"+u:u}function K(t,e){for(var n,i=1,r=new $(t[0]);i<t.length;i++){if(!(n=new $(t[i])).s){r=n;break}e.call(r,n)&&(r=n)}return r}function Z(t,e,n){for(var i=1,r=e.length;!e[--r];e.pop());for(r=e[0];r>=10;r/=10,i++);return(n=i+n*f-1)>M?t.c=t.e=null:n<G?t.c=[t.e=0]:(t.e=n,t.c=e),t}function H(t,e,n,i){var r,l,u,a,p,g,y,d=t.c,m=c;if(d){t:{for(r=1,a=d[0];a>=10;a/=10,r++);if((l=e-r)<0)l+=f,u=e,y=(p=d[g=0])/m[r-u-1]%10|0;else if((g=s((l+1)/f))>=d.length){if(!i)break t;for(;d.length<=g;d.push(0));p=y=0,r=1,u=(l%=f)-f+1}else{for(p=a=d[g],r=1;a>=10;a/=10,r++);y=(u=(l%=f)-f+r)<0?0:p/m[r-u-1]%10|0}if(i=i||e<0||null!=d[g+1]||(u<0?p:p%m[r-u-1]),i=n<4?(y||i)&&(0==n||n==(t.s<0?3:2)):y>5||5==y&&(4==n||i||6==n&&(l>0?u>0?p/m[r-u]:0:d[g-1])%10&1||n==(t.s<0?8:7)),e<1||!d[0])return d.length=0,i?(e-=t.e+1,d[0]=m[(f-e%f)%f],t.e=-e||0):d[0]=t.e=0,t;if(0==l?(d.length=g,a=1,g--):(d.length=g+1,a=m[f-l],d[g]=u>0?o(p/m[r-u]%m[u])*a:0),i)for(;;){if(0==g){for(l=1,u=d[0];u>=10;u/=10,l++);for(u=d[0]+=a,a=1;u>=10;u/=10,a++);l!=a&&(t.e++,d[0]==h&&(d[0]=1));break}if(d[g]+=a,d[g]!=h)break;d[g--]=0,a=1}for(l=d.length;0===d[--l];d.pop());}t.e>M?t.c=t.e=null:t.e<G&&(t.c=[t.e=0])}return t}function Y(t){var e,n=t.e;return null===n?t.toString():(e=d(t.c),e=n<=C||n>=B?w(e,n):E(e,n,"0"),t.s<0?"-"+e:e)}return $.clone=t,$.ROUND_UP=0,$.ROUND_DOWN=1,$.ROUND_CEIL=2,$.ROUND_FLOOR=3,$.ROUND_HALF_UP=4,$.ROUND_HALF_DOWN=5,$.ROUND_HALF_EVEN=6,$.ROUND_HALF_CEIL=7,$.ROUND_HALF_FLOOR=8,$.EUCLID=9,$.config=$.set=function(t){var e,n;if(null!=t){if("object"!=typeof t)throw Error(l+"Object expected: "+t);if(t.hasOwnProperty(e="DECIMAL_PLACES")&&(x(n=t[e],0,g,e),A=n),t.hasOwnProperty(e="ROUNDING_MODE")&&(x(n=t[e],0,8,e),k=n),t.hasOwnProperty(e="EXPONENTIAL_AT")&&((n=t[e])&&n.pop?(x(n[0],-g,0,e),x(n[1],0,g,e),C=n[0],B=n[1]):(x(n,-g,g,e),C=-(B=n<0?-n:n))),t.hasOwnProperty(e="RANGE"))if((n=t[e])&&n.pop)x(n[0],-g,-1,e),x(n[1],1,g,e),G=n[0],M=n[1];else{if(x(n,-g,g,e),!n)throw Error(l+e+" cannot be zero: "+n);G=-(M=n<0?-n:n)}if(t.hasOwnProperty(e="CRYPTO")){if((n=t[e])!==!!n)throw Error(l+e+" not true or false: "+n);if(n){if("undefined"==typeof crypto||!crypto||!crypto.getRandomValues&&!crypto.randomBytes)throw q=!n,Error(l+"crypto unavailable");q=n}else q=n}if(t.hasOwnProperty(e="MODULO_MODE")&&(x(n=t[e],0,9,e),D=n),t.hasOwnProperty(e="POW_PRECISION")&&(x(n=t[e],0,g,e),z=n),t.hasOwnProperty(e="FORMAT")){if("object"!=typeof(n=t[e]))throw Error(l+e+" not an object: "+n);U=n}if(t.hasOwnProperty(e="ALPHABET")){if("string"!=typeof(n=t[e])||/^.?$|[+\-.\s]|(.).*\1/.test(n))throw Error(l+e+" invalid: "+n);j="0123456789"==n.slice(0,10),F=n}}return{DECIMAL_PLACES:A,ROUNDING_MODE:k,EXPONENTIAL_AT:[C,B],RANGE:[G,M],CRYPTO:q,MODULO_MODE:D,POW_PRECISION:z,FORMAT:U,ALPHABET:F}},$.isBigNumber=function(t){if(!t||!0!==t._isBigNumber)return!1;if(!$.DEBUG)return!0;var e,n,i=t.c,r=t.e,s=t.s;t:if("[object Array]"=={}.toString.call(i)){if((1===s||-1===s)&&r>=-g&&r<=g&&r===o(r)){if(0===i[0]){if(0===r&&1===i.length)return!0;break t}if((e=(r+1)%f)<1&&(e+=f),String(i[0]).length==e){for(e=0;e<i.length;e++)if((n=i[e])<0||n>=h||n!==o(n))break t;if(0!==n)return!0}}}else if(null===i&&null===r&&(null===s||1===s||-1===s))return!0;throw Error(l+"Invalid BigNumber: "+t)},$.maximum=$.max=function(){return K(arguments,I.lt)},$.minimum=$.min=function(){return K(arguments,I.gt)},$.random=(S=9007199254740992,T=Math.random()*S&2097151?function(){return o(Math.random()*S)}:function(){return 8388608*(1073741824*Math.random()|0)+(8388608*Math.random()|0)},function(t){var e,n,i,r,u,h=0,a=[],p=new $(P);if(null==t?t=A:x(t,0,g),r=s(t/f),q)if(crypto.getRandomValues){for(e=crypto.getRandomValues(new Uint32Array(r*=2));h<r;)(u=131072*e[h]+(e[h+1]>>>11))>=9e15?(n=crypto.getRandomValues(new Uint32Array(2)),e[h]=n[0],e[h+1]=n[1]):(a.push(u%1e14),h+=2);h=r/2}else{if(!crypto.randomBytes)throw q=!1,Error(l+"crypto unavailable");for(e=crypto.randomBytes(r*=7);h<r;)(u=281474976710656*(31&e[h])+1099511627776*e[h+1]+4294967296*e[h+2]+16777216*e[h+3]+(e[h+4]<<16)+(e[h+5]<<8)+e[h+6])>=9e15?crypto.randomBytes(7).copy(e,h):(a.push(u%1e14),h+=7);h=r/7}if(!q)for(;h<r;)(u=T())<9e15&&(a[h++]=u%1e14);for(r=a[--h],t%=f,r&&t&&(u=c[f-t],a[h]=o(r/u)*u);0===a[h];a.pop(),h--);if(h<0)a=[i=0];else{for(i=-1;0===a[0];a.splice(0,1),i-=f);for(h=1,u=a[0];u>=10;u/=10,h++);h<f&&(i-=f-h)}return p.e=i,p.c=a,p}),$.sum=function(){for(var t=1,e=arguments,n=new $(e[0]);t<e.length;)n=n.plus(e[t++]);return n},i=function(){var t="0123456789";function e(t,e,n,i){for(var r,s,o=[0],l=0,u=t.length;l<u;){for(s=o.length;s--;o[s]*=e);for(o[0]+=i.indexOf(t.charAt(l++)),r=0;r<o.length;r++)o[r]>n-1&&(null==o[r+1]&&(o[r+1]=0),o[r+1]+=o[r]/n|0,o[r]%=n)}return o.reverse()}return function(i,r,s,o,l){var u,h,f,a,c,p,g,y,m=i.indexOf("."),x=A,b=k;for(m>=0&&(a=z,z=0,i=i.replace(".",""),p=(y=new $(r)).pow(i.length-m),z=a,y.c=e(E(d(p.c),p.e,"0"),10,s,t),y.e=y.c.length),f=a=(g=e(i,r,s,l?(u=F,t):(u=t,F))).length;0==g[--a];g.pop());if(!g[0])return u.charAt(0);if(m<0?--f:(p.c=g,p.e=f,p.s=o,g=(p=n(p,y,x,b,s)).c,c=p.r,f=p.e),m=g[h=f+x+1],a=s/2,c=c||h<0||null!=g[h+1],c=b<4?(null!=m||c)&&(0==b||b==(p.s<0?3:2)):m>a||m==a&&(4==b||c||6==b&&1&g[h-1]||b==(p.s<0?8:7)),h<1||!g[0])i=c?E(u.charAt(1),-x,u.charAt(0)):u.charAt(0);else{if(g.length=h,c)for(--s;++g[--h]>s;)g[h]=0,h||(++f,g=[1].concat(g));for(a=g.length;!g[--a];);for(m=0,i="";m<=a;i+=u.charAt(g[m++]));i=E(i,f,u.charAt(0))}return i}}(),n=function(){function t(t,e,n){var i,r,s,o,l=0,u=t.length,h=e%p,f=e/p|0;for(t=t.slice();u--;)l=((r=h*(s=t[u]%p)+(i=f*s+(o=t[u]/p|0)*h)%p*p+l)/n|0)+(i/p|0)+f*o,t[u]=r%n;return l&&(t=[l].concat(t)),t}function e(t,e,n,i){var r,s;if(n!=i)s=n>i?1:-1;else for(r=s=0;r<n;r++)if(t[r]!=e[r]){s=t[r]>e[r]?1:-1;break}return s}function n(t,e,n,i){for(var r=0;n--;)t[n]-=r,r=t[n]<e[n]?1:0,t[n]=r*i+t[n]-e[n];for(;!t[0]&&t.length>1;t.splice(0,1));}return function(i,r,s,l,u){var a,c,p,g,d,m,x,b,w,E,v,S,T,R,N,O,_,L=i.s==r.s?1:-1,I=i.c,P=r.c;if(!(I&&I[0]&&P&&P[0]))return new $(i.s&&r.s&&(I?!P||I[0]!=P[0]:P)?I&&0==I[0]||!P?0*L:L/0:NaN);for(w=(b=new $(L)).c=[],L=s+(c=i.e-r.e)+1,u||(u=h,c=y(i.e/f)-y(r.e/f),L=L/f|0),p=0;P[p]==(I[p]||0);p++);if(P[p]>(I[p]||0)&&c--,L<0)w.push(1),g=!0;else{for(R=I.length,O=P.length,p=0,L+=2,(d=o(u/(P[0]+1)))>1&&(P=t(P,d,u),I=t(I,d,u),O=P.length,R=I.length),T=O,v=(E=I.slice(0,O)).length;v<O;E[v++]=0);_=P.slice(),_=[0].concat(_),N=P[0],P[1]>=u/2&&N++;do{if(d=0,(a=e(P,E,O,v))<0){if(S=E[0],O!=v&&(S=S*u+(E[1]||0)),(d=o(S/N))>1)for(d>=u&&(d=u-1),x=(m=t(P,d,u)).length,v=E.length;1==e(m,E,x,v);)d--,n(m,O<x?_:P,x,u),x=m.length,a=1;else 0==d&&(a=d=1),x=(m=P.slice()).length;if(x<v&&(m=[0].concat(m)),n(E,m,v,u),v=E.length,-1==a)for(;e(P,E,O,v)<1;)d++,n(E,O<v?_:P,v,u),v=E.length}else 0===a&&(d++,E=[0]);w[p++]=d,E[0]?E[v++]=I[T]||0:(E=[I[T]],v=1)}while((T++<R||null!=E[0])&&L--);g=null!=E[0],w[0]||w.splice(0,1)}if(u==h){for(p=1,L=w[0];L>=10;L/=10,p++);H(b,s+(b.e=p+c*f-1)+1,l,g)}else b.e=c,b.r=+g;return b}}(),R=/^(-?)0([xbo])(?=\w[\w.]*$)/i,N=/^([^.]+)\.$/,O=/^\.([^.]+)$/,_=/^-?(Infinity|NaN)$/,L=/^\s*\+(?=[\w.])|^\s+|\s+$/g,v=function(t,e,n,i){var r,s=n?e:e.replace(L,"");if(_.test(s))t.s=isNaN(s)?null:s<0?-1:1;else{if(!n&&(s=s.replace(R,(function(t,e,n){return r="x"==(n=n.toLowerCase())?16:"b"==n?2:8,i&&i!=r?t:e})),i&&(r=i,s=s.replace(N,"$1").replace(O,"0.$1")),e!=s))return new $(s,r);if($.DEBUG)throw Error(l+"Not a"+(i?" base "+i:"")+" number: "+e);t.s=null}t.c=t.e=null},I.absoluteValue=I.abs=function(){var t=new $(this);return t.s<0&&(t.s=1),t},I.comparedTo=function(t,e){return m(this,new $(t,e))},I.decimalPlaces=I.dp=function(t,e){var n,i,r,s=this;if(null!=t)return x(t,0,g),null==e?e=k:x(e,0,8),H(new $(s),t+s.e+1,e);if(!(n=s.c))return null;if(i=((r=n.length-1)-y(this.e/f))*f,r=n[r])for(;r%10==0;r/=10,i--);return i<0&&(i=0),i},I.dividedBy=I.div=function(t,e){return n(this,new $(t,e),A,k)},I.dividedToIntegerBy=I.idiv=function(t,e){return n(this,new $(t,e),0,1)},I.exponentiatedBy=I.pow=function(t,e){var n,i,r,u,h,a,c,p,g=this;if((t=new $(t)).c&&!t.isInteger())throw Error(l+"Exponent not an integer: "+Y(t));if(null!=e&&(e=new $(e)),h=t.e>14,!g.c||!g.c[0]||1==g.c[0]&&!g.e&&1==g.c.length||!t.c||!t.c[0])return p=new $(Math.pow(+Y(g),h?2-b(t):+Y(t))),e?p.mod(e):p;if(a=t.s<0,e){if(e.c?!e.c[0]:!e.s)return new $(NaN);(i=!a&&g.isInteger()&&e.isInteger())&&(g=g.mod(e))}else{if(t.e>9&&(g.e>0||g.e<-1||(0==g.e?g.c[0]>1||h&&g.c[1]>=24e7:g.c[0]<8e13||h&&g.c[0]<=9999975e7)))return u=g.s<0&&b(t)?-0:0,g.e>-1&&(u=1/u),new $(a?1/u:u);z&&(u=s(z/f+2))}for(h?(n=new $(.5),a&&(t.s=1),c=b(t)):c=(r=Math.abs(+Y(t)))%2,p=new $(P);;){if(c){if(!(p=p.times(g)).c)break;u?p.c.length>u&&(p.c.length=u):i&&(p=p.mod(e))}if(r){if(0===(r=o(r/2)))break;c=r%2}else if(H(t=t.times(n),t.e+1,1),t.e>14)c=b(t);else{if(0===(r=+Y(t)))break;c=r%2}g=g.times(g),u?g.c&&g.c.length>u&&(g.c.length=u):i&&(g=g.mod(e))}return i?p:(a&&(p=P.div(p)),e?p.mod(e):u?H(p,z,k,undefined):p)},I.integerValue=function(t){var e=new $(this);return null==t?t=k:x(t,0,8),H(e,e.e+1,t)},I.isEqualTo=I.eq=function(t,e){return 0===m(this,new $(t,e))},I.isFinite=function(){return!!this.c},I.isGreaterThan=I.gt=function(t,e){return m(this,new $(t,e))>0},I.isGreaterThanOrEqualTo=I.gte=function(t,e){return 1===(e=m(this,new $(t,e)))||0===e},I.isInteger=function(){return!!this.c&&y(this.e/f)>this.c.length-2},I.isLessThan=I.lt=function(t,e){return m(this,new $(t,e))<0},I.isLessThanOrEqualTo=I.lte=function(t,e){return-1===(e=m(this,new $(t,e)))||0===e},I.isNaN=function(){return!this.s},I.isNegative=function(){return this.s<0},I.isPositive=function(){return this.s>0},I.isZero=function(){return!!this.c&&0==this.c[0]},I.minus=function(t,e){var n,i,r,s,o=this,l=o.s;if(e=(t=new $(t,e)).s,!l||!e)return new $(NaN);if(l!=e)return t.s=-e,o.plus(t);var u=o.e/f,a=t.e/f,c=o.c,p=t.c;if(!u||!a){if(!c||!p)return c?(t.s=-e,t):new $(p?o:NaN);if(!c[0]||!p[0])return p[0]?(t.s=-e,t):new $(c[0]?o:3==k?-0:0)}if(u=y(u),a=y(a),c=c.slice(),l=u-a){for((s=l<0)?(l=-l,r=c):(a=u,r=p),r.reverse(),e=l;e--;r.push(0));r.reverse()}else for(i=(s=(l=c.length)<(e=p.length))?l:e,l=e=0;e<i;e++)if(c[e]!=p[e]){s=c[e]<p[e];break}if(s&&(r=c,c=p,p=r,t.s=-t.s),(e=(i=p.length)-(n=c.length))>0)for(;e--;c[n++]=0);for(e=h-1;i>l;){if(c[--i]<p[i]){for(n=i;n&&!c[--n];c[n]=e);--c[n],c[i]+=h}c[i]-=p[i]}for(;0==c[0];c.splice(0,1),--a);return c[0]?Z(t,c,a):(t.s=3==k?-1:1,t.c=[t.e=0],t)},I.modulo=I.mod=function(t,e){var i,r,s=this;return t=new $(t,e),!s.c||!t.s||t.c&&!t.c[0]?new $(NaN):!t.c||s.c&&!s.c[0]?new $(s):(9==D?(r=t.s,t.s=1,i=n(s,t,0,3),t.s=r,i.s*=r):i=n(s,t,0,D),(t=s.minus(i.times(t))).c[0]||1!=D||(t.s=s.s),t)},I.multipliedBy=I.times=function(t,e){var n,i,r,s,o,l,u,a,c,g,d,m,x,b,w,E=this,v=E.c,S=(t=new $(t,e)).c;if(!(v&&S&&v[0]&&S[0]))return!E.s||!t.s||v&&!v[0]&&!S||S&&!S[0]&&!v?t.c=t.e=t.s=null:(t.s*=E.s,v&&S?(t.c=[0],t.e=0):t.c=t.e=null),t;for(i=y(E.e/f)+y(t.e/f),t.s*=E.s,(u=v.length)<(g=S.length)&&(x=v,v=S,S=x,r=u,u=g,g=r),r=u+g,x=[];r--;x.push(0));for(b=h,w=p,r=g;--r>=0;){for(n=0,d=S[r]%w,m=S[r]/w|0,s=r+(o=u);s>r;)n=((a=d*(a=v[--o]%w)+(l=m*a+(c=v[o]/w|0)*d)%w*w+x[s]+n)/b|0)+(l/w|0)+m*c,x[s--]=a%b;x[s]=n}return n?++i:x.splice(0,1),Z(t,x,i)},I.negated=function(){var t=new $(this);return t.s=-t.s||null,t},I.plus=function(t,e){var n,i=this,r=i.s;if(e=(t=new $(t,e)).s,!r||!e)return new $(NaN);if(r!=e)return t.s=-e,i.minus(t);var s=i.e/f,o=t.e/f,l=i.c,u=t.c;if(!s||!o){if(!l||!u)return new $(r/0);if(!l[0]||!u[0])return u[0]?t:new $(l[0]?i:0*r)}if(s=y(s),o=y(o),l=l.slice(),r=s-o){for(r>0?(o=s,n=u):(r=-r,n=l),n.reverse();r--;n.push(0));n.reverse()}for((r=l.length)-(e=u.length)<0&&(n=u,u=l,l=n,e=r),r=0;e;)r=(l[--e]=l[e]+u[e]+r)/h|0,l[e]=h===l[e]?0:l[e]%h;return r&&(l=[r].concat(l),++o),Z(t,l,o)},I.precision=I.sd=function(t,e){var n,i,r,s=this;if(null!=t&&t!==!!t)return x(t,1,g),null==e?e=k:x(e,0,8),H(new $(s),t,e);if(!(n=s.c))return null;if(i=(r=n.length-1)*f+1,r=n[r]){for(;r%10==0;r/=10,i--);for(r=n[0];r>=10;r/=10,i++);}return t&&s.e+1>i&&(i=s.e+1),i},I.shiftedBy=function(t){return x(t,-9007199254740991,a),this.times("1e"+t)},I.squareRoot=I.sqrt=function(){var t,e,i,r,s,o=this,l=o.c,u=o.s,h=o.e,f=A+4,a=new $("0.5");if(1!==u||!l||!l[0])return new $(!u||u<0&&(!l||l[0])?NaN:l?o:1/0);if(0==(u=Math.sqrt(+Y(o)))||u==1/0?(((e=d(l)).length+h)%2==0&&(e+="0"),u=Math.sqrt(+e),h=y((h+1)/2)-(h<0||h%2),i=new $(e=u==1/0?"5e"+h:(e=u.toExponential()).slice(0,e.indexOf("e")+1)+h)):i=new $(u+""),i.c[0])for((u=(h=i.e)+f)<3&&(u=0);;)if(s=i,i=a.times(s.plus(n(o,s,f,1))),d(s.c).slice(0,u)===(e=d(i.c)).slice(0,u)){if(i.e<h&&--u,"9999"!=(e=e.slice(u-3,u+1))&&(r||"4999"!=e)){+e&&(+e.slice(1)||"5"!=e.charAt(0))||(H(i,i.e+A+2,1),t=!i.times(i).eq(o));break}if(!r&&(H(s,s.e+A+2,0),s.times(s).eq(o))){i=s;break}f+=4,u+=4,r=1}return H(i,i.e+A+1,k,t)},I.toExponential=function(t,e){return null!=t&&(x(t,0,g),t++),V(this,t,e,1)},I.toFixed=function(t,e){return null!=t&&(x(t,0,g),t=t+this.e+1),V(this,t,e)},I.toFormat=function(t,e,n){var i,r=this;if(null==n)null!=t&&e&&"object"==typeof e?(n=e,e=null):t&&"object"==typeof t?(n=t,t=e=null):n=U;else if("object"!=typeof n)throw Error(l+"Argument not an object: "+n);if(i=r.toFixed(t,e),r.c){var s,o=i.split("."),u=+n.groupSize,h=+n.secondaryGroupSize,f=n.groupSeparator||"",a=o[0],c=o[1],p=r.s<0,g=p?a.slice(1):a,y=g.length;if(h&&(s=u,u=h,h=s,y-=s),u>0&&y>0){for(s=y%u||u,a=g.substr(0,s);s<y;s+=u)a+=f+g.substr(s,u);h>0&&(a+=f+g.slice(s)),p&&(a="-"+a)}i=c?a+(n.decimalSeparator||"")+((h=+n.fractionGroupSize)?c.replace(new RegExp("\\d{"+h+"}\\B","g"),"$&"+(n.fractionGroupSeparator||"")):c):a}return(n.prefix||"")+i+(n.suffix||"")},I.toFraction=function(t){var e,i,r,s,o,u,h,a,p,g,y,m,x=this,b=x.c;if(null!=t&&(!(h=new $(t)).isInteger()&&(h.c||1!==h.s)||h.lt(P)))throw Error(l+"Argument "+(h.isInteger()?"out of range: ":"not an integer: ")+Y(h));if(!b)return new $(x);for(e=new $(P),p=i=new $(P),r=a=new $(P),m=d(b),o=e.e=m.length-x.e-1,e.c[0]=c[(u=o%f)<0?f+u:u],t=!t||h.comparedTo(e)>0?o>0?e:p:h,u=M,M=1/0,h=new $(m),a.c[0]=0;g=n(h,e,0,1),1!=(s=i.plus(g.times(r))).comparedTo(t);)i=r,r=s,p=a.plus(g.times(s=p)),a=s,e=h.minus(g.times(s=e)),h=s;return s=n(t.minus(i),r,0,1),a=a.plus(s.times(p)),i=i.plus(s.times(r)),a.s=p.s=x.s,y=n(p,r,o*=2,k).minus(x).abs().comparedTo(n(a,i,o,k).minus(x).abs())<1?[p,r]:[a,i],M=u,y},I.toNumber=function(){return+Y(this)},I.toPrecision=function(t,e){return null!=t&&x(t,1,g),V(this,t,e,2)},I.toString=function(t){var e,n=this,r=n.s,s=n.e;return null===s?r?(e="Infinity",r<0&&(e="-"+e)):e="NaN":(null==t?e=s<=C||s>=B?w(d(n.c),s):E(d(n.c),s,"0"):10===t&&j?e=E(d((n=H(new $(n),A+s+1,k)).c),n.e,"0"):(x(t,2,F.length,"Base"),e=i(E(d(n.c),s,"0"),10,t,r,!0)),r<0&&n.c[0]&&(e="-"+e)),e},I.valueOf=I.toJSON=function(){return Y(this)},I._isBigNumber=!0,I[Symbol.toStringTag]="BigNumber",I[Symbol.for("nodejs.util.inspect.custom")]=I.valueOf,null!=e&&$.set(e),$}(),S=class{key;left=null;right=null;constructor(t){this.key=t}},T=class extends S{constructor(t){super(t)}},R=class{size=0;modificationCount=0;splayCount=0;splay(t){const e=this.root;if(null==e)return this.compare(t,t),-1;let n=null,i=null,r=null,s=null,o=e;const l=this.compare;let u;for(;;)if(u=l(o.key,t),u>0){let e=o.left;if(null==e)break;if(u=l(e.key,t),u>0&&(o.left=e.right,e.right=o,o=e,e=o.left,null==e))break;null==n?i=o:n.left=o,n=o,o=e}else{if(!(u<0))break;{let e=o.right;if(null==e)break;if(u=l(e.key,t),u<0&&(o.right=e.left,e.left=o,o=e,e=o.right,null==e))break;null==r?s=o:r.right=o,r=o,o=e}}return null!=r&&(r.right=o.left,o.left=s),null!=n&&(n.left=o.right,o.right=i),this.root!==o&&(this.root=o,this.splayCount++),u}splayMin(t){let e=t,n=e.left;for(;null!=n;){const t=n;e.left=t.right,t.right=e,e=t,n=e.left}return e}splayMax(t){let e=t,n=e.right;for(;null!=n;){const t=n;e.right=t.left,t.left=e,e=t,n=e.right}return e}_delete(t){if(null==this.root)return null;if(0!=this.splay(t))return null;let e=this.root;const n=e,i=e.left;if(this.size--,null==i)this.root=e.right;else{const t=e.right;e=this.splayMax(i),e.right=t,this.root=e}return this.modificationCount++,n}addNewRoot(t,e){this.size++,this.modificationCount++;const n=this.root;null!=n?(e<0?(t.left=n,t.right=n.right,n.right=null):(t.right=n,t.left=n.left,n.left=null),this.root=t):this.root=t}_first(){const t=this.root;return null==t?null:(this.root=this.splayMin(t),this.root)}_last(){const t=this.root;return null==t?null:(this.root=this.splayMax(t),this.root)}clear(){this.root=null,this.size=0,this.modificationCount++}has(t){return this.validKey(t)&&0==this.splay(t)}defaultCompare(){return(t,e)=>t<e?-1:t>e?1:0}wrap(){return{getRoot:()=>this.root,setRoot:t=>{this.root=t},getSize:()=>this.size,getModificationCount:()=>this.modificationCount,getSplayCount:()=>this.splayCount,setSplayCount:t=>{this.splayCount=t},splay:t=>this.splay(t),has:t=>this.has(t)}}},N=class t extends R{root=null;compare;validKey;constructor(t,e){super(),this.compare=t??this.defaultCompare(),this.validKey=e??(t=>null!=t&&null!=t)}delete(t){return!!this.validKey(t)&&null!=this._delete(t)}deleteAll(t){for(const e of t)this.delete(e)}forEach(t){const e=this[Symbol.iterator]();let n;for(;n=e.next(),!n.done;)t(n.value,n.value,this)}add(t){const e=this.splay(t);return 0!=e&&this.addNewRoot(new T(t),e),this}addAndReturn(t){const e=this.splay(t);return 0!=e&&this.addNewRoot(new T(t),e),this.root.key}addAll(t){for(const e of t)this.add(e)}isEmpty(){return null==this.root}isNotEmpty(){return null!=this.root}single(){if(0==this.size)throw"Bad state: No element";if(this.size>1)throw"Bad state: Too many element";return this.root.key}first(){if(0==this.size)throw"Bad state: No element";return this._first().key}last(){if(0==this.size)throw"Bad state: No element";return this._last().key}lastBefore(t){if(null==t)throw"Invalid arguments(s)";if(null==this.root)return null;if(this.splay(t)<0)return this.root.key;let e=this.root.left;if(null==e)return null;let n=e.right;for(;null!=n;)e=n,n=e.right;return e.key}firstAfter(t){if(null==t)throw"Invalid arguments(s)";if(null==this.root)return null;if(this.splay(t)>0)return this.root.key;let e=this.root.right;if(null==e)return null;let n=e.left;for(;null!=n;)e=n,n=e.left;return e.key}retainAll(e){const n=new t(this.compare,this.validKey),i=this.modificationCount;for(const t of e){if(i!=this.modificationCount)throw"Concurrent modification during iteration.";this.validKey(t)&&0==this.splay(t)&&n.add(this.root.key)}n.size!=this.size&&(this.root=n.root,this.size=n.size,this.modificationCount++)}lookup(t){if(!this.validKey(t))return null;return 0!=this.splay(t)?null:this.root.key}intersection(e){const n=new t(this.compare,this.validKey);for(const t of this)e.has(t)&&n.add(t);return n}difference(e){const n=new t(this.compare,this.validKey);for(const t of this)e.has(t)||n.add(t);return n}union(t){const e=this.clone();return e.addAll(t),e}clone(){const e=new t(this.compare,this.validKey);return e.size=this.size,e.root=this.copyNode(this.root),e}copyNode(t){if(null==t)return null;const e=new T(t.key);return function t(e,n){let i,r;do{if(i=e.left,r=e.right,null!=i){const e=new T(i.key);n.left=e,t(i,e)}if(null!=r){const t=new T(r.key);n.right=t,e=r,n=t}}while(null!=r)}(t,e),e}toSet(){return this.clone()}entries(){return new L(this.wrap())}keys(){return this[Symbol.iterator]()}values(){return this[Symbol.iterator]()}[Symbol.iterator](){return new _(this.wrap())}[Symbol.toStringTag]="[object Set]"},O=class{tree;path=new Array;modificationCount=null;splayCount;constructor(t){this.tree=t,this.splayCount=t.getSplayCount()}[Symbol.iterator](){return this}next(){return this.moveNext()?{done:!1,value:this.current()}:{done:!0,value:null}}current(){if(!this.path.length)return null;const t=this.path[this.path.length-1];return this.getValue(t)}rebuildPath(t){this.path.splice(0,this.path.length),this.tree.splay(t),this.path.push(this.tree.getRoot()),this.splayCount=this.tree.getSplayCount()}findLeftMostDescendent(t){for(;null!=t;)this.path.push(t),t=t.left}moveNext(){if(this.modificationCount!=this.tree.getModificationCount()){if(null==this.modificationCount){this.modificationCount=this.tree.getModificationCount();let t=this.tree.getRoot();for(;null!=t;)this.path.push(t),t=t.left;return this.path.length>0}throw"Concurrent modification during iteration."}if(!this.path.length)return!1;this.splayCount!=this.tree.getSplayCount()&&this.rebuildPath(this.path[this.path.length-1].key);let t=this.path[this.path.length-1],e=t.right;if(null!=e){for(;null!=e;)this.path.push(e),e=e.left;return!0}for(this.path.pop();this.path.length&&this.path[this.path.length-1].right===t;)t=this.path.pop();return this.path.length>0}},_=class extends O{getValue(t){return t.key}},L=class extends O{getValue(t){return[t.key,t.key]}},I=t=>t,P=t=>{if(t){const e=new N(n(t)),i=new N(n(t)),r=(t,e)=>e.addAndReturn(t),s=t=>({x:r(t.x,e),y:r(t.y,i)});return s({x:new v(0),y:new v(0)}),s}return I};const A=t=>({set:t=>{k=A(t)},reset:()=>A(t),compare:n(t),snap:P(t),orient:i(t)});let k=A();const C=(t,e)=>t.ll.x.isLessThanOrEqualTo(e.x)&&e.x.isLessThanOrEqualTo(t.ur.x)&&t.ll.y.isLessThanOrEqualTo(e.y)&&e.y.isLessThanOrEqualTo(t.ur.y),B=(t,e)=>{if(e.ur.x.isLessThan(t.ll.x)||t.ur.x.isLessThan(e.ll.x)||e.ur.y.isLessThan(t.ll.y)||t.ur.y.isLessThan(e.ll.y))return null;const n=t.ll.x.isLessThan(e.ll.x)?e.ll.x:t.ll.x,i=t.ur.x.isLessThan(e.ur.x)?t.ur.x:e.ur.x;return{ll:{x:n,y:t.ll.y.isLessThan(e.ll.y)?e.ll.y:t.ll.y},ur:{x:i,y:t.ur.y.isLessThan(e.ur.y)?t.ur.y:e.ur.y}}},G=(t,e)=>t.x.times(e.y).minus(t.y.times(e.x)),M=(t,e)=>t.x.times(e.x).plus(t.y.times(e.y)),q=t=>M(t,t).sqrt(),D=(t,e,n)=>{const i={x:e.x.minus(t.x),y:e.y.minus(t.y)},r={x:n.x.minus(t.x),y:n.y.minus(t.y)};return G(r,i).div(q(r)).div(q(i))},z=(t,e,n)=>{const i={x:e.x.minus(t.x),y:e.y.minus(t.y)},r={x:n.x.minus(t.x),y:n.y.minus(t.y)};return M(r,i).div(q(r)).div(q(i))},U=(t,e,n)=>e.y.isZero()?null:{x:t.x.plus(e.x.div(e.y).times(n.minus(t.y))),y:n},F=(t,e,n)=>e.x.isZero()?null:{x:n,y:t.y.plus(e.y.div(e.x).times(n.minus(t.x)))};class j{point;isLeft;segment;otherSE;consumedBy;static compare(t,e){const n=j.comparePoints(t.point,e.point);return 0!==n?n:(t.point!==e.point&&t.link(e),t.isLeft!==e.isLeft?t.isLeft?1:-1:V.compare(t.segment,e.segment))}static comparePoints(t,e){return t.x.isLessThan(e.x)?-1:t.x.isGreaterThan(e.x)?1:t.y.isLessThan(e.y)?-1:t.y.isGreaterThan(e.y)?1:0}constructor(t,e){void 0===t.events?t.events=[this]:t.events.push(this),this.point=t,this.isLeft=e}link(t){if(t.point===this.point)throw new Error("Tried to link already linked events");const e=t.point.events;for(let t=0,n=e.length;t<n;t++){const n=e[t];this.point.events.push(n),n.point=this.point}this.checkForConsuming()}checkForConsuming(){const t=this.point.events.length;for(let e=0;e<t;e++){const n=this.point.events[e];if(void 0===n.segment.consumedBy)for(let i=e+1;i<t;i++){const t=this.point.events[i];void 0===t.consumedBy&&(n.otherSE.point.events===t.otherSE.point.events&&n.segment.consume(t.segment))}}}getAvailableLinkedEvents(){const t=[];for(let e=0,n=this.point.events.length;e<n;e++){const n=this.point.events[e];n!==this&&!n.segment.ringOut&&n.segment.isInResult()&&t.push(n)}return t}getLeftmostComparator(t){const e=new Map,n=n=>{const i=n.otherSE;e.set(n,{sine:D(this.point,t.point,i.point),cosine:z(this.point,t.point,i.point)})};return(t,i)=>{e.has(t)||n(t),e.has(i)||n(i);const{sine:r,cosine:s}=e.get(t),{sine:o,cosine:l}=e.get(i);return r.isGreaterThanOrEqualTo(0)&&o.isGreaterThanOrEqualTo(0)?s.isLessThan(l)?1:s.isGreaterThan(l)?-1:0:r.isLessThan(0)&&o.isLessThan(0)?s.isLessThan(l)?-1:s.isGreaterThan(l)?1:0:o.isLessThan(r)?-1:o.isGreaterThan(r)?1:0}}}let $=0;class V{id;leftSE;rightSE;rings;windings;ringOut;consumedBy;prev;_prevInResult;_beforeState;_afterState;_isInResult;static compare(t,e){const n=t.leftSE.point.x,i=e.leftSE.point.x,r=t.rightSE.point.x,s=e.rightSE.point.x;if(s.isLessThan(n))return 1;if(r.isLessThan(i))return-1;const o=t.leftSE.point.y,l=e.leftSE.point.y,u=t.rightSE.point.y,h=e.rightSE.point.y;if(n.isLessThan(i)){if(l.isLessThan(o)&&l.isLessThan(u))return 1;if(l.isGreaterThan(o)&&l.isGreaterThan(u))return-1;const n=t.comparePoint(e.leftSE.point);if(n<0)return 1;if(n>0)return-1;const i=e.comparePoint(t.rightSE.point);return 0!==i?i:-1}if(n.isGreaterThan(i)){if(o.isLessThan(l)&&o.isLessThan(h))return-1;if(o.isGreaterThan(l)&&o.isGreaterThan(h))return 1;const n=e.comparePoint(t.leftSE.point);if(0!==n)return n;const i=t.comparePoint(e.rightSE.point);return i<0?1:i>0?-1:1}if(o.isLessThan(l))return-1;if(o.isGreaterThan(l))return 1;if(r.isLessThan(s)){const n=e.comparePoint(t.rightSE.point);if(0!==n)return n}if(r.isGreaterThan(s)){const n=t.comparePoint(e.rightSE.point);if(n<0)return 1;if(n>0)return-1}if(!r.eq(s)){const t=u.minus(o),e=r.minus(n),f=h.minus(l),a=s.minus(i);if(t.isGreaterThan(e)&&f.isLessThan(a))return 1;if(t.isLessThan(e)&&f.isGreaterThan(a))return-1}return r.isGreaterThan(s)?1:r.isLessThan(s)||u.isLessThan(h)?-1:u.isGreaterThan(h)?1:t.id<e.id?-1:t.id>e.id?1:0}constructor(t,e,n,i){this.id=++$,this.leftSE=t,t.segment=this,t.otherSE=e,this.rightSE=e,e.segment=this,e.otherSE=t,this.rings=n,this.windings=i}static fromRing(t,e,n){let i,r,s;const o=j.comparePoints(t,e);if(o<0)i=t,r=e,s=1;else{if(!(o>0))throw new Error(`Tried to create degenerate segment at [${t.x}, ${t.y}]`);i=e,r=t,s=-1}const l=new j(i,!0),u=new j(r,!1);return new V(l,u,[n],[s])}replaceRightSE(t){this.rightSE=t,this.rightSE.segment=this,this.rightSE.otherSE=this.leftSE,this.leftSE.otherSE=this.rightSE}bbox(){const t=this.leftSE.point.y,e=this.rightSE.point.y;return{ll:{x:this.leftSE.point.x,y:t.isLessThan(e)?t:e},ur:{x:this.rightSE.point.x,y:t.isGreaterThan(e)?t:e}}}vector(){return{x:this.rightSE.point.x.minus(this.leftSE.point.x),y:this.rightSE.point.y.minus(this.leftSE.point.y)}}isAnEndpoint(t){return t.x.eq(this.leftSE.point.x)&&t.y.eq(this.leftSE.point.y)||t.x.eq(this.rightSE.point.x)&&t.y.eq(this.rightSE.point.y)}comparePoint(t){return k.orient(this.leftSE.point,t,this.rightSE.point)}getIntersection(t){const e=this.bbox(),n=t.bbox(),i=B(e,n);if(null===i)return null;const r=this.leftSE.point,s=this.rightSE.point,o=t.leftSE.point,l=t.rightSE.point,u=C(e,o)&&0===this.comparePoint(o),h=C(n,r)&&0===t.comparePoint(r),f=C(e,l)&&0===this.comparePoint(l),a=C(n,s)&&0===t.comparePoint(s);if(h&&u)return a&&!f?s:!a&&f?l:null;if(h)return f&&r.x.eq(l.x)&&r.y.eq(l.y)?null:r;if(u)return a&&s.x.eq(o.x)&&s.y.eq(o.y)?null:o;if(a&&f)return null;if(a)return s;if(f)return l;const c=((t,e,n,i)=>{if(e.x.isZero())return F(n,i,t.x);if(i.x.isZero())return F(t,e,n.x);if(e.y.isZero())return U(n,i,t.y);if(i.y.isZero())return U(t,e,n.y);const r=G(e,i);if(r.isZero())return null;const s={x:n.x.minus(t.x),y:n.y.minus(t.y)},o=G(s,e).div(r),l=G(s,i).div(r),u=t.x.plus(l.times(e.x)),h=n.x.plus(o.times(i.x)),f=t.y.plus(l.times(e.y)),a=n.y.plus(o.times(i.y));return{x:u.plus(h).div(2),y:f.plus(a).div(2)}})(r,this.vector(),o,t.vector());return null===c?null:C(i,c)?k.snap(c):null}split(t){const e=[],n=void 0!==t.events,i=new j(t,!0),r=new j(t,!1),s=this.rightSE;this.replaceRightSE(r),e.push(r),e.push(i);const o=new V(i,s,this.rings.slice(),this.windings.slice());return j.comparePoints(o.leftSE.point,o.rightSE.point)>0&&o.swapEvents(),j.comparePoints(this.leftSE.point,this.rightSE.point)>0&&this.swapEvents(),n&&(i.checkForConsuming(),r.checkForConsuming()),e}swapEvents(){const t=this.rightSE;this.rightSE=this.leftSE,this.leftSE=t,this.leftSE.isLeft=!0,this.rightSE.isLeft=!1;for(let t=0,e=this.windings.length;t<e;t++)this.windings[t]*=-1}consume(t){let e=this,n=t;for(;e.consumedBy;)e=e.consumedBy;for(;n.consumedBy;)n=n.consumedBy;const i=V.compare(e,n);if(0!==i){if(i>0){const t=e;e=n,n=t}if(e.prev===n){const t=e;e=n,n=t}for(let t=0,i=n.rings.length;t<i;t++){const i=n.rings[t],r=n.windings[t],s=e.rings.indexOf(i);-1===s?(e.rings.push(i),e.windings.push(r)):e.windings[s]+=r}n.rings=null,n.windings=null,n.consumedBy=e,n.leftSE.consumedBy=e.leftSE,n.rightSE.consumedBy=e.rightSE}}prevInResult(){return void 0!==this._prevInResult||(this.prev?this.prev.isInResult()?this._prevInResult=this.prev:this._prevInResult=this.prev.prevInResult():this._prevInResult=null),this._prevInResult}beforeState(){if(void 0!==this._beforeState)return this._beforeState;if(this.prev){const t=this.prev.consumedBy||this.prev;this._beforeState=t.afterState()}else this._beforeState={rings:[],windings:[],multiPolys:[]};return this._beforeState}afterState(){if(void 0!==this._afterState)return this._afterState;const t=this.beforeState();this._afterState={rings:t.rings.slice(0),windings:t.windings.slice(0),multiPolys:[]};const e=this._afterState.rings,n=this._afterState.windings,i=this._afterState.multiPolys;for(let t=0,i=this.rings.length;t<i;t++){const i=this.rings[t],r=this.windings[t],s=e.indexOf(i);-1===s?(e.push(i),n.push(r)):n[s]+=r}const r=[],s=[];for(let t=0,i=e.length;t<i;t++){if(0===n[t])continue;const i=e[t],o=i.poly;if(-1===s.indexOf(o))if(i.isExterior)r.push(o);else{-1===s.indexOf(o)&&s.push(o);const t=r.indexOf(i.poly);-1!==t&&r.splice(t,1)}}for(let t=0,e=r.length;t<e;t++){const e=r[t].multiPoly;-1===i.indexOf(e)&&i.push(e)}return this._afterState}isInResult(){if(this.consumedBy)return!1;if(void 0!==this._isInResult)return this._isInResult;const t=this.beforeState().multiPolys,e=this.afterState().multiPolys;switch(Q.type){case"union":{const n=0===t.length,i=0===e.length;this._isInResult=n!==i;break}case"intersection":{let n,i;t.length<e.length?(n=t.length,i=e.length):(n=e.length,i=t.length),this._isInResult=i===Q.numMultiPolys&&n<i;break}case"xor":{const n=Math.abs(t.length-e.length);this._isInResult=n%2==1;break}case"difference":{const n=t=>1===t.length&&t[0].isSubject;this._isInResult=n(t)!==n(e);break}}return this._isInResult}}class K{poly;isExterior;segments;bbox;constructor(t,e,n){if(!Array.isArray(t)||0===t.length)throw new Error("Input geometry is not a valid Polygon or MultiPolygon");if(this.poly=e,this.isExterior=n,this.segments=[],"number"!=typeof t[0][0]||"number"!=typeof t[0][1])throw new Error("Input geometry is not a valid Polygon or MultiPolygon");const i=k.snap({x:new v(t[0][0]),y:new v(t[0][1])});this.bbox={ll:{x:i.x,y:i.y},ur:{x:i.x,y:i.y}};let r=i;for(let e=1,n=t.length;e<n;e++){if("number"!=typeof t[e][0]||"number"!=typeof t[e][1])throw new Error("Input geometry is not a valid Polygon or MultiPolygon");const n=k.snap({x:new v(t[e][0]),y:new v(t[e][1])});n.x.eq(r.x)&&n.y.eq(r.y)||(this.segments.push(V.fromRing(r,n,this)),n.x.isLessThan(this.bbox.ll.x)&&(this.bbox.ll.x=n.x),n.y.isLessThan(this.bbox.ll.y)&&(this.bbox.ll.y=n.y),n.x.isGreaterThan(this.bbox.ur.x)&&(this.bbox.ur.x=n.x),n.y.isGreaterThan(this.bbox.ur.y)&&(this.bbox.ur.y=n.y),r=n)}i.x.eq(r.x)&&i.y.eq(r.y)||this.segments.push(V.fromRing(r,i,this))}getSweepEvents(){const t=[];for(let e=0,n=this.segments.length;e<n;e++){const n=this.segments[e];t.push(n.leftSE),t.push(n.rightSE)}return t}}class Z{multiPoly;exteriorRing;interiorRings;bbox;constructor(t,e){if(!Array.isArray(t))throw new Error("Input geometry is not a valid Polygon or MultiPolygon");this.exteriorRing=new K(t[0],this,!0),this.bbox={ll:{x:this.exteriorRing.bbox.ll.x,y:this.exteriorRing.bbox.ll.y},ur:{x:this.exteriorRing.bbox.ur.x,y:this.exteriorRing.bbox.ur.y}},this.interiorRings=[];for(let e=1,n=t.length;e<n;e++){const n=new K(t[e],this,!1);n.bbox.ll.x.isLessThan(this.bbox.ll.x)&&(this.bbox.ll.x=n.bbox.ll.x),n.bbox.ll.y.isLessThan(this.bbox.ll.y)&&(this.bbox.ll.y=n.bbox.ll.y),n.bbox.ur.x.isGreaterThan(this.bbox.ur.x)&&(this.bbox.ur.x=n.bbox.ur.x),n.bbox.ur.y.isGreaterThan(this.bbox.ur.y)&&(this.bbox.ur.y=n.bbox.ur.y),this.interiorRings.push(n)}this.multiPoly=e}getSweepEvents(){const t=this.exteriorRing.getSweepEvents();for(let e=0,n=this.interiorRings.length;e<n;e++){const n=this.interiorRings[e].getSweepEvents();for(let e=0,i=n.length;e<i;e++)t.push(n[e])}return t}}class H{isSubject;polys;bbox;constructor(t,e){if(!Array.isArray(t))throw new Error("Input geometry is not a valid Polygon or MultiPolygon");try{"number"==typeof t[0][0][0]&&(t=[t])}catch(t){}this.polys=[],this.bbox={ll:{x:new v(Number.POSITIVE_INFINITY),y:new v(Number.POSITIVE_INFINITY)},ur:{x:new v(Number.NEGATIVE_INFINITY),y:new v(Number.NEGATIVE_INFINITY)}};for(let e=0,n=t.length;e<n;e++){const n=new Z(t[e],this);n.bbox.ll.x.isLessThan(this.bbox.ll.x)&&(this.bbox.ll.x=n.bbox.ll.x),n.bbox.ll.y.isLessThan(this.bbox.ll.y)&&(this.bbox.ll.y=n.bbox.ll.y),n.bbox.ur.x.isGreaterThan(this.bbox.ur.x)&&(this.bbox.ur.x=n.bbox.ur.x),n.bbox.ur.y.isGreaterThan(this.bbox.ur.y)&&(this.bbox.ur.y=n.bbox.ur.y),this.polys.push(n)}this.isSubject=e}getSweepEvents(){const t=[];for(let e=0,n=this.polys.length;e<n;e++){const n=this.polys[e].getSweepEvents();for(let e=0,i=n.length;e<i;e++)t.push(n[e])}return t}}class Y{events;poly;_isExteriorRing;_enclosingRing;static factory(t){const e=[];for(let n=0,i=t.length;n<i;n++){const i=t[n];if(!i.isInResult()||i.ringOut)continue;let r=null,s=i.leftSE,o=i.rightSE;const l=[s],u=s.point,h=[];for(;r=s,s=o,l.push(s),s.point!==u;)for(;;){const t=s.getAvailableLinkedEvents();if(0===t.length){const t=l[0].point,e=l[l.length-1].point;throw new Error(`Unable to complete output ring starting at [${t.x}, ${t.y}]. Last matching segment found ends at [${e.x}, ${e.y}].`)}if(1===t.length){o=t[0].otherSE;break}let n=null;for(let t=0,e=h.length;t<e;t++)if(h[t].point===s.point){n=t;break}if(null!==n){const t=h.splice(n)[0],i=l.splice(t.index);i.unshift(i[0].otherSE),e.push(new Y(i.reverse()));continue}h.push({index:l.length,point:s.point});const i=s.getLeftmostComparator(r);o=t.sort(i)[0].otherSE;break}e.push(new Y(l))}return e}constructor(t){this.events=t;for(let e=0,n=t.length;e<n;e++)t[e].segment.ringOut=this;this.poly=null}getGeom(){let t=this.events[0].point;const e=[t];for(let n=1,i=this.events.length-1;n<i;n++){const i=this.events[n].point,r=this.events[n+1].point;0!==k.orient(i,t,r)&&(e.push(i),t=i)}if(1===e.length)return null;const n=e[0],i=e[1];0===k.orient(n,t,i)&&e.shift(),e.push(e[0]);const r=this.isExteriorRing()?1:-1,s=this.isExteriorRing()?0:e.length-1,o=this.isExteriorRing()?e.length:-1,l=[];for(let t=s;t!=o;t+=r)l.push([e[t].x.toNumber(),e[t].y.toNumber()]);return l}isExteriorRing(){if(void 0===this._isExteriorRing){const t=this.enclosingRing();this._isExteriorRing=!t||!t.isExteriorRing()}return this._isExteriorRing}enclosingRing(){return void 0===this._enclosingRing&&(this._enclosingRing=this._calcEnclosingRing()),this._enclosingRing}_calcEnclosingRing(){let t=this.events[0];for(let e=1,n=this.events.length;e<n;e++){const n=this.events[e];j.compare(t,n)>0&&(t=n)}let e=t.segment.prevInResult(),n=e?e.prevInResult():null;for(;;){if(!e)return null;if(!n)return e.ringOut;if(n.ringOut!==e.ringOut)return n.ringOut?.enclosingRing()!==e.ringOut?e.ringOut:e.ringOut?.enclosingRing();e=n.prevInResult(),n=e?e.prevInResult():null}}}class W{exteriorRing;interiorRings;constructor(t){this.exteriorRing=t,t.poly=this,this.interiorRings=[]}addInterior(t){this.interiorRings.push(t),t.poly=this}getGeom(){const t=this.exteriorRing.getGeom();if(null===t)return null;const e=[t];for(let t=0,n=this.interiorRings.length;t<n;t++){const n=this.interiorRings[t].getGeom();null!==n&&e.push(n)}return e}}class X{rings;polys;constructor(t){this.rings=t,this.polys=this._composePolys(t)}getGeom(){const t=[];for(let e=0,n=this.polys.length;e<n;e++){const n=this.polys[e].getGeom();null!==n&&t.push(n)}return t}_composePolys(t){const e=[];for(let n=0,i=t.length;n<i;n++){const i=t[n];if(!i.poly)if(i.isExteriorRing())e.push(new W(i));else{const t=i.enclosingRing();t?.poly||e.push(new W(t)),t?.poly?.addInterior(i)}}return e}}class J{queue;tree;segments;constructor(t,e=V.compare){this.queue=t,this.tree=new N(e),this.segments=[]}process(t){const e=t.segment,n=[];if(t.consumedBy)return t.isLeft?this.queue.delete(t.otherSE):this.tree.delete(e),n;t.isLeft&&this.tree.add(e);let i=e,r=e;do{i=this.tree.lastBefore(i)}while(null!=i&&null!=i.consumedBy);do{r=this.tree.firstAfter(r)}while(null!=r&&null!=r.consumedBy);if(t.isLeft){let s=null;if(i){const t=i.getIntersection(e);if(null!==t&&(e.isAnEndpoint(t)||(s=t),!i.isAnEndpoint(t))){const e=this._splitSafely(i,t);for(let t=0,i=e.length;t<i;t++)n.push(e[t])}}let o=null;if(r){const t=r.getIntersection(e);if(null!==t&&(e.isAnEndpoint(t)||(o=t),!r.isAnEndpoint(t))){const e=this._splitSafely(r,t);for(let t=0,i=e.length;t<i;t++)n.push(e[t])}}if(null!==s||null!==o){let t=null;if(null===s)t=o;else if(null===o)t=s;else{t=j.comparePoints(s,o)<=0?s:o}this.queue.delete(e.rightSE),n.push(e.rightSE);const i=e.split(t);for(let t=0,e=i.length;t<e;t++)n.push(i[t])}n.length>0?(this.tree.delete(e),n.push(t)):(this.segments.push(e),e.prev=i)}else{if(i&&r){const t=i.getIntersection(r);if(null!==t){if(!i.isAnEndpoint(t)){const e=this._splitSafely(i,t);for(let t=0,i=e.length;t<i;t++)n.push(e[t])}if(!r.isAnEndpoint(t)){const e=this._splitSafely(r,t);for(let t=0,i=e.length;t<i;t++)n.push(e[t])}}}this.tree.delete(e)}return n}_splitSafely(t,e){this.tree.delete(t);const n=t.rightSE;this.queue.delete(n);const i=t.split(e);return i.push(n),void 0===t.consumedBy&&this.tree.add(t),i}}const Q=new class{type;numMultiPolys;run(t,e,n){Q.type=t;const i=[new H(e,!0)];for(let t=0,e=n.length;t<e;t++)i.push(new H(n[t],!1));if(Q.numMultiPolys=i.length,"difference"===Q.type){const t=i[0];let e=1;for(;e<i.length;)null!==B(i[e].bbox,t.bbox)?e++:i.splice(e,1)}if("intersection"===Q.type)for(let t=0,e=i.length;t<e;t++){const e=i[t];for(let n=t+1,r=i.length;n<r;n++)if(null===B(e.bbox,i[n].bbox))return[]}const r=new N(j.compare);for(let t=0,e=i.length;t<e;t++){const e=i[t].getSweepEvents();for(let t=0,n=e.length;t<n;t++)r.add(e[t])}const s=new J(r);let o=null;for(0!=r.size&&(o=r.first(),r.delete(o));o;){const t=s.process(o);for(let e=0,n=t.length;e<n;e++){const n=t[e];void 0===n.consumedBy&&r.add(n)}0!=r.size?(o=r.first(),r.delete(o)):o=null}k.reset();const l=Y.factory(s.segments);return new X(l).getGeom()}},tt=k.set;t.difference=(t,...e)=>Q.run("difference",t,e),t.intersection=(t,...e)=>Q.run("intersection",t,e),t.setPrecision=tt,t.union=(t,...e)=>Q.run("union",t,e),t.version="0.16.8",t.xor=(t,...e)=>Q.run("xor",t,e),Object.defineProperty(t,"__esModule",{value:!0})}));