9158: Hello

In a distant land, there is a small peaceful village, which can be represented as a 2-dimensional plane.

There are $n$ houses in the village, the $i$-th of which locates at the coordinate (xi,yi)(x_i, y_i)(xi,yi). There are also $n-1$
\textbf{straight} bidirectional roads, each connecting two houses. In other words, each house can be treated as a point on the 2-d plane, and each road can be treated as a line segment with two houses as its endpoints. In this village, every two houses can reach to each other through the roads, and no two roads intersect except at their endpoints.

Today $m$ villagers plan to go for a walk. The $i$-th villager will start walking from the coordinate (sxi,syi)(sx_i, sy_i)(sxi,syi), and end at the coordinate (exi,eyi)(ex_i, ey_i)(exi,eyi). It is guaranteed that both the starting point and ending point are either at a certain house or on a certain road in the village.

During their walk, when two villagers meet, they will say hello to each other. However, since their starting time may differ, it is difficult to determine who will greet each other. So let us focus on a simpler task: for each villager, figure out how many other villagers' routes intersect with his/her own.

The route of a villager is defined as the unique simple path connecting his/her starting and ending points via the roads. Two routes are defined to intersect, if and only if they share at least one common point.

The first line of input consists of two positive integers $n,m$ (1≤n≤1051 \le n \le 10^51≤n≤105, 1≤m≤1051 \le m \le 10^51≤m≤105), representing the number of houses and the number of villagers respectively.
Then follows $n$ lines. The $i$-th line consist of two integers xi, yix_i,\ y_ixi, yi (∣xi∣, ∣yi∣≤106|x_i|,\ |y_i| \le 10^6∣xi∣, ∣yi∣≤106), denoting the coordinate of the $i$-th house. It is guaranteed that all the coordinates of houses are distinct.
Then follows $n-1$ lines. The $i$-th line consist of two positive integers uiu_iui and viv_ivi (1≤ui,vi≤n, ui≠vi1 \le u_i, v_i \le n,~u_i \ne v_i1≤ui,vi≤n, ui=vi), indicating there is a road connecting the uiu_iui-th house and the viv_ivi-th house. It is guaranteed that the roads meet with the restrictions mentioned above.
Then follows $m$ lines. The $i$-th line consist of eight integers pisx, qisx, pisy, qisy, piex, qiex, piey, qieyp_i^{sx},\ q_i^{sx},\ p_i^{sy},\ q_i^{sy},\ p_i^{ex},\ q_i^{ex},\ p_i^{ey},\ q_i^{ey}pisx, qisx, pisy, qisy, piex, qiex, piey, qiey (∣pi∗∣≤1012|p_i^*| \le 10^{12}∣pi∗∣≤1012, 0<qi∗≤1060 < q_i^* \le 10^60<qi∗≤106), denoting the route of the $i$-th villager -- the starting point is (pisxqisx, pisyqisy)(\frac{p_i^{sx}}{q_i^{sx}},\ \frac{p_i^{sy}}{q_i^{sy}})(qisxpisx, qisypisy), and the ending point is (piexqiex, pieyqiey)(\frac{p_i^{ex}}{q_i^{ex}},\ \frac{p_i^{ey}}{q_i^{ey}})(qiexpiex, qieypiey). It is guaranteed that each pair of numerator and denominator is co-prime, and the starting point and ending point won't coincide

Print $m$ non-negative integers in a single line, each separated by a single space. The $i$-th integer represents the number of other villagers whose route intersects with that of the $i$-th villager.

6 5
-2 0
3 4
10 2
4 -1
6 2
3 -1
1 2
2 3
3 4
2 5
2 6
4 3 8 3 29 5 16 5
-1 2 6 5 9 2 3 1
6 1 2 1 4 1 10 3
3 1 -1 1 34 7 -4 7
-1 2 6 5 -1 1 4 5

2 4 1 2 1