Fast Fingers Thomas is delivering poutine to Wilson's restaurants!
Fast Fingers Thomas will drive a truck on a directed, weighted graph with vertices. The weight of each edge in the graph is the length of the edge. He has
trips he needs to make.
Each trip has three parameters, a source vertex , a destination vertex
, and a number of days
. Thomas has
days to travel
from vertex
to vertex
. In a given day, Thomas starts at a vertex and traverses a nonnegative number of edges, ending the day at some vertex
(possibly the same one).
Define
to be the smallest value such that, in a single day, the sum of the weights of the edges that Thomas drives on does not exceed
, and subject to this, Thomas can get from
to
in
days. In the event that it's impossible to do this, Thomas does no driving and
is zero.
Constraints
.
All queries are pairwise distinct.
Input Specification
The first line contains a single positive integer, .
The next lines contain
space-separated nonnegative integers. The
th integer in the
th line of this section,
,
indicates the length of the directed edge connecting vertex
to vertex
, or
if no such edge exists. It is guaranteed
there are no self-loops.
The next line contains a single positive integer, .
The next lines each contain three space-separated positive integers,
,
, and
, representing
a query for
.
Output Specification
Output lines. On the
th line, output the answer to the
th query.
Sample Input
3
0 1 2
1 0 1
2 1 0
2
1 3 1
1 3 2
Sample Output
2
1
Comments