def merge_sort(A,B): pos_A,pos_B = 0,0 n,m = len(A),len(B) res = [] while pos_A < n and pos_B < m: a,b = A[pos_A],B[pos_B] if a < b: res.append(a) pos_A += 1 else: res.append(b) pos_B += 1 res += A[pos_A:] res += B[pos_B:] return res class SegmentTree: def __init__(self, n, segfunc, ide_ele): self.segfunc = segfunc self.ide_ele = ide_ele #self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * n self.size = n def update(self, k, x): k += self.size self.tree[k] = self.segfunc(self.tree[k],x) while k > 1: self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1]) k >>= 1 def query(self, l, r): if r==self.size: r = self.size res = self.ide_ele l += self.size r += self.size while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: res = self.segfunc(res, self.tree[r - 1]) l >>= 1 r >>= 1 return res class SegmenTree2D: def __init__(self,n,w_list,segfunc,ide_ele): self.num = n self.segfunc = segfunc self.ide_ele = ide_ele self.val = [[] for i in range(2 * n)] self.segtree = [None for i in range(2 * n)] for i in range(n): self.val[i+self.num] = w_list[i] if self.val[i+self.num]: self.segtree[i+self.num] = SegmentTree(len(self.val[i+self.num]),segfunc,ide_ele) for i in range(self.num-1,0,-1): self.val[i] = merge_sort(self.val[2*i],self.val[2*i+1]) if self.val[i]: self.segtree[i] = SegmentTree(len(self.val[i]),segfunc,ide_ele) def update(self,l,r,x): l += self.num while l: #assert self.segment[l] idx = bisect.bisect_left(self.val[l],r) self.segtree[l].update(idx,x) l >>= 1 def query(self,lx,rx,ly,ry): res = self.ide_ele lx += self.num rx += self.num while lx < rx: if lx&1: if self.val[lx]: tmp_l = bisect.bisect_left(self.val[lx],ly) tmp_r = bisect.bisect_left(self.val[lx],ry) res = self.segfunc(res,self.segtree[lx].query(tmp_l,tmp_r)) lx += 1 if rx&1: if self.val[rx-1]: tmp_l = bisect.bisect_left(self.val[rx-1],ly) tmp_r = bisect.bisect_left(self.val[rx-1],ry) res = self.segfunc(res,self.segtree[rx-1].query(tmp_l,tmp_r)) lx >>= 1 rx >>= 1 return res def area(a,b,c,d,e,f): A,B,C,D = c-a,d-b,e-a,f-b return abs(A*D-B*C) import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import gcd,log input = lambda :sys.stdin.buffer.readline() mi = lambda :map(int,input().split()) li = lambda :list(mi()) n,q = mi() triangle = [tuple(mi()) for i in range(n)] Query = [tuple(mi()) for i in range(q)] X = set() for a,b,c,d,e,f in triangle: X.add(min(a,c,e)) for t,*query in Query: if t==1: a,b,c,d,e,f = query X.add(min(a,c,e)) else: l,r = query X.add(l) X.add(r) X = sorted(X) comp = {e:i for i,e in enumerate(X)} H = len(comp) w_list = [[] for i in range(H)] for a,b,c,d,e,f in triangle: idx = comp[min(a,c,e)] w_list[idx].append(max(a,c,e)) for t,*query in Query: if t==1: a,b,c,d,e,f = query idx = comp[min(a,c,e)] w_list[idx].append(max(a,c,e)) for i in range(H): w_list[i].sort() seg = SegmenTree2D(H,w_list,max,-1) for a,b,c,d,e,f in triangle: idx = comp[min(a,c,e)] seg.update(idx,max(a,c,e),area(a,b,c,d,e,f)) for t,*query in Query: if t==1: a,b,c,d,e,f = query idx = comp[min(a,c,e)] seg.update(idx,max(a,c,e),area(a,b,c,d,e,f)) else: l,r = query l_idx = comp[l] r_idx = comp[r] print(seg.query(l_idx,r_idx+1,l,r+1))