Description

Rinne gives you a sequence $a_1,a_2,\dots,a_n$. You need to perform $m$ operations in order.

There are two types of operations:

1. Given $l,r,x,y$, change all numbers equal to $x$ among $a_l,a_{l+1},a_{l+2},\dots,a_r$ into $y$.

2. Given $l,r,x,y$, find $i,j$ such that $i,j\in[l,r]$ and $a_i=x,a_j=y$, and require $|i-j|$ to be minimized. Output this minimum value. If there is no solution, output $-1$.

Input Format

The first line contains two positive integers $n,m$, representing the sequence length and the number of operations.

The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$.

The next $m$ lines each contain five positive integers $op,l,r,x,y$. If $op=1$, it is a modification operation. If $op=2$, it is a query operation. The meanings of $l,r,x,y$ are as described in the statement.

Output Format

For each operation with $op=2$, output one line with one integer, representing the answer.

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

0
3
-1

Hint

For $100\%$ of the testdata, $1\leq n,m,a_i,x,y\leq 10^5$, $1\leq l\leq r\leq n$.

This problem has $6$ subtasks, with the following limits:

Subtask $1$ ($1$ point): Guaranteed that for any operation, $l=1,r=n$.

Subtask $2$ ($5$ points): $n,m\leq 50$.

Subtask $3$ ($18$ points): $n,m\leq 2000$.

Subtask $4$ ($7$ points): Guaranteed that $a_i,x,y\in\{1,2\}$.

Subtask $5$ ($29$ points): Guaranteed that when $op=2$, $x=y$.

Subtask $6$ ($40$ points): No special restrictions.

Time limit: $1.5\rm s$

Memory limit: $512\rm MB$

Idea: nzhtl1477, mrsrz.

Solution: mrsrz, nzhtl1477.

Code: mrsrz.

Data: mrsrz.

Background: disangan233, mrsrz.

Translated by ChatGPT 5