A trend over any window

regression prefix sums binary search analytics

A climate archive holds a series of yearly mean temperatures: the year x_i and the temperature y_i in tenths of a degree. The years increase, but with gaps: during a war, when the station was moved, because of lost logbooks; the oldest records are reconstructed from indirect data and go far back before the Common Era (such years are negative).

Researchers ask questions of the form “what is the trend from year A to year B?”. The answer is the slope of the line drawn by least squares through all measurements with A ≤ x_i ≤ B. The temperature is in tenths of a degree and the time in years, so the slope comes out in tenths of a degree per year, that is, exactly in degrees per ten years. If fewer than two measurements fall into the window, no line can be drawn.

There are many questions, and they need answering quickly. One of the tests is the real yearly mean temperatures of Almaty from 1941 to 2025 (the ERA5 reanalysis) and all windows of ten years or longer.

Input

The first line holds the number n (1 ≤ n ≤ 50,000). Each of the next n lines holds two integers x_i and y_i (|x_i| ≤ 50,000, |y_i| ≤ 1000), the years strictly increasing. Then comes the number of questions q (1 ≤ q ≤ 100,000) and q lines with integers A and B (−50,000 ≤ A ≤ B ≤ 50,000).

Output

For each question, a line with the slope of the line, or the symbol - if the window has fewer than two measurements. A slope is accepted if it differs from the correct one by at most 10⁻⁶ (for numbers greater than one in absolute value, by at most 10⁻⁶ of their size).

Examples

Example 1

Input

Output

1.538759690
1.900000000
7.000000000
-
-
7.000000000
3.500000000

Limits

Time · Python: 6000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

For one window everything is clear: find its measurements and draw a line by the formula from the article. But there are up to a hundred thousand windows, and each may cover almost the whole series. What does the formula actually need from the series? Not the points themselves, but a few numbers about them. Which ones?

2Hint 2

Expand the brackets in the slope formula: Σ(x − x̄)(y − ȳ) = Σxy − Σx·Σy/m, and likewise for Σ(x − x̄)². Four sums and the number of points remain. And a sum over a stretch of a series can be computed in O(1).

3Hint 3

A window is given by years, not by measurement numbers. The years are sorted: how do you quickly find the first measurement no earlier than A and the last no later than B?

4The idea

The slope of the least-squares line depends on just five numbers: m, Σx, Σy, Σxy, Σx². Multiplying the numerator and denominator of the formula by m², we get

$$b = \frac{m\sum xy - \sum x \sum y}{m\sum x^2 - \bigl(\sum x\bigr)^2}.$$

All four sums add up, so they are stored as prefix sums: the sum over measurements numbered lo to hi − 1 is the difference of two prefixes. The window’s bounds in years are found by binary search. It is the same thought as in the article: regression needs not the rows but their sums, and a window’s sums are assembled from ready pieces.

5Walkthrough

Go over the series once and build four arrays of prefixes. For a question (A, B) find by binary search lo, the first measurement with x ≥ A, and hi, the first with x > B; the window has m = hi − lo measurements. If m < 2, print a dash. Otherwise take the differences of prefixes and divide by the formula.

For m ≥ 2 the denominator is strictly positive: it equals m²·(the variance of the years), and the years are distinct. The numerator and denominator are integers. In Python they are exact by themselves. In Go, estimate their size: |Σx| ≤ 5·10⁴ · 5·10⁴ = 2.5·10⁹, its square 6.25·10¹⁸; m·Σx² ≤ 5·10⁴ · 1.25·10¹⁴, the same. That is below the int64 limit of 9.2·10¹⁸, so compute the numerator and denominator exactly and divide once. The fifth test is built right at this bound.

On the real Almaty data the answers match the table in the article: the window 1941–2025 gives 0.122, the window 1976–2025 0.494 (these are degrees per ten years). For 1941–1975 it is −0.714 here, not −0.72 as in the article: in the problem the yearly means are rounded to tenths of a degree.

5+Solution

6Complexity

O(n) for the prefixes and O(log n) per question: O(n + q log n) in all. The brute-force solution is O(n·q), up to 5·10⁹ steps.

7Common mistakes

Each question over its window from scratch. Correct, but the fourth test with a hundred thousand wide windows will not fit in the time limit in any language.
Prefixes in floating point and the formula through a difference. Here it usually gets away, but the habit is dangerous: mΣx² and (Σx)² are two large close numbers, and with years far from zero their difference in float64 loses correct digits. While the data is integer, compute in integers.
Overflow in 32-bit integers. Σx² over fifty thousand years alone is up to 10¹⁴.
A window of one year. One point does not define a line: the denominator is zero. A dash, not a division by zero.
The bounds of the binary search. Year B belongs to the window: you need the right bound “first year greater than B”, not “not less than”.

Algorithms behind it

ML Algorithm Linear regression Picks a model’s coefficients so that the sum of squared misses over the data is smallest. O(n·d² + d³) 2 problems TEC Technique Prefix sums The sum of any segment in O(1) after one pass; the two-dimensional version gives the sum of any rectangle of a picture. O(n) to build, O(1) per query 2 problems