Description

Arena of Valor is a well-known action mobile game. The heroes in the game are divided into three classes: Archer, Mage, and Tank. Each class has its own advantages, making it a beloved fair competitive game for everyone.

Each hero can inflict damage on enemies through basic attacks and skills. The cooldown time for skills is 5 seconds, while basic attacks have no such limitation. Basically, the amount of damage to the enemy's health is determined by the hero's corresponding basic attack or skill attack power, but each class has some special effects:

• Archer: Basic attacks within 3 seconds after casting a skill gain bonus damage, decreasing in ratios of $2$ times, $\frac{5}{3}$ times, and $\frac{4}{3}$ times respectively (rounded down).
• Mage: Skills only have a cooldown time of two seconds.
• Tank: Damage received is halved (rounded down).

Now, a new mode called Deathmatch Arena has been introduced. There are $n$ heroes fighting each other, with each hero having their own health points ($\text{hp}$), basic attack power ($\text{atk1}$), and skill attack power ($\text{atk2}$).

You are currently acting as a battle recorder. You know what happens in the next $q$ seconds. At the $t$-th second, the $i$-th hero attacks the $j$-th hero. Also, the skill attack would be performed whenever the skill cooldown ends.

Please output the remaining HP of the attacked hero at the end of each second.

Notes:

• When a hero's remaining HP is less than or equal to zero, they are dead. You should record the HP as 0.
• When the attacker or the attacked hero is dead, the attack action is considered invalid, it won't trigger the cooldown of the skill, nor will it affect either side's health points, also, you don't need to output anything in this second.

Input

The first line contains two integers $n, q$.
Each of the next $n$ lines contain one string and three integers $\text{type}_i, \text{hp}_i, \text{atk1}_i, \text{atk2}_i$, represent the $i$-th hero.
Each of the next $q$ lines have two integers $i, j$, represent the $i$-th hero attacks the $j$-th hero.

$n \quad q$
$\text{type}_0 \quad \text{hp}_0 \quad \text{atk1}_0 \quad \text{atk2}_0$
$\text{type}_1 \quad \text{hp}_1 \quad \text{atk1}_1 \quad \text{atk2}_1$
$\vdots$
$\text{type}_{n - 1} \quad \text{hp}_{n - 1} \quad \text{atk1}_{n - 1} \quad \text{atk2}_{n - 1}$ $i_0 \quad j_0$
$i_1 \quad j_1$
$\vdots$
$i_{q - 1} \quad j_{q - 1}$

Constraints

• $1 \le n, q \le 10^5$
• $0 \le \text{hp}, \text{atk1}, \text{atk2} \le 10^9$
• $0 \le i, j < n$
• type = "Archer" / "Mage" / "Tank"
• Testcase 1, 2 only contain "Archer" and "Mage"
• Testcase 3, 4 only contain "Mage" and "Tank"
• Testcase 5, 6 only contain "Archer" and "Tank"
• Testcase 7, 8 contain all types

Output

After each second, if the attack action is valid, output the remaining health points of the attacked hero at the end of each second.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14305.cpp

Partial Judge Header

14305.h

Tags

Discuss