Wind‐Walker Tree Adventure

You are given a rooted tree with (n) nodes numbered from 1 to (n) with node 1 as the root. There are (m) Wind Gods’ Eyes placed on some nodes. The (i)th Wind God’s Eye is located at node (a_i).

You start at the root (node 1). In each second, you can either:

1. Walk from your current node to any adjacent node (the tree is undirected), or
2. Call upon the help of Wendy to generate a wind field which lets you move in one second exactly \(k\) steps in the downward direction (from a node with smaller depth towards its descendants along a continuous chain of child nodes). Formally, if you are at node \(u\), you may choose any path going strictly through children of \(u\) and move exactly \(k\) steps to reach a descendant.

Whenever you arrive at a node that has a Wind God’s Eye, you immediately collect it (if you have not collected it before) without spending any extra time. However, you must return to the root (node 1) at the end because coming down from the tree causes injury.

You are given \(q\) queries. In the \(i\)th query you have \(t_i\) seconds available, and you need to determine the maximum number of Wind God’s Eyes you can collect if you start at node 1, complete your journey in at most \(t_i\) seconds and finish at node 1.

inputFormat

The input is given as follows:

• The first line contains four integers \(n\), \(m\), \(k\), and \(q\).
• The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\).
• The next line contains \(m\) integers \(a_1, a_2, \ldots, a_m\) denoting the nodes which have a Wind God’s Eye.
• Then \(q\) lines follow, each containing a single integer \(t_i\) representing the available time (in seconds) for the \(i\)th query.

outputFormat

For each query, output a single integer on a new line: the maximum number of Wind God’s Eyes you can collect within (t_i) seconds while starting and ending at node 1.

sample

3 1 1 3
1 2
1 3
2
2
3
4

1
1
1

</p>