L. Laser
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A mega-scale project to convert laser light into usable energy for general purposes has begun in the almost infinite experiment area with laser-amplifying glass panes.

The experiment was conducted by placing a laser emitter in one room. After that, the $$$N$$$ laser receivers were placed in room coordinates $$$(x_i,y_i)$$$; each room has a glass pane on the vertical and horizontal side which is shared between adjacent rooms.

  • When the laser passes through each vertical glass pane, the laser intensity is increased by $$$A$$$ units.
  • When the laser passes through each horizontal glass pane, the laser intensity is increased by $$$B$$$ units.
We can choose to activate only 1 laser receiver which further amplifies the laser intensity by $$$c_i$$$ units when the laser stops at that receiver, generating energy in proportion to the final laser intensity. To prevent accidental damage from the experiment, all equipment must be placed in the center of the room, and the laser must start with a horizontal or vertical trajectory, and the laser path must end on the activated laser receiver.
The room coordinate in the experiment area with a glass pane on each side

Furthermore, the administrator of the project has provided 1 L-shaped reflector to change the trajectory of the laser from horizontal to vertical or vice versa. You want to run $$$Q$$$ simulation tests to provide the information on the minimum possible laser intensity given the starting point for the laser at coordinates $$$(s_i,t_i)$$$; your task is to come up with the resulting laser intensity.

Input

The first line contains four integers $$$N,Q,A,B$$$ ($$$0 \le A,B \le 10^9,1 \le N,Q \le 100\,000$$$) — number of laser receivers, simulations, amplification power of vertical and horizontal glass panes.

Next, $$$N$$$ lines contain $$$x_i,y_i,c_i$$$ ($$$0 \le x_i,y_i \le 10^9,0 \le c_i \le 10^{18}$$$) — laser receiver coordinates in the Cartesian plane and laser amplification power.

Next, $$$Q$$$ lines contain $$$s_i,t_i$$$ ($$$0 \le s_i,t_i \le 10^9$$$) — laser emitter starting coordinates in the Cartesian plane in each simulation.

Output

Print $$$Q$$$ lines, each line contains a single integer — the minimum possible laser intensity for the simulation.

Example
Input
5 3 1 2
1 1 0
4 2 0
2 3 3
5 4 0
4 5 2
3 3
4 1
1 6
Output
3
2
7
Note
The arrangement for minimum possible laser intensity for first and third simulation
Let the red point and blue point be the laser receiver and the laser emitter in each simulation respectively.

For the first simulation, the L-shaped reflector can be placed on coordinate (3,4); by activating the second receiver, the minimum final laser intensity is $$$1+2+0 = 3$$$.

For the second simulation, the L-shaped reflector is not used; by activating the second receiver, the minimum final laser intensity is $$$2+0 = 2$$$.

For the third simulation, the L-shaped reflector can be placed on coordinate (1,5); by activating the fifth receiver, the minimum final laser intensity is $$$2+1+1+1+2 = 7$$$.