Electi Robot - KhIMIO

Some vertices are equipped with battery chargers. A robot that is currently at a charger vertex may instantly recharge its battery back to full capacity (i.e., to $b_i$). It is guaranteed that both $U_i$ and $V_i$ are charger vertices for every robot $i$.

A robot moves along edges one by one. Traversing an edge $e$ consumes $w_e$ units of its current battery. A robot may only traverse an edge if its current battery level is at least $w_e$ at that moment. Robots may visit vertices and edges multiple times and may recharge any number of times at charger vertices. Robots act independently (no interference or congestion).

For each robot $i$ $(1 \le i \le Q)$, determine the minimum battery capacity $b_i^\star$ such that robot $i$ can start at $U_i$ with a full battery, follow some route that respects the energy and recharge rules, and arrive at $V_i$.

Input Format

• The first line contains one integer $T \ (1 \leq T \leq 10^3)$, the number of tests.

  • Then, for each test:

    • The first line contains three separated integers $N, M, Q \ (1 \leq N, M, Q \leq 2 \cdot 10^5)$.
    • The second line contains $N$ integers $c_1, c_2, \ldots, v_N$. If $$, then there is battery charger at vertex . Otherwise .
    • Then, $M$ lines follow, the description of the graph. Each line consists of three separated integers $x_i, \ y_i, \ w_i$ ($$, ), description of edge . There is edge between vertex and in the graph with length . The graph might contain multiple edges.
    • Then, $Q$ lines follow, description of the queries. Each line consists of two separated integers $U_i, V_i$ ($1 \leq U_i, V_i \leq N$.

It is guaranteed, that the graph is connected.

Constraints

• The total sum of $N$ in all tests doesn't exceed $2 \cdot 10^5$
• The total sum of $M$ in all tests doesn't exceed $2 \cdot 10^5$
• The total sum of $Q$ in all tests doesn't exceed $2 \cdot 10^5$

Output Format

For each test, and for each query print the minimum capacity battery required.

Scoring

Let $S_N$ be the sum of $N$ in all tests.
With the same logic, let $S_M, S_Q$ be the sums of $M$ and $Q$ respectively.