{"code":"spiral","name":"Xoắn ốc","description":"Một lưới ô vuông kích thước $(2n+1)\\text{ x }(2n+1)$ được xây dựng như sau: Số $1$ sẽ được điền vào ô trung tâm, số $2$ được điền vào ô bên phải của số $1$, và những số tự nhiên tiếp theo sẽ được điền theo một đường xoắn ốc ngược chiều kim đồng hồ.\r\n\r\nNhiệm vụ của bạn là trả lời $q$ truy vấn về tổng của các số được điền trong một hình chữ nhật con của lưới ô vuông xoắn ốc này (theo modulo $10^9+7$). Ví dụ, trong lưới ô vuông dưới đây, $n=2$ và tổng các số trong hình chữ nhật con được tô màu xám là $74$:\r\n\r\n![Hình minh họa][1]\r\n\r\n\r\n  [1]: https://i.ibb.co/WvVxZrT/spiral.png\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên chứa hai số nguyên $n$ và $q$ thể hiện kích thước của lưới ô vuông và số lượt truy vấn.\r\n\r\n- $q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $x_1$, $y_1$, $x_2$ và $y_2$ $\\left(-n\\leq x_1\\leq x_2\\leq n, -n\\leq y_1\\leq y_2\\leq n\\right)$. Bạn cần tính tổng các số trong hình chữ nhật có hai góc đối là $\\left(x_1, y_1\\right)$ và $\\left(x_2, y_2\\right)$.\r\n\r\n#### Output\r\n\r\n- Gồm $q$ dòng, mỗi dòng ghi một số nguyên là câu trả lời cho truy vấn tương ứng (theo module $\\left.10^9+7\\right)$.\r\n####Scoring\r\n- $1\\leq q\\leq 100$.\r\n- $1\\leq n\\leq 10^9$.\r\n- Subtask $1$ ($12\\%$ số điểm): $1\\leq n\\leq 1000$.\r\n- Subtask $2$ ($15\\%$ số điểm): $1\\leq n\\leq 10^9$, $x_1=x_2$ và $y_1=y_2$.\r\n- Subtask $3$ ($17\\%$ số điểm): $1\\leq n\\leq 10^5$.\r\n- Subtask $4$ ($31\\%$ số điểm): $1\\leq n\\leq 10^9$ và $x_1=y_1=1$.\r\n\r\n####Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2 3\r\n        0 -2 1 1\r\n        -1 0 1 0\r\n        1 2 1 2 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        74\r\n        9\r\n        14\r\n        ```","points":600.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}