String Sequence Maintenance and LCS Query

You are given a sequence of n strings \(\{S_n\}\), initially all empty. Then you must process \(q\) operations. The allowed character set is \([1, q] \cap \mathbb{N}_+\). The operations (numbered from \(1\) to \(q\)) are given in order, and the current operation index is used as a character when appending.

There are two types of operations:

1. 1 l r: For all strings with indices in the range \([l, r]\), append the character equal to the current operation index \(i\) (note that \(i \in [1,q]\)).
2. 2 l r: Query the longest common subsequence (LCS) length among all strings with indices in the range \([l, r]\). In particular, when \(l = r\), the LCS length is defined as the length of that string.

Observation: Since the only way to add characters is via the type-1 operation and each operation appends a unique character (the operation index), a character appended in a type-1 operation will appear in a string if and only if the update range of that operation covers that string. Hence, for a query 2 l r, the answer is precisely the number of type-1 operations whose update range \([l', r']\) completely covers \([l, r]\), i.e. \(l' \le l\) and \(r' \ge r\).

inputFormat

The first line contains two integers \(n\) and \(q\) which denote the number of strings and the number of operations, respectively.

Then \(q\) lines follow. Each of these lines is in one of the following formats:

• 1 l r — append the current operation index (as a character) to every string with index in \([l, r]\).
• 2 l r — query the longest common subsequence length among strings with indices in \([l, r]\).

outputFormat

For each operation of type 2, output the answer (the LCS length) on a separate line.

sample

3 5
1 1 2
1 2 3
2 1 2
1 1 3
2 2 3

1
2