#1168448 (C++23) No.3567 Modulo Grid

• 問題: No.3567 Modulo Grid
• ユーザー: Kude
• 提出日時: 2026-06-06 07:55:21
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 19,003 bytes
• コンパイル時間: 4,124 ms
• コンパイル使用メモリ: 379,496 KB
• 実行使用メモリ: 12,220 KB
• 最終ジャッジ日時: 2026-06-06 07:55:30
• 合計ジャッジ時間: 9,508 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 1 WA * 1
other	AC * 15 WA * 10

ソースコード

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

template<class T>
vector<pair<T, int>> factorize(T x) {
  vector<pair<T, int>> res;
  for(T p = 2; p * p <= x; p++) {
    int cnt = 0;
    while(x % p == 0) x /= p, cnt++;
    if (cnt) res.emplace_back(p, cnt);
  }
  if (x > 1) res.emplace_back(x, 1);
  return res;
}

VVI memo[33][33];

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  memo[3][4]={{1,2,3,7},{12,10,9,11},{6,5,4,8}};
  memo[3][8]={{1,7,3,13,16,12,15,23},{5,8,2,24,17,20,21,22},{6,11,10,9,4,19,14,18}};
  memo[4][4]={{1,5,9,13},{2,6,10,14},{3,7,11,15},{4,8,12,16}};
  memo[4][6]={{8,4,5,10,24,22},{3,16,7,11,19,15},{2,1,6,13,14,21},{9,20,12,17,18,23}};
  memo[5][6]={{6,15,30,8,23,20},{12,5,2,21,24,27},{3,10,11,13,14,22},{1,25,4,17,16,26},{9,7,18,19,29,28}};
  memo[6][6]={{1,8,14,18,23,6},{3,16,9,26,28,29},{15,7,11,33,24,30},{4,2,13,36,25,31},{5,10,17,20,27,35},{12,21,22,19,32,34}};
  memo[6][8]={{3,9,18,25,4,26,41,12},{8,15,10,14,31,37,32,38},{1,21,13,30,20,33,24,45},{48,7,17,40,35,28,34,46},{5,2,19,22,27,44,43,36},{6,11,23,29,42,16,39,47}};
  memo[6][10]={{3,4,14,26,17,15,20,52,58,56},{12,18,16,11,19,32,31,43,36,51},{10,8,42,13,33,29,37,47,45,57},{1,9,28,5,24,44,34,38,49,60},{6,2,22,54,25,50,41,39,40,53},{7,21,30,27,23,35,55,46,48,59}};
  memo[8][8]={{1,9,17,25,33,41,49,57},{2,10,18,26,34,42,50,58},{3,11,19,27,35,43,51,59},{4,12,20,28,36,44,52,60},{5,13,21,29,37,45,53,61},{6,14,22,30,38,46,54,62},{7,15,23,31,39,47,55,63},{8,16,24,32,40,48,56,64}};
  memo[8][9]={{3,24,13,9,41,32,61,46,45},{6,10,28,16,33,60,72,52,62},{30,20,8,36,26,40,38,66,70},{18,15,17,29,34,53,48,56,63},{1,12,19,31,43,55,65,68,54},{5,7,23,35,47,39,44,64,51},{2,11,25,21,42,27,67,50,57},{4,14,22,37,49,59,71,58,69}};
  memo[8][12]={{1,20,10,23,42,34,58,51,57,56,71,88},{4,12,13,14,52,38,37,47,63,81,64,85},{6,48,17,25,31,39,45,49,69,87,73,86},{5,30,19,29,54,46,41,53,55,59,77,89},{7,28,44,22,68,50,8,80,32,61,93,91},{18,3,16,24,76,78,43,92,75,74,79,96},{2,9,21,72,66,36,40,84,62,65,83,95},{11,15,27,33,26,35,60,90,70,67,82,94}};
  memo[9][10]={{1,13,21,28,31,51,56,67,71,78},{18,10,19,27,40,38,58,74,73,81},{7,54,16,33,37,44,80,48,75,84},{11,4,5,12,50,63,59,15,82,87},{3,20,22,29,41,47,62,57,30,60},{2,17,25,32,24,49,61,69,66,88},{9,8,26,34,42,46,64,65,86,83},{6,72,23,45,43,52,55,76,77,89},{36,14,35,39,70,53,68,90,79,85}};
  memo[9][16]={{4,10,19,31,44,38,144,108,58,69,132,105,107,129,120,141},{1,48,8,28,15,21,59,50,51,72,52,101,111,128,121,134},{9,17,20,22,26,64,61,112,79,75,70,74,109,106,116,133},{5,3,30,12,41,49,46,71,62,56,91,92,94,114,125,137},{7,16,23,35,43,54,65,117,78,88,68,90,113,126,122,142},{2,32,27,37,63,53,96,73,83,89,102,82,123,138,127,140},{11,6,25,45,34,33,40,39,135,104,76,86,115,110,124,139},{13,14,42,60,47,80,99,84,57,87,95,100,24,118,131,143},{18,36,29,66,81,55,67,77,85,93,97,103,98,119,130,136}};
  memo[10][12]={{3,8,50,51,28,44,69,24,78,83,103,114},{9,21,4,34,57,62,52,88,71,89,108,100},{6,40,13,16,31,41,49,82,20,98,115,116},{5,14,26,38,120,63,64,86,73,91,93,107},{1,27,25,23,58,15,53,104,77,76,110,109},{18,10,35,29,70,43,45,94,87,97,48,113},{2,33,17,60,55,32,74,59,95,102,72,117},{42,54,12,36,37,47,75,84,105,92,99,119},{7,30,39,46,65,56,81,61,68,101,112,118},{11,22,19,90,80,85,66,67,79,106,111,96}};
  memo[12][12]={{2,19,15,8,56,99,79,75,36,111,121,133},{1,22,35,42,49,65,83,98,68,100,124,64},{3,6,30,81,53,51,85,87,90,116,114,80},{5,23,37,4,58,62,82,97,107,120,123,138},{7,48,41,18,55,44,89,60,76,118,125,141},{10,25,43,50,28,67,91,101,84,32,129,112},{11,29,34,47,54,71,57,103,72,126,130,137},{9,24,38,20,33,73,95,106,136,132,134,135},{13,144,12,40,59,70,69,93,109,115,117,139},{14,45,46,66,88,77,102,104,92,119,140,143},{27,26,63,16,39,96,86,52,113,122,127,128},{17,31,21,78,61,74,94,110,105,108,131,142}};
  memo[12][16]={{1,13,12,64,51,72,77,87,56,98,130,124,166,153,184,128},{6,17,36,37,62,59,79,68,112,99,121,131,176,104,160,162},{5,15,60,33,49,61,83,97,86,106,125,133,170,155,165,181},{7,19,38,108,70,65,75,101,92,90,134,137,143,138,171,174},{3,22,29,50,28,69,132,103,144,110,180,139,145,150,163,186},{11,23,27,30,8,67,85,107,88,105,142,129,32,159,167,172},{48,21,46,58,42,71,89,76,115,111,146,126,178,157,177,185},{9,25,24,39,53,96,81,82,93,117,102,154,148,136,169,187},{18,16,31,41,54,44,80,66,119,123,127,135,149,182,173,183},{2,26,35,45,57,120,91,109,192,118,114,158,164,161,175,191},{10,4,20,43,55,74,52,113,94,156,100,141,151,152,190,189},{14,34,84,47,63,73,95,40,78,122,116,140,147,168,179,188}};
  memo[12][20]={{15,13,85,50,44,88,78,112,89,155,138,117,139,171,135,96,187,211,196,233},{1,3,23,31,46,115,75,69,94,175,72,162,143,177,189,176,215,217,231,180},{7,42,9,37,47,62,92,79,91,107,124,123,200,170,201,179,165,208,214,216},{5,2,10,34,49,76,73,82,97,93,131,129,149,105,161,181,182,219,212,160},{11,8,56,64,52,125,77,83,114,109,133,240,151,220,163,188,191,194,156,228},{6,16,22,90,68,150,145,81,87,113,108,148,147,164,167,166,132,202,224,237},{18,17,28,41,58,36,57,86,101,119,40,205,153,186,198,144,193,235,80,239},{4,55,21,12,53,74,24,104,116,98,106,141,136,152,146,207,197,222,204,236},{25,54,95,27,39,51,63,20,103,60,111,48,157,183,169,190,195,232,227,226},{35,14,26,38,59,210,120,100,126,99,185,122,130,184,173,178,199,221,229,225},{45,65,29,33,61,71,102,84,128,121,137,134,159,168,154,192,203,206,218,238},{30,19,32,43,67,66,70,140,110,127,118,174,142,172,158,213,209,223,234,230}};
  memo[15][16]={{3,17,38,42,65,77,52,66,76,80,150,181,189,135,219,200},{2,12,32,48,30,86,136,118,127,60,161,187,203,120,202,212},{1,19,46,53,58,79,132,122,114,96,174,230,198,165,140,220},{4,22,35,59,62,99,97,109,141,139,154,160,209,213,184,176},{7,23,33,51,108,104,90,78,147,143,158,191,152,234,223,235},{11,29,39,61,74,83,101,117,131,146,163,183,222,124,231,232},{13,31,28,88,70,94,40,123,142,138,167,175,75,192,227,239},{15,16,72,57,69,44,111,113,170,149,186,228,105,216,229,218},{14,24,64,84,82,95,45,134,153,92,204,240,211,128,195,208},{6,10,36,67,81,115,68,145,112,144,169,193,217,148,188,226},{8,26,37,71,85,98,106,156,190,151,166,210,182,185,206,225},{5,27,41,50,110,168,103,119,133,155,177,178,194,164,233,236},{9,34,43,73,54,125,130,129,137,171,173,100,201,205,196,224},{21,56,47,55,87,89,107,121,126,157,179,197,116,172,215,237},{25,18,49,63,93,91,20,102,159,162,180,199,207,221,214,238}};
  memo[16][18]={{8,28,56,88,55,57,85,101,208,159,139,157,175,191,250,268,273,253},{1,13,25,41,66,67,12,111,122,216,196,161,179,218,249,227,241,257},{2,30,29,104,80,70,74,103,150,125,143,48,181,226,203,204,245,259},{10,9,45,62,59,160,164,90,130,127,153,186,185,231,205,234,240,279},{4,44,38,52,78,71,89,107,123,131,145,182,194,246,108,255,264,263},{96,16,31,68,54,73,135,94,126,133,212,195,202,162,200,248,266,265},{14,3,35,76,102,114,91,109,129,165,149,190,222,193,224,254,228,272},{22,27,33,43,51,148,95,98,134,174,151,210,187,197,261,229,247,269},{6,15,128,24,61,77,82,113,172,120,166,171,206,230,180,262,280,271},{5,72,46,47,99,112,86,106,142,177,170,201,168,260,209,256,285,286},{26,17,63,49,65,79,87,110,84,144,178,189,244,238,232,267,252,275},{7,64,50,92,288,83,192,152,121,184,156,163,213,199,211,270,258,277},{20,34,58,18,116,117,97,176,141,188,220,167,214,198,215,233,282,281},{32,19,42,100,124,69,60,115,146,137,236,169,36,237,217,235,251,276},{40,21,37,53,136,138,93,118,147,132,183,207,219,242,221,284,274,283},{11,23,81,39,140,75,105,119,154,158,155,173,225,243,223,239,278,287}};
  memo[18][20]={{5,3,29,41,59,50,138,147,148,167,187,154,171,192,256,277,287,276,290,343},{1,21,10,38,61,97,129,124,186,75,175,246,223,244,189,281,282,270,334,347},{6,14,78,43,74,252,86,106,164,222,191,225,227,204,214,238,312,294,319,354},{2,22,63,92,67,30,109,240,151,201,99,237,212,273,272,228,327,299,323,346},{4,13,39,108,71,101,104,128,115,190,193,205,229,178,259,234,289,344,297,349},{7,17,51,140,160,84,130,131,122,169,117,158,233,232,255,285,266,279,329,351},{9,19,68,116,73,70,141,133,157,145,184,249,267,195,263,309,243,301,308,345},{42,8,56,47,77,220,94,159,172,173,185,208,235,253,218,304,280,298,331,358},{18,20,57,72,79,103,113,48,177,196,197,210,239,268,284,283,336,307,316,353},{27,54,100,49,15,107,174,136,183,142,105,215,241,248,303,207,261,311,332,350},{36,35,26,93,123,65,119,118,176,213,199,166,236,250,226,242,274,302,337,359},{11,16,102,46,64,120,121,95,188,179,231,198,247,182,144,254,216,314,338,348},{25,33,31,81,88,24,98,137,132,146,203,217,251,291,269,321,278,313,357,342},{40,23,69,111,83,60,127,152,161,219,209,258,180,194,275,264,328,322,310,352},{80,52,37,55,89,82,112,139,90,135,96,153,224,202,292,262,293,306,333,288},{28,126,87,53,114,150,85,143,134,155,211,156,300,330,296,295,339,326,315,320},{12,66,76,58,45,162,360,149,163,230,260,221,245,206,271,340,286,317,318,355},{44,32,34,62,91,110,170,324,125,181,165,168,265,257,200,305,325,335,341,356}};
  memo[20][24]={{6,36,37,104,67,98,97,164,139,161,215,224,261,278,288,302,357,363,345,383,260,434,451,440},{4,9,68,65,78,106,129,126,143,250,242,266,276,195,456,289,319,369,366,398,395,433,446,467},{1,19,56,54,87,156,146,113,202,196,179,274,265,295,255,314,296,381,367,389,340,423,432,458},{28,5,27,57,130,102,154,153,175,163,181,120,267,286,263,324,270,300,374,391,468,304,420,471},{2,160,88,24,71,114,101,136,177,167,219,248,211,233,305,293,140,349,344,393,404,435,450,472},{14,25,33,92,73,79,103,182,206,400,198,245,217,239,342,285,323,308,382,399,412,390,453,466},{7,23,58,63,82,118,216,119,184,185,232,246,275,241,244,327,329,358,350,372,409,437,370,469},{30,21,41,96,93,122,95,121,138,201,231,312,180,236,208,284,331,352,356,397,415,376,462,473},{3,34,39,59,72,83,141,145,162,169,105,197,165,225,210,333,337,362,371,406,413,439,410,445},{32,84,51,74,86,168,107,190,172,226,222,40,256,247,303,315,325,272,373,414,419,426,457,476},{80,48,62,132,99,90,115,194,214,207,254,228,221,251,269,299,326,348,378,401,417,429,474,448},{22,29,42,61,111,144,147,159,149,150,212,243,273,176,309,301,341,354,375,396,421,380,424,360},{11,35,55,50,94,170,158,127,218,173,234,258,282,298,268,339,220,316,386,364,418,460,452,477},{13,31,43,69,116,89,166,131,183,290,187,199,192,291,384,322,343,332,377,411,425,392,459,455},{44,10,64,70,124,20,128,155,151,238,237,203,223,253,271,307,330,240,335,444,427,442,430,470},{26,38,47,66,85,134,125,133,189,186,235,209,294,306,277,311,292,353,402,388,428,441,368,465},{12,52,49,45,60,142,336,137,188,264,191,249,227,318,321,313,334,359,394,403,431,443,461,478},{17,16,53,320,148,123,178,152,230,213,135,252,280,257,281,317,338,328,379,407,422,447,454,475},{8,15,76,110,117,91,109,171,157,100,262,200,229,297,283,310,347,387,355,385,436,438,480,479},{18,46,108,81,77,204,75,112,174,205,193,408,279,259,287,351,346,361,365,405,416,449,463,464}};
  memo[24][24]={{1,12,51,91,107,48,32,114,211,241,324,231,319,341,309,383,386,439,352,485,506,507,541,510},{64,21,50,87,123,122,16,191,80,186,265,246,248,343,350,468,495,414,464,478,444,476,438,553},{5,18,58,56,109,124,167,96,172,320,183,293,228,396,365,385,415,443,404,420,492,517,486,534},{9,35,90,93,113,24,72,193,204,230,269,295,280,387,367,389,304,360,393,482,513,521,496,568},{7,37,45,86,115,133,146,197,188,245,112,258,244,284,441,294,419,410,463,487,460,519,544,546},{11,30,62,81,52,130,140,126,215,247,264,299,323,347,308,364,421,445,354,491,465,523,462,556},{2,41,66,94,119,137,154,147,217,251,195,237,314,334,316,374,425,375,454,552,336,525,522,573},{13,43,67,95,68,132,180,148,196,184,201,192,260,349,332,391,427,449,467,366,450,527,561,557},{10,47,71,99,121,189,120,194,297,165,271,301,276,273,371,395,394,418,458,493,471,520,474,564},{3,54,73,117,153,134,158,159,221,253,275,305,322,296,340,327,160,422,469,497,514,426,550,570},{15,27,70,60,76,139,169,243,152,238,236,274,176,282,358,397,357,430,412,390,488,528,554,559},{17,49,128,88,125,102,225,256,223,242,262,232,351,338,408,306,380,434,399,435,518,529,512,540},{6,53,77,36,92,141,166,261,174,220,277,234,249,285,459,401,363,381,473,490,516,484,545,563},{19,33,57,98,106,142,136,216,227,257,333,278,326,292,373,403,398,424,475,402,505,537,562,480},{23,55,79,105,127,207,173,199,206,162,198,286,325,405,356,382,431,240,456,494,509,500,536,566},{14,42,83,111,110,143,170,203,229,259,222,290,268,353,362,407,376,442,466,499,526,542,547,567},{4,34,85,97,84,145,178,205,214,200,213,307,329,291,270,409,406,451,479,448,511,543,551,384},{22,59,74,28,129,149,175,164,218,210,144,311,369,346,370,342,378,388,411,447,530,533,498,574},{25,40,63,101,100,151,182,138,233,250,281,312,255,355,348,413,330,455,440,503,483,416,560,565},{26,61,69,135,131,155,179,252,168,263,283,313,267,423,477,208,392,224,428,453,489,432,558,569},{29,38,82,103,576,157,190,279,235,177,219,298,331,359,321,339,368,446,481,436,515,535,524,571},{8,39,78,44,116,161,181,202,212,288,287,302,335,361,344,318,372,457,417,502,501,539,532,575},{20,65,89,108,171,156,185,209,239,315,289,317,337,303,377,272,433,400,470,452,538,508,549,572},{31,46,75,104,118,163,187,150,226,254,266,310,300,328,379,345,437,461,429,472,531,555,548,504}};
  memo[30][32]={{2,31,52,153,24,207,249,169,209,185,456,301,337,397,335,394,484,499,549,553,816,619,685,715,730,774,812,791,850,876,874,939},{1,38,45,126,118,131,143,173,258,342,351,307,341,401,427,546,615,490,654,542,628,598,668,673,707,727,830,793,806,863,878,931},{6,39,82,71,130,133,216,225,218,296,328,311,462,388,431,512,434,618,530,515,587,602,632,716,770,810,480,843,846,858,886,955},{7,51,78,73,800,220,186,182,268,204,262,298,416,358,429,372,479,704,529,608,589,614,669,677,694,796,763,804,784,869,950,956},{18,57,20,77,112,184,165,194,156,228,266,235,464,295,355,398,442,501,666,557,593,622,645,682,690,731,822,849,839,871,905,948},{3,63,117,70,103,208,261,246,320,284,308,426,343,403,433,555,481,466,482,559,574,633,662,679,672,733,805,797,879,884,906,944},{11,28,49,110,177,232,212,255,211,333,316,438,347,370,348,452,384,507,533,573,578,510,710,699,750,755,754,782,825,892,898,934},{9,46,68,76,183,145,149,202,304,339,274,180,349,465,362,447,420,445,494,579,590,626,588,700,753,737,767,834,845,890,916,937},{14,37,102,90,72,142,270,279,282,528,357,369,353,486,374,472,446,513,539,572,591,516,649,740,759,718,769,799,814,882,960,918},{13,58,50,12,107,128,158,179,217,251,277,302,359,305,365,451,459,508,561,563,912,625,832,711,768,739,732,794,818,924,921,941},{5,224,85,159,168,144,267,181,221,253,344,314,364,407,382,457,471,524,541,535,595,623,681,636,698,801,819,870,841,560,640,938},{22,62,123,36,122,213,151,206,226,408,504,313,387,409,392,453,477,642,502,569,644,639,620,683,708,722,776,760,856,877,925,942},{26,69,95,138,134,137,157,291,294,285,281,350,544,399,437,461,415,503,678,96,597,634,653,717,772,734,758,824,826,881,940,943},{25,56,53,84,75,164,166,297,223,257,283,322,361,460,300,463,487,478,506,571,603,638,674,724,738,742,836,860,891,883,902,951},{21,16,59,171,108,219,161,244,175,259,250,368,496,411,600,467,540,509,514,545,599,629,659,689,725,786,792,803,847,887,935,885},{17,65,129,104,152,248,163,187,227,354,380,317,435,280,522,580,483,519,576,554,610,652,695,684,705,743,773,809,828,848,911,957},{19,81,88,79,210,231,336,170,306,254,290,319,367,325,525,476,396,531,475,577,609,635,661,723,709,712,820,795,838,889,913,880},{34,87,115,83,189,146,198,352,238,256,414,345,371,417,386,585,491,568,485,714,520,655,675,630,771,735,766,811,842,893,917,946},{10,30,141,89,360,162,222,191,200,263,363,375,265,495,439,656,444,511,556,581,601,646,687,748,777,775,779,817,851,909,914,915},{35,41,192,92,109,132,330,193,318,205,278,381,373,624,424,406,493,532,518,565,621,631,664,729,745,798,781,821,854,899,932,954},{27,93,61,100,176,237,234,303,229,366,215,323,393,592,412,385,488,517,400,583,607,651,288,741,713,807,844,861,868,901,855,904},{55,43,48,91,105,139,264,214,390,252,287,329,474,500,448,558,497,548,567,616,650,657,570,680,706,785,780,900,853,910,927,958},{240,44,67,150,124,135,167,197,321,276,289,245,377,498,534,688,425,537,526,660,611,637,667,691,788,749,778,823,865,862,919,947},{15,99,160,116,148,172,312,199,233,378,450,405,379,413,430,752,536,521,468,575,627,665,676,697,719,751,756,867,872,920,923,888},{4,42,86,136,140,188,178,60,327,269,286,332,383,324,440,418,454,584,538,550,726,663,692,701,783,746,765,827,857,894,922,936},{8,111,64,106,201,155,195,309,239,190,310,326,389,419,443,470,582,543,547,596,586,641,744,747,896,790,815,829,852,908,864,949},{32,74,114,125,113,243,236,260,242,271,552,356,391,421,449,395,458,648,702,696,613,643,736,703,789,813,808,835,897,907,926,953},{23,54,94,120,119,174,432,272,340,230,315,334,338,410,428,422,489,523,492,562,605,564,671,686,762,728,787,873,859,875,929,959},{29,47,98,97,121,196,273,80,241,402,293,376,346,404,441,469,594,455,505,566,617,647,612,928,720,757,831,833,903,895,933,952},{33,66,147,101,127,154,40,203,247,292,299,331,275,423,436,473,606,527,551,604,670,658,693,764,721,761,837,802,930,866,840,945}};int h, w;
  cin >> h >> w;
  bool flip = h > w;
  if (flip) swap(h, w);
  VVI g(h, VI(w));
  if (h < 33 && w < 33 && !memo[h][w].empty()) g = memo[h][w];
  else {
    int m = h * w;
    VVI vals(m + 1);
    rrep(v, m) vals[gcd(m, v + 1)].emplace_back(v + 1);
    vector<P> pos(m);
    rep(i, h) rep(j, w) pos[i*w+j] = {i, j};
    ranges::sort(pos, greater{}, [](P p) {
      auto [i, j] = p;
      return tuple((i+j)&1, i+j, i);
    });
    auto ps = factorize(m);
    int sz = ps.size();
    VI path;
    auto dfs = [&](auto&& self, int i, int val) -> void {
      path.emplace_back(val);
      bool first = true;
      int ptr = ssize(path) - 1;
      for (; i < sz; i++) {
        auto [p, e] = ps[i];
        int v = val;
        rep(_, e) {
          if (!first) {
            int todo = h;
            while (todo) {
              assert(ptr >= 0);
              int val = path[ptr];
              if (vals[val].empty()) {
                ptr--;
                continue;
              }
              auto [i, j] = pos.back(); pos.pop_back();
              g[i][j] = vals[val].back();
              vals[val].pop_back();
              todo--;
            }
          } else {
            first = false;
          }
          v *= p;
          self(self, i + 1, v);
        }
      }
      while (vals[val].size()) {
        auto [i, j] = pos.back(); pos.pop_back();
        g[i][j] = vals[val].back();
        vals[val].pop_back();
      }
      path.pop_back();
    };
    dfs(dfs, 0, 1);
  }
  if (!flip) rep(i, h) rep(j, w) cout << g[i][j] << " \n"[j + 1 == w];
  else rep(j, w) rep(i, h) cout << g[i][j] << " \n"[i + 1 == h];
}