B'Polycarp is developing a new version of an old video game "Pac-Man". Though he really enjoyed playing the original game, he didn 't like some aspects of it, so he decided to alter the rules a bit. In Polycarp 's version, you play as Pac-Man and you have to collect pellets scattered over the game world while avoiding dangerous ghosts (no difference from the original yet). Polycarp didn 't like the fact that there was no escape from the ghosts in the original, so, in his version, the game world is divided into n safe zones with m one-directional pathways between them -- and it is guaranteed that Pac-Man can reach any safe zone from any other. Since safe zones are safe, the ghosts cannot attack Pac-Man while it is there, it is in danger only while traversing the pathways. Pac-Man starts the game in the safe zone s . All pellets are scattered over the safe zones; initially, the i -th safe zone contains a_i pellets (and if Pac-Man is in a safe zone, it may freely collect all the pellets in it). The pellets disappear after being collected, but after the last pellet in the game world is collected, new pellets spawn in the safe zones in the same quantity as before ( a_i new pellets spawn in the i -th zone). The pellets can be respawned any number of times, so the game is essentially infinite. Polycarp has already determined the structure of the game world and the number of pellets in each safe zone. Now he is trying to find out if the game is difficult enough. There are q goals in the game, the i -th goal is to collect at least C_i pellets from the beginning of the game. Polycarp denotes the difficulty of the i -th goal as the minimum number of times the player has to traverse a one-directional pathway in order to collect C_i pellets (since only traversing a pathway puts Pac-Man in danger). If some pathway is traversed multiple times while Pac-Man is collecting the pellets, it is included in the answe'...