Problem Description

Given $n$ distinct points $(x_i, y_i)_{i=1}^n$ on the plane, each point has a weight, initially $v_i$.

There are $m$ operations in total:

• Update operation: given $X$, change the weight $v_i$ of every point satisfying $x_i = X$ to $v_i^2$.
• Query operation: given $Y$, compute the sum of weights $v_i$ of all points satisfying $y_i = Y$.

The answer should be taken modulo $10^9+7$.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain three integers $x_i, y_i, v_i$.

The next $m$ lines each contain two integers. An update operation is written as $1, X$, and a query operation is written as $2, Y$.

Output Format

For each query operation, output one line containing the answer.

5 10
1 3 597843412
1 1 613307236
1 2 488247075
1 4 29761102
1 5 101159431
1 1
2 2
1 1
2 2
2 1
2 2
1 1
1 1
2 3
1 1

577359197
27079329
482035359
27079329
220579797

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For $100\%$ of the testdata, $1 \le n, m \le 1.2 \times 10^6$, $1 \le x_i, y_i \le n$, $0 \le v_i \le 10^9+6$, and $1 \le X, Y \le n$.

For $25\%$ of the testdata, $n, m \le 5000$.

For another $25\%$ of the testdata, there are no update operations.

For another $25\%$ of the testdata, $x_i, y_i, X, Y$ are independently chosen uniformly at random from $1, 2, \dots, n$.

For the remaining $25\%$ of the testdata, there are no special constraints.

Translated by ChatGPT 5