Vasya

Time limit2sMemory limit1024 MB

Summary

Check whether a recorded rooftop walk is valid, simulating jumps and moves, and report the final building or the first failing action.

Level: Medium4 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Statement

The city of Flatburg is celebrating. At last the city has its own King Kong, named Vasya. In his first week in Flatburg, Vasya chose one of the central streets, where all the buildings stand on one straight line. He likes best to walk across the rooftops along the street.

Vasya can move from the roof of a building of height $h_1$ to an adjacent building of height $h_2$ that is not taller, if $0 \le h_1 - h_2 \le d$ .

Vasya always carries a huge bamboo pole of length $l$ meters. With the pole, he can climb onto an adjacent building whose height $h_2$ exceeds the height $h_1$ of his current building by at most $l$ . After that, a piece of the pole of length $h_2 - h_1$ always breaks off.

Sometimes Vasya jumps on rooftops. If he jumps on the roof of building $i$ , its height decreases by $a_i$ , and the height of every other building increases by $b_i$ . If a building is trampled into the ground (its height becomes non-positive), Vasya will not jump on it anymore, since that is not interesting.

Recently the residents of Flatburg gave Vasya a birthday story about one of his walks, from the roof of the first building to the roof of the $n$ -th building. Vasya doubts the story is factual. He asks you to check whether he could have walked from the roof of building 1 to the roof of building $n$ exactly as the story describes.

Input

The first line contains integers $n$ , $d$ , and $l$ , where $1 \le n \le 2000$ and $0 \le d, l \le 10^9$ . Each of the next $n$ lines contains three integers $h_i$ , $a_i$ , and $b_i$ : the initial height of building $i$ , the amount its height drops when Vasya jumps on it, and the amount it rises when Vasya jumps on another building. It is given that $0 < h_i, a_i, b_i \le 10^9$ .

The remaining lines of the input contain the story. Each action in the story is written in one of these forms:

'Vasya jumps on building $i$ ' describes a jump on building $i$ .
'Vasya moves from building $i$ to building $j$ ' describes a move from building $i$ to building $j$ . It is guaranteed that $|i - j| = 1$ .

The story is at most 100 kilobytes. Each line has at most 1000 characters. The story uses only Latin letters and digits. Any two adjacent words are separated by exactly one space or a line break.

Output

If the story contains an error, meaning Vasya cannot perform some described action, print 'ERROR' on the first line. On the second line, print $i$ , the number of the first action Vasya could not perform.

Otherwise, print the number of the building where Vasya is at the end of the story.

Examples3

Example 1

Input

2 1 1
1 1 1
5 5 5
Vasya moves from building 1
to building 2

Expected output

ERROR
1

Example 2

Input

3 1 10
11 3 4
21 7 2
5 2 2
That wonderful summer morning Vasya decided to have a walk
After drinking a cup of tea Vasya moves from building 1
to building 2 then Vasya jumps on building 2 then
he jumps on building 2 Vasya jumps on building 2
And he jumps and jumps and jumps
Vasya moves from building 2 to building 3

Expected output

ERROR
4

Example 3

Input

3 1 10
11 3 4
21 7 1
5 2 2
That wonderful summer morning Vasya decided to have a walk
After drinking a cup of tea Vasya moves from building 1
to building 2 then Vasya jumps on building 2 then
he jumps on building 2 Vasya jumps on building 2
And he jumps and jumps and jumps
Vasya moves from building 2 to building 3

Expected output