#859978 (JavaScript) No.2263 Perms

• 問題: No.2263 Perms
• ユーザー: kariya1975
• 提出日時: 2023-04-15 13:14:45
• 言語: JavaScript (node v21.7.1)
• 結果: AC
• 実行時間: 186 ms / 2,000 ms
• コード長: 18,223 bytes
• コンパイル時間: 63 ms
• コンパイル使用メモリ: 6,944 KB
• 実行使用メモリ: 48,912 KB
• 最終ジャッジ日時: 2024-04-19 08:01:35
• 合計ジャッジ時間: 5,874 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	73 ms; 39,040 KB
testcase_01	AC	69 ms; 39,296 KB
testcase_02	AC	67 ms; 39,296 KB
testcase_03	AC	68 ms; 39,552 KB
testcase_04	AC	68 ms; 39,168 KB
testcase_05	AC	71 ms; 39,552 KB
testcase_06	AC	160 ms; 46,980 KB
testcase_07	AC	142 ms; 48,328 KB
testcase_08	AC	99 ms; 47,996 KB
testcase_09	AC	186 ms; 48,912 KB
testcase_10	AC	68 ms; 39,552 KB
testcase_11	AC	140 ms; 47,888 KB
testcase_12	AC	142 ms; 47,116 KB
testcase_13	AC	158 ms; 47,620 KB
testcase_14	AC	154 ms; 46,332 KB
testcase_15	AC	69 ms; 39,424 KB
testcase_16	AC	74 ms; 40,064 KB
testcase_17	AC	75 ms; 40,320 KB
testcase_18	AC	73 ms; 40,448 KB
testcase_19	AC	84 ms; 44,544 KB
testcase_20	AC	147 ms; 47,616 KB
testcase_21	AC	149 ms; 46,336 KB
testcase_22	AC	142 ms; 47,472 KB
testcase_23	AC	122 ms; 47,792 KB
testcase_24	AC	92 ms; 44,748 KB
testcase_25	AC	150 ms; 46,596 KB
testcase_26	AC	155 ms; 47,252 KB
testcase_27	AC	122 ms; 48,172 KB
testcase_28	AC	86 ms; 44,364 KB
testcase_29	AC	88 ms; 45,288 KB
testcase_30	AC	71 ms; 39,808 KB
testcase_31	AC	71 ms; 39,680 KB
testcase_32	AC	81 ms; 44,516 KB
testcase_33	AC	74 ms; 40,448 KB
testcase_34	AC	71 ms; 39,424 KB
testcase_35	AC	68 ms; 39,296 KB
testcase_36	AC	72 ms; 39,552 KB
testcase_37	AC	71 ms; 39,680 KB
testcase_38	AC	145 ms; 47,744 KB
testcase_39	AC	69 ms; 39,168 KB
testcase_40	AC	68 ms; 39,808 KB

ソースコード

