Glow, Pixel, Glow!

Time limit2sMemory limit512 MB

Summary

Given horizontal and vertical pulses crossing a grid of wires, count the pixels where current passes through both intersecting wires at the same time.

Level: Hard8 of 10
Topics: Sorting, Implementation, Math, Intervals
Solved: No attempts yet

Problem

An LCD panel is a grid of pixels spaced 1 ALU (Arbitrary Length Unit) apart both horizontally and vertically. Wires run along each row and each column, intersecting at the pixels. Wires are numbered beginning with 1 up to a panel-dependent maximum. The vertical wire numbered 1 lies along the left edge of the panel, and the horizontal wire numbered 1 lies along the bottom edge of the panel.

For a period of time, pulses of current are sent down selected wires. The current flows down the wires at a speed of one ALU per ATU (Arbitrary Time Unit). The pulses themselves have a length measured in ATUs. A pixel activates, and glows, when current is passing through both intersecting wires at the same time. It deactivates when either current is no longer present. If the leading edge of a pulse on one wire reaches the intersection at the exact same time that the trailing edge of a pulse on the other wire leaves that intersection, the pixel is not activated.

All pulses in vertical wires start from the bottom of the grid. All pulses in horizontal wires start from the left of the grid. At most one pulse travels along any one wire.

Given the schedule of pulses to be sent through the wires, determine how many pixels will have been activated by the time all pulses have exited the top and right of the grid.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 2 ∙ 105), which is the number of current pulses.

Each of the next n lines consists of four space-separated parameters, describing a pulse:

d character (d = ’h’, or d = ’v’)
t integer (1 ≤ t ≤ 2 ∙ 105)
m integer (1 ≤ m ≤ 105)
a integer (1 ≤ a ≤ 2 ∙ 105)

where d indicates whether the pulse is horizontal (‘h’) or vertical (‘v’), t is the time at which it starts (i.e., when a horizontal [vertical] pulse crosses vertical [horizontal] wire #1), m is its length, and a is the wire (horizontal or vertical) along which the pulse will travel.

Output

Output a single integer, which is the number of pixels that will have activated by the time the last pulse of current has left the grid.

Examples3

Example 1
Input
```
4
h 1 4 1
v 2 4 2
h 10 2 2
v 11 2 3
```
Expected output
```
2
```

Example 2

Input

Expected output

Example 3

Input

Expected output