God D bought many, many chocolates for his girlfriend and stored them in his storage room. As a chocolate lover, little R naturally wants to sneak into God D's storage room to eat the chocolates.

There are $n$ chocolate storage points in God D's storage room, numbered from $0$ to $n - 1$, each containing one piece of chocolate. There are $m$ directed paths, each connecting two storage points. Little R starts from the storage point numbered $0$. Because he loves chocolate so much, he will definitely eat the chocolate at every storage point he passes. Additionally, he cannot pass through the same storage point twice, or he will trigger an alarm and alert God D.

Each piece of chocolate has a different sweetness. The $i$-th chocolate little R eats provides a sweetness of $s \cdot k^{i-1}$, where $s$ is the sweetness of the chocolate itself, and $k$ is a given positive real number no greater than $1$. The total sweetness little R perceives is the sum of the sweetness of each chocolate he eats. Please find a route that maximizes the total sweetness little R perceives.

Input

The first line contains two positive integers $n, m$ and a positive real number $k\ (0 \leq k \leq 1)$, where $n$ is the number of chocolate storage points, $m$ is the number of directed paths, and $k$ is the sweetness decay coefficient.

The second line contains $n$ positive integers, representing the sweetness of each piece of chocolate.

The next $m$ lines each contain two positive integers $u, v$, representing a directed edge from $u$ to $v$.

Output

The first line contains a non-negative integer $l$, representing the length of the path.

The second line contains $l$ positive integers, representing the sequence of storage point labels visited.

Examples

Input 1

5 5 0.5
1 3 5 7 2
0 1
0 2
1 3
3 1
2 3
3 4

Output 1

4
0 2 3 1

Note

The total sweetness of this route is $1 + 0.5 \times 5 + 0.25 \times 7 + 0.125 \times 3 = 5.625$.

Another route is $0 \ 2 \ 3 \ 4$, with a total sweetness of $1 + 0.5 \times 5 + 0.25 \times 7 + 0.125 \times 2 = 5.5$.

Scoring

For each test case, if your output route has any of the following issues, you will receive $0$ points for that test case:

• Contains illegal characters;
• The route does not start at the point numbered $0$;
• There is no path between any two adjacent points in the sequence;
• Any point is visited more than once;
• Passed through a non-existent point.

Otherwise, for each test case, assuming the total sweetness of your route is $\mathrm{ans}$, we provide $10$ scoring parameters $s_1, s_2, \dots, s_{10}$ in increasing order. If $\mathrm{ans} \geq s_{10}$, you will receive $10$ points. Otherwise, if $s_i \leq \mathrm{ans} < s_{i + 1}$, you will receive $i$ points.