Problem:
 Score: 600 points    Problem Statement  There is a grass field that stretches infinitely.  In this field, there is a negligibly small cow. Let (x, y) denote the point that is x\ \mathrm{cm} south and y\ \mathrm{cm} east of the point where the cow stands now. The cow itself is standing at (0, 0) .  There are also N north-south lines and M east-west lines drawn on the field. The i -th north-south line is the segment connecting the points (A_i, C_i) and (B_i, C_i) , and the j -th east-west line is the segment connecting the points (D_j, E_j) and (D_j, F_j) .  What is the area of the region the cow can reach when it can move around as long as it does not cross the segments (including the endpoints)? If this area is infinite, print INF instead.      Constraints   All values in input are integers between -10^9 and 10^9 (inclusive).  1 \leq N, M \leq 1000  A_i < B_i\ (1 \leq i \leq N)  E_j < F_j\ (1 \leq j \leq M)  The point (0, 0) does not lie on any of the given segments.         Input  Input is given from Standard Input in the following format:  N  M  A_1  B_1  C_1  :  A_N  B_N  C_N  D_1  E_1  F_1  :  D_M  E_M  F_M       Output  If the area of the region the cow can reach is infinite, print INF ; otherwise, print an integer representing the area in \mathrm{cm^2} .  (Under the constraints, it can be proved that the area of the region is always an integer if it is not infinite.)        Sample Input 1 5 6
1 2 0
0 1 1
0 2 2
-3 4 -1
-2 6 3
1 0 1
0 1 2
2 0 2
-1 -4 5
3 -2 4
1 2 4      Sample Output 1 13  The area of the region the cow can reach is 13\ \mathrm{cm^2} .        Sample Input 2 6 1
-3 -1 -2
-3 -1 1
-2 -1 2
1 4 -2
1 4 -1
1 4 1
3 1 4      Sample Output 2 INF  The area of the region the cow can reach is infinite.

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[y] 
        self.parent[y] = x 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def getsize(self,x): 
        return self.size[self.root(x)]



import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m = map(int, readline().split())
yoko = [list(map(int, readline().split())) for _ in range(n)]
tate = [list(map(int, readline().split())) for _ in range(m)]

INF = 10**9+5
xcoord = [-INF,0,INF]
ycoord = [-INF,0,INF]

for a,b,c in yoko: 
    xcoord.append(a)
    xcoord.append(b)
    ycoord.append(c)
for d,e,f in tate: 
    ycoord.append(e)
    ycoord.append(f)
    xcoord.append(d)

xcoord = list(sorted(set(xcoord)))
ycoord = list(sorted(set(ycoord)))

zaatu_x = {a:i for i,a in enumerate(xcoord)}
zaatu_y = {a:i for i,a in enumerate(ycoord)}

P = len(xcoord)
Q = len(ycoord)
QQ=Q-1



ok_up = [[0]*P for _ in range(Q)]
ok_ri = [[0]*Q for _ in range(P)]

for a,b,c in yoko: 
    xa = zaatu_x[a]
    xb = zaatu_x[b]
    yc = zaatu_y[c]
    ok_up[yc-1][xa] += 1
    ok_up[yc-1][xb] -= 1


for d,e,f in tate: 
    ye = zaatu_y[e]
    yf = zaatu_y[f]
    xd = zaatu_x[d]
    ok_ri[xd-1][ye] += 1
    ok_ri[xd-1][yf] -= 1



"""
from itertools import accumulate
for i in range(Q):
    ok_up[i] = list(accumulate(ok_up[i]))
for j in range(P):
    ok_ri[j] = list(accumulate(ok_ri[j]))
"""
for i in range(Q):
    for j in range(P-1):
        ok_up[i][j+1] += ok_up[i][j]

for j in range(P):
    for i in range(Q-1):
        ok_ri[j][i+1] += ok_ri[j][i]



UF = UnionFind((P-1)*QQ)
for i in range(P-1):
    for j in range(Q-2):
        v = i*QQ+j
        if ok_up[j][i]==0: UF.merge(v,v+1)
for i in range(P-2):
    for j in range(Q-1):
        v = i*QQ+j
        if ok_ri[i][j]==0: UF.merge(v,v+QQ)
        
x0 = zaatu_x[0]
y0 = zaatu_y[0]


r = UF.root(x0*QQ+y0) 
if UF.root(0) == r:
    print("INF")
