Graphics Design

You are taking a graphics design course, and every student in the class has to finish a final project. The instructor lends out three kinds of items: cameras, camcorders and super computers.

A project consists of several subprojects that the student completes in order. The subprojects are not the same for every student. A subproject may need a camera, a camcorder, a super computer, any combination of these, or no item at all, which gives 8 possibilities. Every subproject also carries a number, its priority.

A subproject is eligible to start when every item it needs is available and the student has finished all of their earlier subprojects. Among the eligible subprojects, the one with the highest priority starts first. The student borrows the items the subproject needs and returns them once the subproject is finished.

After a subproject has started and its items have been borrowed, if some subproject is still eligible, the eligible subproject with the highest priority starts as well. Several subprojects can start at the same moment this way. It is also possible that every unfinished student is waiting for an item, so no subproject starts at that moment. The order of a student's subprojects is fixed: the first subproject comes first, then the second one, and so on, even when the priorities do not decrease along the way.

If a student starts a subproject at time $x$ and the subproject takes $t$ time units, the subproject is finished at time $x + t$ and the student returns the borrowed items then. Those items can be borrowed again at time $x + t$, and the student can start their next subproject at time $x + t$, subject to availability and priority as described above. One camera, camcorder or super computer is used by at most one student at a time. A student whose later subproject has all of its items available still waits when the current subproject is missing an item, because the subprojects are done in order.

For each student, compute the time at which they finish their last subproject.

The first line contains an integer $n$ ($1 \le n \le 1000$), the number of students in the class. The second line contains three integers $a$ ($1 \le a \le 1000$), the number of cameras, $b$ ($1 \le b \le 1000$), the number of camcorders, and $c$ ($1 \le c \le 1000$), the number of super computers. The third line contains $n$ integers $d_1, \dots, d_n$ ($1 \le d_i \le 250$), the number of subprojects each student has to complete.

Then come $d_i$ lines for each student $i$, one line per subproject, in the order that student completes them. Each of these lines contains an integer $t$ ($1 \le t \le 1000000$), the time the subproject takes, an integer $p$ ($1 \le p \le 1000000$), the priority of the subproject, and between zero and three distinct strings. Each of these strings is one of Camera, Camcorder or Computer.

All priorities are distinct.

Print $n$ numbers on one line, separated by single spaces: the time at which each student finishes their last subproject, in the order the students are given in the input.