There is competition between two bike-sharing companies, Company A and Company B, on a university campus. To maximize its market share on campus, Company A attempts to obstruct Company B's bike collection operations.

The campus consists of $N$ regions and $M$ roads, with each road connecting two regions. There is a region $K$ that serves as Company B's base, and all bike collection operations start from this region. To minimize costs, Company B always chooses the shortest path from region $K$ to any region $X$. If there are multiple shortest paths to a region, it chooses the one where the predecessor of that region has the smallest index. This path is called the collection route from $K$ to $X$. All collection routes together form a tree structure, referred to as the collection route tree.

Company B collects bikes from several regions, which are called collection regions. Company B also designates some regions as deployment regions, while the remaining regions are non-deployment regions. On the collection route tree, the region $K$, all collection regions, and the lowest common ancestor (LCA) of any two collection regions are marked.

Company A obstructs Company B's operations if and only if for any marked deployment region $X$ (other than $K$), there exist two marked regions on the collection route from $K$ to $X$ such that all roads between them (the path between the two points on the collection route tree) are obstructed.

The cost of obstructing a road is equal to its length. Your task is to help Company A calculate the minimum cost to obstruct Company B's collection operations.

Input

The first line contains four integers $N, M, K, Q$, representing the number of regions on campus, the number of roads, the index of Company B's base $K$, and the number of operations, respectively.

The next $M$ lines describe the roads, each containing three integers $S, T, Len$, representing a bidirectional road of length $Len$ between $S$ and $T$.

The following $Q$ lines each start with an integer representing the operation type. $0$ indicates that Company B changes its deployment regions, and $1$ indicates a bike collection operation by Company B.

For operation type $0$, it is followed by an integer $num$, representing the number of regions being changed, followed by $num$ integers representing the region indices. For each changed region, if it is a deployment region, it becomes a non-deployment region; if it is a non-deployment region, it becomes a deployment region.

For operation type $1$, it is followed by an integer $num$ representing the number of collection regions, followed by $num$ integers representing the indices of the collection regions. Each time, the markings on the collection route tree must be re-evaluated.

Output

For each collection operation, output a single line representing the minimum cost for Company A to obstruct Company B's operations. Note that if there are no marked deployment regions, output $-1$.

Examples

Input 1

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

Output 1

10
6

Input 2

12 11 4 5
4 1 32
4 6 42
1 3 29
7 1 17
7 10 23
9 7 21
5 6 16
2 6 28
5 8 14
8 11 11
8 12 17
1 11 1 2 3 5 6 7 8 9 10 11 12
0 4 3 11 5 2
1 4 10 9 6 11
0 4 7 8 12 11
1 4 11 2 9 10

Output 2

-1
41
77

Subtasks

For $30\%$ of the data, $N \le 200$, $Q \le 200$.

For $60\%$ of the data, the number of collection regions is always $N-1$.

For $80\%$ of the data, $N \le 20000$, $M = N-1$, $Q \le 1000$, $num \le 200$.

For $100\%$ of the data, $N \le 50000$, $M \le 100000$, $Q \le 1500$, $num \le 500$.

All data guarantees that there are no self-loops, all road lengths are less than $2000$, and region $K$ is never a deployment region at any time.