This year marks the May Fourth Youth Day. On such a wonderful day, the young explorer Niuniu takes his scientific expedition team to explore a primeval forest.

Before the expedition begins, Niuniu obtains a map of this primeval forest. There are $n$ assembly points in the forest, numbered with integers from $1$ to $n$. Between these assembly points, there are $m$ paths, numbered with integers from $1$ to $m$. Each path has one assembly point as its starting point and one as its destination.

To improve the efficiency of the scientific expedition, Niuniu divides his team into $p$ squads, each capable of completing tasks independently. They agree to start from the assembly point numbered $S$ and eventually converge at the assembly point numbered $T$. During the expedition, they will encounter many difficulties; for example, expedition members can slowly descend from the top of a cliff to the bottom, but cannot climb directly from the bottom to the top. Therefore, all input paths are one-way.

When a squad travels along a path, it records various information and data along that path. However, some paths need to be opened by the expedition team themselves, which requires a certain amount of material and incurs some costs. Due to limited equipment, the equipment allocated to each squad by Niuniu may differ; therefore, on some difficult paths, some squads may be unable to pass due to insufficient equipment. However, by reasonably allocating equipment, Niuniu ensures that every squad can successfully reach the assembly point numbered $T$.

After they all arrive at point $T$ and converge, Niuniu will aggregate all the information and data. The total value of this information and data is the total revenue of this scientific expedition. If multiple squads pass through the same path, the value is only counted once because the data recorded about this path is redundant. The cost of opening a path is the total expenditure of this scientific expedition; similarly, even if multiple squads pass through the same path that needs to be opened, this path only needs to be opened once.

Now, Niuniu hopes to design reasonable action paths for his $p$ squads to maximize the value of total revenue minus total expenditure.

Input

For each set of input data:

The first line contains $5$ integers: $n, m, p, S, T$, with meanings as described above.

The next $2m$ lines describe the paths, with two lines per path.

The first line of each path description contains three integers $u, v, w$, indicating that the path starts at $u$ and ends at $v$. If $w > 0$, it means the data value on this path is $w$, and it does not need to be opened. If $w \leq 0$, it means the data value on this path is $0$, and the cost to open it is $-w$.

The second line of each path description starts with an integer $k$, representing the number of squads that cannot pass through this path. This is followed by $k$ distinct integers, representing the IDs of these $k$ squads.

Output

For each set of input data, you need to output $p$ lines. The $i$-th line represents the action sequence of the $i$-th squad.

The first number in each line is $k$, representing the total number of paths this squad has traveled. This is followed by $k$ integers, representing the IDs of the paths the squad traveled in order while moving from $S$ to $T$.

Examples

Input 1

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

Output 1

2 1 4
3 2 3 4

Note

There are $4$ assembly points and $4$ paths on the map. The first squad can pass through paths $1, 2, 4$, and the second squad can pass through paths $2, 3, 4$. Finally, squad $1$ passes through paths $1, 4$ in order, and squad $2$ passes through paths $2, 3, 4$ in order. The total revenue obtained is $3 + 5 + 1 = 9$. The total expenditure is $2$. The value of total revenue minus total expenditure is $9 - 2 = 7$.

Subtasks

Each test case is scored individually. You may receive partial points for each test case.

For each test case, we set $10$ scoring parameters $a_1, a_2, a_3, \dots, a_9, a_{10}$. If the participant's output is invalid, the score is zero. Otherwise, if the total revenue of your plan is $w_{user}$, your score will be given by the table below. If multiple conditions in the table are met, the highest score is taken:

| :---: | :---: | :---: | :---: | | Score | Condition | Score | Condition | | $10$ | $w_{user} \geq a_{10}$ | $5$ | $w_{user} \geq a_{5}$ | | $9$ | $w_{user} \geq a_{9}$ | $4$ | $w_{user} \geq a_{4}$ | | $8$ | $w_{user} \geq a_{8}$ | $3$ | $w_{user} \geq a_{3}$ | | $7$ | $w_{user} \geq a_{7}$ | $2$ | $w_{user} \geq a_{2}$ | | $6$ | $w_{user} \geq a_{6}$ | $1$ | $w_{user} \geq a_{1}$ |

All scoring parameter files expedition1.ans~expedition10.ans are already in the problem directory. Each scoring parameter file contains $10$ lines. The $i$-th line contains a non-negative integer representing $a_i$.