Flower Sequence Segmentation

Initially, Youxiang chose n flowers from a sunflower field. Each flower has a height \(h_i\) and belongs to a type \(t_i\). The flowers are arranged in a row and are numbered \(1,2,3,\dots,n\).

Youxiang then performs \(m\) operations. There are two types of operations:

• 1 l r x: Consider the flowers in the range \([l, r]\) (1-indexed). From these, select the flowers whose height is not greater than \(x\) (i.e. \(h_i \le x\)). Maintain their relative order as in the original row. Then, partition this filtered sequence into segments according to their type. That is, consecutive flowers of the same type form one segment. For example, the sequence \[ \{1,\; 2,2,\; 1,1,\; 3,\; 4,4,4\} \] is split into 5 segments. You are required to output the number of segments.
• 2 x y: Append a new flower to the end. This new flower has height \(x\) and type \(y\).

Note: This is an online problem, so operations should be processed sequentially.

inputFormat

The input begins with two integers \(n\) and \(m\) representing the initial number of flowers and the number of operations, respectively.

The second line contains \(n\) integers \(h_1, h_2, \dots, h_n\), where \(h_i\) is the height of the \(i\)-th flower.

The third line contains \(n\) integers \(t_1, t_2, \dots, t_n\), where \(t_i\) is the type of the \(i\)-th flower.

Each of the next \(m\) lines represents an operation in one of the following formats:

• 1 l r x
• 2 x y

outputFormat

For each operation of type 1, output a single line with the number of segments in the filtered sequence.

sample

5 4
1 2 3 4 5
1 1 2 2 1
1 1 5 3
1 2 4 4
2 6 3
1 1 6 6

2
2
4