Implement a Quadtree for Geospatial Point Storage and Range Query

Problem: Implement a Quadtree for Geospatial Point Storage and Range Query Design and implement a quadtree data structure to store 2D location points (x, y), which may represent (longitude, latitude) or generic 2D coordinates. Required APIs insert(x, y, data): insert a point with associated data. query(range): given a rectangular boundary, return all points inside the range. Discuss how to handle multiple points with identical coordinates. Discuss tree degeneration, imbalance, and mitigation strategies. Rectangle Definition A rectangle is represented as min_x min_y max_x max_y, including boundary points. Input Format First line: min_x min_y max_x max_y capacity, the root boundary and max capacity per leaf. Second line: integer m, number of operations. Next m lines contain one operation: INSERT x y data QUERY min_x min_y max_x max_y Output Format For every QUERY, print a JSON-style array. Each point is printed as [x, y, data]. Results are sorted by data for deterministic judging. Constraints 1 <= m <= 200000 1 <= capacity <= 100 Coordinates are floating-point numbers. Inserted points are inside the initial boundary. Example Input 0 0 100 100 2 5 INSERT 10 10 a INSERT 20 20 b INSERT 90 90 c QUERY 0 0 50 50 QUERY 80 80 100 100 Output [[10.0, 10.0, "a"], [20.0, 20.0, "b"]] [[90.0, 90.0, "c"]]