거의 깨끗한 돈의 트리

정점 $N$개로 이루어진 트리에서 돈이 자란다. 정점에는 $0$번부터 $N-1$번까지 번호가 붙어 있고, $0$번 정점이 루트다. $0$번을 제외한 모든 정점 $i$에는 부모 $p(i)$가 있으며 $p(i) < i$를 만족한다. 처음에 정점 $i$에는 화폐 $v(i)$단위가 들어 있다.

어떤 조직이 이 트리에 연산 $Q$개를 수행한다. 각 연산은 두 단계로 이루어진다.

1. 트리에서 정점 $K$개 $x(1), \dots, x(K)$를 고른다 ($0 \le x(i) \le N-1$). 같은 정점을 여러 번 골라도 된다. $1 \le i \le K$인 각 $i$에 대해 정점 $x(i)$에 화폐 $y(i)$단위를 더한다.
2. 정점 두 개 $u$와 $v$를 고른다 ($0 \le u, v \le N-1$). $u$와 $v$를 잇는 유일한 경로 위에 놓인 정점에 들어 있는 화폐의 총합을 구한다. 양 끝인 $u$와 $v$도 경로에 포함한다.

각 연산의 2단계 답을 구하라.

제한은 다음과 같다.

• $1 \le N \le 500000$
• $1 \le Q \le 50000$
• $1 \le K \le 1000$
• $0 \le v(i) < 1000000007$
• $0 \le y(i) < 1000000007$

첫째 줄에 정점의 개수 $N$이 주어진다. 다음 $N-1$개의 줄에는 트리의 간선 하나를 나타내는 두 정수 $p(i)$와 $i$가 공백으로 구분되어 주어진다. 다음 줄에는 각 정점의 처음 금액 $v(0), \dots, v(N-1)$이 공백으로 구분되어 주어진다.

다음 줄에는 연산의 개수 $Q$가 주어진다. 이어지는 $Q$개의 줄에는 연산 하나가 정수 아홉 개로 주어지며, 순서는 $K$, $x(1)$, $y(1)$, $A$, $B$, $C$, $D$, $u$, $v$이다 ($0 \le A, B, C, D < 1000000007$). 직접 주어지는 값은 $x(1)$과 $y(1)$뿐이고, $2 \le i \le K$인 나머지는 다음 식으로 만든다.

$x(i) = (A \cdot x(i-1) + B) \bmod N$

$y(i) = (C \cdot y(i-1) + D) \bmod 1000000007$

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 연산의 2단계 답을 출력한다. 1단계에서 더한 금액은 정점에 그대로 남으므로, 각 연산은 앞선 연산의 1단계와 자기 자신의 1단계를 모두 반영한 상태에서 답을 계산한다.

답은 32비트 정수의 범위를 넘을 수 있다.

첫 번째 예제의 연산 1은 $A = C = 1$, $B = D = 0$이므로 정점 $1$에 값 $1$을 1000번 더한다. $0$번과 $2$번을 잇는 경로는 정점 $0$, $1$, $2$를 지나고, 세 정점에 든 금액의 합은 $1006$이다.

연산 2에서는 $x(1)=0$, $y(1)=5$, $x(2)=1$, $y(2)=12$가 되고, $2$번과 $3$번을 잇는 경로는 트리의 정점을 모두 지난다.

연산 3은 $K = 1$이므로 $A$, $B$, $C$, $D$를 쓰지 않는다.