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~