For a given undirected connected weighted graph G and K servers, which can travel between two vertices u and v of G in time $distance(u, v)$, the goal is to handle Q queries. The i-th query contains a single vertex v and demands at least one server to arrive at vertex v in order to handle the request there. So if there is no server at vertex v currently, at least one server has to be moved there with cost $distance(u, v)$, where u is its current position. The goal is to minimize the total time needed to handle all the requests.

Input format:

In the first line there are 4 space separated integers $N, M, K$ and Q denoting respectively the number of vertices in the graph, the number of edges in the graph, the number of servers, and the number of queries to handle. After that, M lines follow. Each of them consists of 3 space separated integers $u, v, w$ denoting that there is an edge between vertices u and v with weight w. It the next line there are K space separated integers $p_1, p_2, \ldots, p_K$, where $p_i$ denotes the initial vertex position of server i. Then, Q lines follow. On the i-th line there is a single integer $q_i$ denoting the vertex where the i-th request has to be handled.

Output format:

In the first line output a single integer A denoting the number of actions your solution performs. A must not be greater than $2 \cdot 10^7$.

After that print exactly A lines. Each of these lines should be in one of two formats:

• MOVE $s_i$ $v_i$ := denoting that a server $s_i$ is moved to vertex $v_i$
• HANDLE := denotes that the first not yet handled request is handled now

The output is considered correct if it is in the correct format, there are exactly Q HANDLE actions, and whenever a HANDLE action is performed, there is at least one server on the vertex corresponding to the query this action handles.

Constraints:

$1 \leq N \leq 10^3$
$1 \leq M \leq 10^4$
$1 \leq K \leq 100$
$1 \leq Q \leq 10^5$
$0 \leq A \leq 2 \cdot 10^7$
$1 \leq u, v \leq N$
$1 \leq p_i \leq N$
$1 \leq q_i \leq N$
$1 \leq s_i \leq K$
$1 \leq v_i \leq N$

Scoring:

For a single test case let the total time (i.e. total distance traveled by all servers) needed to handle all requests by performing all moves given in output returned by your program be $\mathit{time}$.

Now the score for the given case is defined as

$(10^{11} - \mathit{time}) \cdot (M/N)^2 \cdot K$

If the output for a particular case is wrong the score for that case is 0. The total absolute score of a problem is the sum of scores for all the test cases. In this problem, scoring is set to relative, which means that the final score for a problem is your absolute score divided by the score of the best solution submitted by any participant.

The objective is to minimize the time taken i.e. to maximize the score.

Test generation:

In all test cases $N = 10^3$, $Q = 10^5$, edge weights are generated uniformly at random from range $[1, 10^3]$, initial position of each server is generated uniformly at random from range $[1, N]$, vertices corresponding to queries are generated uniformly at random from range $[1, N]$.

There are 3 types of graphs used in the test cases, each of them is used in $1/3$ test cases:

1. path graph with N nodes
2. random graph with N nodes and $10 \cdot N$ edges, generated with this function
3. random tree with N nodes generated by first picking a random graph generated in method 2, then assigning random weights to its edges, computing minimum spanning tree of this graph and returning this minimum spanning tree with edge weights removed

In each of the 3 above groups, there are 3 classes of tests denoted by the range from K is chosen uniformly at random. Each such class corresponds to $1/3$ test cases in a group. These ranges are:

1. $[2,5]$
2. $[10,20]$
3. $[50, 100]$