题目描述

你需要维护一个字符串序列 $\{S_n\}$，其中有 $n$ 个字符串，初始全为空。接下来有 $q$ 次操作，支持两种操作，下面设当前为第 $i$ 次操作，且本题中字符集为 $[1,q]\cap \N_+$：

• 1 l r，表示在所有编号在 $[l,r]$ 内的字符串末尾添加字符 $i$，这里 $i$ 是一个 $[1,q]$ 范围内的整数。
• 2 l r，表示询问所有编号在 $[l,r]$ 内的字符串的最长公共子序列长度。当 $l=r$ 时，我们认为其最长公共子序列长度即为该字符串的长度。

输入格式

第一行两个正整数 $n,q$。

接下来 $q$ 行每行三个正整数形如 1 l r 或 2 l r。

输出格式

对于每次操作 $2$，输出一行非负整数作为你的答案。

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

提示

样例解释

对于第一组样例：
第一次操作后，序列为 $\{[1],[1],[1],[],[]\}$。
第二次操作后，序列为 $\{[1,2],[1,2],[1,2],[2],[2]\}$。
第三次操作，容易发现询问的最长公共子序列为 $[2]$，长度为 $1$。

数据范围

本题采用捆绑测试。

• Subtask 1（10 pts）：$n,q\le 500$。
• Subtask 2（20 pts）：$n,q\le 1000$。
• Subtask 3（15 pts）：$n\le 1000$，操作 $1$ 不超过 $500$ 次，时限 $2000$ms。
• Subtask 4（15 pts）：$n\le 1000$，操作 $2$ 不超过 $500$ 次，时限 $2000$ms。
• Subtask 5（40 pts）：无特殊限制，时限 $3000$ms。

对于 $100\%$ 的数据，$1\le n,q\le 10^5$，除了特殊标明的 Subtask，其它 Subtask 时限均为 $1000$ms。