407432: GYM102788 J Multidimensional Points

The distance between points $$$a = (a_1, a_2, \dots, a_n)$$$ and $$$b = (b_1, b_2, \dots, b_n)$$$ in an $$$n$$$-dimensional space is determined according to the Euclidean metric: $$$$$$dist(a, b) = \sqrt{(a_1-b_1)^2 + (a_2-b_2)^2+ \dots + (a_n-b_n)^2}.$$$$$$ Some optimization tasks require calculation of partial distance between points – only for coordinates with indices within a certain range $$$[i, j]$$$: $$$$$$dist(a, b, i, j) = \sqrt{(a_i-b_i)^2 + (a_{i+1}-b_{i+1})^2 + \dots + (a_j-b_j)^2}.$$$$$$ Such calculations can be performed multiple times. Write a program that will efficiently calculate partial distance based on given points.

The first line contains a single positive integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ – the number of dimensions in the space. The second and third line contain $$$n$$$ positive integers separated by spaces – coordinates of points $$$a$$$ and $$$b$$$ $$$(-1000 \leq a_i, b_i \leq 1000)$$$, respectively. The fourth line contains the number $$$m$$$ $$$(1 \leq m \leq 10^6)$$$ – the number of partial distance calculations. Each of the following $$$m$$$ lines contains two positive integers $$$i$$$ and $$$j$$$ $$$(1 \leq i \leq j \leq n)$$$ separated by a space, setting the limits of the interval for the calculations.

The output file consists of $$$m$$$ lines. Each of the lines contains a real number accurate to the third decimal place – calculated partial distance. The distances must be printed in the same order as the order of intervals in the input file.

5
1 2 3 4 5
1 1 2 1 1
1
4 5

5.000000