The Need for Seed

The Need for Seed is a racing video game set in the fictional Fortune City. You, as a player of the game, need to carry seeds to the farmers by driving your car from one town to another. There are $N$ towns in Fortune City conveniently numbered from $0$ to $N-1$. The towns are connected by $M$ weighted bidirectional roads. Each town has a unique positive integer difficulty level, $diff$. The time taken to go from one town to another can be different. When you drive from town $u$ to town $v$, you will face obstacles if $diff[u] < diff[v]$. The weight of each road denotes the time taken to go from one town to another.

There will be multiple races in the game. In each race, you will start from town $X_i$ and your goal is to reach town $Y_i$. Assume that whenever your car hits an obstacle, you lose all the seeds. So your goal is to reach town $Y_i$ without facing any obstacles. You also want to minimize the time taken to go from town $X_i$ to town $Y_i$.

You need to determine the minimum time required to go from town $X_i$ to town $Y_i$.

Input

Input will start with an integer $T$, denoting the number of test cases.

Each test case will start with 3 space-separated integers $N$, $M$, and $L$, where $N$ denotes the number of towns in Fortune City, $M$ denotes the number of roads connecting them, and $L$ denotes the number of races to be held.

The following line will contain $N$ space-separated integers $diff[0], diff[1], \dots, diff[N-1]$ where $diff[i]$ denotes the difficulty of the $i^{th}$ town.

The next $M$ lines each will contain 3 space-separated integers $u$, $v$, and $w$ indicating that there’s a bidirectional road between the town $u$ and town $v$ with that takes time$w$.

The following $L$ lines each will contain two space-separated integers $X_i$ and $Y_i$, where $X_i$ denotes the starting town and $Y_i$ denotes the goal town for the $i^{\text{th}}$ race.

Constraints

• $1 \leq N \leq 10^5$

• $1 \leq M \leq 10^5$

• $1 \leq L \leq 100$

• $1 \leq diff[i] \leq 10^9$ where $0 \leq i < N$

• $0 \leq u, v < N$

• $1 \leq w \leq 10^9$

• $0 \leq X_i, Y_i < N$ where $0 \leq i < L$

• $1 \leq T \leq 5$

Subtask #1 (40 points): $1 \leq L \leq 20$

Subtask #2 (60 points): Original constraints

Output

For each race, if there exists no path from town $X_i$ to town $Y_i$, print $-1$. Otherwise, print the time taken to reach $Y_i$. Print a newline after the output of each race.

Sample

Input	Output
1 3 3 2 3 2 1 0 1 1 0 2 3 1 2 1 0 2 2 0	2 -1