### University of Toronto ACM-ICPC Tryouts 2012

## B: Attack of the Bloons

The Bloons (not to be confused with balloons) are attacking! They are attempting to navigate your course of `L` (1 ≤ `L` ≤ 1000) cells, laid out in a row and numbered from 1 to `L`. You don't know what they'll do to you if they manage reach the end, and you don't want to find out! To that end, you've constructed some defensive towers along the course. You might say that this is a Bloons Tower Defense.

There are `N` (1 ≤ `N` ≤ 1000) towers ready to take out any Bloons that get close. The `i`-th tower is located next to cell `C _{i}` (1 ≤

`C`≤ L), and can launch darts at any Bloons that are no more than

_{i}`R`(0 ≤

_{i}`R`≤ 1000) cells away - that is, Bloons in cells

_{i}`C`−

_{i}`R`to

_{i}`C`+

_{i}`R`, inclusive. Every second, it will do

_{i}`D`(1 ≤

_{i}`D`≤ 10

_{i}^{9}) HP worth of damage to any Bloons in this range.

`M` (1 ≤ `M` ≤ 1000) Bloons will attempt to float through your course, one after another. The `i`-th Bloon begins with `H _{i}` (1 ≤

`≤ 10`

`H`_{i}^{9}) HP, and will pop as soon as it has taken at least that much damage in total. Each Bloon starts in cell 1, and moves along the course at a speed of 1 cell per second. If a Bloon moves past cell

`L`, it safely exits the course and can no longer be popped.

There are `T` (1 ≤ `T` ≤ 20) scenarios as described above. For each, you'd like to determine how far along the course each of the `M` Bloons will make it.

### Input

Line 1: 1 integer, `T`

For each scenario:

Line 1: 2 integers, `L` and `N`

Next `N` lines: 3 integers, `C _{i}`,

`R`, and

_{i}`D`, for

_{i}`i`= 1..

`N`

Next line: 1 integer,

`M`

Next

`M`lines: 1 integer,

`H`, for

_{i}`i`= 1..

`M`

### Output

For each scenario:

`M` lines: If the `i`-th Bloon will survive the course, the string "Bloon leakage" (without quotes) - otherwise, 1 integer, the furthest cell which the `i`-th Bloon will reach, for `i` = 1..`M`

### Sample Input

1 10 3 3 3 1 4 0 4 10 2 2 4 1 20 9 11

### Sample Output

1 Bloon leakage 5 8

### Explanation of Sample

The following diagram illustrates which cells each tower can hit:

The first Bloon, having only 1 HP, will go down to the first tower in cell 1.

The second Bloon will manage to clear the course, surviving past cell 10 with 4 HP remaining.

The third Bloon will lose its final HP while at cell 5, having taken 5 damage from the first tower, and 4 from the second.

The final Bloon will survive past cell 6 with 1 HP remaining, but will then go down at cell 8 when it takes 2 damage from the third tower.

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 5.00s

**Memory Limit:** 64M

**Added:** Oct 02, 2012

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

SUPER_ET_DUPERon Feb 23, 2015 - 11:28:05 pm UTC What am I doing wrong?jargonon Feb 24, 2015 - 7:00:58 pm UTC Re: What am I doing wrong?SUPER_ET_DUPERon Mar 03, 2015 - 10:00:58 pm UTC Re: What am I doing wrong?Apparently list[-1] get you the last element in list

Thank you