else:
    ans = 0
    for i in range(P-1):
        for j in range(Q-1):
            if UF.root(i*QQ+j) == r:
                ans += (xcoord[i+1]-xcoord[i])*(ycoord[j+1]-ycoord[j]) 
    print(ans)

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def compress(X, Y):
    dx = list(sorted(set(X)))
    dx_inv = {x: i for i, x in enumerate(dx)}
    dy = list(sorted(set(Y)))
    dy_inv = {y: i for i, y in enumerate(dy)}
    return (dx, dy), (dx_inv, dy_inv)


def main():
    
    
    
    

    
    N, M = map(int, readline().split())
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        A[i], B[i], C[i] = map(int, readline().split())
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        D[i], E[i], F[i] = map(int, readline().split())

    
    X = [-INF, 0, INF] + A + B + D
    Y = [-INF, 0, INF] + C + E + F
    (mx, my), (invx, invy) = compress(X, Y)
    H = len(my)
    W = len(mx)

    
    
    
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    
    
    uf = UnionFind(W*H)

    
    
    
    
    for i in range(W):
        for j in range(H):
            if i+1 < W and segy[i][j] == 0:
                uf.union(i+j*W, i+1+j*W)
            if j+1 < H and segx[i][j] == 0:
                uf.union(i+(j+1)*W, i+j*W)

    
    
    ushi = invx[0]+invy[0]*W
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    ushi = uf.find(ushi)
    for mem in range(uf.n):
        if uf.find(mem) == ushi:
            j, i = divmod(mem, W)
            area += (mx[i+1]-mx[i])*(my[j+1]-my[j])

    print(area)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def compress(X, Y):
    dx = list(sorted(set(X)))
    dx_inv = {x: i for i, x in enumerate(dx)}
    dy = list(sorted(set(Y)))
    dy_inv = {y: i for i, y in enumerate(dy)}
    return (dx, dy), (dx_inv, dy_inv)


def main():
    
    
    
    

    
    N, M = map(int, readline().split())
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        A[i], B[i], C[i] = map(int, readline().split())
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        D[i], E[i], F[i] = map(int, readline().split())

    
    X = [-INF, 0, INF] + A + B + D
    Y = [-INF, 0, INF] + C + E + F
    (mx, my), (invx, invy) = compress(X, Y)
    H = len(my)
    W = len(mx)

    
    
    
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    
    
    uf = UnionFind(W*H)

    
    
    
    
    for i in range(W):
        for j in range(H):
            if i+1 < W and segy[i][j] == 0:
                uf.union(i+j*W, i+1+j*W)
            if j+1 < H and segx[i][j] == 0:
                uf.union(i+(j+1)*W, i+j*W)

    
    
    ushi = invx[0]+invy[0]*W
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    for mem in uf.members(ushi):
        j, i = divmod(mem, W)
        area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def compress(X, Y):
    dx = list(sorted(set(X)))
    dx_inv = {x: i for i, x in enumerate(dx)}
    dy = list(sorted(set(Y)))
    dy_inv = {y: i for i, y in enumerate(dy)}
    return (dx, dy), (dx_inv, dy_inv)


def main():
    
    
    
    

    
    N, M = map(int, readline().split())
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f

    
    X = [-INF, 0, INF] + A + B + D
    Y = [-INF, 0, INF] + C + E + F
    (mx, my), (invx, invy) = compress(X, Y)
    H = len(my)
    W = len(mx)

    
    
    
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    
    
    uf = UnionFind(W*H)

    
    
    
    
    for i in range(W):
        for j in range(H):
            if i+1 < W and segy[i][j] == 0:
                uf.union(i+j*W, i+1+j*W)
            if j+1 < H and segx[i][j] == 0:
                uf.union(i+(j+1)*W, i+j*W)

    
    
    ushi = invx[0]+invy[0]*W
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    for i in range(W-1):
        for j in range(H-1):
            if uf.same(ushi, i+j*W):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    
    
    
    

    
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)

    
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx = {x: i for i, x in enumerate(mx)}
    invy = {y: i for i, y in enumerate(my)}
    H = len(my)
    W = len(mx)

    
    
    
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    
    
    uf = UnionFind(W*H)

    
    
    
    
    for i in range(W):
        for j in range(H):
            if i+1 < W and segy[i][j] == 0:
                uf.union(i+j*W, i+1+j*W)
            if j+1 < H and segx[i][j] == 0:
                uf.union(i+(j+1)*W, i+j*W)

    
    
    ushi = invx[0]+invy[0]*W
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    for i in range(W-1):
        for j in range(H-1):
            if uf.same(ushi, i+j*W):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = [-1]*N

    def root(self, i):
        if self.tree[i] < 0:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.tree[y] < self.tree[x]:
                x, y = y, x
            self.tree[x] += self.tree[y]
            self.tree[y] = x
        return x == y


