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$.