题目背景

ZYG 解决第二题后，看到一个老太婆从迷之地方出现，并邀请他参加宴会。

在宴会上，大家都在开心地玩游戏，威严满满大小姐喝水喝醉后出了一道题，
扬言没有人能做出来，但 ZYG 没过多久就解出，大小姐恼羞成怒，当场抱头蹲防。

题目描述

冥界的白玉楼里有一棵很大的树，有 n 个节点，每个节点上有一个正整数。
白玉楼的园丁每天开始工作前进行一定计算，这个习惯已经持续了 m 天，对于某
一天，园丁会计算节点 u、v 之间的最短路径上所有节点（包括节点 u、v）当中，
数值不小于 L 且不大于 R 的节点个数。请问园丁这 m 天的计算结果。

Format

输入格式

第一行，一个正整数 n。
第二行，n 个正整数，依次为各节点上的数值。
接下来 n-1 行，每行两个正整数 x、y，表示节点 x 与节点 y 相连。
第 n+2 行，一个正整数 m。
接下来 m 行，每行四个正整数 u、v、L、R，含意如题所述。

输出格式

共 m 行，每行一个正整数，即为每天里园丁的计算结果。

Sample 1

Input

5
1 9 5 5 1
1 2
2 3
1 5
4 2
10
2 3 1 10 
5 4 5 7 
5 3 4 9 
1 5 3 7 
1 3 2 7 
1 3 7 9 
4 2 4 8 
5 2 2 2 
5 2 7 9 
4 2 5 9 

Output

2
1 
2 
0 
1 
1 
1 
0 
1 
2 

Limitation

1s, 512MiB for each test case.

Hint

对于100%的数据，n<=100000，m<=100000。

Source

8月23日 炎炎夏日大礼包