The Massey Green club has gone out into the field to plant trees (for bonus marks, of course). The field is a grid with the top-left square labelled . The square
would be located
units to the right of
and
units below
. The grid is infinitely long in the positive
and
axes. The Massey Green club can perform 2 operations:
Plant
trees at position
. It is guaranteed that the Manhattan distance of square
from square
will be less than or equal to
and that
are positive integers.
Find the number of trees on all squares on the diagonal from squares
to
. It is guaranteed that the Manhattan distance of
from square
will be less than or equal to
,
, and
are positive integers.
Input Specification
The first line will contain
, the number of commands you will be given. The next
lines each contain a command as
space-separated integers.
The first integer will be either or
, for the type of operation you will be asked to perform. If the type is
, the next
integers are
in that order. If the type is
, the next 3 integers are
in that order.
Output Specification
Print the sum of the answers to all the type operations, modulo
.
Sample Input
5
1 2 3 2
2 4 1 3
1 4 3 4
1 3 2 3
2 4 1 3
Sample Output
7
Explanation for Sample Output
The first command places 2 trees at the spot . The second command asks you to count the trees between
and
, as marked by the "X"s on the grid. The 2 trees from the first command fall in this area, therefore the answer is
. For the last command, the trees from the first and the third commands fall in the range, therefore the result is
. You should print
.
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
1 | X | |||||
2 | 3 | |||||
3 | 2 | 4 | ||||
4 | X | |||||
5 | ||||||
6 |
Comments
oops
Print the sum of the answers to all the type 2 operations, modulo
. (so
)
I noticed something odd, as I increased my 2D array size, I got more and more cases correct until I hit approx sqrt((256 mb -> bits)/64) as my 2D array...
Wasn't this a CCC question???
You may be thinking of Nutrient Tree.
Not that I know of.