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

There are $m$ operations:

Update operation: Given $X$, update the weights $v_i$ of all points satisfying $x_i = X$ to $v_i^2$.

Query operation: Given $Y$, calculate the sum of weights $v_i$ for all points satisfying $y_i = Y$.

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

Input

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

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

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

Output

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

Examples

Input 1

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

Output 1

577359197
27079329
482035359
27079329
220579797

Subtasks

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

For $100\%$ of the data, $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$, $1\le X, Y\le n$.

For $20\%$ of the data, $n, m\le 5000$.

For another $20\%$ of the data, there are no update operations.

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

For the remaining $20\%$ of the data, there are no special restrictions.