Problem Statement

There are $N$ sets $S_1, \ldots,S_N$. Initially, all sets are empty.

You are given $Q$ queries in the following formats. Process them in order.

• Type $1$: Given as 1 L R x. For each $S_i$ satisfying $L \leq i \leq R$, add $x$.
• Type $2$: Given as 2 L R x. For each $S_i$ satisfying $L \leq i \leq R$, remove $x$.
• Type $3$: Given as 3 L R. Find the maximum number of elements among $S_i$ satisfying $L \leq i \leq R$, and the number of sets that achieve this maximum.

Constraints

• $1\leq N \leq 3\times 10^5$
• $1\leq Q \leq 3\times 10^5$
• For each query, $1 \leq L \leq R \leq N$.
• For type $1,2$ queries, $1 \leq x \leq 60$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Here, $\mathrm{query}_i$ represents the $i$-th query, and each is given in one of the following formats as shown in the problem statement:

1 L R x

2 L R x

3 L R

Output

Let $q$ be the number of type $3$ queries, and print $q$ lines. The $i$-th line should contain $x,y$ separated by a space, where $x$ is the maximum number of elements and $y$ is the number of sets that achieve this maximum for the $i$-th type $3$ query.