Description

You need to maintain a sequence of strings $\{S_n\}$, where there are $n$ strings, all initially empty. Then there are $q$ operations, and two types of operations are supported. Let the current operation be the $i$-th one. The character set in this problem is $[1,q]\cap \N_+$:

• 1 l r means appending the character $i$ to the end of every string whose index is in $[l,r]$. Here $i$ is an integer in the range $[1,q]$.
• 2 l r means querying the length of the longest common subsequence of all strings whose indices are in $[l,r]$. When $l=r$, we consider the longest common subsequence length to be the length of that string.

Input Format

The first line contains two positive integers $n,q$.

The next $q$ lines each contain three positive integers in the form 1 l r or 2 l r.

Output Format

For each operation $2$, output one line with a non-negative integer as your answer.

5 3
1 1 3
1 1 5
2 1 4

1

8 8
2 8 8
1 3 8
2 5 8
1 1 8
1 1 1
2 3 5
2 1 7
1 2 7

0
1
2
1

Hint

Sample Explanation

For the first sample:
After the first operation, the sequence is $\{[1],[1],[1],[],[]\}$.
After the second operation, the sequence is $\{[1,2],[1,2],[1,2],[2],[2]\}$.
For the third operation, it is easy to see that the longest common subsequence queried is $[2]$, with length $1$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (10 pts): $n,q\le 500$.
• Subtask 2 (20 pts): $n,q\le 1000$.
• Subtask 3 (15 pts): $n\le 1000$, operation $1$ occurs no more than $500$ times, time limit $2000$ms.
• Subtask 4 (15 pts): $n\le 1000$, operation $2$ occurs no more than $500$ times, time limit $2000$ms.
• Subtask 5 (40 pts): no special restrictions, time limit $3000$ms.

For $100\%$ of the data, $1\le n,q\le 10^5$. Except for the specially marked Subtasks, the time limit for the other Subtasks is $1000$ms.

Translated by ChatGPT 5