/// source code (in typescript) // // @kariay1975/atcoder-tslib is a private package: // import { // Input, // InputStdin, // sortAsNumber, // sumNumber, // } from '@kariya1975/atcoder-tslib'; // // use babel-plugin-macros for speed. // import { // range, // arrayWith, // } from '@kariya1975/atcoder-tslib/macro'; // import bipartiteMatching from 'bipartite-matching'; // // // type int = number; // // const nextPerm = (xs: int[]): boolean => { // const swap = (i: int, j: int): void => { // const t = xs[i]; // xs[i] = xs[j]; // xs[j] = t; // }; // for (const i of range(xs.length - 2, -1, -1)) { // if (xs[i] >= xs[i + 1]) continue; // for (const j of range(xs.length -1, -1, -1)) { // if (xs[j] <= xs[i]) continue; // swap(i, j); // for (const k of range(xs.length - i - 1)) { // const l = i + 1 + k; // const m = xs.length - 1 - k; // if (l > m) break; // swap(l, m); // } // break; // } // return true; // } // return false; // }; // // const gcd = (n: int, m: int): int => { // if (m === 0) return n; // return gcd(m, n % m); // }; // // const gcds = (xs: int[]): int => { // const [x, ...rest] = xs; // if (rest.length === 0) return x; // return gcd(x, gcds(rest)); // }; // // const main = (input: Input, output: any[]): void => { // const [N, M] = input.getInts(2); // const A: int[][] = []; // for (const _ of range(N)) { // const a = input.getInts(N); // if (sumNumber(a) !== M) { // output.push(-1); // return; // } // A.push(a); // } // // const solve = (): int[] | false => { // const n = N; // let m = 0; // const g: [int, int][] = []; // for (const i of range(N)) { // for (const j of range(N)) { // if (A[i][j] === 0) continue; // g.push([i, j]); // m += 1; // } // } // const result = bipartiteMatching(n, m, g); // // console.error(result); // if (result.length !== N) return false; // return result.map(x => x[1]); // }; // // const ans: int[][] = []; // for (const m of range(M)) { // const result = solve(); // if (result === false) { // output.push(-1); // return; // } else { // // console.error(result.join(' ')) // // for (const a of A) console.error('#', m, a.join(' ')) // ans.push(result); // for (const i of range(N)) { // A[i][result[i]] -= 1; // } // } // } // for (const t of ans) { // output.push(t.map(x => x + 1).join(' ')); // } // }; // // const input = new InputStdin(); // input.setup().then(_ => { // const output = []; // main(input, output); // console.log(output.join('n')); // }); // /// The code above transpiles as follows: var Mt=Object.create;var k=Object.defineProperty;var Dt=Object.getOwnPropertyDescriptor;var Ot=Object.getOwnPropertyNames;var Ct=Object.getPrototypeOf,Rt=Object.prototype.hasOwnProperty;var Lt=t=>k(t,"__esModule",{value:!0});var z=(t,e)=>()=>(e||t((e={exports:{}}).exports,e),e.exports);var Pt=(t,e,r)=>{if(e&&typeof e=="object"||typeof e=="function")for(let i of Ot(e))!Rt.call(t,i)&&i!=="default"&&k(t,i,{get:()=>e[i],enumerable:!(r=Dt(e,i))||r.enumerable});return t},S=t=>Pt(Lt(k(t!=null?Mt(Ct(t)):{},"default",t&&t.__esModule&&"default"in t?{get:()=>t.default,enumerable:!0}:{value:t,enumerable:!0})),t);var tt=z((fe,K)=>{"use strict";var $t=function(t,e){return t0&&(r=e-1>>1,i=this.array[r],!!this.compare(t,i));)this.array[e]=i,e=r;this.array[e]=t};l.prototype.heapify=function(t){this.array=t,this.size=t.length;var e;for(e=this.size>>1;e>=0;e--)this._percolateDown(e)};l.prototype._percolateUp=function(t,e){for(var r=this.array[t],i,n;t>0&&(i=t-1>>1,n=this.array[i],!(!e&&!this.compare(r,n)));)this.array[t]=n,t=i;this.array[t]=r};l.prototype._percolateDown=function(t){for(var e=this.size,r=this.size>>>1,i=this.array[t],n,o,s;tthis.size-1||t<0))return this._percolateUp(t,!0),this.poll()};l.prototype.remove=function(t){for(var e=0;e1?(this.array[0]=this.array[--this.size],this._percolateDown(0)):this.size-=1,t}};l.prototype.replaceTop=function(t){if(this.size!=0){var e=this.array[0];return this.array[0]=t,this._percolateDown(0),e}};l.prototype.trim=function(){this.array=this.array.slice(0,this.size)};l.prototype.isEmpty=function(){return this.size===0};l.prototype.forEach=function(t){if(!(this.isEmpty()||typeof t!="function"))for(var e=0,r=this.clone();!r.isEmpty();)t(r.poll(),e++)};l.prototype.kSmallest=function(t){if(this.size==0)return[];t=Math.min(this.size,t);var e=new l(this.compare);let r=Math.min((t>0?Math.pow(2,t-1):0)+1,this.size);e.size=r,e.array=this.array.slice(0,r);for(var i=new Array(t),n=0;n{"use strict";function u(t){if(this._capacity=it(t),this._length=0,this._front=0,rt(t)){for(var e=t.length,r=0;r1){var n=this._capacity;if(i+r>n){for(var s=0;s1){var s=this._capacity;if(r+i>s){for(var h=i-1;h>=0;h--){this._checkCapacity(r+1);var s=this._capacity,n=(this._front-1&s-1^s)-s;this[n]=arguments[h],r++,this._length=r,this._front=n}return r}else{for(var o=this._front,h=i-1;h>=0;h--){var n=(o-1&s-1^s)-s;this[n]=arguments[h],o=n}return this._front=o,this._length=r+i,r+i}}if(i===0)return r;this._checkCapacity(r+1);var s=this._capacity,h=(this._front-1&s-1^s)-s;return this[h]=e,this._length=r+1,this._front=h,r+1};u.prototype.peekBack=function(){var e=this._length;if(e!==0){var r=this._front+e-1&this._capacity-1;return this[r]}};u.prototype.peekFront=function(){if(this._length!==0)return this[this._front]};u.prototype.get=function(e){var r=e;if(r===(r|0)){var i=this._length;if(r<0&&(r=r+i),!(r<0||r>=i))return this[this._front+r&this._capacity-1]}};u.prototype.isEmpty=function(){return this._length===0};u.prototype.clear=function(){for(var e=this._length,r=this._front,i=this._capacity,n=0;nr){var o=i+n&r-1;Vt(this,0,this,r,o)}};var rt=Array.isArray;function Vt(t,e,r,i,n){for(var o=0;o>>0,t=t-1,t=t|t>>1,t=t|t>>2,t=t|t>>4,t=t|t>>8,t=t|t>>16,t+1}function it(t){if(typeof t!="number")if(rt(t))t=t.length;else return 16;return Yt(Math.min(Math.max(16,t),1073741824))}st.exports=u});var ut=z(f=>{"use strict";var W=32;f.INT_BITS=W;f.INT_MAX=2147483647;f.INT_MIN=-1<0)-(t<0)};f.abs=function(t){var e=t>>W-1;return(t^e)-e};f.min=function(t,e){return e^(t^e)&-(t65535)<<4,t>>>=e,r=(t>255)<<3,t>>>=r,e|=r,r=(t>15)<<2,t>>>=r,e|=r,r=(t>3)<<1,t>>>=r,e|=r,e|t>>1};f.log10=function(t){return t>=1e9?9:t>=1e8?8:t>=1e7?7:t>=1e6?6:t>=1e5?5:t>=1e4?4:t>=1e3?3:t>=100?2:t>=10?1:0};f.popCount=function(t){return t=t-(t>>>1&1431655765),t=(t&858993459)+(t>>>2&858993459),(t+(t>>>4)&252645135)*16843009>>>24};function at(t){var e=32;return t&=-t,t&&e--,t&65535&&(e-=16),t&16711935&&(e-=8),t&252645135&&(e-=4),t&858993459&&(e-=2),t&1431655765&&(e-=1),e}f.countTrailingZeros=at;f.nextPow2=function(t){return t+=t===0,--t,t|=t>>>1,t|=t>>>2,t|=t>>>4,t|=t>>>8,t|=t>>>16,t+1};f.prevPow2=function(t){return t|=t>>>1,t|=t>>>2,t|=t>>>4,t|=t>>>8,t|=t>>>16,t-(t>>>1)};f.parity=function(t){return t^=t>>>16,t^=t>>>8,t^=t>>>4,t&=15,27030>>>t&1};var B=new Array(256);(function(t){for(var e=0;e<256;++e){var r=e,i=e,n=7;for(r>>>=1;r;r>>>=1)i<<=1,i|=r&1,--n;t[e]=i<>>8&255]<<16|B[t>>>16&255]<<8|B[t>>>24&255]};f.interleave2=function(t,e){return t&=65535,t=(t|t<<8)&16711935,t=(t|t<<4)&252645135,t=(t|t<<2)&858993459,t=(t|t<<1)&1431655765,e&=65535,e=(e|e<<8)&16711935,e=(e|e<<4)&252645135,e=(e|e<<2)&858993459,e=(e|e<<1)&1431655765,t|e<<1};f.deinterleave2=function(t,e){return t=t>>>e&1431655765,t=(t|t>>>1)&858993459,t=(t|t>>>2)&252645135,t=(t|t>>>4)&16711935,t=(t|t>>>16)&65535,t<<16>>16};f.interleave3=function(t,e,r){return t&=1023,t=(t|t<<16)&4278190335,t=(t|t<<8)&251719695,t=(t|t<<4)&3272356035,t=(t|t<<2)&1227133513,e&=1023,e=(e|e<<16)&4278190335,e=(e|e<<8)&251719695,e=(e|e<<4)&3272356035,e=(e|e<<2)&1227133513,t|=e<<1,r&=1023,r=(r|r<<16)&4278190335,r=(r|r<<8)&251719695,r=(r|r<<4)&3272356035,r=(r|r<<2)&1227133513,t|r<<2};f.deinterleave3=function(t,e){return t=t>>>e&1227133513,t=(t|t>>>2)&3272356035,t=(t|t>>>4)&251719695,t=(t|t>>>8)&4278190335,t=(t|t>>>16)&1023,t<<22>>22};f.nextCombination=function(t){var e=t|t-1;return e+1|(~e&-~e)-1>>>at(t)+1}});var lt=z((Gr,ft)=>{"use strict";function ht(t,e,r){var i=t[r]|0;if(i<=0)return[];var n=new Array(i),o;if(r===t.length-1)for(o=0;o0)return Kt(t|0,e);break;case"object":if(typeof t.length=="number")return ht(t,e,0);break}return[]}ft.exports=te});var qt=z(a=>{"use strict";var I=ut(),p=lt(),ct=require("buffer").Buffer;global.__TYPEDARRAY_POOL||(global.__TYPEDARRAY_POOL={UINT8:p([32,0]),UINT16:p([32,0]),UINT32:p([32,0]),BIGUINT64:p([32,0]),INT8:p([32,0]),INT16:p([32,0]),INT32:p([32,0]),BIGINT64:p([32,0]),FLOAT:p([32,0]),DOUBLE:p([32,0]),DATA:p([32,0]),UINT8C:p([32,0]),BUFFER:p([32,0])});var ee=typeof Uint8ClampedArray!="undefined",re=typeof BigUint64Array!="undefined",ie=typeof BigInt64Array!="undefined",c=global.__TYPEDARRAY_POOL;c.UINT8C||(c.UINT8C=p([32,0]));c.BIGUINT64||(c.BIGUINT64=p([32,0]));c.BIGINT64||(c.BIGINT64=p([32,0]));c.BUFFER||(c.BUFFER=p([32,0]));var D=c.DATA,O=c.BUFFER;a.free=function(e){if(ct.isBuffer(e))O[I.log2(e.length)].push(e);else{if(Object.prototype.toString.call(e)!=="[object ArrayBuffer]"&&(e=e.buffer),!e)return;var r=e.length||e.byteLength,i=I.log2(r)|0;D[i].push(e)}};function pt(t){if(!!t){var e=t.length||t.byteLength,r=I.log2(e);D[r].push(t)}}function se(t){pt(t.buffer)}a.freeUint8=a.freeUint16=a.freeUint32=a.freeBigUint64=a.freeInt8=a.freeInt16=a.freeInt32=a.freeBigInt64=a.freeFloat32=a.freeFloat=a.freeFloat64=a.freeDouble=a.freeUint8Clamped=a.freeDataView=se;a.freeArrayBuffer=pt;a.freeBuffer=function(e){O[I.log2(e.length)].push(e)};a.malloc=function(e,r){if(r===void 0||r==="arraybuffer")return g(e);switch(r){case"uint8":return Q(e);case"uint16":return dt(e);case"uint32":return mt(e);case"int8":return gt(e);case"int16":return _t(e);case"int32":return yt(e);case"float":case"float32":return wt(e);case"double":case"float64":return bt(e);case"uint8_clamped":return It(e);case"bigint64":return Ft(e);case"biguint64":return vt(e);case"buffer":return zt(e);case"data":case"dataview":return xt(e);default:return null}return null};function g(t){var t=I.nextPow2(t),e=I.log2(t),r=D[e];return r.length>0?r.pop():new ArrayBuffer(t)}a.mallocArrayBuffer=g;function Q(t){return new Uint8Array(g(t),0,t)}a.mallocUint8=Q;function dt(t){return new Uint16Array(g(2*t),0,t)}a.mallocUint16=dt;function mt(t){return new Uint32Array(g(4*t),0,t)}a.mallocUint32=mt;function gt(t){return new Int8Array(g(t),0,t)}a.mallocInt8=gt;function _t(t){return new Int16Array(g(2*t),0,t)}a.mallocInt16=_t;function yt(t){return new Int32Array(g(4*t),0,t)}a.mallocInt32=yt;function wt(t){return new Float32Array(g(4*t),0,t)}a.mallocFloat32=a.mallocFloat=wt;function bt(t){return new Float64Array(g(8*t),0,t)}a.mallocFloat64=a.mallocDouble=bt;function It(t){return ee?new Uint8ClampedArray(g(t),0,t):Q(t)}a.mallocUint8Clamped=It;function vt(t){return re?new BigUint64Array(g(8*t),0,t):null}a.mallocBigUint64=vt;function Ft(t){return ie?new BigInt64Array(g(8*t),0,t):null}a.mallocBigInt64=Ft;function xt(t){return new DataView(g(t),0,t)}a.mallocDataView=xt;function zt(t){t=I.nextPow2(t);var e=I.log2(t),r=O[e];return r.length>0?r.pop():new ct(t)}a.mallocBuffer=zt;a.clearCache=function(){for(var e=0;e<32;++e)c.UINT8[e].length=0,c.UINT16[e].length=0,c.UINT32[e].length=0,c.INT8[e].length=0,c.INT16[e].length=0,c.INT32[e].length=0,c.FLOAT[e].length=0,c.DOUBLE[e].length=0,c.BIGUINT64[e].length=0,c.BIGINT64[e].length=0,c.UINT8C[e].length=0,D[e].length=0,O[e].length=0}});var At=z((Wr,Tt)=>{"use strict";var v=qt(),F=1<<28;Tt.exports=ne;function ne(t,e,r){for(var i=new Array(t),n=v.mallocInt32(t),o=v.mallocInt32(t),s=0;s=0&&(J=o[$]),J===o[x]+1&&N($))return n[x]=P,m[P]=x,!0}return o[x]=F,!1}for(var w=v.mallocInt32(t),E=0;;){for(var q=0,s=0;s0)for(let i=t;ie;i+=r)yield i}var b=(t,e=null,r=null)=>e===null?Jt(t):r===null?ot(t,e):ot(t,e,r);var j=t=>{let e=0;for(let r of t)e+=r;return e};var Bt=S(At());var oe=(t,e)=>{let[r,i]=t.getInts(2),n=[];for(let h=0,m=r;h{let h=r,m=0,y=[];for(let d=0,N=r;dd[1])},s=[];for(let h=0,m=i;hm+1).join(" "))},Nt=new M;Nt.setup().then(t=>{let e=[];oe(Nt,e),console.log(e.join(` `))});