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, there are \(n\) heroes with \(q\) one-by-one matches. 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.

As a battle recorder, you know which heroes are engaged in each battle. You need to record the outcome of each match, declaring the winner.

Please output the winner of each one-by-one match.

Shorter Description: Most of the topics are similar to Arena of Valor, the difference is that there are many one-by-one matches, and you need to output the winning hero.

Notes:

• When a hero's remaining HP is less than or equal to zero, they are dead, which means their apponent wins.
• When each battle ends, every hero can use their own cure power to reset their own hp and skill cooldown time.
• \(i\) battle with \(j\) means \(i\) attack \(j\) at the first second, \(j\) attack \(i\) at the second second, \(i\) attack \(j\) in the third second, and so on.

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 battles with 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^4\)
• \(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

Please output the winner of each one-by-one match.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14317.cpp

Partial Judge Header

14317.h

Tags

Discuss