트럭 배송

Charles는 Googleland라는 도시의 트럭 운전사이다. Googleland는 $\mathbf{N}$개의 노드로 이루어진 트리 형태로 건설되어 있으며, 각 노드는 도시를 나타내고 각 간선은 두 도시 사이의 도로를 나타낸다. 도시에는 $1$부터 $\mathbf{N}$까지 번호가 매겨져 있다. Googleland의 수도는 도시 $1$이다. Charles는 매일 도시 $\mathbf{C}$에서 무게가 $\mathbf{W}$인 화물을 싣고, 두 도시 사이의 단순 경로(유일함)를 이용해 도시 $1$로 배송하려 한다. 각 도로 $i$에는 통행료가 있으며, 화물의 무게가 적재 한도 $\mathbf{L_i}$ 이상이면 $\mathbf{A_i}$의 금액을 부과한다.

Charles는 $\mathbf{Q}$일 동안 일하며, 매일 Charles에게 출발 도시 $\mathbf{C}$와 화물의 무게 $\mathbf{W}$가 주어진다. 각 날짜에 대해 Charles가 그날 지불하는 모든 통행료의 최대공약수를 구한다. Charles가 어떤 통행료도 지불할 필요가 없었다면 답은 $0$이다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{L_i} \le 2 \times 10^5$. 모든 $i$에 대해 $1 \le \mathbf{A_i} \le 10^{18}$. 모든 $\mathbf{L_i}$은 서로 다르다. 모든 $j$에 대해 $2 \le \mathbf{C_j} \le \mathbf{N}$. 모든 $j$에 대해 $1 \le \mathbf{W_j} \le 2 \times 10^5$. 주어진 도로들이 트리를 이룬다는 것이 보장된다.

테스트 세트 1

시간 제한: 20초. $2 \le \mathbf{N} \le 1000$. $1 \le \mathbf{Q} \le 1000$.

테스트 세트 2

시간 제한: 80초. 최대 $20$개의 테스트 케이스에 대해 $2 \le \mathbf{N} \le 5 \times 10^4$ 및 $1 \le \mathbf{Q} \le 10^5$. 나머지 케이스에서는 $2 \le \mathbf{N} \le 1000$ 및 $1 \le \mathbf{Q} \le 1000$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $\mathbf{N}$와 $\mathbf{Q}$가 주어진다.

다음 $\mathbf{N}-1$개의 줄은 도로를 설명한다. 이 줄들 중 $i$번째 줄에는 공백으로 구분된 네 정수 $\mathbf{X}$, $\mathbf{Y}$, $\mathbf{L_i}$, $\mathbf{A_i}$가 주어지며, 이는 도시 $\mathbf{X}$와 $\mathbf{Y}$ 사이에 적재 한도가 $\mathbf{L_i}$이고 통행료가 $\mathbf{A_i}$인 도로가 있음을 나타낸다.

다음 $\mathbf{Q}$개의 줄은 쿼리를 설명한다. 이 줄들 중 $j$번째 줄에는 공백으로 구분된 두 정수 $\mathbf{C_j}$와 $\mathbf{W_j}$가 주어지며, 이는 $j$번째 날의 출발 도시와 화물의 무게를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), $y$는 $\mathbf{Q}$일 동안의 답을 순서대로 공백으로 구분한 목록이다.

예제 케이스 #1

첫째 날, Charles는 도시 $(5,3), (3,2)$와 $(2,1)$ 사이의 도로에서 통행료를 지불해야 한다. 답은 $\gcd(9,8,4) = 1$이다.

둘째 날, Charles는 도시 $(3,2)$와 $(2,1)$ 사이의 도로에서 통행료를 지불해야 한다. 답은 $\gcd(8,4) = 4$이다.

셋째 날, Charles는 어떤 도시에서도 통행료를 지불할 필요가 없다. 따라서 답은 $0$이다.

예제 케이스 #2

첫째 날, Charles는 도시 $(2,1)$ 사이의 도로에서 통행료를 지불해야 한다. 답은 $10$이다.

둘째 날, Charles는 도시 $(3,2)$와 $(2,1)$ 사이의 도로에서 통행료를 지불해야 한다. 답은 $\gcd(5,10) = 5$이다.