~X~ by ~Y~ sheet of paper. He has two tools, a pair of scissors and a paper cutter. The paper cutter will always cut the whole sheet (from one end to another). With the scissors though, he can choose how deep to cut the paper. Unfortunately, the paper cutter is set up to only cut vertically, and thus, he will only use the scissors to cut horizontally. Before he actually cuts the paper, he wants to know how many pieces of paper he will end up with after the ~N~ cuts.is doing some arts and crafts. Hypothetically speaking, he is cutting horizontal and vertical lines on a
A piece of paper is freed when all 4 sides of the rectangular area is cut (including the original edges of the paper). He may cut multiple times at the same spot. When this happens, infinitely small pieces of paper will not be created, i.e., the longer cut takes precedence.
Three space separated integers, ~N~, ~X~ and ~Y~.
~N~ lines follow, of the form:
h s da horizontal cut of depth ~d_n~ ~(1 \le d_n \le X)~ starting ~s~ ~(1 \le s < Y)~ above the bottom of the piece of paper.
v sa vertical cut from the top to the bottom starting ~s~ ~(1 \le s < X)~ to the right of the left edge of the sheet.
Subtask 1 [5%]
~0 \le N \le 20~
~1 \le X,Y \le 100~
Subtask 2 [5%]
~0 \le N \le 40\,000~
~1 \le X,Y \le 10^4~
Subtask 3 [90%]
~0 \le N \le 100\,000~
~1 \le X,Y \le 10^9~
Note: fast input may be required.
The number of pieces of paper thatwill end up with after performing the cuts.
3 4 6 h 3 4 h 1 3 v 2
Explanation for Sample Output
The cuts are shown in the picture below. The gold numbers show the pieces of paper.