Ana y Bruno han decidido comprar casas en Centrolandia (una para cada uno). Debido a que son amigos desde el preuniversitario, quieren comprar sus casas en la misma calle.

En Centrolandia, las casas de cada calle están convenientemente enumeradas desde ~1~ hasta ~10^9~. La casa ~i~ tiene una belleza de ~a_i~, y la belleza de la casa ~i~ es igual a la diferencia entre la belleza de la casa ~i-1~ y la belleza de la casa ~i-2~ (es decir, ~a_i = a_{i-1} - a_{i-2}~).

Ana y Bruno están interesados en la belleza que tendrá la carretera entre sus casas, y por eso analizan cuidadosamente ~q~ calles independientes de las cuales solo conocen la belleza de las dos primeras casas ~a_1~ y ~a_2~, y las dos casas disponibles ~l~ y ~r~.

La belleza de la carretera en una calle entre la casa ~x~ y la casa ~y~ se puede calcular como la suma de la belleza de las casas en el intervalo ~[x,y]~ (es decir, ~\sum_{i=x}^{y} a_i~).

Tu tarea es ayudar a Ana y Bruno a encontrar la belleza de la carretera entre las casas ~l~ y ~r~ en cada una de las ~q~ calles.

Entrada

La primera línea contiene un solo entero ~q~ (~1\le q\le 10^5~) ~-~ el número de calles que Ana y Bruno van a analizar.

Las siguientes ~q~ líneas contienen cuatro enteros ~a_1~, ~a_2~, ~l~ y ~r~ (~-10^9 \le a_1,a_2\le 10^9~, ~1\le l<r\le 10^9~) ~-~ la belleza de la primera casa, la belleza de la segunda casa, y los índices de las dos casas disponibles, respectivamente.

Salida

Imprime ~q~ líneas, cada una con un entero ~-~ la belleza de la carretera entre las casas ~l~ y ~r~ para cada calle.

Subtareas

Subtarea	Puntos	Restricciones adicionales	Dependencias
~1~	~1~	~a_1 = 0~, ~a_2 = 0~	~-~
~2~	~11~	~1\le q\le 10^4~, ~1\le r\le 100~	~-~
~3~	~14~	~1\le r\le 10^7~, ~a_1~ y ~a_2~ serán los mismos para todas las ~q~ calles.	~-~
~4~	~21~	~\sum r-l+1\le 10^6~	~2~
~5~	~23~	~a_1 = a_2~	~1~
~6~	~30~	Sin restricciones adicionales.	~1-5~

Ejemplos

Entrada 1

5
0 0 100 1000
3 -5 1 2
2025 2025 2 4
-1 1 3 10
6 3 1 3

Salida 1

0
-2
0
3
6

En el ejemplo anterior, Ana y Bruno van a analizar ~5~ calles.

En la quinta calle, las casas disponibles son ~1~ y ~3~. La casa ~1~ tiene una belleza de ~6~, la casa ~2~ tiene una belleza de ~3~, y la belleza de la casa ~3~ es igual a ~a_2 - a_1 = 3 - 6 = -3~. Entonces, la belleza de la carretera entre las casas es:

~\sum_{i=1}^{3} a_i = a_1 + a_2 + a_3 = 3 + 6 + (-3) = 6~