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 . 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  indicates that the -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 .

2 1
King
8 8
1 2
2 1 1 2 1

5
8

2 1
Queen
8 8
1 2
2 1 2 2 2

21
25

2 1
Rook
8 8
1 2
1 1 6

14
14

2 1
Bishop
8 8
1 2
2 1 2 2 2

7
11

2 1
Knight
8 8
1 2
2 1 1 2 2

3
6