QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB
[-1]

# 3003. Cost of Living

Statistics

Problem Description

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 (inflation(x)>0) for year x to the next year (x+1). Also, each commodity A has a modifier (modifier(A)>0) that is fixed for that commodity. So, for commodity A in year x+1:

price(A,x+1)=price(A,x)inflation(x)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 (1y10), c (1c100), and q (1qyc), 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 y1 lines will contain a single real number r (1.0r1.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 (1ac) and b (1by), 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 104.

Sample

Sample Input

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

Sample Output

6.0000000000
5.5000000000