Note that this is $$\textbf{not an approximate task}$$. It is labeled as an approximate task because of multiple solutions.

Given a graph with $$N$$ vertices and $$M$$ edges. There are $$D$$ type of edges. the $$i^{th}$$ $$(1 \le i \le D)$$ type of edges you can use at second $$i$$. You have $$K$$ pointers, in the second $$0$$ they are situated in $$s_1, s_2, \dots, s_K$$. Each second you instantly move all the points through some of the allowed edges with the condition that you can't move two pointers in the same vertex. At the $$(D + 1)$$ you stop moving them.

Provide a way to move the pointers at each second. It is guaranteed that there's always a solution.

$$\textbf{Input}$$

The first line contains four integers - $$N, M, K, D (1 \le D \le 100, 1 \le K \le N \le 500, 1 \le M \le 50000)$$.

The next line contains $$K$$ integers - $$s_1, s_2, \dots, s_K$$ $$(1 \le s_1 < s_2 < \dots < s_K \le N)$$.

The next $$M$$ lines contain three integers - $$x, y, z (1 \le x, y \le N, 1 \le z \le D)$$, meaning there is a directed edge $$(x,y)$$ of type $$z$$

$$\textbf{Output}$$

Output $$K$$ lines, each containing $$D + 1$$ integers. The $$j^{th}$$ number on the $$i^{th}$$ line represents the vertex where will be the $$i^{th}$$ pointer at the second $$j - 1$$.