Archery Training Optimization

Farmer John is preparing his cow archers for the Paris Mooving Games. He has set up a training exercise on the 2D plane. There are \(N\) axis‐parallel rectangles (arrow targets) and \(4N\) cows. Target \(i\) appears at time \(i\) with its bottom–left vertex at \( (X_1, y^{(i)}_1) \) and its top–right vertex at \( (x^{(i)}_2, y^{(i)}_2) \) (note: \(X_1\) is the same for every target). At time \(i\) the four cows assigned to target \(i\) shoot an arrow from some point on the \(y\)–axis (i.e. from a point with \(x=0\)) towards the vertices that have been assigned to them. Each cow has a preset aiming slope \(s\) (with \(0<|s|<10^9\)), so that if a cow positioned at \((0,y)\) is assigned to hit a target vertex \((x,y')\) then she must be placed so that

[ y + s, x = y'. ]

However, the shot is only successful if the cow’s arrow does not pass through the interior of the arrow target before hitting the vertex. More precisely, suppose a cow at \((0,y)\) with aiming slope \(s\) is assigned to a vertex \((a,b)\) of a target whose other vertex is \((x^{(i)}_2,y^{(i)}_2)\) (with \(a\) equal either to \(X_1\) or \(x^{(i)}_2\)); then her shot is successful only if the line segment from \((0,y)\) to \((a,b)\) does not enter the open interior of the rectangle. It can be shown that if one chooses an appropriate vertex for each cow, then the shot will be successful provided that the cow’s slope satisfies some extra conditions:

• For a shot aimed at a left–vertex (i.e. \((X_1, y^{(i)}_1)\) or \((X_1, y^{(i)}_2)\)) the shot is always safe.
• For the bottom–right vertex \((x^{(i)}_2, y^{(i)}_1)\), the cow’s slope must be such that if \(s0\) then the shot is safe.
• For the top–right vertex \((x^{(i)}_2, y^{(i)}_2)\), if \(s>0\) then we need \(s\ge \frac{y^{(i)}_2-y^{(i)}_1}{x^{(i)}_2-X_1}\); if \(s<0\) then the shot is safe.

Farmer John is free both to choose which cow is assigned to which target vertex and where exactly on the \(y\)–axis the cows stand (subject to their positions being distinct). His goal is to minimize the range (the difference between the highest and lowest \(y\)–coordinates) of the cows. Help him decide what is the smallest possible range between cows if an assignment exists that allows every cow’s shot to hit its designated vertex (and if not, output \(-1\)).

inputFormat

The first line contains an integer \(T\) (\(1\le T\le10\)), the number of test cases. Each test case begins with a line containing two integers \(N\) (\(1\le N\le 4\cdot10^4\)) and \(X_1\) (\(1\le X_1\le10^9\)). Then follow \(N\) lines; the \(i\)–th of these contains three integers \(y^{(i)}_1, x^{(i)}_2, y^{(i)}_2\) satisfying \(1\le y^{(i)}_1<y^{(i)}_2\le10^9\) and \(X_1<x^{(i)}_2\le10^9\). Finally there is a line containing \(4N\) numbers, the aiming slopes \(s\) for the \(4N\) cows (each a nonzero real number with \(0<|s|<10^9\)).

outputFormat

Output a single number: the minimum possible difference between the highest and lowest \(y\)–coordinates at which the cows can be placed to have a valid shot for every target. If no valid assignment exists, output \(-1\).

sample

1
1 5
3 10 8
1 -2 3 -4

50