{"raw_statement":[{"iden":"statement","content":"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.\n\nThis simulator should answer to the following types of query: \n\nWhen 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).\n\nUnfortunately, they are too tired from playing Battleship and asked for your help to implement the simulator.\n\nThe 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.\n\nEach of the following Q lines describe a query. Each description starts with an integer .\n\nIf ship_type = L the ship is placed in a line. Otherwise, its place in a column. (The same is valid for range_type).\n\nAll ships are placed within the map boundaries.\n\nFor each query of type 1, print -1 if it's not possible to place the ship in the given position.\n\nFor each query of type 2, print the quantity of cells which are occupied by a ship in the specified range.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ denote the dimensions of the grid ($1 \\leq N, M \\leq 10^9$).  \nLet $ Q \\in \\mathbb{Z}^+ $ denote the number of queries ($1 \\leq Q \\leq 10^5$).  \n\nLet $ S $ be a set of placed ships, where each ship $ s \\in S $ is a tuple $ (l, c, len, dir) $:  \n- $ l \\in \\{1, \\dots, N\\} $: starting row  \n- $ c \\in \\{1, \\dots, M\\} $: starting column  \n- $ len \\in \\{1, \\dots, 6\\} $: length of ship  \n- $ dir \\in \\{H, V\\} $: direction (Horizontal if $ dir = H $, Vertical if $ dir = V $)  \n\nLet $ R \\subseteq \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ be the set of occupied cells (initially empty).\n\n---\n\n**Constraints**  \n1. All ship placements must lie entirely within the grid:  \n   - If $ dir = H $: $ c + len - 1 \\leq M $  \n   - If $ dir = V $: $ l + len - 1 \\leq N $  \n2. Ships cannot overlap: for any two distinct ships $ s_1, s_2 \\in S $, their cell sets are disjoint.  \n3. Ship length $ len \\leq 6 $ for all type-1 queries.  \n\n---\n\n**Operations**  \nFor each query $ q_i $ ($1 \\leq i \\leq Q$):  \n\n- **Type 1 (Place ship)**: Given $ l, c, len, dir $:  \n  - If the ship can be placed without overlapping existing ships and within bounds, add it to $ S $ and update $ R $.  \n  - Otherwise, output $-1$.  \n\n- **Type 2 (Count occupied cells in range)**: Given $ r_1, r_2, c_1, c_2 $ (rectangular range):  \n  - Output $ |R \\cap \\{r_1, \\dots, r_2\\} \\times \\{c_1, \\dots, c_2\\}| $  \n\n---\n\n**Objective**  \nProcess $ Q $ queries as defined, maintaining consistency of $ S $ and $ R $, and output results for each query of type 1 or 2.","simple_statement":"You are given an N×M grid. Initially empty. Process Q queries:\n\n- Type 1: Place a ship of size L horizontally (if dir=0) or vertically (if dir=1) starting at (x,y). If it overlaps or goes out of bounds, output -1. Otherwise, place it.\n- Type 2: Count how many ship cells are in the rectangle from (x1,y1) to (x2,y2).\n\nOutput -1 for failed placements, or the count for type 2 queries.","has_page_source":false}