More Fantastic Chess Problem
时间限制:C/C++/Rust/Pascal 8秒,其他语言16秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

Grammy is a chess enthusiast as well as a famous mathematician. She likes to study chess tactics in higher-dimensional space.

The movement of every chess piece in k dimensional space is similar to planar ones. All chess pieces must stay inside the board. Note that two of the corners of the board have coordinates  and (a_1,a_2,...,a_k). Detailed movement rules are as follows.


- The King: Choose a non-empty subset of dimensions, add  or subtract to each of the chosen coordinates.
 
- The Queen: Choose a non-empty subset of dimensions and a positive integer , add  or subtract  to each of the chosen coordinates.
 
- The Rook: Choose one dimension and a positive integer , add  or subtract  to that coordinate.
 
- The Bishop: Choose two dimensions and a positive integer , add  or subtract  to each of the chosen coordinates.
 
- The Knight: Choose one dimension, add  or subtract  to that dimension, then choose a different dimension, add  or subtract  to that dimension.
 
- The Pawn: The rule is too difficult, so we do not care about this piece in this problem.


After telling you about the rules, Grammy brought out a huge k dimensional hyper-cuboid chessboard and a chess piece. The size of the board is . She places the chess piece in a particular cell inside the board and asks you to find the number of different cells the piece can arrive in one move. Since the answer may be too large, you only need to output the result modulo .

However, since this problem is still too easy, Grammy then moves the piece q times according to the movement rule of that piece and challenges you to answer the problem after each move.

输入描述:

The first line contains two integers and , indicating the dimension of the board and the number of additional movements.

The second line contains the name of the given chess piece, which is either ``King'', ``Queen'', ``Rook'', ``Bishop'', or ``Knight''.

The third line contains  positive integers , indicating the size of the board.

The fourth line contains  positive integers , indicating the starting position of the given piece.

The following  lines contains the description of the additional movements.

Each description contains numbers, where d denotes the number of moved dimensions.

The first number in the description is , and each of the following d pairs of integers in strictly increasing order of x_i indicates that the x_i-th coordinate of the chess piece changes by in the move.

It is guaranteed that each movement is valid that the chess piece still stay inside the board after each movement, and the sum of d in all movements is no greater than .

输出描述:

Output  lines, each of which contains a single integer, indicating the answer before the first movement and after each movement modulo .
示例1

输入

复制
2 1
King
8 8
1 2
2 1 1 2 1

输出

复制
5
8
示例2

输入

复制
2 1
Queen
8 8
1 2
2 1 2 2 2

输出

复制
21
25
示例3

输入

复制
2 1
Rook
8 8
1 2
1 1 6

输出

复制
14
14
示例4

输入

复制
2 1
Bishop
8 8
1 2
2 1 2 2 2

输出

复制
7
11
示例5

输入

复制
2 1
Knight
8 8
1 2
2 1 1 2 2

输出

复制
3
6