Taro 正在一个国家内旅行，该国由 $N$ 个城市组成，编号从 $1$ 到 $N$。此外还有 $K$ 家火车公司，编号从 $1$ 到 $K$，负责在该国运营火车。最初，有 $M$ 条单向火车服务，每条服务可以用三元组 $(u, v, k)$ 描述，表示由公司 $k$ 运营的从城市 $u$ 到城市 $v$ 的火车。

Taro 目前在城市 $1$。在接下来的 $Q$ 个月中，可能会发生以下三种事件之一：

• 1 u v k：公司 $k$ 开通了一条从城市 $u$ 到城市 $v$ 的新火车服务。换句话说，将 $(u, v, k)$ 加入火车网络。
• 2 u v k：公司 $k$ 终止了其从城市 $u$ 到城市 $v$ 的火车服务。换句话说，从火车网络中移除 $(u, v, k)$。
• 3 k：Taro 可以选择留在当前所在的城市，或者乘坐公司 $k$ 运营的、从他当前所在城市出发前往另一个城市的火车。

题目保证在整个事件过程中，现有的服务 $(u, v, k)$ 始终是不同的，且事件 $2$ 总是移除当前已存在的服务。

每当发生事件 $3$ 时，请根据目前为止发生的事件序列，找出 Taro 可能身处的不同城市的数量。

输入格式

第一行包含三个整数 $N, M, K$ 和 $Q$ ($2 \le N \le 300\,000$; $1 \le M, K, Q \le 300\,000$)。接下来的 $M$ 行，每行包含三个整数 $u, v, k$ ($1 \le u, v \le N$; $1 \le k \le K$; $u \neq v$)，描述初始的火车服务。

接下来的 $Q$ 行，每行包含一个如上所述的事件。输入保证在整个事件过程中，现有的服务 $(u, v, k)$ 始终是不同的。

输出格式

对于每个事件 $3$，输出一行，表示 Taro 可能身处的不同城市的数量。

样例

输入 1

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

1
2
5

说明 1

最初，Taro 在城市 $1$。

1. 在第一次事件 $3$ 中，没有由公司 $2$ 运营且从城市 $1$ 出发的火车服务，因此 Taro 必须留在城市 $1$。
2. 在第二次事件 $3$ 中，Taro 可以留在城市 $1$，或者乘坐服务 $(1, 3, 1)$ 到达城市 $3$。因为 Taro 可能在城市 $1$ 或 $3$，所以你需要输出 $2$。
3. 在第三次事件 $3$ 中，现有的火车服务为 $(1, 3, 1), (1, 4, 2), (3, 2, 2), (3, 5, 2)$。如果 Taro 当前在城市 $1$，他可以乘坐服务 $(1, 4, 2)$ 到达城市 $4$。如果 Taro 当前在城市 $3$，他可以乘坐服务 $(3, 2, 2)$ 或 $(3, 5, 2)$ 分别到达城市 $2$ 或 $5$。由于他可能身处城市 $1, 2, 3, 4$ 和 $5$，你需要输出 $5$。