問題文

虎王国には $1, 2, \ldots, N$ の番号がつけられた $N$ 個の藩と $M$ 個の道があります。 $i$ 番目の道は藩 $A_i$ と藩 $B_i$ を双方向に繋いでおり、通過するのにかかる時間は $C_i$ です。すべての藩の間が道によって行き来可能です。

虎王国では、スタンプラリーが開催されています。 $0, 1, \ldots, K$ の番号がつけられた $K+1$ 個のスタンプが設定されており、はじめスタンプ $i$ は藩 $S_i$ に存在します。 スタンプラリーの目的は、番号の連続したいくつかのスタンプを番号の小さい順に押すことです。

星宮さんは、何回かスタンプラリーを巡ろうとしています。しかし、同時にスタンプの位置の変更も計画されています。

あなたは、 $Q$ 個のクエリに答える必要があります。 $i$ 番目のクエリでは整数 $T_i, X_i, Y_i$ が与えられるので、以下の処理をしてください。

• $T_i = 1$ のとき
  • スタンプ $X_i$ が藩 $Y_i$ に移動される。
• $T_i = 2$ のとき
  • 星宮さんはスタンプ $X_i, X_i + 1, \ldots, Y_i-1, Y_i$ を順に押す。このとき、かかる時間ができるだけ小さくなるように移動する。
  • あなたは、星宮さんがスタンプ $X_i$ を押してからスタンプ $Y_i$ を押すまでにかかる時間を出力する。ただし、スタンプを押すのにかかる時間は無視する。

制約

• $2 \leq N \leq 200$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq K \leq 2 \times 10^5$
• $1 \leq S_i \leq N$
• $1 \leq A_i < B_i \leq N$
• $0 \leq C_i \leq 10^9$
• $i \neq j$ ならば $(A_i, B_i) \neq (A_j, B_j)$
• すべての藩の間が道によって行き来可能
• $1 \leq Q \leq 10^5$
• $T_i = 1$ または $T_i = 2$
• $T_i = 1$ のとき、
  • $0 \leq X_i \leq K$
  • $1 \leq Y_i \leq N$
• $T_i = 2$ のとき、
  • $0 \leq X_i \leq Y_i \leq K$
• 少なくとも $1$ つのクエリで $T_i = 2$

入力

$N\ M\ K$
$S_0\ S_1\ \cdots\ S_K$
$A_1\ B_1\ C_1$
$\vdots$
$A_M\ B_M\ C_M$
$Q$
$T_1\ X_1\ Y_1$
$\vdots$
$T_Q\ X_Q\ Y_Q$

出力

$T_i = 2$ であるような各クエリについて、それぞれ答えを $1$ 行に出力せよ。

サンプル

サンプル1

入力サンプルをコピー

入力

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

出力

11
4
0
10

このケースで与えられるグラフは、上のような見た目をしています。

$1$ つめのクエリでは、星宮さんはスタンプ $0$ から $3$ までを押すために、藩を $1 \to 2 \to 4 \to 2$ という順で巡ります。 このとき、星宮さんが全てのスタンプを押すのにかかる時間は $11$ です。

$2$ つめのクエリでスタンプ $1$ は 藩 $3$ に移動します。よって、 $3$ つめのクエリで星宮さんは藩を $1 \to 3 \to 4$ という順で巡ります。