D. Phaethon's Melody
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As Vivian heard her beloved Lord Phaethon was able to fight himself, she prepared $$$n$$$ W-Engines and $$$m$$$ sets of Drive Discs for him.

The $$$i$$$-th W-Engine provides $$$a_i$$$ ATK. Each W-Engine also has an associated value $$$b_i$$$. The W-Engine's type determines to which critical hit property this bonus magnitude is applied:

  • If the W-Engine is of Type $$$1$$$, it contributes this $$$\frac{b_i}{P}$$$ magnitude to the total CRIT Rate.
  • If the W-Engine is of Type $$$2$$$, it contributes this $$$\frac{b_i}{P}$$$ magnitude to the total CRIT Damage.

The $$$j$$$-th set of Drive Discs obtains $$$\frac{x_j}{P}$$$ CRIT Rate and $$$\frac{y_j}{P}$$$ CRIT Damage. Phaethon can only equip one W-Engine and one set of Drive Discs at the same time, and the same property will accumulate.

When Phaethon deals damage, let his total CRIT Rate be $$$c$$$ and his total CRIT Damage be $$$d$$$. These values are accumulated from the equipped W-Engine and Drive Discs. His base damage for an attack, hereafter referred to as $$$A$$$, is the $$$a_i$$$ value from the currently equipped W-Engine. The damage dealt by a single attack is determined as follows:

  • A critical hit occurs with a probability of $$$\min\{c, 1\}$$$. If a critical hit occurs, the damage dealt is $$$A \times (1+d)$$$.
  • If a critical hit does not occur, the damage dealt is $$$A$$$ itself.

Since each of her $$$n$$$ W-Engines has a distinct use under certain cases, Vivian needs to know how to choose Drive Discs to maximize the expected damage with each of the W-Engines. She wants you to help her verify her results.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5\cdot10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$P$$$ ($$$1 \le n, m \le 5 \cdot 10^5$$$, $$$2 \le P \le 10^9$$$).

Each of the following $$$n$$$ lines contains three integers $$$k_i$$$, $$$a_i$$$ and $$$b_i$$$ ($$$1 \le k \le 2$$$, $$$1 \le a_i, b_i \le 10^9$$$), where $$$k_i$$$ indicates the type of the $$$i$$$-th W-Engine.

Each of the following $$$m$$$ lines contains two integers $$$x_j$$$ and $$$y_j$$$ ($$$1 \le x_j, y_j \le 10^9$$$).

Output

For each test case, output $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$, where $$$c_i$$$ indicates the maximum expected damage with the $$$i$$$-th W-Engine. To avoid float precision error, you need to output the maximum values modulo $$$10^9+7$$$. Formally, let $$$M = 10^9+7$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Please note that the modulus is different from the other problems'.

Example
Input
1
2 2 100
1 40 80
2 40 80
60 120
80 100
Output
88 200000099
Note

In the example, Vivian has two W-Engines and two sets of Drive Discs.

When Phaethon is equipped with the first W-Engine:

  • If he is equipped with the first set of Drive Discs, he has a CRIT Rate of $$$140\%$$$ and a CRIT Damage of $$$120\%$$$. Because his CRIT Rate exceeds $$$100\%$$$, his expected damage is $$$40 \times (1+120\%)=88$$$.
  • If he is equipped with the second set of Drive Discs, he has a CRIT Rate of $$$160\%$$$ and a CRIT Damage of $$$100\%$$$. Because his CRIT Rate exceeds $$$100\%$$$, his expected damage is $$$40 \times (1+100\%)=80$$$.

Therefore, the first answer is $$$88$$$.

When Phaethon is equipped with the second W-Engine:

  • If he is equipped with the first set of Drive Discs, he has a CRIT Rate of $$$60\%$$$ and a CRIT Damage of $$$200\%$$$. He has a $$$60\%$$$ probability to deal $$$40 \times (1+200\%)=120$$$ damage, and another $$$40\%$$$ probability to deal $$$40$$$ damage, so his expected damage is $$$120 \times 60\% + 40 \times 40\% = 88$$$.
  • If he is equipped with the second set of Drive Discs, he has a CRIT Rate of $$$80\%$$$ and a CRIT Damage of $$$180\%$$$. He has a $$$80\%$$$ probability to deal $$$40 \times (1+180\%)=112$$$ damage, and another $$$20\%$$$ probability to deal $$$40$$$ damage, so his expected damage is $$$112 \times 80\% + 40 \times 20\% = 97.6$$$.

Therefore, the second answer is $$$97.6=\frac{488}{5}$$$. Because $$$488\cdot 5^{-1} \equiv 200000099\pmod{10^9+7}$$$, the output is $$$200000099$$$.