Kabul Kabir is a computer science student who decided to improve his health by taking a regular morning walk. He walks on a park trail that forms a closed, simple loop of total length $$$L$$$ meters. The trail has multiple entry points and walkers may move in either direction along the trail.
Kabul always walks in the forward direction at a constant speed of $$$v_0$$$ meters per second and continues walking for exactly $$$T$$$ seconds.
While walking, Kabul encounters other walkers on the trail. Some walk in the same direction, while others walk in the opposite direction. Whenever Kabul and another walker occupy the same position on the trail at the same time, Kabul considers it a meeting. Meetings can occur either when they cross paths (opposite directions) or when one overtakes the other (same direction).
For each walker $$$X_i$$$, Kabul records the following information:
- $$$t_i$$$ – the time (in seconds) after Kabul starts walking when he first meets $$$X_i$$$.
- $$$v_i$$$ – the signed walking speed of $$$X_i$$$ in meters per second: positive if the walker moves in the same direction as Kabul, and negative if the walker moves in the opposite direction.
Your task is to determine how many times in total Kabul meets each walker during the time interval from $$$0$$$ to $$$T$$$, including the first meeting and any meeting that occurs exactly at time $$$T$$$.
The first line of the input contains a single integer $$$K \: (1 \le K \le 10^{4})$$$ — the number of test cases.
The first line of each test case contains four space-separated integers $$$L$$$, $$$v_0$$$, $$$T$$$, and $$$N$$$ $$$(1 \le L \le 10^{6},\; 1 \le v_0 \le 10^{3},\; 1 \le T \le 10^{7},\; 1 \le N \le 2 \cdot 10^{5})$$$ — the length of the trail in meters, Kabul's walking speed in meters per second, the total walking time in seconds, and the number of other walkers, respectively.
Each of the next $$$N$$$ lines contains two space-separated integers $$$t_i$$$ and $$$v_i$$$ $$$(0 \le t_i \le T,\; -10^{3} \le v_i \le 10^{3},\; v_i \ne 0,\; v_i \ne v_0)$$$ — the time of the first meeting with the $$$i$$$-th walker and that walker's signed walking speed in meters per second.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.
For each test case, output a single line containing $$$N$$$ space-separated integers. The $$$i$$$-th integer should be the total number of meetings Kabul has with the $$$i$$$-th walker, listed in the same order as the input.
3 200 30 75 1 45 10 400 5 5400 3 600 4 750 -6 1200 6 1000 5 5400 2 0 6 5400 -5
4 13 128 11 6 1
In the first sample test case, the trail length is $$$200$$$ meters and Kabul walks at $$$30$$$ m/s for $$$75$$$ seconds. The walker moves in the same direction at $$$10$$$ m/s and first meets Kabul at $$$t = 45$$$. They meet again at $$$t = 55$$$, $$$t = 65$$$, and $$$t = 75$$$, resulting in a total of $$$4$$$ meetings.
