Гонка

Совсем недавно компания <<Memtendo>> выпустила новую версию культовой игры <<Super Mario Kart>>! В новой версии игры, как и в оригинальной, герои участвуют в гонках на машинах.

Всего в игре есть $n$ персонажей, пронумерованных целыми числами от $1$ до $n$. Перед выпуском игры разработчики провели опрос фанатов, и выяснили, насколько они любят каждого из персонажей. По итогам опроса для каждого персонажа была выявлена его популярность --- целое неотрицательное число. Популярность $i$-го персонажа равна $b\_i$.

Каждая игра состоит из нескольких заездов, в каждом из которых принимают участие все персонажи. По итогам каждого заезда лучшие $k$ персонажей получают некоторое количество баллов в общий зачет. А именно, персонаж, финишировавший первым, получает $a\_1$ баллов, персонаж, финишировавший вторым, получает $a\_2$ баллов, и так далее. Персонаж, финишировавший $k$-м, получает $a\_k$ баллов в общий зачет. Все остальные персонажи получают $0$ баллов в общий зачет по итогам заезда. Благодаря современным технологиям, время финиша измеряется абсолютно точно, а потому можно считать, что никакие два персонажа не финишируют одновременно. Также, исходя из принципа справедливого распределения баллов, выполняется неравенство $a\_1 > a\_2 > \ldots > a\_k > 0$.

Для подведения итогов игры для каждого из персонажей вычисляется его общий балл в этой игре. Общий балл персонажа определяется следующим образом: берутся все баллы (в том числе и нулевые), набранные этим персонажем за все заезды, из этих баллов вычеркивается $s$ минимальных значений, а оставшиеся значения складываются и прибавляются к популярности персонажа. Например, если Луиджи обладает популярностью $3$, в четырех заездах он набрал $2$, $1$, $3$ и $0$ баллов соответственно, а $s = 2$, то из баллов, полученных за заезды, будут вычеркнуты два минимальных, то есть $1$ и $0$, а общий балл Луиджи будет равен $3 + 2 + 3 = 8$. Итоги игр, в которых было менее $s$ заездов, не подводятся, чтобы избежать неоднозначности трактовки правил.

Во время очередной игры Марио и динозаврик Йоши решили немного пофантазировать. За время игры уже было проведено $m$ заездов, результаты которых Марио и Йоши знают. Пока готовится очередной заезд, герои играют в следующую мини-игру: Йоши называет номера двух различных персонажей $u$ и $v$, а Марио должен ответить, какое минимальное число заездов нужно ещё провести, чтобы общий балл персонажа $v$ был строго больше общего балла персонажа $u$. Обратите внимание, что герои лишь фантазируют, а Марио интересует теоретический минимум количества дополнительных звездов, то есть Марио может выбрать самый выгодный для себя исход каждого из дополнительных заездов. Мини-игра показалась Марио довольно скучной, поэтому он просит вас написать программу, которая могла бы играть с Йоши вместо него.

Первая строка входных данных содержит четыре целых числа $n$, $m$, $k$, $s$ --- количество персонажей в игре, количество уже проведенных заездов, количество персонажей, которые получают ненулевые баллы в общий зачет по итогам одного заезда, и количество заездов, не учитываемых при подведении итогов игры, соответствено ($2 \le n \le 1000$, $1 \le m \le 1000$, $1 \le k \le n$, $0 \le s \le \min(10, m)$).

Вторая строка содержит $k$ чисел $a\_1, a\_2, \ldots, a\_k$ --- баллы, которые получают лучшие $k$ персонажей по итогам каждого заезда ($1 \le a\_k < a\_{k - 1} < \ldots < a\_2 < a\_1 \le 10^9$).

Третья строка содержит $n$ чисел $b\_1, b\_2, \ldots, b\_n$ --- значения популярности каждого из персонажей ($0 \le b\_1, b\_2, \ldots, b\_n \le 10^9$).

Следующие $m$ строк описывают результаты уже состоявшихся заездов. Каждая из них содержит $n$ различных чисел от $1$ до $n$ --- список номеров персонажей в том порядке, в котором они финишировали в очередном заезде.

Следующая строка содержит единственное целое число $q$ --- количество вопросов, заданных Йоши ($1 \le q \le 10^5$).

Каждая из следующих $q$ строк содержит два целых числа $u$ и $v$ --- номера персонажей, фигурирующих в очередном вопросе ($1 \le u, v \le n$, $u \neq v$).

Для каждого вопроса выведите единственное целое число --- минимальное количество дополнительных заездов, которое необходимо провести, чтобы была теоретическая возможность того, что у персонажа с номером $v$ общий балл по итогам всех заездов будет больше, чем у персонажа с номером $u$. Если дополнительных заездов проводить не надо вообще, в качестве ответа на вопрос выведите число $0$.

Гарантируется, что ответ на каждый вопрос существует, то есть всегда имеется теоретическая возможность того, что персонаж с номером $v$ через конечное число дополнительных заездов будет иметь больший общий балл, чем персонаж с номером $u$.