Baltic Olympiad in Informatics: 2016 Day 1, Problem 3
A grid of size has been constructed as follows. Number has been placed in the center square, number has been placed to the right of it, and the following numbers have been placed along the spiral counterclockwise.
Your task is to calculate answers for queries where the sum of numbers in a rectangular region in the grid is requested (modulo ). For example, in the following grid and the sum of numbers in the gray region is :
Constraints
For all subtasks:
Subtask 1 [12%]
Subtask 2 [15%]
and
Subtask 3 [17%]
Subtask 4 [31%]
Subtask 5 [25%]
Input Specification
The first input line contains two integers and : the size of the grid and the number of queries.
After this, there are lines, each containing four integers , , and . This means that you should calculate the sum of numbers in a rectangular region with corners and .
Output Specification
You should output the answer for each query (modulo ).
Sample Input
2 3
0 -2 1 1
-1 0 1 0
1 2 1 2
Sample Output
74
9
14
Comments