Задача №113517. Спираль
Сетка размера (2 n + 1) * (2 n + 1) была построена следующим образом. Номер 1 был помещен в центральный квадрат, номер 2 был помещен справа от него, а следующие числа были помещены вдоль спирали против часовой стрелки.
Ваша задача - рассчитать ответы на q запросов, где запрашивается сумма чисел в прямоугольной области в сетке (по модулю 10 9 + 7 ). Например, в следующей сетке n = 2 а сумма чисел в серой области 74 :
Первая строка ввода содержит два целых числа n и q : размер сетки и количество запросов.
дальше идут q строк, каждая из которых содержит четыре целых числа x 1 , y 1 , x 2 , y 2 , ( - n ≤ x 1 ≤ x 2 ≤ n , - n ≤ y 1 ≤ y 2 ≤ n , ) . Вы должны рассчитать сумму чисел в прямоугольной области с углами ( x 1 , y 1 ) и ( x 2 , y 2 ) .
Вы должны вывести ответ для каждого запроса (по модулю 10 9 + 7 ).
Во всех тестах 1 ≤ q ≤ 100
Подгруппа 1(12 баллов)
1 ≤ n ≤ 1000
Подгруппа 2(15 баллов)
1 ≤ n ≤ 10 9
x 1 = x 2 и y 1 = y 2
Подгруппа 3(17 баллов)
1 ≤ n ≤ 10 5
Подгруппа 4(31 балл)
1 ≤ n ≤ 10 9
x 1 = y 1 = 1
Подгруппа 5(25 балл)
1 ≤ n ≤ 10 9
2 3 0 -2 1 1 -1 0 1 0 1 2 1 2
74 9 14