Problem Description

You are given a sequence $a_{1\sim n}$ of length $n$. There are $q$ operations. Initially, there are $m$ empty sets $S_{1\sim m}$. There are two types of operations, as follows:

• 1 l r k: Add $l\sim r$ into set $S_k$, i.e., $S_k\gets S_k\cup\{x|x\in[l,r]\cap \N\}$.
• 2 l r k: Query, among all $a_i$ for $l\le i\le r$, how many are in set $S_k$, i.e., query $\displaystyle\sum_{i=l}^r[a_i\in S_k]$.

Input Format

All inputs are non-negative integers.

The first line contains $3$ numbers $n, q, m$.
The second line contains $n$ numbers, where the $i$-th number denotes $a_i$.
The next $q$ lines each contain $4$ numbers, describing one operation.

Output Format

All outputs are non-negative integers.

For each operation of type 2, output one line with the answer.

5 10 2
5 4 3 2 1
2 1 5 1
2 1 5 2
1 2 3 1
1 2 3 2
2 1 4 1
2 1 4 2
1 1 4 1
1 1 4 2
2 1 5 1
2 3 5 2

0
0
2
2
4
3

Hint

Constraints

For $100\%$ of the testdata, $1\le n,q\le 10^6$, $1\le m\le 10^9$, $1\le a_i\le 10^9$.

In operation 1, $1\le l\le r\le 10^9$. In operation 2, $1\le l\le r\le n$. In all operations, $1\le k\le m$.

No $\text{Subtask}$ reaches the maximum values of all constraints. Each $\text{Subtask}$ has its own limits. Please read the constraints table.

The input file of this problem is large. Please use an appropriate input method.

Late at night, Touma Kamijou's phone made the sound of receiving a message. Then, he came to the place written in the email: the iron bridge in District 7.

When Kamijou arrived, the sender had already been waiting there.

"Misaka...?"

"The thing you forgot."

As she spoke, she threw something over. Kamijou caught it with one hand and found it was a Gekota phone charm. This should have been lost when he sank into the Arctic Ocean. The strap used to tie it to the phone had been shattered back then, but now it had been replaced with a strap of another color.

"I finally managed to find it. Don't lose it again."

"Sorry."

Kamijou thanked her and tied it to his phone again.

Seeing that, Mikoto smiled slightly.

It was an expression as if she had finally restored something to the way it should be, and let out a sigh of relief.

"I figure a guy like you won't stay in one place forever... Next, are you going somewhere again?"

"Pretty much."

Kamijou sighed.

"Honestly, even though I look calm, I'm actually totally confused about what exactly is happening. I only know the name of the one behind it. But this disturbance has already spread to Academy City, and I, who am investigating Academy City, got dragged into it. The Academy City I'm investigating got dragged in as well... so I can't just ignore it."

It seemed Mikoto had only come to deliver the charm. Kamijou put his phone into his pocket.

Since there was no topic left, they could only part ways.

"Goodbye." Kamijou said.

He turned his back to Mikoto and was about to leave the iron bridge,

about to leave this Academy City built on scientific common sense, and stride into the outside world. But the boy's hand was grabbed by Mikoto.

Firmly, tightly, she held onto the boy who wanted to drift away.

By Kamijou's motionless ear, Mikoto's voice came.

"But this time, you won't be alone."

Translated by ChatGPT 5