Set and Sequence Query

You are given a sequence \(a_1, a_2,\dots,a_n\) of length \(n\), and initially \(m\) empty sets \(S_1, S_2, \dots, S_m\). There are \(q\) operations. Each operation is one of the following two types:

• 1 l r k: Add all natural numbers from \(l\) to \(r\) (inclusive) to the set \(S_k\), i.e. update \(S_k \gets S_k \cup \{x \mid x \in [l, r] \cap \mathbb{N}\}\).
• 2 l r k: For every index \(i\) with \(l \le i \le r\), count whether \(a_i \in S_k\). Formally, output the value of \(\sum_{i=l}^{r} [a_i \in S_k]\), where \([P]\) equals 1 if the predicate \(P\) is true, and 0 otherwise.

You need to process all operations in order. For each operation of type 2 output its answer on a new line.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) --- the length of the sequence, the number of sets, and the number of operations, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the sequence.

The following \(q\) lines each contain an operation in one of the two formats described above.

outputFormat

For each operation of type 2, output a single integer --- the result of the query. Each answer should be printed on a new line.

sample

7 3 6
1 3 5 7 9 11 3
1 2 3 1
2 1 4 1
1 5 9 3
2 3 7 3
1 1 11 2
2 1 7 2

1
3
7