Hide

Problem BD
Cost of Living

A newspaper columnist recently wrote a column comparing Disneyland’s price increases to other things in the economy; e.g., If gasoline were to have increased at the same rate as Disneyland’s admission since 1990, it would cost $\$ 6.66$ per gallon.

Consider the prices of a number of commodities over a number of consecutive years. There is an inflation rate ($\operatorname {inflation}(x){>}0$) for year $x$ to the next year ($x{+}1$). Also, each commodity $A$ has a modifier ($\operatorname {modifier}(A){>}0$) that is fixed for that commodity. So, for commodity $A$ in year $x{+}1$:

$\operatorname {price}(A,x{+}1)\! =\! \operatorname {price}(A,x)\cdot \operatorname {inflation}(x)\cdot \operatorname {modifier}(A)$

Unfortunately, the modifiers are unknown, and some of the prices and inflation rates are unknown.

Given some inflation rates, the prices for a number of commodities over a number of consecutive years, and some queries for prices for certain commodities in certain years, answer the queries.

Input

Each test case will begin with a line with three space-separated integers $y$ ($1{\le }y\! \le \! 10$), $c$ ($1{\le }c{\le }100$), and $q$ ($1\! \le \! q\! \le \! y{\cdot }c$), where $y$ is the number of consecutive years, $c$ is the number of commodities, and $q$ is the number of queries to answer.

Each of the next $y\! -\! 1$ lines will contain a single real number $r$ ($1.0\! \le \! r\! \le \! 1.5$, or $r\! =\! -1.0$), which are the inflation rates. A value of $-1.0$ indicates that the inflation rate is unknown. The first inflation rate is the change from year $1$ to year $2$, the second from year $2$ to year $3$, and so on. Known inflation rates will conform to the limits specified; unknown but uniquely determinable inflation rates may not, and are only guaranteed to be strictly greater than zero.

Each of the next $y$ lines will describe one year’s prices. They will contain $c$ space-separated real numbers $p$ ($1.0\! <\! p\! <\! 1\, 000\, 000.0$, or $p\! =\! -1.0$), which indicate the price of that commodity in that year. A value of $-1.0$ indicates that the price is unknown.

Each of the next $q$ lines will contain two space-separated integers $a$ ($1\! \le \! a\! \le \! c$) and $b$ ($1\! \le \! b\! \le \! y$), which represent a query for the price of commodity $a$ in year $b$. All queries will be distinct.

All prices that can be uniquely determined will be strictly greater than zero and strictly less than $1\, 000\, 000.0$. Values for prices and inflation rates in the input may not be exact, but will be accurate to $10$ decimal places. All real values contain no more than $10$ digits after the decimal point.

Output

Produce $q$ lines of output. Each line should contain a single real number, which is the price of the given commodity in the given year, or $-1.0$ if it cannot be determined. Answer the queries in the order that they appear in the input. Your answers will be accepted if they are within an absolute or relative error of $10^{-4}$.

Sample Input 1 Sample Output 1
4 2 2
1.3333333333
1.2500000000
-1
3.00 -1
4.00 8.00
5.00 10.00
-1 11.00
2 1
1 4
6.0000000000
5.5000000000

Please log in to submit a solution to this problem

Log in