You are given a snapshot of the implied volatility surface of a single underlying: quotes at a sparse set of strikes and maturities. Each quote is the true implied volatility of the underlying's price process plus independent quoting noise N(0, sigma_q^2). The price process is not disclosed and its parameters vary between test cases. The forward is 1 and rates are zero.

Predict the true implied volatility at a set of query points, given in the same coordinates as the quotes: log-strike k = ln(K / F) and time to maturity T in years. Every query maturity lies within the range of quoted maturities.

Input

The first line contains n, m and sigma_q. Each of the next n lines contains one quote: k, T and the quoted implied volatility. Each of the next m lines contains one query point: k and T. All values have 6 digits after the decimal point.

Output

m real numbers: your predicted implied volatility at each query point, in order.

Scoring

An output is rejected (score 0) unless it has exactly m finite positive values. A prediction y at a query point with true implied volatility sigma scores

s = sigma_q^2 / (sigma_q^2 + (y - sigma)^2)

the ratio of the quoting noise variance to the noise variance plus your squared error. The case score is the mean of s over the query points, and the total score is the mean over the cases.

Constraints

4 to 6 quoted maturities between one week and two years, 5 to 9 quotes per maturity

m = 40 query points: 20 at quoted maturities, 20 at unquoted maturities

0.003 <= sigma_q <= 0.010