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.
All queries are pairwise distinct.
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 lines. On the th line, output the answer to the th query.
3 0 1 2 1 0 1 2 1 0 2 1 3 1 1 3 2