404765: GYM101628 B Battleship

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:

• 1. Place a ship in the map. If the placement of the ship would make it overlap with another, do not place it.
• 2. Sum the number of occupied cells in a segment of a line or column.

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 ≤ 10⁹ and 1 ≤ Q ≤ 10⁵). 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.

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.

5 5 3
1 L 1 1 3
1 C 5 1 3
2 L 1 1 5

4