题目描述

Taro is travelling within a country, which consists of $N$ cities numbered from $1$ to $N$. There are also $K$ train companies, numbered from $1$ to $K$, that operate the trains within the nation. Initially, there are $M$ one-way train services, each of which can be described as a triple $(u, v, k)$, meaning that there are trains operated by company $k$ that goes from city $u$ to city $v$.

Taro is currently in city $1$. In the next $Q$ months, one of the following three events may happen.

• $\texttt{1 u v k}$: company $k$ $\textbf{starts}$ a new train service that goes from city $u$ to city $v$. In other words, add $(u, v, k)$ to the train network.
• $\texttt{2 u v k}$: company $k$ $\textbf{ends}$ its train service that goes from city $u$ to city $v$. In other words, remove $(u, v, k)$ from the train network.
• $\texttt{3 k}$: Taro either $\textbf{stays}$ in the city he is currently in, or $\textbf{takes}$ one of the trains operated by company $k$ from the city he is currently in to another city.

It is guaranteed to you that the existing services $(u, v, k)$ are always distinct throughout the course of events, and event $2$ always removes a currently existing service.

Every time an event $3$ happens, find the number of different cities Taro can possibly be in, given the course of events so far.

输入格式

The first line contains three integers $N$, $M$, $K$, and $Q$ ($2 \le N \le 300\;000$; $1 \le M, K, Q \le 300\;000$).

Each of the next $M$ lines contains three integers $u$, $v$, $k$ ($1 \leq u, v \leq N$; $1 \leq k \leq K$; $u \neq v$) describing the initial train services.

Each of the next $Q$ lines contains an event as described above.

The input guarantees that the existing services $(u, v, k)$ are always distinct throughout the event.

输出格式

For each event $3$, output, in a single line, the number of different cities Taro can possibly be in.

6 4 2 5
1 3 1
3 6 2
3 2 2
3 5 2
3 2
3 1
1 1 4 2
2 3 6 2
3 2

1
2
5

提示

$\textit{Explanation of Sample 1:}$ Initially, Taro is in city $1$.

• In the first event $3$, there are no train services operated by company $2$ that departs from city $1$, so Taro has to stay in city $1$.
• In the second event $3$, Taro can either stay in city $1$, or take the service $(1, 3, 1)$ and end in city $3$. Because Taro can be in either city $1$ or $3$, you have to output $2$.
• In the third event $3$, the existing train services are $(1, 3, 1)$, $(1, 4, 2)$, $(3, 2, 2)$, $(3, 5, 2)$. If Taro is currently in city $1$, he can take service $(1, 4, 2)$ and end in city $4$. If Taro is currently in city $3$, he can take services $(3, 2, 2)$ or $(3, 5, 2)$ and end in city $2$ or $5$ respectively. Since he can possibly in city $1$, $2$, $3$, $4$, and $5$, you have to output $5$.