A. Alibaba and Forty Thieves
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the vast and mysterious land of Arabia, the legendary Alibaba discovers a hidden cave filled with treasures beyond imagination. However, the cave holds a strange secret. It stores not only riches but also magical arrays, each locked by a unique pattern. Alibaba, along with his loyal companions, must now figure out how to unlock the secrets of these arrays, using clever tricks and reasoning.

You are given an array $$$A$$$ of $$$n$$$ integers, representing a magic sequence in the cave. Your task is to process $$$Q$$$ queries, which are of two types:

  • Type $$$1$$$ (Add Array): You are given an array $$$M$$$ of length $$$k$$$ that you need to store as a potential magical array. These arrays will later be compared against parts of the main array $$$A$$$.

  • Type $$$2$$$ (Match Occurrences): You are given two indices $$$l$$$ and $$$r$$$. Your goal is to count how many of the stored arrays match the pattern of occurrences of the subarray $$$A[l..r]$$$. An array $$$M$$$ matches if, for each unique element $$$X$$$ in all the arrays including $$$A$$$, the occurrence of $$$X$$$ in $$$A[l..r]$$$ is equal to the occurrence of $$$X$$$ in $$$M$$$.

For example, consider the array $$$A = [1, 2, 3, 3]$$$ and two stored arrays $$$M_1$$$ and $$$M_2$$$:

- $$$M_1 = [2, 3, 1, 3]$$$ — This array matches the subarray $$$A[1..4]$$$.

- $$$M_2 = [2, 3, 1, 3, 5]$$$ — This array does not match.

Input

The first line contains two integers $$$n$$$ and $$$Q$$$ $$$(1 \leq n \leq 10^5, 1 \leq Q \leq 2 \times 10^5)$$$ — the size of the array $$$A$$$ and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \leq a_i \leq 10^9)$$$ — the elements of the array.

The next $$$Q$$$ lines contain queries of one of the following types:

  • Type $$$1$$$ (Add Array): The line contains two integers '$$$1$$$ $$$k$$$' $$$(1 \leq k \leq 10^6)$$$, indicating that the next line contains $$$k$$$ integers $$$b_1, b_2, \dots, b_k$$$ $$$(1 \leq b_i \leq 10^9)$$$. This array $$$M$$$ should be stored for future queries.

  • Type $$$2$$$ (Match Occurrences): The line contains three integers '$$$2$$$ $$$l$$$ $$$r$$$' $$$(1 \leq l \leq r \leq n)$$$.

Note:

  • The sum of $$$k$$$ over all queries doesn't exceed $$$10^6$$$.

  • The total number of distinct integers over ALL arrays does not exceed $$$100$$$.
Output

For each query of type 2, you need to output how many stored arrays match the pattern of occurrences of the subarray $$$A[l..r]$$$.

Examples
Input
10 6
5 1 2 4 1 5 2 1 9 7
1 7
4 1 2 5 2 1 1
2 2 8
1 6
2 5 4 5 1 1
2 1 6
1 6
1 2 1 5 5 4
2 1 6
Output
1
1
2
Input
5 4
1 2 3 4 5
1 3
5 3 4
1 2
4 3
2 3 5
2 3 4
Output
1
1