George and the Water Park Pipes

On his way back from the water park, George encountered an unusual problem. He recalled all the slides (pipes) he had taken. The slides connect various nodes in a tree-like structure. Each node has a pair of coordinates \( (r, c) \). It is guaranteed that for every slide from a node to another, the pipe goes downward so that if there is an edge from node \( u \) to node \( v \), then \( r_u < r_v \).

George now poses many queries. In each query, he gives you two nodes, identified by their coordinates \( (r_1, c_1) \) and \( (r_2, c_2) \). Your task is to determine the coordinate \( (r_3, c_3) \) of a node such that starting from this node, following the slides (i.e. moving from a node to its children repeatedly) one can reach both \( (r_1, c_1) \) and \( (r_2, c_2) \). Moreover, among all nodes that can reach both, you must choose the one that is the "lowest" (i.e. with the largest \( r \) value). It can be proved that such a node exists and is unique.

This problem can be reformulated as finding the lowest common ancestor (LCA) in a rooted tree whose nodes are arranged so that the parent's \( r \) value is smaller than that of any of its descendants.

Input Format

The input begins with a line containing two integers \( N \) and \( Q \) (\( 1 \le N, Q \le 10^5 \)) denoting the number of nodes and the number of queries respectively. Then follow \( N \) lines. The \( i\)-th of these lines contains two integers \( r_i \) and \( c_i \), giving the coordinates of node \( i \) (nodes are numbered from 1 to \( N \)). It is guaranteed that all nodes have unique coordinates.

Next, there are \( N-1 \) lines. Each line contains two integers \( u \) and \( v \), representing a slide (directed edge) from node \( u \) to node \( v \). This relation establishes a tree with a unique root (the only node that never appears as \( v \)).

Finally, there are \( Q \) lines, each representing a query. Each query consists of four integers: \( r_1\, c_1\, r_2\, c_2 \). It is guaranteed that there exist nodes with coordinates \( (r_1, c_1) \) and \( (r_2, c_2) \) in the tree.

Output Format

For each query, output a single line with two integers \( r_3 \) and \( c_3 \) separated by a space, which are the coordinates of the node that is the lowest common ancestor of the two given nodes (i.e. the common ancestor with the maximum \( r \) value).

Example

Input:
5 2
1 1
2 2
3 2
4 3
5 1
1 2
1 3
2 4
2 5
4 3 5 1
4 3 3 2
Output:
2 2
1 1

</p>

Explanation:

• In the first query, the nodes with coordinates \( (4,3) \) and \( (5,1) \) are located in the subtree rooted at node 2 (which has coordinates \( (2,2) \)). This is the lowest node from which both can be reached.
• In the second query, the only common ancestor of nodes \( (4,3) \) and \( (3,2) \) is the root node \( (1,1) \).

inputFormat

The first line contains two integers \( N \) and \( Q \): the number of nodes and the number of queries.

Then \( N \) lines follow, each with two integers \( r_i \) and \( c_i \) representing the coordinates of the \( i^{th} \) node.

Next, \( N-1 \) lines follow, each containing two integers \( u \) and \( v \) indicating a directed edge from node \( u \) to node \( v \) (i.e. a slide from \( u \) to \( v \)).

Finally, \( Q \) lines follow. Each query line contains four integers: \( r_1\, c_1\, r_2\, c_2 \), representing the coordinates of two nodes.

outputFormat

For each query, output a line containing two integers \( r_3 \) and \( c_3 \) separated by a space, representing the coordinates of the lowest common ancestor of the two given nodes.

sample

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

2 2
1 1

</p>