#include "atcoder/scc.hpp" #include #include using namespace std; using i32 = int; using i64 = long long; using i128 = __int128_t; using p2 = pair; using el = tuple; using f64 = long double; using mint = atcoder::modint998244353; void _main(); int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(18); _main(); } i64 pow(i64 a, i64 n) { i64 res = 1; i64 x = a; while (n > 0) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } p2 op(p2 a, p2 b) {return min(a, b);} p2 e() {return {1e18, 1e18};} p2 mpn(i64 f, p2 x) {return x.second == -1 ? x : (p2){min(f, x.first), x.second};} i64 cmp(i64 f, i64 g) {return min(f, g);} i64 idn() {return 1e18;} p2 opx(p2 a, p2 b) {return max(a, b);} p2 ex() {return {0, -1};} bool dfs(i64 v, vector> &g, atcoder::segtree &seg0, atcoder::segtree &seg1) { seg0.set(v, {0, v}); for (auto [l, r, c] : g[v]) { if (c != 0) continue; while (seg1.prod(l, r).first == 1) { auto [_, nv] = seg1.prod(l, r); if (seg0.get(nv).first == 0) return true; bool res = dfs(nv, g, seg0, seg1); if (res) return true; } } seg1.set(v, {0, v}); return false; } void _main() { i64 n, m; cin >> n >> m; vector> edge(m); vector> g(n); for (i64 i = 0; i < m; i++) { i64 x, l, r, c; cin >> x >> l >> r >> c; x--; l--; edge[i] = {x, l, r, c}; g[x].push_back({l, r, c}); } vector dist(n, 1e18); { atcoder::lazy_segtree seg(n); for (i64 i = 0; i < n; i++) seg.set(i, {1e18, i}); seg.set(0, {0, 0}); while (seg.all_prod().first != 1e18) { auto [d, i] = seg.all_prod(); seg.set(i, {1e18, -1}); dist[i] = d; for (auto [l, r, c] : g[i]) { seg.apply(l, r, d + c); } } } for (i64 i = 0; i < n; i++) { if (dist[i] == 1e18) continue; for (auto [l, r, c] : g[i]) { if (c == 0 && l <= i && i < r) { cout << "Too Many\n"; return; } } } { atcoder::segtree seg0(n), seg1(n); for (i64 i = 0; i < n; i++) { seg0.set(i, {1, i}); seg1.set(i, {1, i}); } bool f = dfs(0, g, seg0, seg1); if (f) { cout << "Too Many\n"; return; } } return; vector ord(n); for (i64 i = 0; i < n; i++) { ord[i] = i; } sort(ord.begin(), ord.end(), [&](i64 a, i64 b){ if (dist[a] < dist[b]) return a; if (dist[b] < dist[a]) return b; for (auto [l, r, x] : g[a]) { if (x == 0 && l <= b && b < r) return a; } return b; }); for (i64 i = 0; i < n; i++) { if (dist[i] == 1e18) continue; } }