Stranded

Stranded

You have a graph of $n$ nodes and $m$ edges. Each node either has fuel, or doesn't. At a node with fuel you can refuel any amount of fuel for free. You must answer q queries of the form: what is the minimum fuel capacity with which you can get from node $a$ to $b$.

It is guaranteed that $a$ and $b$ will both be fuel nodes and the graph is connected.

Input Format

The first line is n m. The next line is a binary string of length m, where the i-th digit represents whether the i-th node has fuel. The next m lines are of the form a b c, meaning that there is an edge from a to b of length c. The next line has a single integer q, the number of queries. Finally, the next q lines are of the form x y, representing a query from x to y.

Sample Input 1

7 8
0101100
1 2 5
2 3 7
3 4 10
3 5 3
4 5 4
5 7 10
4 6 8
6 7 2
1
2 4

Sample Output 1

10

Constraints

$n \le 1e5$ $n-1 \le m \le 2e5$