<p>Given a <strong>0-indexed</strong> 2D integer matrix <code><font face="monospace">grid</font></code><font face="monospace"> </font>of size <code>n * m</code>, we define a <strong>0-indexed</strong> 2D matrix <code>p</code> of size <code>n * m</code> as the <strong>product</strong> matrix of <code>grid</code> if the following condition is met:</p>

<ul>
	<li>Each element <code>p[i][j]</code> is calculated as the product of all elements in <code>grid</code> except for the element <code>grid[i][j]</code>. This product is then taken modulo <code><font face="monospace">12345</font></code>.</li>
</ul>

<p>Return <em>the product matrix of</em> <code><font face="monospace">grid</font></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,2],[3,4]]
<strong>Output:</strong> [[24,12],[8,6]]
<strong>Explanation:</strong> p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
So the answer is [[24,12],[8,6]].</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[12345],[2],[1]]
<strong>Output:</strong> [[2],[0],[0]]
<strong>Explanation:</strong> p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2.
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0. So p[0][1] = 0.
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0. So p[0][2] = 0.
So the answer is [[2],[0],[0]].</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n == grid.length&nbsp;&lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m == grid[i].length&nbsp;&lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= n * m &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

MOD = 12345
class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        p = SegmentTree2D(grid, default=1, func=lambda a, b: a * b % MOD)
        m = len(grid)
        n = len(grid[0])
        g = []
        for i in range(m):
            row = []
            for j in range(n):
                prod = p.query(0, 0, i, n) * p.query(i + 1, 0, m, n) * p.query(i, 0, i + 1, j) * p.query(i, j + 1, i + 1, n)
                row.append(prod % MOD)
            g.append(row)
        return g

class SegmentTree2D:
    def __init__(self, data, default=0, func=max):
        """Initialize the 2D segment tree with data"""
        self._default = default
        self._func = func
        self._len_y = len(data)
        self._len_x = len(data[0]) if data else 0
        self.tree = [[default] * (2 * self._len_x) for _ in range(2 * self._len_y)]
        for i in range(self._len_y):
            for j in range(self._len_x):
                self.tree[i + self._len_y][j + self._len_x] = data[i][j]
        self._build()

    def _build(self):
        for i in range(self._len_y):
            for j in reversed(range(self._len_x)):
                self.tree[i + self._len_y][j] = self._func(self.tree[i + self._len_y][j * 2],
                                                           self.tree[i + self._len_y][j * 2 + 1])
        for i in reversed(range(self._len_y)):
            for j in range(2 * self._len_x):
                self.tree[i][j] = self._func(self.tree[i * 2][j], self.tree[i * 2 + 1][j])

    def update(self, y, x, value):
        y += self._len_y
        x += self._len_x
        self.tree[y][x] = value
        while x > 1:
            x //= 2
            self.tree[y][x] = self._func(self.tree[y][2 * x], self.tree[y][2 * x + 1])
        while y > 1:
            y //= 2
            for x in range(2 * self._len_x):
                self.tree[y][x] = self._func(self.tree[2 * y][x], self.tree[2 * y + 1][x])

    def query(self, y1, x1, y2, x2):
        """Query the 2D range [y1, y2) x [x1, x2)"""
        res = self._default
        y1 += self._len_y
        y2 += self._len_y
        while y1 < y2:
            if y1 & 1:
                res = self._func(res, self._query_x(y1, x1, x2))
                y1 += 1
            if y2 & 1:
                y2 -= 1
                res = self._func(res, self._query_x(y2, x1, x2))
            y1 //= 2
            y2 //= 2
        return res

    def _query_x(self, y, x1, x2):
        res = self._default
        x1 += self._len_x
        x2 += self._len_x
        while x1 < x2:
            if x1 & 1:
                res = self._func(res, self.tree[y][x1])
                x1 += 1
            if x2 & 1:
                x2 -= 1
                res = self._func(res, self.tree[y][x2])
            x1 //= 2
            x2 //= 2
        return res

    def __repr__(self):
        return f"SegmentTree2D({self.tree})"

71400