def main():
    
    
    
    

    
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)

    
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(mx):
        invx[x] = i
    for i, y in enumerate(my):
        invy[y] = i
    H = len(my)
    W = len(mx)

    
    
    
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    
    
    uf = UnionFind(W*H)

    
    
    
    
    for i in range(W):
        for j in range(H):
            if i+1 < W and segy[i][j] == 0:
                uf.unite(i+j*W, i+1+j*W)
            if j+1 < H and segx[i][j] == 0:
                uf.unite(i+(j+1)*W, i+j*W)

    
    
    ushi = invx[0]+invy[0]*W
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    for i in range(W-1):
        for j in range(H-1):
            if uf.same(ushi, i+j*W):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline


def compress(set_):
    """座標圧縮した辞書を返す"""
    array2 = sorted(list(set_))
    memo = {value: index for index, value in enumerate(array2)}
    return memo


def calc_s(hi, wj):
    """座標圧縮後の範囲hi <= i < hi - 1, wj <= j < wj + 1について、
    座標圧縮前の面積を求める
    """
    res = abs(h_rests[hi] - h_rests[hi - 1]) * abs(w_rests[wj] - w_rests[wj + 1]) 
    return res   


h, w = map(int, input().split())
info_h = [list(map(int, input().split())) for i in range(h)]
info_w = [list(map(int, input().split())) for i in range(w)]
INF = 10 ** 20

h_coords = set([-INF, 0, INF])
w_coords = set([-INF, 0, INF])

for h1, h2, w1 in info_h:
    h_coords.add(h1)
    h_coords.add(h2)
    w_coords.add(w1)
for h1, w1, w2 in info_w:
    h_coords.add(h1)
    w_coords.add(w1)
    w_coords.add(w2)


h_comps = compress(h_coords)
w_comps = compress(w_coords)


h_rests = {h_comps[index]: index for index in h_comps}
w_rests = {w_comps[index]: index for index in w_comps}



















grid = [[1] * (len(w_rests) + 2) for i in range(len(h_rests) + 2)]
for h1, h2, w1 in info_h:
    h1, h2, w1 = h_comps[h1], h_comps[h2], w_comps[w1]
    for hi in range(h1 + 1, h2 + 1):
        grid[hi][w1] *= 2

for h1, w1, w2 in info_w:
    h1, w1, w2 = h_comps[h1], w_comps[w1], w_comps[w2]
    for wi in range(w1, w2):
        grid[h1][wi] *= 3


used = [[False] * (len(w_rests) + 2) for i in range(len(h_rests) + 2)]
si, sw = h_comps[0], w_comps[0]
OFFSET = 5000
stack = [si * 5000 + sw]
ans = 0
used[si][sw] = True

while stack:
    ij = stack.pop()
    i, j = divmod(ij, OFFSET)
    ans += calc_s(i, j)

    
    nxt_i, nxt_j = i - 1, j
    if grid[nxt_i][nxt_j] % 3 == 0 or used[nxt_i][nxt_j]:
        
        pass
    else:
        used[nxt_i][nxt_j] = True
        stack.append(nxt_i * OFFSET + nxt_j)

    
    nxt_i, nxt_j = i + 1, j
    if grid[i][j] % 3 == 0 or used[nxt_i][nxt_j]:
        
        pass
    else:
        used[nxt_i][nxt_j] = True
        stack.append(nxt_i * OFFSET + nxt_j)

    
    nxt_i, nxt_j = i, j + 1
    if grid[nxt_i][nxt_j] % 2 == 0 or used[nxt_i][nxt_j]:
        
        pass
    else:
        used[nxt_i][nxt_j] = True
        stack.append(nxt_i * OFFSET + nxt_j)
        
    
    nxt_i, nxt_j = i, j - 1
    if grid[i][j] % 2 == 0 or used[nxt_i][nxt_j]:
        
        pass
    else:
        used[nxt_i][nxt_j] = True
        stack.append(nxt_i * OFFSET + nxt_j)
        
    if ans > INF:
        
        print("INF")
        exit()

print(ans)

