You are given a treasure map. The map looks like a matrix with integers written over it. You don’t know where the treasure is. Since the map is too big, you can’t take a look at all of it at once. You select a sub-matrix and analyze it. The sum of all integers that lie on the middle row and column gives you the coordinates of the next clue.

The matrix A is indexed from $[1..N][1..N]$, where N is the size. You are given L queries, each query describing a sub-matrix by the coordinates of its top left and bottom right corner. There are 2 types of queries :

F $x1$ $y1$ $x2$ $y2$ : For this type of query, find the sum of elements that lie on the plus mark formed by the middle row and column of the submatrix having top-left co-ordinates $(x1, y1)$, and bottom-right co-ordinates $(x2, y2)$.

C x y k : Change the element at $(x, y)$ to k.

Input Format

First line has two integers N and L, which represents the size of the matrix and number of queries respectively.

To avoid large input, instead of giving the matrix, 3 integers $a, b, c$ will be provided to you on the next line. Calculate the matrix values using the following pseudo code.

void func(int a, int b, int c)
{
    int num = a
    int M = 1000000007

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            A[i][j] = num
            num = (num*b+c)%M
        }
    }
}

Next line contains the integer L , the number of queries.

Next L lines contain L queries, which are either of the 2 types mentioned in the problem statement.

Constraints :

$1 ≤ N ≤ 2000$
$1 ≤ L ≤ 500000$
$x1 ≤ x2$ and $y1 ≤ y2$
$1 ≤ K ≤ 10^9$

It is guaranteed that $(x2-x1)$ and $(y2-y1)$ are even.

Output Format

For each query of type F, output one line with one integer, the sum of integers lying on the plus mark of the submatrix.

Note: The input/output files can be really large. Prefer scanf/printf over cin/cout.