Description

Xiao Q is a programmer.

As a young programmer, Xiao Q is always bullied by old C, who often assigns him troublesome tasks. Whenever Xiao Q does not know how to solve them, he has to ask you for help.

To complete the task, Xiao Q needs to make a table with infinitely many rows and infinitely many columns, both indexed starting from $1$. Every cell in the table contains an integer. For convenience, Xiao Q denotes the integer in row $a$, column $b$ as $f(a, b)$. The table must satisfy the following conditions:

1. For any positive integers $a, b$, it must hold that $f(a, b) = f(b, a)$.
2. For any positive integers $a, b$, it must hold that $b \times f(a, a + b) = (a + b) \times f(a, b)$.

Initially, the numbers in the table are very regular: the number in row $a$, column $b$ is exactly $a \times b$, which obviously satisfies the two conditions above. To complete the task, Xiao Q will keep modifying the numbers in the table. Each time a cell is changed, in order to keep the table satisfying the two conditions, Xiao Q must also update all cells that can be affected by this modification to appropriate values. By some mysterious power, it is guaranteed that after each round of modification all entries remain integers. Xiao Q also needs to query, at any time, the sum of all numbers in the finite region of the first $k$ rows and first $k$ columns; since the answer may be large, it suffices to output the result ${} \bmod 1,000,000,007$.

Input Format

The first line contains two integers $m, n$, indicating that there are $m$ operations, and that all row and column indices mentioned in the operations and queries do not exceed $n$.

Then follow $m$ lines, each containing four integers $a, b, x, k$, meaning: set the number in row $a$, column $b$ to $x$, then update all cells that can be affected by this change, with the guarantee that after the modification all entries are still integers. After the modification is completed, compute the sum of all numbers in the first $k$ rows and first $k$ columns.

Output Format

Output $m$ lines. After each operation, output one line containing the answer modulo $1,000,000,007$.

3 3
1 1 1 2
2 2 4 3
1 2 4 2

9
36
14

4 125
1 2 4 8
1 3 9 27
1 4 16 64
1 5 25 125

2073
316642
12157159
213336861

Hint

Sample Explanation #1

Initially, the top-left $3 \times 3$ submatrix is as shown on the left. There is no change after the first $2$ operations. After the $3$rd operation, the table becomes as shown on the right.

1 2 3     2  4  6
2 4 6     4  4 12
3 6 9     6 12  9

Constraints

For $100\%$ of the testdata, $1 \le m \le 10^4$, $1 \le a, b, k \le n \le 4 \times 10^6$, $0 \le x \le 10^{18}$.

Translated by ChatGPT 5