Little D has joined the national traffic management department. His first task is to be responsible for speed violation detection for vehicles on a north-south main road of length $L$. To test Little D, his supervisor first asks him to solve a simplified scenario.

This weekend, $n$ vehicles are expected to appear on the main road. The $i$-th vehicle enters the main road at a position $d_i$ from the south end and travels north with an initial velocity $v_i$ and an acceleration $a_i$ in uniformly accelerated motion. We only consider vehicles traveling from south to north, where $v_i > 0$, but $a_i$ can be positive, negative, or zero. When a vehicle reaches the north end of the main road (i.e., at a position $L$ from the south end) and its velocity drops to $0$ (this can only happen if $a_i < 0$), we consider the vehicle to have exited the main road.

There are $m$ speed cameras set up on the main road, where the $j$-th camera is located at a position $p_j$ from the south end. Each camera can be turned on or off. When a vehicle passes an active camera, if the vehicle's instantaneous velocity exceeds the road speed limit $V$, the vehicle is judged to be speeding. Note that when a vehicle enters or exits the main road, if there is an active camera at the corresponding position, that camera will also measure the vehicle's speed.

The supervisor first wants to know how many of the $n$ vehicles will be judged as speeding if all cameras are turned on.

Secondly, for energy saving, the department wants to turn off some cameras. However, they do not want to miss any speeding vehicles. That is, any vehicle that is judged as speeding when all cameras are on must still be judged as speeding after some cameras are turned off. The supervisor also wants to know the maximum number of cameras that can be turned off under these conditions.

Since $n$ is large, the supervisor allows Little D to use programming to solve these two problems, so Little D has come to you.

If you are not familiar with acceleration, Little D has kindly provided the relevant acceleration formulas in the "Note" section of this problem.

Input

The input is read from the file detect.in.

This problem contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. The following contains $T$ test cases, and the format for each test case is as follows: The first line contains four integers $n, m, L, V$, representing the number of vehicles, the number of speed cameras, the length of the main road, and the road speed limit, respectively. The next $n$ lines: The $i$-th line contains three integers $d_i, v_i, a_i$ describing a vehicle. The last line contains $m$ integers $p_1, p_2, \dots, p_m$ describing the positions of the speed cameras on the road.

Output

Output to the file detect.out.

For each test case: output a line containing two integers. The first is the number of vehicles judged as speeding when all cameras are turned on, and the second is the maximum number of cameras that can be turned off on the premise that no speeding vehicles are missed.

Examples

Input 1

1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15

Output 1

3 3

Note

In this test case, the main road length is $15$, the speed limit is $3$, and speed cameras are set at positions $2, 5, 8, 9, 15$ from the south end.

• The first vehicle enters at the south end and travels at a constant speed of $3$. This vehicle does not speed on any part of the road.
• The second vehicle enters at a position $12$ from the south end and travels at a constant speed of $4$. When it exits the main road at the north end, it will be judged as speeding by the camera at position $15$ from the south end.
• The third vehicle enters at a position $1$ from the south end with an initial velocity of $1$ and an acceleration of $4$. It travels a distance of $\frac{3^2 - 1^2}{2 \times 4} = 1$, reaching position $2$, where its velocity becomes $3$, and it speeds thereafter. Therefore, this vehicle will be judged as speeding by all cameras except the one at position $2$ from the south end.
• The fourth vehicle enters at a position $5$ from the south end with an initial velocity of $5$ and an acceleration of $-2$. It travels a distance of $\frac{3^2 - 5^2}{2 \times (-2)} = 4$, reaching position $9$, where its velocity becomes $3$. Therefore, this vehicle speeds in the interval $[5, 9)$ from the south end and will be judged as speeding by the two cameras at positions $5$ and $8$ from the south end.
• The fifth vehicle enters at a position $6$ from the south end with an initial velocity of $4$ and an acceleration of $-4$. After traveling a distance of $\frac{3^2 - 4^2}{2 \times (-4)} = \frac{7}{8}$, it reaches position $6 \frac{7}{8}$, where its velocity becomes $3$. Therefore, this vehicle speeds in the interval $[6, 6 \frac{7}{8})$ from the south end, but there are no cameras in this interval, so it will not be judged as speeding.

Thus, the second, third, and fourth vehicles will be judged as speeding, and the first output is $3$.

We can turn off the three cameras at positions $2, 8, 9$ from the south end and keep the two cameras at $5$ and $15$. At this time, the three vehicles previously judged as speeding are still judged as speeding. It can be proven that no better solution exists, so the second output is $3$.

Constraints

For all test cases, it is guaranteed that: $1 \le T \le 20$; $1 \le n, m \le 10^5$, $1 \le L \le 10^6$, $1 \le V \le 10^3$; $0 \le d_i < L$, $1 \le v_i \le 10^3$, $|a_i| \le 10^3$; $0 \le p_1 < p_2 < \dots < p_m \le L$.

Special Property A: Guaranteed $a_i = 0$. Special Property B: Guaranteed $a_i > 0$. Special Property C: Guaranteed $a_i < 0$, and no vehicles exit the main road at the north end.

Note

Definitions and formulas related to acceleration are as follows: Uniformly accelerated motion refers to motion where the acceleration remains constant during the movement, meaning the change in velocity per unit time is constant. If a vehicle has an initial velocity $v_0$ and acceleration $a \neq 0$ in uniformly accelerated motion, then after time $t$, its velocity is $v_1 = v_0 + a \times t$, and its displacement (i.e., distance traveled) is $s = v_0 \times t + 0.5 \times a \times t^2$. If a vehicle has an initial velocity $v_0$ and acceleration $a \neq 0$ in uniformly accelerated motion, then its displacement (i.e., distance traveled) is $s$, and the vehicle's instantaneous velocity is $\sqrt{v_0^2 + 2 \times a \times s}$. If a vehicle has an initial velocity $v_0$ and acceleration $a \neq 0$, when its displacement (i.e., distance traveled) is $\frac{v_1^2 - v_0^2}{2a}$, the vehicle's instantaneous velocity is $v_1$.

If you use floating-point numbers for calculations, be aware of potential precision issues.