After achieving the "Perfectionist ++" achievement in Balatro, the great Balatro sage Clonoth has decided to test your understanding of card games.

Clonoth poses the following problem: Given a deck of $n$ cards, each card has a positive integer from $[1, m]$ written on its front and back. You can choose a subset of cards and flip them. For $1 \le l \le r \le m$, an interval $[l, r]$ is called coverable if there exists a way to flip the cards such that every integer $i$ in $[l, r]$ appears on the front of at least one card. Formally, let the integers on the front and back of the $i$-th card ($1 \le i \le n$) be $a_{i,0}$ and $a_{i,1}$ respectively. Then $[l, r]$ is coverable if and only if there exists a binary string $s$ of length $n$ such that for all $l \le i \le r$, there exists $1 \le j \le n$ satisfying $a_{j,s_j} = i$.

Since the deck changes dynamically during the game, Clonoth has designed a dynamic scenario. Specifically, the deck is initially empty ($n = 0$). Clonoth will then perform $q$ operations, where each operation is one of the following three types:

1. Insert a card: Given positive integers $x, y$ ($1 \le x, y \le m$), let $n \leftarrow n + 1$, and insert a card into the deck with index $n$, front $x$, and back $y$.
2. Remove a card: Given a positive integer $p$ ($1 \le p \le n$), such that the card with index $p$ is currently in the deck, remove that card from the deck.
3. Query: Given positive integers $s, t, u, v$ ($1 \le s \le t \le m, 1 \le u \le v \le m$), you need to find the number of intervals $[l, r]$ such that $s \le l \le t$, $u \le r \le v$, and $[l, r]$ is coverable.

If you can correctly answer all queries, the Balatro sage Clonoth will grant you a precious amulet—"The Glory of the Joker Master"!

Input

Read the data from standard input.

The first line contains two positive integers $m, q$, representing the range of numbers on the cards and the number of operations.

The $(i+1)$-th line ($1 \le i \le q$) contains several positive integers representing the $i$-th operation, where the first positive integer $o$ represents the type of the $i$-th operation.

• If $o = 1$, the line contains three positive integers $o, x, y$, representing the insertion of a card with front $x$ and back $y$.
• If $o = 2$, the line contains two positive integers $o, p$, representing the removal of the card with index $p$.
• If $o = 3$, the line contains five positive integers $o, s, t, u, v$, representing a query.

Output

Output to standard output.

For each query, output a single non-negative integer on a new line, representing the number of intervals that satisfy the requirements.

Examples

Input 1

8 10
1 6 5
3 2 3 8 8
1 3 3
1 4 5
3 2 6 6 8
1 1 2
2 4
1 2 5
3 1 3 2 7
3 2 3 2 3

Output 1

0
2
8
3

Input 2

9 17
1 6 6
3 1 1 3 3
1 5 1
1 3 4
2 2
1 9 9
1 2 2
1 7 9
2 4
1 2 3
3 1 7 3 3
1 8 6
1 7 5
3 6 9 9 9
1 4 5
2 3
3 3 5 2 9

Output 2

0
2
4
16

Subtasks

For all test data, we have: $1 \le m, q \le 2 \times 10^5$; For each operation, $o \in \{1, 2, 3\}$, and the given parameters satisfy the constraints in the problem description.

Special Property A: All card insertion and removal operations occur before all queries. Special Property B: There are no card removal operations. Special Property C: All queries satisfy $s = t$ and $u = v$.