Triangulated Convex Polygon Cost XOR

Given n points on a 2D plane with coordinates \( (x_i,y_i) \) for \(1 \le i \le n\), it is guaranteed that if for every \(i\) the points \(i\) and \( (i \bmod n)+1 \) are connected, they form the convex hull. In addition, there are exactly \(2n-3\) segments in the plane. The \(i\textsuperscript{th} segment connects point \(u_i\) and \(v_i\) with weight \(w_i\). Besides their endpoints, no two segments intersect.

A simple path from one point to another is a sequence of segments such that no point is visited more than once. For every two consecutive segments in the path, say connecting \(u \to v\) and \(v \to w\), consider the triple of points \(u,v,w\). If the segment connecting \(u\) and \(w\) is present in the set of segments, then these three points form a triangle which is said to be a pure triangle if there is no other segment lying in its interior. (In degenerate cases the triangle may collapse to a line segment.)

The cost of a path is defined as the sum of the weights of all segments used plus \(2k\) times the sum of the areas of all pure triangles formed on the path. Formally, if a path from \(i\) to \(j\) uses a set \(E\) of segments and visits a set \(V\) of points, and if \(H(V,E)\) denotes the total area (in the standard geometric sense) of all pure triangles found among every two consecutive segments (where the area of a triangle with vertices \(a,b,c\) is computed as \(\frac12\big|x_a(y_b-y_c)+x_b(y_c-y_a)+x_c(y_a-y_b)\big|\)), then the cost is:

[ f(i,j)=\min_{\text{simple paths from } i \text{ to } j} \left(\sum_{e\in E}w_e+2k\times H(V,E)\right). ]

Your task is to compute the XOR of \(f(i,j)\) over all pairs \(1\le i<j\le n\), i.e.,

[ \bigoplus_{i=1}^{n}\bigoplus_{j=i+1}^{n} f(i,j). ]

Note: The area of a triangle with vertices \(a\), \(b\), and \(c\) is defined as \(\frac12\big|x_a(y_b-y_c)+x_b(y_c-y_a)+x_c(y_a-y_b)\big|\). Observe that if you multiply this area by \(2k\), then the fractional part is eliminated, yielding an integer value.

inputFormat

The input begins with a line containing two integers \(n\) and \(k\).

The next \(n\) lines each contain two integers \(x_i\) and \(y_i\), representing the coordinates of the \(i\)-th point.

The following \(2n-3\) lines each contain three integers \(u_i\), \(v_i\) and \(w_i\) indicating that there is a segment connecting point \(u_i\) and point \(v_i\) with weight \(w_i\). It is guaranteed that the segments (apart from sharing endpoints) do not intersect and they form a triangulation of the convex polygon defined by the points.

outputFormat

Output a single integer: the XOR of all \(f(i,j)\) for \(1\le i<j\le n\).

sample

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

2