Magic Suitcase

Time limit1.5sMemory limit1024 MB

Summary

Given n values, apply m swaps of equal-length segments and answer how many values in a segment lie between a and b.

Level: Hard8 of 10
Topics: Array, Sorting, Binary search, Divide and conquer
Solved: No attempts yet

Statement

Newt Scamander's suitcase holds $n$ magical animals and the same number of compartments. The compartments are numbered from 1 to $n$ . Each compartment holds exactly one animal. Every creature has a danger level $t$ . The animals are very active. They dislike staying in one place, so they keep swapping positions inside the suitcase.

A group of consecutive animals in compartments $l$ through $r$ is called a segment.

During $m$ minutes, two types of events happened:

Two non-overlapping segments of equal length trade places. Segment $l_1$ to $r_1$ is swapped with segment $l_2$ to $r_2$ . Formally, for each $i$ from $l_1$ to $r_1$ , the animal in compartment $i$ swaps with the animal in compartment $i - l_1 + l_2$ .
A zoologist asks how many animals in segment $l$ to $r$ have a danger level $t$ with $a \le t \le b$ .

Input

The first line contains $n$ and $m$ , the number of compartments and the number of queries ( $1 \le n \le 10^6$ ; $1 \le m \le 2 \cdot 10^3$ ).

The second line contains the sequence $t_i$ of length $n$ , the danger levels of the animals ( $1 \le t_i \le 10^9$ ).

Each of the next $m$ lines starts with $type$ , the query type ( $1 \le type \le 2$ ).

If $type = 1$ , four numbers $l_1$ , $r_1$ , $l_2$ , $r_2$ follow, describing a swap. The segments do not overlap and have equal length ( $1 \le l_1 \le r_1 \le n$ , $1 \le l_2 \le r_2 \le n$ ).

If $type = 2$ , four numbers $l$ , $r$ , $a$ , $b$ follow, describing a zoologist's query ( $1 \le l \le r \le n$ , $1 \le a \le b \le 10^9$ ).

Output

For each query of type 2, print the number of animals that match.

Examples2

Example 1
Input
```
3 2
1 2 3
1 1 1 3 3
2 2 3 1 2
```
Expected output
```
2
```

Example 2

Input

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

Expected output

2
3