L. Синий Трактор Airlines
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
По полям, по полям

Синий трактор едет к нам.

У него в прицепе кто-то

Песенку поёт.

— Синий трактор

Blue tractor tide throw fields, numerated with naturals numbers and sing the song. There are $$$n$$$ animals, waitings for him, $$$i$$$-d animal — on the $$$a_i$$$-d field. Each of $$$a_i$$$ different. У каждого животного есть ровно один ценитель. Ценители также находятся на некоторых полях $$$b_i$$$. Все $$$b_i$$$ также различны. Относительный порядок животных совпадает с относительным порядком ценителей. Более формально: $$$a_i \lt a_j \Leftrightarrow b_i \lt b_j\ \forall 1\le i, j\le n$$$.

Синий трактор хочет $$$q$$$ раз проехать по полям. Каждый раз он проедет от поля $$$s_i$$$ до поля $$$t_i$$$ и посадит в свой прицеп всех животных, которых встретит. Если животное едет в прицепе Синего трактора и оказывается на одном поле со своим ценителем, то этот ценитель начинает подпевать Синему трактору. Когда трактор доезжает до конца своего пути, он высаживает всех животных на этом поле, а все ценители прекращают петь.

Для каждого проезда Синего трактора определите количество ценителей, которые пели во время этого проезда.

Input

В первой строке содержится число $$$n\ (1 \le n \le 2 \cdot 10^5)$$$ — число животных (и их ценителей).

Во второй строке содержатся $$$n$$$ чисел $$$a_i\ (1 \le a_i \le 10^9)$$$ — координаты животных.

В третьей строке содержатся $$$n$$$ чисел $$$b_i\ (1 \le b_i \le 10^9)$$$ — координаты ценителей.

В четвертой строке содержится число $$$q\ (1 \le q \le 2 \cdot 10^5)$$$ — количество проездов Синего трактора.

В следующих $$$q$$$ строках содержится по $$$2$$$ числа: $$$s$$$ и $$$t$$$ $$$(1 \le s, t \le 10^9)$$$ — координаты начала и конца пути Синего трактора.

Output

Для каждого из $$$q$$$ запросов выведите ответ на задачу. Ответы разделяйте переводом строки.

Example
Input
3
2 8 11
4 6 13
3
7 15
20 5
1 9
Output
1
2
2