Problem Background

Ju Run has become obsessed with a game called "The Binding of Isaac: Rebirth." He has reached the final level, which requires special movement techniques.

1. Ju Run starts controlling Isaac from time $0$ to move from the starting point to the endpoint.
2. Ju Run can only reach the endpoint exactly at time $k$. (Moving from one room to another takes one unit of time. Ju Run is fast and will not stay in the same room; Isaac can move back and forth between these rooms.)
3. If rooms $u$ and $v$ are connected, Ju Run can control Isaac to pass through the passage between these two rooms if and only if Isaac's health is greater than or equal to $f(u, v)$.
4. There are a bunch of monsters roaming between these rooms.
5. To ensure safety, Ju Run found a decoder online and discovered that the monsters follow a fixed pattern: they always move from one room to another (also taking one unit of time), and they roam within a fixed set of rooms in a fixed order, with the number of rooms being $T$.

To avoid mistakes while playing, Ju Run wants to avoid all monsters and reach the endpoint unscathed, i.e., pass the final level without taking any damage. He hopes you can find the minimum health required for Isaac to complete this task. Being unfamiliar with programming, he turns to you for help. If you cannot solve it, just tell him straightforwardly: 'IMP0SSBLE!!' He definitely won't hurt you.

Problem Description

Determine if Ju Run can pass the final level unscathed under the given conditions. If possible, output the minimum health $B$ required for Isaac; otherwise, output 'IMP0SSBLE!!'.

Input Format

The first line contains five numbers: $n, m, s, t, k$, representing the total number of rooms, the number of pairs of adjacent rooms and their required health to pass, the starting point $s$, the endpoint $t$, and the exact time $k$ to reach the endpoint.

The next $m$ lines each contain three numbers: $u, v, w$, indicating that rooms $u$ and $v$ are adjacent, and the health required to pass between them is $w$.

The next line contains a single number $a$, representing the total number of monsters.

The following $a$ data sets describe the roaming patterns of each monster.

Each data set starts with a number $T$, indicating the number of rooms the monster roams in, followed by $T$ room numbers indicating the sequence and cycle of the monster's movement starting from the zeroth time.

Output Format

A single line, either the minimum required health $B$ for Isaac or 'IMP0SSBLE!!'.

Sample Input and Output

Sample Input #1

2 1 1 2 1
1 2 1
0

Sample Output #1

1

Sample Input #2

2 1 1 2 1
1 2 2
0

Sample Output #2

2

Sample Input #3

2 1 1 2 10000001
1 2 2
0

Sample Output #3

2

Sample Input #4

2 1 1 2 10000001
1 2 2
1
2
2 1

Sample Output #4

2

Notes

There are 20 test cases in total.

For 15% of the data, $a = 0$, $k \leq 20$.

For 25% of the data, $a \leq 3$, $k \leq 1500$.

For 50% of the data, $a \leq 3$, $k \leq 10^4$.

For 70% of the data, $a \leq 20$, $k \leq 10^6$.

For 85% of the data, $a \leq 30$, $k \leq 10^8$.

For 100% of the data, $a \leq 30$, $k \leq 2*10^9$, $2 \leq T \leq 4$, $n \leq 50$, $m \leq 1250$.

All inputs are within the int range.

All data are greater than zero. There may be duplicate edges; if an edge appears multiple times, the value of the last occurrence is considered.

见题面 Input 部分

见题面 Output 部分