E. Гукиз ба Гукизиана

хугацааны хязгаарлалт 10 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Профессор Гукиз дахиад л массивуудаар тоглож байгаа ба санамсаргүйгээр Гукизиана хэмээх шинэ функц нээжээ. $1$-ээс $n$ хүртэл дугаарлагдсан өгөгдсөн $a$ массив болон $y$ тооны хувьд $GukiZiana(a, y)$ нь $a_{j} = a_{i} = y$ байх $(j - i)$-ийн хамгийн их утгыг илэрхийлнэ. Хэрвээ $a$ массивын аль ч элемент $y$-тэй тэнцүү биш бол $GukiZiana(a, y) = -1$ байна.

Гукиз танд даалгавар бэлдсэн бөгөөд энэ удаад танд хоёр төрлийн хүсэлт байна:

  1. Эхнийх нь "$1$ $l$ $r$ $x$" хэлбэрийн хүсэлт ба $l ≤ i ≤ r$ байх бүх $a_{i}$-г сөрөг биш бүхэл $x$ тоогоор нэмэгдүүлнэ.
  2. Хоёр дахь нь $2$ $y$ хэлбэрийн хүсэлт ба $GukiZiana(a, y)$-ийн утгыг олох ёстой.

$2$-дугаар төрлийн хүсэлт бүрийн хариуг хэвлэж Гукизыг баярлуулаарай!

Оролт

Эхний мөрөнд $a$ массивын хэмжээ болон хүсэлтүүдийн тоог илэрхийлэх $n$, $q$ ($1 ≤ n ≤ 5 \cdot 10^{5}, 1 ≤ q ≤ 5 \cdot 10^{4}$) бүхэл тоонууд байна.

Хоёр дахь мөрөнд $a$ массивыг бүрдүүлж буй $n$ ширхэг $a_{1}, a_{2}, ... a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) бүхэл тоонууд байна.

Дараагийн $q$ мөр бүрт дээр тодорхойлсон хэлбэрийн дөрөв эсвэл хоёр ширхэг тоонууд байна:

Хэрвээ тухайн мөр нэгийн тоогоор эхэлж байгаа бол $1$ $l$ $r$ $x$ ($1 ≤ l ≤ r ≤ n$, $0 ≤ x ≤ 10^{9}$) хэлбэрийн буюу нэгдүгээр төрлийн хүсэлт.

Харин $2$-ын тоогоор эхэлж байгаа бол $2$ $y$ ($1 ≤ y ≤ 10^{9}$) хэлбэрийн буюу хоёрдугаар төрлийн хүсэлт.

Гаралт

$2$-дугаар төрлийн хүсэлт бүрийн $y$ утгын хувьд $GukiZiana(a, y)$-ийн утгыг хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
4 3
1 2 3 4
1 1 2 1
1 1 1 1
2 3
Гаралт
2
Оролт
2 3
1 2
1 2 2 1
2 3
2 4
Гаралт
0
-1
Сэтгэгдлүүдийг ачааллаж байна...