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

• 問題: No.3567 Modulo Grid
• ユーザー: Kude
• 提出日時: 2026-06-06 08:24:38
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 18,901 bytes
• コンパイル時間: 3,615 ms
• コンパイル使用メモリ: 373,928 KB
• 実行使用メモリ: 12,088 KB
• 最終ジャッジ日時: 2026-06-06 08:24:46
• 合計ジャッジ時間: 7,265 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_1

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

ソースコード

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