During the past holiday, unfortunately, you became addicted to a new turn-based action combat game developed by Zhili Academy.

You are now planning to challenge a dungeon in the game. However, entering this dungeon requires consuming very precious resources, so you want to be well-prepared before heading in. To do this, you intend to write a simulator to predict the combat outcome.

You have figured out the game mechanics (note: if you don't understand something while reading, you can skip it for now, as it may be explained later):

Game Mechanics: Basic Stats

In the game, a skill has 3 attributes: base damage, toughness damage, and mana cost. All are integers.

Each hero has 9 attributes: attack power, defense power, health points (HP), toughness, continuous damage power, max mana, mana recovery, speed, and ID. All are integers.

Each hero possesses a certain number of skills, which varies.

Each hero can be in one of three states:

1. If HP is less than or equal to 0, the hero is in the dead state and will not perform any further actions.
2. If HP is greater than 0 and toughness is less than or equal to 0, the hero is in the bleeding state and will receive an attack during the judgment phase (explained later).
3. Otherwise, the hero is in the normal state.

Game Mechanics: Skills

A skill is always cast by an attacker A on a target B, immediately causing:

1. B's HP to decrease by $\lfloor \text{base damage} \times \text{A's attack power} / \text{B's defense power} \rfloor$.
2. B's toughness to decrease by the skill's toughness damage.
3. A's mana to decrease by the skill's mana cost.

Game Mechanics: Combat

Combat in the game involves the player controlling several heroes fighting against several heroes controlled by the system.

The game proceeds in several rounds until at least one of the following conditions is met:

1. Victory/Defeat condition: One side has no heroes that are not in the dead state.
2. Timeout condition: The end of round $R_{max}$.

In each round, all heroes on both sides who are not in the dead state act in descending order of speed (if speeds are equal, the one with the smaller ID acts first; IDs are guaranteed to be unique). When it is hero A's turn, they proceed through the following phases:

1. Judgment phase: If the hero is currently in the bleeding state, they immediately suffer one skill attack: let B be the hero who first caused the hero's toughness to become less than or equal to 0. This skill is considered to be cast by B, with base damage equal to B's continuous damage power, toughness damage of 0, and mana cost of 0. (Note: This is "considered to be"; even if hero B is already in the dead state, hero A will still receive the attack.)
2. Recovery phase: The hero's mana recovers by their mana recovery amount. If the mana exceeds the max mana after recovery, it is set to the max mana.
3. Attack phase: The hero chooses a skill with a mana cost not exceeding their current mana and casts it on a chosen enemy hero. If no skill meets the requirements, this phase is skipped. (The specific mechanism for choosing is described in "Attack Selection Principles".)

Any hero who reaches an HP of less than or equal to 0 at any moment immediately enters the dead state and ends their action (e.g., if they die during the judgment phase, they will not proceed to the recovery or attack phases).

The victory/defeat condition is checked after each hero's action.

Attack Selection Principles

You have discovered that the automatic combat rules for the opponent are simple:

1. Skill selection: Choose a castable skill with the highest mana cost. (If multiple skills have the same mana cost, choose the one with the highest base damage. If multiple skills still have the same base damage, choose the one with the highest toughness damage.)

2. Attack target selection:

   • If the opponent still has heroes in the normal state, choose the one with the lowest HP among them.
   • If the opponent has no heroes in the normal state, choose the one with the lowest HP among the opponent's heroes in the bleeding state.
   • It is guaranteed that there will always be at least one living enemy hero when a target needs to be chosen.

   If there are multiple candidates meeting the requirements, prioritize the one with the smaller ID.

You decide to use this same automatic combat system yourself.

Now that you have obtained all the stats for all the opponent's heroes and have arranged your own lineup, you want to know the HP of each hero when the combat ends (note that HP can be negative).

Initially, each hero's mana is equal to their max mana.

Input

The input is read from standard input.

The first line contains three non-negative integers $n, m, R_{max}$, representing the number of your heroes, the number of the opponent's heroes, and the maximum number of rounds, respectively.

The next $n+m$ groups of data represent the heroes. The first $n$ groups represent your heroes, and the following $m$ groups represent the opponent's heroes.

Each group consists of several lines. The first line contains 10 positive integers: attack power, defense power, HP, toughness, continuous damage power, max mana, mana recovery, speed, ID, and the number of skills.

The next lines (equal to the number of skills) each contain 3 positive integers: base damage, toughness damage, and mana cost.

Output

Output to standard output.

There are $n+m$ lines in total. The $i$-th line contains an integer representing the HP of the $i$-th hero from the input at the end of the combat.

Examples

Input 1

2 1 3
1 1 3 4 5 6 7 8 1 1
1 0 0
1 1 4 4 5 6 7 8 2 1
1 0 0
1 1 5 4 5 6 7 8 3 1
1 0 0

Output 1

1
4
0

Note 1

Referring to heroes by their IDs:

Round 1:

1. Hero1's turn:
   • Judgment phase: Not in bleeding state, no damage.
   • Recovery phase: Hero1's mana changes 6->6.
   • Attack phase: Selects Hero3, uses first skill.
     • Hero1's mana changes 6->6 (mana cost 0).
     • Hero3's HP changes 5->4.
     • Hero3's toughness changes 4->4.
2. Hero2's turn: Hero2 attacks Hero3, Hero3's HP changes 4->3.
3. Hero3's turn: Hero3 attacks Hero1, Hero1's HP changes 3->2.

Round 2:

1. Hero1 attacks Hero3, Hero3's HP changes 3->2.
2. Hero2 attacks Hero3, Hero3's HP changes 2->1.
3. Hero3 attacks Hero1, Hero1's HP changes 2->1.

Round 3:

1. Hero1 attacks Hero3, Hero3's HP changes 1->0. Hero3 enters the dead state.

At this point, the opponent has no heroes that are not in the dead state, and the game ends.

The final HP values are 1, 4, 0.

Input 2

See ex_2.in and ex_2.ans in the download directory.

Input 3

See ex_3.in and ex_3.ans in the download directory.

Subtasks

For all data, it is guaranteed that $1\leq n\leq 10^{2}, 1\leq m\leq 10^{2}, 1\leq R_{max}\leq 10^{4}$. The number of skills per hero does not exceed 10. All input numbers are within the range $[0, 2^{31}-1]\cap\mathbb{Z}$.

Special Property A: Each hero has only one skill. Special Property B: The toughness damage of all skills is 0, meaning no hero will enter the bleeding state.

Note

This problem can be solved by straightforward simulation, but please avoid overly inefficient methods.

This problem follows the IOI format; you can submit your code and consider corner cases if it does not pass.

Be careful about whether calculations exceed the range of a 32-bit integer.

If you find this problem too tedious, you may want to look at the subsequent problems first.