测试数据来自 system/1935

描述

今天，是2015年2月14日，星期六，情人节。

这真是一个不可思议的日子，今天早上，我打开窗户，太阳居然从西侧升了起来。

我与木姑娘已经有2年半没有联系了，今天早上却被她的电话弄醒。她告诉我，她已经到了上海，希望可以和我以特殊的方式见面。

今天，SH市的交通情况异常有趣，很多道路都被严令禁止通行。或许是因为太阳从西侧升起来的缘故吧。

余下的交通网行程了一个树型结构，以n个路口为结点，第i个路口附近有p[i]处咖啡厅。

如果知道了我和木姑娘分别所处的位置，在选择余下某一个路口的某一处咖啡厅作为见面的场所，如何呢？

哦，那或者距离我近，或者距离木姑娘近。

那么，到底有多少咖啡厅距离我更近，又有多少咖啡厅距离木姑娘更近呢？（对于距离我和距离木姑娘一样近的咖啡厅，将被排除在这两类之外。）

格式

输入格式

输入数据的第一行是一个整数n，表示路口的数目。

接下来的n-1行，每行三个整数u,v,w表示一条边从路口u到路口v，长度为w。

接下来的一行n个数p1,p2,...,pn表示每个路口的咖啡厅个数。

接下来的一行一个整数Q表示询问的数目。

接下来的Q行，每行两个整数x,y表示一组询问，其中我在x路口的位置，木姑娘在y路口的位置。

输出格式

对于每组询问，输出一行两个整数分别表示距离x更近的咖啡厅总数，与距离y更近的咖啡厅总数。

样例1

样例输入1

3
1 2 1
1 3 1
10 1 1
2
2 3
1 3

样例输出1

1 1
11 1

限制

对于30％的数据，n<=1000。
对于50％的数据，n<=20000。
对于100％的数据，n<=100000，Q<=50000，0<=w,p[i]<=1000000000。