Traffickers

Pablo is one of the most notorious men in the Wild West, with influence over $N$ cities connected by roads that form a tree. Pablo's trusted men are traffickers, and they transport merchandise nonstop.

Each trafficker is defined by a pair of cities $(u, v)$. The trafficker starts at time 0 in city $u$ and travels toward $v$ along the shortest path. At each integer time, the trafficker delivers one unit of merchandise and moves on to the next city. When a trafficker reaches $v$ and delivers there, at the next moment he teleports back to $u$. So if he delivers in $v$ at time $t$, he delivers in $u$ at time $t + 1$. The traffickers follow their routes forever.

Pablo wants to know whether the system can be improved. He runs three types of queries.

• 1 u v: Adds a trafficker traveling between $u$ and $v$.
• 2 u v: Removes a trafficker traveling between $u$ and $v$. Such a trafficker is guaranteed to exist.
• 3 u v t1 t2: Counts the total units of merchandise delivered by all current traffickers, in every city on the shortest path between $u$ and $v$ (both endpoints included), at times from $t_1$ to $t_2$ (both included).

The first line contains the number of cities $N$. The next $N - 1$ lines each contain two integers $u$ and $v$, meaning there is a direct road between those two cities.

The next line contains $K$, the number of traffickers initially present. The next $K$ lines each contain two integers $u$ and $v$, the pair of cities defining that trafficker's route.

The next line contains $Q$, the number of queries. The next $Q$ lines each contain one query in the format described above.

For each query of type 3, print the answer on a separate line.

• $1 \le N \le 30{,}000$
• $0 \le K \le 50{,}000$
• $1 \le Q \le 50{,}000$
• $0 \le t_1 \le t_2 \le 2{,}000{,}000{,}000$
• The path of each trafficker covers at most 20 cities, including its endpoints.