Problem: There are n cities in Treeland connected with n - 1 bidirectional roads in such that a way that any city is reachable from any other; in other words, the graph of cities and roads is a tree. Treeland is preparing for a seasonal virus epidemic, and currently, they are trying to evaluate different infection scenarios.

In each scenario, several cities are initially infected with different virus species. Suppose that there are k_i virus species in the i-th scenario. Let us denote v_j the initial city for the virus j, and s_j the propagation speed of the virus j. The spread of the viruses happens in turns: first virus 1 spreads, followed by virus 2, and so on. After virus k_i spreads, the process starts again from virus 1.

A spread turn of virus j proceeds as follows. For each city x not infected with any virus at the start of the turn, at the end of the turn it becomes infected with virus j if and only if there is such a city y that:

  * city y was infected with virus j at the start of the turn;
  * the path between cities x and y contains at most s_j edges;
  * all cities on the path between cities x and y (excluding y) were uninfected with any virus at the start of the turn.



Once a city is infected with a virus, it stays infected indefinitely and can not be infected with any other virus. The spread stops once all cities are infected.

You need to process q independent scenarios. Each scenario is described by k_i virus species and m_i important cities. For each important city determine which the virus it will be infected by in the end.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of cities in Treeland.

The following n - 1 lines describe the roads. The i-th of these lines contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ n) — indices of cities connecting by the i-th road. It is guaranteed that the given graph of cities and roads is a tree.

The next line contains a single integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of infection scenarios. q scenario descriptions follow.

The description of the i-th scenario starts with a line containing two integers k_i and m_i (1 ≤ k_i, m_i ≤ n) — the number of virus species and the number of important cities in this scenario respectively. It is guaranteed that ∑_{i = 1}^ q k_i and ∑_{i = 1}^ q m_i do not exceed 2 ⋅ 10^5.

The following k_i lines describe the virus species. The j-th of these lines contains two integers v_j and s_j (1 ≤ v_j ≤ n, 1 ≤ s_j ≤ 10^6) – the initial city and the propagation speed of the virus species j. It is guaranteed that the initial cities of all virus species within a scenario are distinct.

The following line contains m_i distinct integers u_1, …, u_{m_i} (1 ≤ u_j ≤ n) — indices of important cities.

Output

Print q lines. The i-th line should contain m_i integers — indices of virus species that cities u_1, …, u_{m_i} are infected with at the end of the i-th scenario.

Example

Input


7
1 2
1 3
2 4
2 5
3 6
3 7
3
2 2
4 1
7 1
1 3
2 2
4 3
7 1
1 3
3 3
1 1
4 100
7 100
1 2 3


Output


1 2
1 1
1 1 1

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeSet;

/*

7
1 2
1 3
2 4
2 5
3 6
3 7
1
2 2
4 3
7 1
1 3

7
1 2
1 3
2 4
2 5
3 6
3 7
1
3 3
1 1
4 100
7 100
1 2 3

1
1
1 1
1 100
1

7
1 2
1 3
2 4
2 5
3 6
3 7
3

1 1
1 100
1

1 1
1 100
7

1 1
5 7
1

2
2 1
2

2 2
1 100
2 1000000
1 2

1 2
2 100
1 2
 */
public class _525E {

	public static void main(String[] args) throws InterruptedException {
		Thread t=new Thread(null, null, "T", 1<<27) {
			public void run() {
				go();
			}
		};
		t.start();
		t.join();
	}
	
	static void go() {
		FastScanner fs=new FastScanner();
		int n=fs.nextInt();
		Node[] nodes=new Node[n];
		for (int i=0; i<n; i++) nodes[i]=new Node(i);
		for (int i=1; i<n; i++) {
			int a=fs.nextInt()-1, b=fs.nextInt()-1;
			nodes[a].adj.add(nodes[b]);
			nodes[b].adj.add(nodes[a]);
		}
		nodes[0].dfs0(null, 0, 0);
		for (int e=1; e<20; e++)
			for (Node nn:nodes) 
				if (nn.lift[e-1]!=null) 
					nn.lift[e]=nn.lift[e-1].lift[e-1];
	
		int nQueries=fs.nextInt();
		for (int qq=0; qq<nQueries; qq++) {
			clearVT();
			
			int nViruses=fs.nextInt();
			int nImportant=fs.nextInt();
			TreeSet<Node> relevant=new TreeSet<>();
			for (int i=0; i<nViruses; i++) {
				int getVir=fs.nextInt()-1, travelSpeed=fs.nextInt();
				nodes[getVir].gotVirusFrom=nodes[getVir];
				nodes[getVir].travelSpeed=travelSpeed;
				nodes[getVir].virusNumber=i;
				relevant.add(nodes[getVir]);
			}
			Node[] importantNodes=new Node[nImportant];
			for (int i=0; i<nImportant; i++) importantNodes[i]=nodes[fs.nextInt()-1];
			for (Node nn:importantNodes) relevant.add(nn);
			
			buildVirtualTree(relevant);

			Node root=inVirtualTree.first();
			root.virtualDFS1();
			root.virtualDFS2();
			for (Node query:importantNodes) {
				System.out.print(query.gotVirusFrom.virusNumber+1+" ");
			}
			System.out.println();
		}
		
	}
	
