Intersection#411
It is known that a bypass highway is being constructed in Metropolis. This highway is not a ring road, meaning it has distinct western and eastern ends (though this might change in the future). The most intriguing engineering features of this road are the bridges. Clearly, a reinforced concrete bridge is too costly for a section with only one car per day, while a wooden bridge cannot accommodate a highway with a dozen cars per minute. Therefore, to design bridges appropriately, it is essential to know how many cars will pass over them.
The road will primarily use «cloverleaf» interchanges; a diagram of such an interchange is shown in the figure. According to this scheme, a car turning right does not go over the bridge, a car turning left (which in this interchange turns degrees to the right and crosses its path on the second level) always goes over the bridge, and a car going straight may or may not go over the bridge, depending on the direction of travel.
The flow of cars on roads intersecting the bypass road has been studied. The task is to calculate the flow of cars that will travel over the bridges of the bypass road. It should be noted that for some intersections, the bypass road runs on the ground and the bridge contains the crossroad—such bridges should not be counted. Although the road is two-way, each test examines only one direction of the bypass road (for example, from west to east).
The first line of the input contains the number of tests.
The first line of each test contains the number N \leq 100—the number of intersections, listed from west to east.
The next lines provide information about the type of crossing, followed by the flow of the crossroad. The type of crossing is indicated by a Latin letter: means the bypass road runs at ground level and the crossroad runs over the bridge; means the crossroad runs at ground level and the bypass road runs over the bridge. Then numbers are given, indicating the number of cars that left the bypass road: the first number is for those turning left, the second for those turning right. Then another numbers are given, indicating the number of cars entering the bypass road: the first number for those turning left, the second for those turning right. For any crossroad, the number of cars does not exceed 10^9.
The input data is guaranteed to be correct (initially, there are no cars on the highway; the number of cars leaving the highway is equal to the number entering it; the eastern intersection point is located after the western intersection).
For each test, the output should contain one line with numbers—the car flows on the bridges of the bypass road. If the bypass road runs on the ground and the bridge is above it, output .
Example 1