小H收到了一棵美丽的圣诞树，圣诞树是一棵树(废话)，有N个节点，编号为1~N，每个节点上都有一件礼物，礼物也分为N种，编号为1~N，每件礼物都有一个种类。 现在小H想问你Q个问题，每个问题形如x，y，表示询问所有满足下列条件的路径长度和： 路径的一个端点上的礼物种类是x，另一端点上礼物种类是y，且这条路径是简单路径 注意： (x,y),(y,x)是相同的路径 树的每条边有边权，路径的长度为路径上所有边的长度和

输入描述:

第1行，一个整数N(1≤N≤100,000)第2行N个属于[1,N]的正整数，依次表示每个节点上的礼物种类接下来N-1行，每行三个正整数，依次表示树上的一条边的起点u、终点v、长度l (1≤u,v≤N,0≤l≤100,000)接下来一行，一个整数Q(1≤Q≤100,000)接下来Q行，每行两个整数x，y，意义见题目描述,1≤x,y≤N

输出描述:

对于每个询问输出一行，表示你给出的答案(答案保证在long long范围内)