You have a row of boxes, numbered $1, 2, 3, \dots, n$ from left to right. You can perform four types of instructions:

• 1 X Y: Move box $X$ to the left of box $Y$ (if $X$ is already to the left of $Y$, ignore this instruction).
• 2 X Y: Move box $X$ to the right of box $Y$ (if $X$ is already to the right of $Y$, ignore this instruction).
• 3 X Y: Swap the positions of box $X$ and box $Y$.
• 4: Reverse the entire chain.

The instructions are guaranteed to be valid, meaning $X \neq Y$. For example, when $n=6$, starting from the initial state and executing 1 1 4, the sequence of boxes becomes $2, 3, 1, 4, 5, 6$. Next, executing 2 3 5, the sequence becomes $2, 1, 4, 5, 3, 6$. Then, executing 3 1 6 results in $2, 6, 4, 5, 3, 1$. Finally, executing 4 results in $1, 3, 5, 4, 6, 2$.

Input

The input contains no more than 10 test cases. Each test case starts with a line containing the number of boxes $n$ and the number of instructions $m$ ($1 \le n, m \le 100,000$), followed by $m$ lines, each containing one instruction.

Output

For each test case, output one line containing the sum of the box numbers at all odd positions. Positions are numbered $1$ to $n$ from left to right.

Examples

Input 1

6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4

Output 1

Case 1: 12
Case 2: 9
Case 3: 2500050000