Solution (Python):

import sys
import numpy as np


def main():
    N, M = map(int, sys.stdin.buffer.readline().split())
    LineData = np.int64(sys.stdin.buffer.read().split())

    INF = 10**9 + 1

    LineData = LineData.reshape(-1, 3)
    A, B, C = LineData[:N].T
    D, E, F = LineData[N:].T
    X = np.unique(np.concatenate([D, [-INF, INF]]))
    Y = np.unique(np.concatenate([C, [-INF, INF]]))
    A = np.searchsorted(X, A)
    B = np.searchsorted(X, B, 'right') - 1
    C = np.searchsorted(Y, C)
    D = np.searchsorted(X, D)
    E = np.searchsorted(Y, E)
    F = np.searchsorted(Y, F, 'right') - 1

    area = cal_area(A, B, C, D, E, F, X, Y)

    if area == 0:
        print("INF")
    else:
        print(area)


def cal_area(A, B, C, D, E, F, X, Y):
    x = np.searchsorted(X, 0, 'right') - 1
    y = np.searchsorted(Y, 0, 'right') - 1

    DX = X[1:] - X[:-1]
    DY = Y[1:] - Y[:-1]

    A = A.tolist()
    B = B.tolist()
    C = C.tolist()
    D = D.tolist()
    E = E.tolist()
    F = F.tolist()
    X = X.tolist()
    Y = Y.tolist()
    DX = DX.tolist()
    DY = DY.tolist()

    LenX = len(X)
    LenY = len(Y)

    visit = [[False] * LenY for _ in range(LenX)]
    visit[x][y] = True
    area = 0
    queue = [(x, y)]

    LineX = [[False] * LenY for _ in range(LenX)]
    LineY = [[False] * LenY for _ in range(LenX)]

    for x1, x2, y in zip(A, B, C):
        for x in range(x1, x2):
            LineY[x][y] = True

    for x, y1, y2 in zip(D, E, F):
        for y in range(y1, y2):
            LineX[x][y] = True

    LenX -= 1
    LenY -= 1

    q_pop = queue.pop
    q_append = queue.append
    
    while queue:
        x, y = q_pop()
        
        if x == 0 or x == LenX or y == 0 or y == LenY:
            area = 0
            break
        
        area += DX[x] * DY[y]
        
        x1 = x - 1
        if not LineX[x][y] and not visit[x1][y]:
            visit[x1][y] = True
            q_append((x1, y))
        y1 = y - 1
        if not LineY[x][y] and not visit[x][y1]:
            visit[x][y1] = True
            q_append((x, y1))
        x1 = x + 1
        if not LineX[x1][y] and not visit[x1][y]:
            visit[x1][y] = True
            q_append((x1, y))
        y1 = y + 1
        if not LineY[x][y1] and not visit[x][y1]:
            visit[x][y1] = True
            q_append((x, y1))

    return area


if __name__ == '__main__':
	main()

sys.exit()

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=sorted(set(X));l=len(s);return{s[i]:i for i in r(l)},s,l
h,s,K=g(X);w,t,L=g(Y);V,U,v=[[[0]*-~K for i in r(L+1)]for _ in r(3)];q=[(h[0],w[0])];z=0
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
while q:
 x,y=q.pop();v[y][x]=1;z+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=(c,d),;v[d][c]=1
print([z,'INF'][z>F])

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=sorted(set(X));l=len(s);return{s[i]:i for i in r(l)},s,l
h,s,K=g(X);w,t,L=g(Y);V,U,v=[[[0]*-~K for i in r(L+1)]for _ in r(3)];q=[(h[0],w[0])];z=0
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
while q:
 x,y=q.pop();v[y][x]=1;z+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=[(c,d)];v[d][c]=1
print([z,'INF'][z>F])

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=sorted(set(X));l=len(s);return{s[i]:i for i in r(l)},s,l
h,s,K=g(X);w,t,L=g(Y);V,U,v=[[[0]*-~K for i in r(L+1)]for _ in r(3)]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];a=0
while q:
 x,y=q.pop();v[y][x]=1;a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);V,U,v=[[[0]*-~K for i in r(L+1)]for _ in r(3)]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];a=0
while q:
 x,y=q.pop();v[y][x]=1;a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);V,U,v=[[[0]*-~K for i in r(L+1)]for j in r(3)]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and(U[(f>0)+y][x]*f+V[y][(e>0)+x]*e)==0:q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Solution (Python):
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])