E. Жуулчид

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

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

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

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

Кибер ертөнцөд $1$-ээс $n$ хүртэл дугаарлагдсан $n$ хотууд байдаг. Эдгээр хотуудыг холбосон $m$ ширхэг зам байдаг ба $j$-р зам нь $a_{j}$ ба $b_{j}$ хотуудыг холбодог. Мөн Кибер ертөнцийн хот бүрд жуулчдад зориулсан бэлэг дурсгалын зүйлс зардаг ба $i$ хотод $w_{i}$ үнээр зардаг.

Одоо танд зохицуулах $q$ хүсэлт байгаа ба хүсэлт бүр дараах хоёр төрлийн нэг байна:

  • C a w : $a$ хотын бэлэг дурсгалын үнэ $w$ болж өөрчлөгдсөн.
  • A a b : Одоо жуулчин $a$ хотоос $b$ хотруу аялна. Тэр нэг хотоор хоёр удаа аялахыг хүсэхгүй байгаа ба маршрутаа өөрөө сонгоно. Мөн тэр бэлэг дурсгал хамгийн хямд байгаа хотоос бэлэг дурсгал худалдаж авахыг хүсэж байгаа ($a$ болон $b$ хотоос ч авж болно). Та түүний аяллын туршид худалдаж авч чадах бэлэг дурсгалын боломжит хамгийн бага үнийг олох ёстой.

Маршрутад тавигдах шаардлагууд:

  • Ямар нэг эерэг бүхэл $k$ тооны хувьд $[x_{1}, x_{2}, ..., x_{k}]$ хотуудын дараалал нь маршрут юм.
  • Ямар нэг $1 ≤ i < j ≤ k$-н хувьд $x_{i} ≠ x_{j}$ байна.
  • Ямар нэг $1 ≤ i < j ≤ k$-н хувьд $x_{i}$ ба $x_{i + 1}$-г холбосон зам байна.
  • $min(w_{x_{1}}, w_{x_{2}}, ..., w_{x_{k}})$ бол хамгийн бага үнэтэй маршрут юм.
  • $a$-аас $b$ хүртэлх бүх зөв маршрутуудын хамгийн бага үнэ бүхий утга нь шаардсан хариу юм.

Оролт

Оролтын эхний мөр нь нэг зайгаар тусгаарлагдсан $n, m, q$ ($1 ≤ n, m, q ≤ 10^{5}$) гурван бүхэл тоог агуулна.

Дараагийн $n$ мөрүүд нь $w_{i}$ ($1 ≤ w_{i} ≤ 10^{9}$) бүхэл тоонуудыг агуулна.

Дараагийн $m$ мөрүүд нь зайгаар тусгаарлагдсан $a_{j}$ ба $b_{j}$ ($1 ≤ a_{j}, b_{j} ≤ n, a_{j} ≠ b_{j}$) бүхэл тоон хосуудыг агуулна.

Хотуудын ижил хосуудыг холбосон зам хамгийн ихдээ нэг байна. Аль хоёр хотын хооронд дор хаяж нэг зөв маршрут үргэлж байдаг.

Дараагийн $q$ мөр бүр "C $a$ $w$" эсвэл "A $a$ $b$" ($1 ≤ a, b ≤ n, 1 ≤ w ≤ 10^{9}$) хэлбэрээр хүсэлтийг тодорхойлно.

Гаралт

"$A$" төрлийн хүсэлт бүрийн харгалзах хариуг хэвлэнэ.

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

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

Оролт
3 3 3
1
2
3
1 2
2 3
1 3
A 2 3
C 1 5
A 2 3
Гаралт
1
2
Оролт
7 9 4
1
2
3
4
5
6
7
1 2
2 5
1 5
2 3
3 4
2 4
5 6
6 7
5 7
A 2 3
A 6 4
A 6 7
A 3 3
Гаралт
2
1
5
3

Тэмдэглэл

Хоёр дахь жишээний хувьд боломжит маршрутууд:

$2$-оос $3$ хүртэлх нь $[2, 3]$.

$6$-аас $4$ хүртэлх нь $[6, 5, 1, 2, 4]$.

$6$-аас $7$ хүртэлх нь $[6, 5, 7]$.

$3$-аас $3$ хүртэлх нь $[3]$.

Сэтгэгдлүүдийг ачааллаж байна...