#include #include using namespace std; using namespace atcoder; using ll = long long; using P = pair; using mint = modint998244353; #define rep(i, a, b) for(ll i = a; i < b; i++) #define rrep(i, a, b) for(ll i = a; i >= b; i--) constexpr ll inf = 4e18; struct RandomNumberGenerator { mt19937_64 mt; RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} ll operator()(ll l, ll r) { uniform_int_distribution dist(l, r); return dist(mt); } } rng; int main(void) { cin.tie(0); ios::sync_with_stdio(0); const vector dx = {1, 0, -1, 0}; const vector dy = {0, 1, 0, -1}; constexpr int m = 14; int n, t; cin >> n >> t; vector a(n), b(n), c(n), d(n); rep(i, 0, n) { cin >> a[i] >> b[i] >> c[i] >> d[i]; a[i]--; b[i]--; c[i]--; d[i]--; } vector> dist(m * m, vector(m * m, 1e9)); rep(i, 0, m * m) { rep(j, 0, m * m) { if(i == j) { dist[i][j] = 0; } else if(abs(i - j) == 1 or abs(i - j) == m) { dist[i][j] = 1000; } } } rep(k, 0, m * m) { rep(i, 0, m * m) { rep(j, 0, m * m) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } vector ty(t), x(t), y(t), z(t), w(t); int curx = -1, cury = -1; ll cnt = 0; ll money = 1e6; rep(day, 0, t) { if(day <= 23) { ty[day] = 2; money += 60ll * cnt; continue; } if(money < ll(2e6)) { ty[day] = 3; money += ll(5e4); money += 60ll * cnt; continue; } if(curx == -1 and cury == -1) { int ma = 0; int mx = -1, my = -1, mz = -1, mw = -1; rep(i, 0, m) { rep(j, 0, m) { rep(dir, 0, 4) { int nx = i, ny = j, nz = i + dx[dir], nw = j + dy[dir]; if(nz < 0 or m <= nz or nw < 0 or m <= nw) continue; vector> ndist = dist; ndist[nx * m + ny][nz * m + nw] = 223; ndist[nz * m + nw][nx * m + ny] = 223; rep(i, 0, m * m) { rep(j, 0, m * m) { ndist[i][j] = min(ndist[i][j], ndist[i][nx * m + ny] + ndist[nx * m + ny][nz * m + nw] + ndist[nz * m + nw][j]); ndist[i][j] = min(ndist[i][j], ndist[i][nz * m + nw] + ndist[nz * m + nw][nx * m + ny] + ndist[nx * m + ny][j]); } } int sum = 0; rep(i, 0, n) { int ti = ndist[a[i] * m + b[i]][c[i] * m + d[i]]; rep(j, 0, 1000) { if((ti - 233 * j) % 1000 == 0) { sum += j; break; } } } if(sum > ma) { ma = sum; mx = nx; my = ny; mz = nz; mw = nw; } } } } ty[day] = 1; x[day] = mx; y[day] = my; z[day] = mz; w[day] = mw; cnt = ma; money -= ll(2e6); money += 60ll * cnt; } else { int ma = 0; int mx = -1, my = -1, mz = -1, mw = -1; rep(dir, 0, 4) { int nx = curx, ny = cury, nz = nx + dx[dir], nw = ny + dy[dir]; if(nz < 0 or m <= nz or nw < 0 or m <= nw) continue; vector> ndist = dist; ndist[nx * m + ny][nz * m + nw] = 223; ndist[nz * m + nw][nx * m + ny] = 223; rep(i, 0, m * m) { rep(j, 0, m * m) { ndist[i][j] = min(ndist[i][j], ndist[i][nx * m + ny] + ndist[nx * m + ny][nz * m + nw] + ndist[nz * m + nw][j]); ndist[i][j] = min(ndist[i][j], ndist[i][nz * m + nw] + ndist[nz * m + nw][nx * m + ny] + ndist[nx * m + ny][j]); } } int sum = 0; rep(i, 0, n) { int ti = ndist[a[i] * m + b[i]][c[i] * m + d[i]]; rep(j, 0, 1000) { if((ti - 233 * j) % 1000 == 0) { sum += j; break; } } } if(sum > ma) { ma = sum; mx = nx; my = ny; mz = nz; mw = nw; } } if(60ll * (ma - cnt) * (t - day) >= ll(2e6)) { ty[day] = 1; x[day] = mx; y[day] = my; z[day] = mz; w[day] = mw; cnt = ma; money -= ll(2e6); money += 60ll * cnt; } else { ty[day] = 3; money += ll(5e4); money += 60ll * cnt; } } } rep(i, 0, t) { if(ty[i] == 1) { cout << ty[i] << ' ' << x[i] + 1 << ' ' << y[i] + 1 << ' ' << z[i] + 1 << ' ' << w[i] + 1 << endl; } else { cout << ty[i] << endl; } } }