Traffickers

Task

Pablo is one of the most notorious men in the Wild West, well known for his influence upon $N$ cities interconnected by roads forming a tree structure. Pablo's trusted men are traffickers, transporting merchandise relentlessly. Each trafficker is defined by a pair a cities $(u, v)$ as follows: the trafficker travels starting with time $0$ from city $u$ towards city $v$, on the shortest path. At each integer moment of time each trafficker delivers one unit of merchandise, then moves on to the next city.

Pablo's traffickers are not easy to track: once a trafficker reaches his destination city $v$ and delivers the merchandise, at the next moment of time he teleports back to city $u$ (if at time $t$ he delivers merchandise in city $v$, then at time $t + 1$ he will deliver in city $u$). As business is flourishing and it would be a shame for it to stop, the traffickers will follow their routes forever.

Although the system put in place by Pablo seems unbreachable, he wonders whether there is any room for improvement. Thus, he will perform $3$ types of queries over the system:

• $1 \ u \ v$: Add a trafficker travelling between the pair of cities $(u, v)$.
• $2 \ u \ v$: Remove a trafficker travelling between the pair of cities (u, v). It is guaranteed that such a trafficker exists.
• $3 \ u \ v \ t_1 \ t_2$: Pablo wishes to know how many units of merchandise are delivered in total by all the existing traffickers, in all the cities along the shortest path between cities $u$ and $v$ inclusive, between times $t_1$ and $t_2$ inclusive.

Input data

The first line contains $N$, the number of cities. The following $N - 1$ lines contain $2$ integers $u$ and $v$ each, signifying that there is a direct road between cities $u$ and $v$.

The next line contains $K$, the number of traffickers initially present in Pablo's network. The following $K$ lines each contain $2$ numbers $u$ and $v$, the pair of cities defining the path of a trafficker.

The next line contains $Q$, the number of queries Pablo intends to perform. The following $Q$ lines each contain a query in the format mentioned above.

Output data

For each query of type $3$ output the answer on a separate line.

Constraints and clarifications

• $1 \leq N \leq 30 \ 000$
• $0 \leq K \leq 50 \ 000$
• $1 \leq Q \leq 50 \ 000$
• $0 \leq t_1 \leq t_2 \leq 2 \ 000 \ 000 \ 000$
• The path of each trafficker covers at most $20$ cities (including its endpoints).
• Test cases will be scored individually.

Example

stdin

5
1 2
2 3
2 4
1 5
1
4 1
3
3 3 5 0 3
1 2 5
3 4 5 1 5

stdout

2
10

Explanation

Trafficker $1$ delivers $2$ units of merchandise on the path $3 → 2 → 1 → 5$ between times $0$ and $3$:

• at city $2$ at time $1$;
• at city $1$ at time $2$.