Everyone knows that the dandelion is the undisputed champion of the flower world. Not only is it edible by humans (and nutritious!), but it forms a puffy seedhead that is fun to blow. Often, it takes several blows to make all the seeds fall off. Given the proportion of seeds that remains after the $$$i^{\text{th}}$$$ blow as a fraction $$$\frac{a_i}{b_i} \lt 1$$$, where the number of remaining seeds is rounded down, find the minimum number of blows required to blow varying amounts of seeds into the wind.
More formally, given two sequences of numbers $$$a_1, a_2, ..., a_n$$$, and $$$b_1, b_2, ..., b_n$$$ and $$$q$$$ queries giving an initial number of seeds $$$m \gt 0$$$, find $$$k$$$ such that the sequence $$$c_0, c_1, ..., c_k$$$ where $$$c_0 = m$$$ and $$$c_i = \lfloor c_{i-1} \cdot \frac{a_i}{b_i}\rfloor$$$ satisfies $$$c_{k-1} \gt 0$$$ and $$$c_k = 0$$$. If more than $$$n$$$ blows are required to make all the seeds fall off, output $$$-1$$$.
The first line of input contains $$$n$$$ ($$$1 \le n \le 10^3$$$), the number of blows for which the proportion of seeds that remain is known.
The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \lt 10^9$$$), the numerators of the proportion of seeds that remain after each blow.
The third line contains $$$n$$$ integers $$$b_1, b_2, ..., b_n$$$ ($$$a_i \lt b_i \le 10^9$$$), the denominators of the proportion of seeds that remain after each blow.
The fourth line contains $$$q$$$ ($$$1 \le q \le 10^6$$$), the number of queries.
The fifth line contains $$$q$$$ integers $$$m_1, m_2, ..., m_q$$$ ($$$1 \le m_i \le 10^{18}$$$), the initial seed count for each query.
The output should be $$$q$$$ integers, each on a separate line, the minimum number of blows required to blow all seeds into the wind for each query.
31 3 52 4 631 5 10
1 3 -1
For the first query, $$$1 \rightarrow \lfloor 1 \cdot \frac{1}{2} \rfloor = 0$$$ requires one blow.
For the second, $$$5 \rightarrow \lfloor 5 \cdot \frac{1}{2} \rfloor = 2 \rightarrow \lfloor 2 \cdot \frac{3}{4} \rfloor = 1 \rightarrow \lfloor 1 \cdot \frac{5}{6} \rfloor = 0$$$ requires $$$3$$$ blows.
For the third, $$$10 \rightarrow \lfloor 10 \cdot \frac{1}{2} \rfloor = 5 \rightarrow \lfloor 5 \cdot \frac{3}{4} \rfloor = 3 \rightarrow \lfloor 3 \cdot \frac{5}{6} \rfloor = 2$$$ does not reach $$$0$$$ after $$$n$$$ blows, so the output is $$$-1$$$.
