In the recent travel to Foz, the competitors entertained themselves playing Battleship. While discussing the best strategy to win the game, they had the idea of implementing a Battleship simulator.
This simulator should answer to the following types of query:
When the simulator starts, there are no ships placed in the map. All queries of type 1 have its size limited to 6 (which is the maximum ship size available in the game).
Unfortunately, they are too tired from playing Battleship and asked for your help to implement the simulator.
The first line of input contains three integers: N, M, Q (1 ≤ N, M ≤ 109 and 1 ≤ Q ≤ 105). N and M are, respectively, the number of lines and columns in the map.
Each of the following Q lines describe a query. Each description starts with an integer .
If ship_type = L the ship is placed in a line. Otherwise, its place in a column. (The same is valid for range_type).
All ships are placed within the map boundaries.
For each query of type 1, print -1 if it's not possible to place the ship in the given position.
For each query of type 2, print the quantity of cells which are occupied by a ship in the specified range.
## Input
The first line of input contains three integers: N, M, Q (1 ≤ N, M ≤ 109 and 1 ≤ Q ≤ 105). N and M are, respectively, the number of lines and columns in the map.Each of the following Q lines describe a query. Each description starts with an integer . If query_type = 1, then follows ship_type x y size (; 1 ≤ x ≤ M; 1 ≤ y ≤ N; and 1 ≤ size ≤ 6). If query_type = 2, then follows range_type x y size (; 1 ≤ x ≤ M; 1 ≤ y ≤ N; and 1 ≤ size ≤ M if range_type = L, 1 ≤ size ≤ N otherwise). If ship_type = L the ship is placed in a line. Otherwise, its place in a column. (The same is valid for range_type).All ships are placed within the map boundaries.
## Output
For each query of type 1, print -1 if it's not possible to place the ship in the given position.For each query of type 2, print the quantity of cells which are occupied by a ship in the specified range.
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ denote the dimensions of the grid ($1 \leq N, M \leq 10^9$).
Let $ Q \in \mathbb{Z}^+ $ denote the number of queries ($1 \leq Q \leq 10^5$).
Let $ S $ be a set of placed ships, where each ship $ s \in S $ is a tuple $ (l, c, len, dir) $:
- $ l \in \{1, \dots, N\} $: starting row
- $ c \in \{1, \dots, M\} $: starting column
- $ len \in \{1, \dots, 6\} $: length of ship
- $ dir \in \{H, V\} $: direction (Horizontal if $ dir = H $, Vertical if $ dir = V $)
Let $ R \subseteq \{1, \dots, N\} \times \{1, \dots, M\} $ be the set of occupied cells (initially empty).
---
**Constraints**
1. All ship placements must lie entirely within the grid:
- If $ dir = H $: $ c + len - 1 \leq M $
- If $ dir = V $: $ l + len - 1 \leq N $
2. Ships cannot overlap: for any two distinct ships $ s_1, s_2 \in S $, their cell sets are disjoint.
3. Ship length $ len \leq 6 $ for all type-1 queries.
---
**Operations**
For each query $ q_i $ ($1 \leq i \leq Q$):
- **Type 1 (Place ship)**: Given $ l, c, len, dir $:
- If the ship can be placed without overlapping existing ships and within bounds, add it to $ S $ and update $ R $.
- Otherwise, output $-1$.
- **Type 2 (Count occupied cells in range)**: Given $ r_1, r_2, c_1, c_2 $ (rectangular range):
- Output $ |R \cap \{r_1, \dots, r_2\} \times \{c_1, \dots, c_2\}| $
---
**Objective**
Process $ Q $ queries as defined, maintaining consistency of $ S $ and $ R $, and output results for each query of type 1 or 2.