	static ArrayDeque<Node> bfs=new ArrayDeque<>();
	static TreeSet<Node> inVirtualTree=new TreeSet<>();
	
	static void buildVirtualTree(TreeSet<Node> specialNodes) {
		
		for (Node nn:specialNodes)
			addToVT(nn);
		
		while (!bfs.isEmpty()) {
			Node next=bfs.remove();
			Node previous=inVirtualTree.lower(next);
			Node after=inVirtualTree.higher(next.rightmostKid);
			Node lcaPar=null;
			if (previous!=null) {
				Node lca=previous.lca(next, 19);
				addToVT(lca);
				if (lcaPar==null || lcaPar.depth<lca.depth) lcaPar=lca;
			}
			if (after!=null) {
				Node lca=next.lca(after, 19);
				addToVT(lca);
				if (lcaPar==null || lcaPar.depth<lca.depth) lcaPar=lca;
			}
			if (lcaPar!=null && lcaPar!=next) {
				next.parInVT=lcaPar;
				lcaPar.virtualAdj.add(next);
			}
		}
	}
	
	static void clearVT() {
		bfs.clear();
		for (Node nn:inVirtualTree) {
			nn.parInVT=null;
			nn.virtualAdj.clear();
			nn.gotVirusFrom=null;
		}
		inVirtualTree.clear();
	}
	
	static void addToVT(Node n) {
		if (inVirtualTree.contains(n)) return;
		inVirtualTree.add(n);
		bfs.add(n);
	}
	
	static class Node implements Comparable<Node> {
		Node[] lift=new Node[20];
		ArrayList<Node> adj=new ArrayList<>();
		int preorder, postorder, depth, index;
		Node rightmostKid;
		
		Node parInVT;
		ArrayList<Node> virtualAdj=new ArrayList<>();
		Node gotVirusFrom;
		int travelSpeed, virusNumber;
		
		public Node(int index) {
			this.index=index;
			rightmostKid=this;
		}
		
		public int dfs0(Node par, int counter, int depth) {
			this.preorder=counter;
			this.depth=depth;
			lift[0]=par;
			if (par!=null)
				adj.remove(par);
			
			for (Node nn:adj) {
				counter=nn.dfs0(this, counter+1, depth+1);
				rightmostKid=nn.rightmostKid;
			}
			
			return this.postorder=counter;
		}
		
		public void virtualDFS1() {
			for (Node nn:virtualAdj) {
				nn.virtualDFS1();
				getSickFromIfScarier(nn.gotVirusFrom);
			}
		}
		
		public void virtualDFS2() {
			if (parInVT!=null) {
				getSickFromIfScarier(parInVT.gotVirusFrom);
			}
			for (Node nn:virtualAdj) {
				nn.virtualDFS2();
			}
		}
		
		public int compareTo(Node o) {
			return Integer.compare(preorder, o.preorder);
		}
		
		Node goUp(int toGoUp) {
			if (toGoUp==0) return this;
			int lowest=Integer.lowestOneBit(toGoUp);
			int exp=Integer.numberOfTrailingZeros(lowest);
			return lift[exp].goUp(toGoUp-lowest);
		}
		
		Node lca(Node o, int maxJump) {
			if (this==o) return this;
			if (depth!=o.depth) {
				if (depth>o.depth) return goUp(depth-o.depth).lca(o, 19);
				return lca(o.goUp(o.depth-depth), 19);
			}
			if (lift[0]==o.lift[0]) return lift[0];
			while (lift[maxJump]==o.lift[maxJump]) maxJump--;
			return lift[maxJump].lca(o.lift[maxJump], maxJump);
		}
		
		boolean contains(Node o) {
			return o.preorder>=preorder && o.preorder<=postorder;
		}
		
		static int dist(Node n1, Node n2) {
			Node lca=n1.lca(n2, 19);
			return n1.depth+n2.depth-2*lca.depth;
		}
		
		void getSickFromIfScarier(Node cand) {
			if (cand==null) return;
			if (gotVirusFrom==null) {
				gotVirusFrom=cand;
				return;
			}
			int curDist=dist(this, gotVirusFrom);
			int curTurns=(curDist+gotVirusFrom.travelSpeed-1)/gotVirusFrom.travelSpeed;
			int nextDist=dist(this, cand);
			int nextTurns=(nextDist+cand.travelSpeed-1)/cand.travelSpeed;
			//TODO: don't overwrite things you start with
			if (nextTurns < curTurns || (curTurns==nextTurns && gotVirusFrom.virusNumber>cand.virusNumber)) {
				gotVirusFrom=cand;
			}
		}
		
		public String toString() {
			return index+1+"";
		}
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");

		String next() {
			while (!st.hasMoreElements())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}

}