#include #include 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) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template void chmax(T& a, const T& b) {a = max(a, b);} template void chmin(T& a, const T& b) {a = min(a, b);} using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; constexpr int SQ = 500; using TR = tuple; TR get_triangle() { int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f; int l = min({a, c, e}); int r = max({a, c, e}) + 1; ll dx1 = c - a, dy1 = d - b; ll dx2 = e - a, dy2 = f - b; ll s = abs(dx1 * dy2 - dx2 * dy1); return {l, r, s}; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector triangles; rep(_, n) { auto t = get_triangle(); triangles.push_back(t); } auto mycmp = [&](const TR& x, const TR& y) { return get<1>(x) < get<1>(y); }; sort(all(triangles), mycmp); VL ans(q, -1); vector is_ask_query(q); for(int b = 0; b < q; b += SQ) { int nb = min(b + SQ, q); vector new_triangles; vector> ask_queries; for(int i = b; i < nb; i++) { int type; cin >> type; if (type == 1) { auto t = get_triangle(); new_triangles.push_back(t); } else { is_ask_query[i] = true; int l, r; cin >> l >> r; r++; ask_queries.emplace_back(i, l, r); for(auto [li, ri, si]: new_triangles) if (li <= l && r <= ri) { chmax(ans[i], si); } } } sort(all(ask_queries), [&](auto& x, auto& y) {return get<2>(x) < get<2>(y);}); auto nxt = triangles.begin(); map mp; mp[-1] = 3002003004005006007LL; mp[1001001001] = -1; for(auto [i, l, r]: ask_queries) { while(nxt != triangles.end() && get<1>(*nxt) <= r) { auto [li, ri, si] = *nxt; nxt++; if (si <= mp.lower_bound(li)->second) continue; mp[li] = si; for(auto it = mp.find(li);;) { auto t = prev(it); if (t->second <= si) { mp.erase(t); } else { break; } } } auto it = mp.lower_bound(l); chmax(ans[i], it->second); } sort(all(new_triangles), mycmp); int old_sz = triangles.size(); for(auto t: new_triangles) triangles.push_back(t); inplace_merge(triangles.begin(), triangles.begin() + old_sz, triangles.end(), mycmp); } rep(i, q) if (is_ask_query[i]) cout << ans[i] << '\n'; }