Description

We all know the concept of food chain in nature, and there is a similar situation in NTHU - The counter cycle among elephants, cats, and bugs (don’t worry, elephants won’t eat cats). These three species engage in battles on campus, the rules are as follows.

• Normal attack: If the attacker and the defender are not of the same species, and the attacker does not counter the defender, the damage dealt will be the attacker's attack power minus the defender's defense power.
• Counter attack: If the attacker and the defender are not of the same species, and the attacker counters the defender, the attacker’s attack power is doubled during that fight. The defender then takes damage equal to the new attack power minus its defense power.
• Heal magic: If the attacker and the defender are of the same species, the attack is converted into healing magic, and the defender recovers HP equal to the attacker’s attack power.

The counter relationship:

• Elephants counter cats
• Cats counter bugs
• Bugs counter elephant

Once a contestant is dead (HP = 0), it cannot attack, heal, or revive anymore (but you still have to output the result of battle).

All attacks will not deal negative damage, and the minimum HP is 0.

There are n contestants and q battles. Please output the remaining HP of the defender after each battle.

This is a partial judge problem. You only need to implement battle() function.

The illustrations below is the demostration of the sample case.

---

Input

The first line contains two integers, n and q.

2 ≤ n, q ≤ 1000

The following n lines each line contain a string and three integers s, hp, atk and def, representing the species, health point, attack power and defend power of i-th (1-based) contestant, respectively.

s belong to {"Elephant", "Cat", "Bug"}

1 ≤ hp ≤ 1000

1 ≤ atk, def ≤ 300

The following q lines each line contain two distinct integers a and b, representing the index of the attcker and the defender.

1 ≤ a, b ≤ n

Output

Output the remain HP of the defender, followed by a new line character '\n';

Sample Input  Download

Sample Output  Download

Partial Judge Code

14532.c

Partial Judge Header

14532.h

Tags

Discuss

Description

Elephants form two types of formations during migration:

1. Sorted by Age: Ensures that older elephants can correctly lead the group to their destination.
2. Sorted by Height: Ensures that elephants at the rear can see every elephant in front of them.

Elephants prefer using merge sort in ascending order. Please help them sort by age, and if the ages are identical, sort by height. If both age and height are the same, maintain the original relative order of the index (stable sort).

This is a partial judge problem. You only need to implement merge_elephants() function, the output function has already been provided for you.

Input

The first line contains a single integer n - the number of elephants.

 2 ≤ n  ≤ 10⁵

The following n lines each line contain two integer a, h - the age and height of i-th elephant.

1 ≤ a, h ≤ 10⁹
(Elephants are tall and long-lived animals.)

 

Output

Output the result of the index in each merge section, the format has already been implemented in the given function.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14555.c

Partial Judge Header

14555.h

Tags

Discuss