/// 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 t<e};function l(t){if(!(this instanceof l))return new l(t);this.array=[],this.size=0,this.compare=t||$t}l.prototype.clone=function(){var t=new l(this.compare);return t.size=this.size,t.array=this.array.slice(0,this.size),t};l.prototype.add=function(t){var e=this.size;this.array[this.size]=t,this.size+=1;for(var r,i;e>0&&(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;t<r&&(n=(t<<1)+1,o=n+1,s=this.array[n],o<e&&this.compare(this.array[o],s)&&(n=o,s=this.array[o]),!!this.compare(s,i));)this.array[t]=s,t=n;this.array[t]=i};l.prototype._removeAt=function(t){if(!(t>this.size-1||t<0))return this._percolateUp(t,!0),this.poll()};l.prototype.remove=function(t){for(var e=0;e<this.size;e++)if(!this.compare(this.array[e],t)&&!this.compare(t,this.array[e]))return this._removeAt(e),!0;return!1};l.prototype.removeOne=function(t){if(typeof t=="function"){for(var e=0;e<this.size;e++)if(t(this.array[e]))return this._removeAt(e)}};l.prototype.removeMany=function(t,e){if(typeof t!="function"||this.size<1)return[];e=e?Math.min(e,this.size):this.size;for(var r=0,i=new Array(e),n=0,o=new Array(this.size);r<e&&!this.isEmpty();){var s=this.poll();t(s)?i[r++]=s:o[n++]=s}i.length=r;for(var h=0;h<n;)this.add(o[h++]);return i};l.prototype.peek=function(){if(this.size!=0)return this.array[0]};l.prototype.poll=function(){if(this.size!=0){var t=this.array[0];return this.size>1?(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<t;n++)i[n]=e.poll();return i};K.exports=l});var nt=z((ze,st)=>{"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;r<e;++r)this[r]=t[r];this._length=e}}u.prototype.toArray=function(){for(var e=this._length,r=new Array(e),i=this._front,n=this._capacity,o=0;o<e;++o)r[o]=this[i+o&n-1];return r};u.prototype.push=function(e){var r=arguments.length,i=this._length;if(r>1){var n=this._capacity;if(i+r>n){for(var s=0;s<r;++s){this._checkCapacity(i+1);var o=this._front+i&this._capacity-1;this[o]=arguments[s],i++,this._length=i}return i}else{for(var o=this._front,s=0;s<r;++s)this[o+i&n-1]=arguments[s],o++;return this._length=i+r,i+r}}if(r===0)return i;this._checkCapacity(i+1);var s=this._front+i&this._capacity-1;return this[s]=e,this._length=i+1,i+1};u.prototype.pop=function(){var e=this._length;if(e!==0){var r=this._front+e-1&this._capacity-1,i=this[r];return this[r]=void 0,this._length=e-1,i}};u.prototype.shift=function(){var e=this._length;if(e!==0){var r=this._front,i=this[r];return this[r]=void 0,this._front=r+1&this._capacity-1,this._length=e-1,i}};u.prototype.unshift=function(e){var r=this._length,i=arguments.length;if(i>1){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;n<e;++n)this[r+n&i-1]=void 0;this._length=0,this._front=0};u.prototype.toString=function(){return this.toArray().toString()};u.prototype.valueOf=u.prototype.toString;u.prototype.removeFront=u.prototype.shift;u.prototype.removeBack=u.prototype.pop;u.prototype.insertFront=u.prototype.unshift;u.prototype.insertBack=u.prototype.push;u.prototype.enqueue=u.prototype.push;u.prototype.dequeue=u.prototype.shift;u.prototype.toJSON=u.prototype.toArray;Object.defineProperty(u.prototype,"length",{get:function(){return this._length},set:function(){throw new RangeError("")}});u.prototype._checkCapacity=function(e){this._capacity<e&&this._resizeTo(it(this._capacity*1.5+16))};u.prototype._resizeTo=function(e){var r=this._capacity;this._capacity=e;var i=this._front,n=this._length;if(i+n>r){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<n;++o)r[o+i]=t[o+e],t[o+e]=void 0}function Yt(t){return t=t>>>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<<W-1;f.sign=function(t){return(t>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)&-(t<e)};f.max=function(t,e){return t^(t^e)&-(t<e)};f.isPow2=function(t){return!(t&t-1)&&!!t};f.log2=function(t){var e,r;return e=(t>65535)<<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<<n&255}})(B);f.reverse=function(t){return B[t&255]<<24|B[t>>>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;o<i;++o)n[o]=e;else for(o=0;o<i;++o)n[o]=ht(t,e,r+1);return n}function Kt(t,e){var r,i;for(r=new Array(t),i=0;i<t;++i)r[i]=e;return r}function te(t,e){switch(typeof e=="undefined"&&(e=0),typeof t){case"number":if(t>0)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<t;++s)n[s]=-1,i[s]=[],o[s]=F;for(var h=new Array(e),m=v.mallocInt32(e),s=0;s<e;++s)m[s]=-1,h[s]=[];for(var y=r.length,s=0;s<y;++s){var _=r[s];i[_[0]].push(_[1]),h[_[1]].push(_[0])}var d=F;function N(x){if(x<0)return!0;for(var Z=i[x],L=0,St=Z.length;L<St;++L){var P=Z[L],$=m[P],J=d;if($>=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;s<t;++s)n[s]<0?(o[s]=0,w[q++]=s):o[s]=F;var V=0;for(d=F;V<q;){var Y=w[V++],C=o[Y];if(C<d)for(var X=i[Y],R=0,Et=X.length;R<Et;++R){var Ut=X[R],U=m[Ut];U<0?d===F&&(d=C+1):o[U]===F&&(o[U]=C+1,w[q++]=U)}}if(d===F)break;for(var s=0;s<t;++s)n[s]<0&&N(s)&&(E+=1)}for(var q=0,H=new Array(E),s=0;s<t;++s)n[s]<0||(H[q++]=[s,n[s]]);return v.free(w),v.free(m),v.free(o),v.free(n),H}});var T=S(require("fs"));var G=class{constructor(e){this.data=e!=null?e:"",this.index=0}isSpace(e){return e===" "||e===`
`}getString(){for(;this.index<this.data.length&&this.isSpace(this.data[this.index]);)this.index++;let e=this.index;for(;this.index<this.data.length&&!this.isSpace(this.data[this.index]);)this.index++;let r=this.index;return this.data.slice(e,r)}getBigInt(){return BigInt(this.getString())}getInt(){return parseInt(this.getString())}getNumber(){return Number(this.getString())}getNumbers(e){let r=[];for(let i of b(e))r.push(this.getNumber());return r}getBigInts(e){let r=[];for(let i of b(e))r.push(this.getBigInt());return r}getInts(e){let r=[];for(let i of b(e))r.push(this.getInt());return r}getStrings(e){let r=[];for(let i of b(e))r.push(this.getString());return r}get(e){if(typeof e=="number")return this.getNumber();if(typeof e=="bigint")return this.getBigInt();if(typeof e=="string")return this.getString()}gets(e,r){if(typeof e=="number")return this.getNumbers(r);if(typeof e=="bigint")return this.getBigInts(r);if(typeof e=="string")return this.getStrings(r)}},M=class extends G{constructor(){super();(0,T.existsSync)("/dev/stdin")&&(super.data=(0,T.readFileSync)("/dev/stdin","utf-8"))}async setup(){if((0,T.existsSync)("/dev/stdin"))return;let e=[];for await(let n of process.stdin)e.push(n);let i=Buffer.concat(e).toString();super.data=i}};var kt=S(tt());var Xt=S(nt());function*Jt(t){for(let e=0;e<t;++e)yield e}function*ot(t,e,r=1){if(r>0)for(let i=t;i<e;i+=r)yield i;else if(r<0)for(let i=t;i>e;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<m;++h){let y=t.getInts(r);if(j(y)!==i){e.push(-1);return}n.push(y)}let o=()=>{let h=r,m=0,y=[];for(let d=0,N=r;d<N;++d)for(let w=0,E=r;w<E;++w)n[d][w]!==0&&(y.push([d,w]),m+=1);let _=(0,Bt.default)(h,m,y);return _.length!==r?!1:_.map(d=>d[1])},s=[];for(let h=0,m=i;h<m;++h){let y=o();if(y===!1){e.push(-1);return}else{s.push(y);for(let _=0,d=r;_<d;++_)n[_][y[_]]-=1}}for(let h of s)e.push(h.map(m=>m+1).join(" "))},Nt=new M;Nt.setup().then(t=>{let e=[];oe(Nt,e),console.log(e.join(`
`))});