Restaurantes
Para comemorar o Dia das Mães Márcia decide levar sua tão amada mãe para almoçar em um restaurante. E como se trata de uma data especial ela se preocupa com todos os detalhes, principalmente, a distância e a qualidade da comida no restaurante.
Por isso, ela decide pegar um mapa de Fortal City, cidade em moram, para saber a distância dos restaurantes a sua casa e a casa de sua mãe. Ao analisar o mapa ela percebe que pode montar uma árvore ligando os restaurantes um aos outros e as suas casas respectivas casas. E agora ela já selecionou os melhores restaurantes mas precisa saber a distância entre eles e a sua casa, para então decidir onde ira almoçar com sua mãe.
Márcia vai lhe dar a árvore T que ela montou analisando o mapa da cidade e algumas perguntas do tipo:
- - Márcia quer saber a distância entre os restaurantes e .
- - Márcia quer saber quem é o k-ésimo restaurante entre e .
Ajude Márcia a responder suas perguntas e assim decidir qual será o restaurante perfeito para almoçar com sua mãe.
Entrada
A primeira linha da entrada contém dois inteiros e , que representa a quantidade de restaurantes na árvore. As próximas linhas contém cada uma três inteiros , e que representam uma estrada entre os restaurantes e com de extensão. Cada uma das próximas linhas contém uma pergunta de Márcia.
Saída
Imprima a resposta para cada uma das perguntas feitas por Márcia.
Exemplos
Entrada |
Saída |
6 1 2 1 2 4 1 2 5 2 1 3 1 3 6 2 1 4 6 2 4 6 4 |
5 3 |