Gas Stations

Xorin was recently elected president in his country and he wants to make travelling from one place to another great again.

His country is rather peculiar, it is composed of N towns placed on a straight line, with a bidirectional road connecting any 2 adjacent ones.

The problem is that not all towns benefit from having a gas station, so travelers must plan in advance for the trip. Each traveler has a car with a given fuel capacity of C litres and any drive to an adjacent town consumes 1 litre of fuel.

When they get to a town which has a gas station, they can fill up the tank to the maximum capacity. Xorin noticed that some people were forced to take the bus because their tank was not large enough for some distances. So he decided that he was going to serve any request coming from the people for gas station construction in additional towns, as long as the proposal consists of a minimal number of gas stations being built.

Xorin's advisor took note of this situation and decided to help the people by telling them what is the minimal number of gas stations that need to be built, starting with the initial configuration, so as to make their trip possible. He now receives a lot of requests of the form A B C, meaning that the traveler wants to get from town A to town B with a tank of capacity C.

The tank is full when the travelers start their journey.


On the first line there is the number of towns N.
On the second line there is an array of N binary digits, without any spaces, where digit i is 1 if town i has a gas station and 0 otherwise.
On the third line there will be an integer Q, representing the number of requests as described above.
The next Q lines contain the requests, in the form of 3 integers A, B, C each, separated by spaces.


Q lines, on line i being the answer to request i, representing the minimal number of gas stations that need to be built in order to make the trip of traveler i possible.


  • 1 ≤ N, Q ≤ 105
  • 1 ≤ C ≤ N
  • 1 ≤ A ≤ B ≤ N
  • Xorin doesn't actually build gas stations for a traveler


1 5 1
1 7 5
1 4 2

The first traveler wants to go from town 1 to town 5. He has a capacity of 1 litre.

In order to arrive at the 5th town, he will travel from 1 to 2, refuel at 2, travel from 2 to 3, refuel at 3, travel from 3 to 4 where he will be stuck as he has an empty reservoir and there is no gas station in 4. If we build a gas station in 4, than our traveler can saftely drive to it's destination, the 5th town.

The second traveler could use the following stategy:

Travel from 1 to 3, refuel and drive all the way from 3 to 7 (by consuming 4 litres).


Sponsors Gold