Problema A - Chegar ao outro lado

O Simão vai todos os dias comprar pão numa padaria da rua onde vive. Ele mora na baixa de Coimbra, e por isso há sempre muito movimento, o que complica a sua deslocação.

A casa do Simão fica de um lado da estrada e a padaria do outro, e ele pode andar em ambos os lados usando o passeio. Cada segmento do passeio separa dois pontos da rua (que podem conter casas, edifícios, etc), e demora um certo tempo diferente a percorrer, dependendo da densidade de pessoas habitual (esse tempo não varia, ou seja, para um dado segmento é sempre o mesmo valor). Além disso, o Simão só pode atravessar a estrada usando as passadeiras com semáforos pré-definidos, que se encontram sempre entre dois pontos opostos (com a mesma coordenada em cada lado do passeio). No entanto, cada semáforo demora um certo tempo para ficar verde, sendo que esse tempo também varia de semáforo para semáforo.

Depois de tirar muitas notas, o Simão conseguiu construir um diagrama com os passeios divididos em segmentos e com os tempos que demora a atravessar cada um. Contudo, ele chegou à conclusão de que há muitos caminhos por onde seguir, sendo que gostaria de saber o mais curto, para poupar tempo na sua viagem. Ainda para mais, a rua do Simão é muito grande e cheia de pessoas e pedidos, como a Dona Ricardina que precisa de ir à farmácia, o Diogo que quer ir ao café, entre outros, que ouviram do Simão que os podias ajudar e também precisam de ti. Dado os tempos para atravessar cada segmento de ambos os lados da rua e a informação sobre as passadeiras, consegues dizer ao Simão e vizinhos o tempo de viagem mais curto para cada 2 pontos pedidos?

Por exemplo, se a rua do Simão tivesse o seguinte aspeto:

Então o Simão demoraria no mínimo 9 unidades de tempo a ir de casa à padaria, por exemplo pelo caminho descrito a vermelho. Já a Dona Ricardina precisaria sempre de pelo menos 12 unidades de tempo para ir buscar os seus medicamentos à farmácia, pelo caminho descrito a verde.

O Problema

Dado N, o número de pontos da rua e o tempo que demora percorrer o cada segmento entre cada par, S o número de passadeiras (com semáforo), S inteiros que representam o tempo de atravessar cada passadeira e Q perguntas indicando dois pontos, para cada pergunta imprimir a distância mínima entre os dois pontos dados.

Input

Na primeira linha vem um inteiro N que representa o número de pontos na rua (numerados de 0 a N-1, da esquerda para a direita). Em cada uma das próximas duas linhas vêm N-1 inteiros que consistem no tempo que demora a atravessar cada segmento, primeiro no passeio 1 (cima) e depois no passeio 2 (baixo). De seguida vem um inteiro S que corresponde ao número de passadeiras com semáforo na rua. Nas seguintes S linhas vêm dois inteiros por linha Pi e Ti, em que Pi é a posição da passadeira (os pontos que ela une) e Ti o tempo que demora a passar o seu semáforo. Finalmente, vem um inteiro Q seguido de Q linhas que correspondem às perguntas. Para cada pergunta vêm quatro inteiros Ai, Bi, Ci e Di em que Ai e Ci são as posições dos pontos que estamos a considerar, e Bi e Di é 1 ou 2 consoante os pontos respetivos se encontrem no passeio de cima ou de baixo.

Output

O output consiste em Q inteiros, um por linha, que correspondem às respostas a cada uma das Q perguntas. Nota: para os casos de teste maiores, estes valores podem exceder 231.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ N ≤ 100 000       Tamanho da rua do Simão
1 ≤ S ≤ N       Número de passadeiras
0 ≤ Pi ≤ N - 1       Posição das passadeiras
1 ≤ Ti, Ni ≤ 1 000 000       Tempo associado aos semáforos das passadeiras e entre segmentos da rua
1 ≤ Qi ≤ 100 000       Número de perguntas
0 ≤ Ai, Ci ≤ N - 1       Posição dos pontos das perguntas
1 ≤ Bi, Di ≤ 2       Número do passeio dos pontos das perguntas

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Grupo Número de Pontos Restrições adicionais
1 15 1 ≤ N ≤ 20, S = 1
2 15 S = 1
3 15 1 ≤ N ≤ 1 000, 1 ≤ S ≤ 1 000, 1 ≤ Q ≤ 1 000
4 15 Ai = Ci
5 20 1 ≤ N ≤ 30 000, 1 ≤ S ≤ 30 000, 1 ≤ Q ≤ 30 000
6 20 -

Input do Exemplo 1

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

Output do Exemplo 1

9
12

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

7
3 3 5 5 3 3
3 5 3 4 4 5
1
6 7
5
2 1 5 2
3 2 1 1
0 1 6 2
6 1 0 2
4 2 4 2

Output do Exemplo 2

28
39
29
31
0

Final Nacional das ONI'2017
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(8 de Maio de 2017)