In a certain mysterious place, there is a Wisdom City where the average IQ of the people is 192. Anyone with an IQ below 150 is considered mentally challenged. The mayor of Wisdom City is named Karp-de-Chant. He obtained his PhD from the Cross Institute at the central university of Wisdom City at the age of 12. Two years later, he invented a sequence called the Karp-de-Chant Number, which can be used to solve or optimize various classic problems in fields such as number theory and graph theory. Later, after the Karp-de-Chant Number was extended by Trajan (the vice mayor of Wisdom City) using a spaly tree, its power increased greatly, allowing various network flow problems and other difficult challenges to be solved in linear time. Consequently, Karp-de-Chant and Trajan were elected as the mayor and vice mayor, respectively. Together with other wise individuals in Wisdom City, they lead the people in building human wisdom, exercising their abilities to create and improve.

However, one day, Wisdom City was suddenly attacked by anti-human wisdom attackers. These attackers set up $N$ cameras in the city (due to their low IQ, they only know how to use such garbage as cameras) in an attempt to monitor the people. Karp-de-Chant and Trajan decided to find these cameras and destroy them.

There is a transmitter in Wisdom City designed using the principle of extended Karp-de-Chant numbers. When placed in a suitable position and set with a radius, all targets located on the surface of a sphere with the transmitter as the center and the specified radius can be detected. Under the leadership of Karp-de-Chant and Trajan, the people of Wisdom City conducted several experiments with this transmitter and discovered the locations of some cameras. Curiously, each emission could and did detect exactly one camera. However, the feedback results seemed a bit off...

Later, people finally found the locations of all $N$ cameras and discovered that during their experiments with the transmitter, some cameras had been moved—this was the reason why the feedback results seemed incorrect. However, when analyzing the experimental results, people could not for the life of them recall which camera was detected in each experiment (possibly due to some paranormal event causing a mental lapse); they only knew the position and radius of the transmitter for each experiment. Your task is to find the ID of the camera detected in each experiment based on the experimental data (which has been encrypted to prevent theft by anti-human wisdom attackers).

Input

The first line contains two positive integers $N$ and $M$, representing the number of cameras (numbered from $1$ to $N$) and the number of events.

The second line contains two real numbers $a$ and $b$, representing the encryption parameters.

The next $N$ lines each contain three real numbers $(x, y, z)$, representing the initial coordinates of cameras $1$ to $N$.

The next $M$ lines each describe an event. There are two possible types of events (it is guaranteed that the precision of the real numbers is sufficiently high):

1. 0 i x y z: Change the coordinates of the camera with ID $i$ to $(x, y, z)$;
2. 1 x y z r: Conduct an experiment by placing the transmitter at $(x, y, z)$ and setting the radius to $r$. The data guarantees that each experiment detects exactly one camera.

Encryption method: Let the function $f(x) = ax - b \sin x$. For all parameters in the events ($i, x, y, z, r$), they are encrypted as $f(\text{last\_res} \times \text{original\_value} + 1)$, where $\text{last\_res}$ is the return value of the previous experimental event (i.e., the ID of the detected camera). If no experiment has been conducted before, $\text{last\_res} = 0.1$.

Output

For each experimental event, output the ID of the detected camera, one per line.

Examples

input

6 10
1 0
-3.6 7.2 3.6
9.7 0.4 0.5
8.8 -4.7 0.5
9.6 8.2 -5.7
0.3 -9.9 1.5
0.5 -5.7 -1.0
0 1.3 1.92 0.13 1.85
1 1.98 1.55 1.2 2.360183811
1 8.2 0.9 2.1 9.981091248
1 -7.4 -44.0 11.2 83.061927835
1 20.8 -9.6 -11.8 31.598039153
0 10.0 11.2 -19.73 -19.1
0 13.0 7.3 28.6 22.6
0 4.0 22.3 -17.6 1.3
1 -3.2 -14.0 16.6 30.9549661993
0 7.0 -3.1 5.8 -0.9

output

1
6
2
3
1

Constraints

All test points satisfy $0 \leq b < a < 5$. The absolute values of the coordinates do not exceed $100$. All coordinates are randomly generated and are accurate to at least $10^{-5}$.

To minimize precision errors, it is recommended to use the long double type in C/C++ and the EXTENDED type in Pascal to store real numbers.