H. Uranus
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Although it is not the farthest planet from the Sun, Uranus is considered to be the coldest planet in the Solar System, experiencing a minimum temperature of 49 K and extreme winds of up to 900 km/h. Undaunted, Sir Vedward V's twin brother, Sir Udward, wishes to send probes to explore Uranus.

Currently, VASA has developed $$$n$$$ probes, where the $$$i^{\text{th}}$$$ probe can survive temperatures of up to $$$x_i$$$ degrees Kelvin and wind speeds of up to $$$y_i$$$ km/h; however, it costs $$$c_i$$$ dollars to construct. In addition, VASA has conducted $$$q$$$ measurements of locations on Uranus, where the $$$i^{\text{th}}$$$ location has a temperature of $$$t_i$$$ degrees Kelvin and a wind speed of $$$w_i$$$ km/h.

Sir Udward will reward you handsomely if you help him determine, for each landing location, the cheapest probe that can survive its temperature and wind speed.

Input

The first line of input contains $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$), the number of probes and locations, respectively.

The second line contains $$$n$$$ integers, $$$x_1, x_2, ..., x_n$$$ ($$$1 \le x_i \le 10^9$$$), the maximum temperature each probe can survive.

The third line contains $$$n$$$ integers, $$$y_1, y_2, ..., y_n$$$ ($$$1 \le y_i \le 10^9$$$), the maximum wind speed each probe can survive.

The fourth line contains $$$n$$$ integers, $$$c_1, c_2, ..., c_n$$$ ($$$1 \le c_i \le 10^9$$$), the cost of each probe.

The next $$$q$$$ lines each contain two integers $$$t_i$$$ and $$$w_i$$$ ($$$1 \le t_i, w_i \le 10^9$$$), the temperature and wind speed at the $$$i^{\text{th}}$$$ location, respectively.

Output

The output should be $$$q$$$ integers, each on a separate line, the minimum cost of a probe that can survive for each location, or $$$-1$$$ if there is no probe that can survive.

Example
Input
3 3
1 2 3
3 1 2
3 2 1
1 2
1 3
3 3
Output
1
3
-1
Note

The first probe ($$$1 \ge 1$$$ and $$$3 \ge 2$$$) and third probe ($$$3 \ge 1$$$ and $$$2 \ge 2$$$) can both survive the first location, but the third probe is cheaper, so the output is $$$1$$$.

Only the first probe ($$$1 \ge 1$$$ and $$$3 \ge 3$$$) can survive the second location, so the output is $$$3$$$.

None of the probes can survive the third location, so the output is $$$-1$$$.