题目描述

Alex 送给 fy 一个棋盘作为生日礼物，棋盘可以看做 $n\times n$ 的矩阵 $mat$，对于最初状态，$mat_{i,j}=(i-1)\times n+j$。

fy 可以对棋盘的子矩阵做旋转和翻转操作，具体定义见「输入格式」。

Alex 想知道操作之后的矩阵，这样 fy 就会觉得 Alex 很厉害。

输入格式

第⼀⾏两个正整数 $n$ 和 $q$。

接下来 $q$ 行，每一行一个操作：

• T x y l：表示将 $(x,y)$ 为左上角，边长为 $l$ 的正方形顺时针旋转 $90^{\text\degree}$。
• R x y l：表示将 $(x,y)$ 为左上角，边长为 $l$ 的正方形沿左下-右上对角线翻转。

输出格式

由于输出量过⼤，假设 $mat$ 存储着最后的矩阵，通过下列过程对矩阵进⾏ hash：

unsigned int ans=0;
for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++){
        ans^=ans<<13;
        ans^=ans>>17;
        ans^=ans<<5;
        ans+=mat[i][j]+1234567;
}

输出⼀个整数，表⽰最后的 $ans$。可参考下发样例中的 matrix_sample.cpp。

样例

详见下发文件。

数据范围

对于 $10\%$ 的数据，$n\le 300$。

对于另外 $20\%$ 的数据，操作的矩阵不交。

对于另外 $20\%$ 的数据，只有 R 操作。

对于另外 $20\%$ 的数据，只有 T 操作。

对于 $100\%$ 的数据，$1\le n,q\le 2000$。