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.
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.
Print the sum of the answers to all the type operations, modulo .
5 1 2 3 2 2 4 1 3 1 4 3 4 1 3 2 3 2 4 1 3
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 .