{"code":"cses1652","name":"CSES - Forest Queries | Truy vấn Khu rừng","description":"Bạn được cho một lưới $n \\times n$ thể hiện bản đồ của một khu rừng. Mỗi ô vuông có thể trống hoặc chứa một cái cây. Ô phía trên bên trái có tọa độ $(1,1)$, và ô phía dưới bên phải có tọa độ $(n,n)$.\r\n\r\nNhiệm vụ của bạn là xử lí $q$ truy vấn dưới dạng: có bao nhiêu cây trong một hình chữ nhật đã cho của khu rừng?\r\n\r\n## Input\r\nDòng đầu vào đầu tiên có hai số nguyên $n$ và $q$: kích thước của khu rừng và số lượng truy vấn.\r\n\r\nKế tiếp, có $n$ dòng mô tả khu rừng. Mỗi dòng có $n$ kí tự: `.` là một ô trống và `*` là một cái cây.\r\n\r\nCuối cùng, có $q$ mô tả các dòng truy vấn. Mỗi dòng có bốn số nguyên $y_1, x_1, y_2, x_2$ tương ứng với các góc của một hình chữ nhật.\r\n\r\n## Output\r\nIn ra số lượng cây trong mỗi hình chữ nhật.\r\n\r\n## Giới hạn\r\n* $1≤n≤1000$\r\n* $1≤q≤2⋅10^5$\r\n* $1≤y_1≤y_2≤n$\r\n* $1≤x_1≤x_2≤n$\r\n\r\n## Ví dụ\r\n### Input:\r\n```\r\n4 3\r\n.*..\r\n*.**\r\n**..\r\n****\r\n2 2 3 4\r\n3 1 3 1\r\n1 1 2 2\r\n```\r\n### Output:\r\n```\r\n3\r\n1\r\n2\r\n```","points":1300.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}